Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
x = 1/3 − 4/3. В этом примере априорная информация состоит в том, что результат ищется в симметричном множестве. Имеем x (mod 11) ≡ (1/3 + (−4)/3) (mod 11) ≡ (1/3 + 7/3) (mod 11) ≡ (1 · 3 −1 + 7 · 3 −1 ) (mod 11) ≡ (1 · 4+ + 7·4) (mod 11) ≡ 32 (mod 11). Отображая результат обратно в симметрич- ное множество, получаем правильный ответ x = −1. В приведенном примере res p = res, поскольку с самого начала известно, что res лежит в симметрич- ном множестве для Z 11 . ¤ Пример 3.9.4. Вычислим x = 1/2 − 2/3, пользуясь той же априорной информацией, что и в предыдущем примере. Имеем x (mod 11) ≡ (1/2 + (−2)/3) (mod 11) ≡ (1/2 + 9/3) (mod 11) ≡ ≡ (1 · 2 −1 + 9 · 3 −1 ) (mod 11) ≡ (1 · 6 + 9 · 4) (mod 11) ≡ 42 (mod 11) ≡ 9. Ес- ли мы отобразим результат в симметричное множество, то получим непра- вильный ответ: x = −2. Поэтому требуется дополнительная информация о том, что мы ищем рациональное число x (mod 11) ≡ (a/b) (mod 11), где b =НОК(2, 3). Тогда a = xb (mod 11) ≡ 9 · 6 (mod 11) ≡ 10 (mod 11) ≡ −1. Следовательно, x = (−1)/6, что является правильным ответом. ¤ Перейдем теперь к арифметике нескольких модулей. Использование этой арифметики позволяет естественно решать проблему компьютерного представления и работы с большими целыми числами, с которой мы сталки- ваемся в арифметике одного модуля: как мы видели, модуль m должен быть достаточно большим, чтобы результат res определялся однозначно по его остатку res m (m > res). Поэтому при работе с большим m мы используем несколько модулей, кодирующих целые числа x (0 6 x 6 m − 1) в соответ- ствии с китайской теоремой об остатках. Для вычисления заданного выражения f (i 1 , i 2 , . . . , i h ), зависящего от це- лочисленных аргументов i 1 , i 2 , . . . , i h , сначала вычисляем f m k (i 1k , i 2k , . . . , i hk ), где i jk — остаток от деления i j на m k (j = 1, 2, . . . , h, k = 1, 2, . . . , n) для ко- ротких модулей m k . При условии, что выражения f m k определены над Z m k , вычисляем их над Z m k и получаем эквивалентные результаты res m k , k = 1, 2, . . . , n. В завершение, пользуясь китайским алгоритмом, получаем окончательный результат res. Модули m k выбираются таким образом, чтобы m 1 · m 2 · . . . · m n > res. Если дана положительная оценка на res, то ищет- ся наименьшее неотрицательное решение системы уравнений по китайскому алгоритму, если же оценивается |res|, то ищется наименьшее по абсолютной 3.9. ТОЧНЫЕ ВЫЧИСЛЕНИЯ 113 Z Выражение (f ) −−−−→ Z m k Эквивалентное выражение (f m k ) y Вычисление над Z y Вычисление над Z m k Результат (res) ←−−−− Эквивалентный результат (res m k ) Рис. 3.4 величине решение. На рис. 3.4 представлена диаграмма, иллюстрирующая приведенный алгоритм. Рассмотрим более подробно арифметику нескольких модулей. Описанные в § 3.2 системы счисления являются линейными, позиционными и весовыми. Это означает, что всем позициям соответствуют веса, зависящие от одного основания P : P 0 , P 1 , P 2 и т. д. Вместо этого многомодульная система счис- ления использует взаимно простые позиционные основания, m 1 , m 2 , . . . , m n Это позволяет однозначно представлять m 1 · m 2 · . . . · m n различных чисел x в виде вектора остатков [a 1 , a 2 , . . . , a n ] относительно вектора оснований β = [m 1 , m 2 , . . . , m n ], где x ≡ a i (mod m i ), i = 1, 2, . . . , n. Как и в случае одного модуля, мы можем определить наименьшую неотрицательную чис- ловую систему (которую будем называть стандартным набором остат- ков) и при условии, что все модули нечетные, наименьшую по абсолютной величине числовую систему или симметричную систему остатков относи- тельно данного вектора оснований β. Если [a 1 , a 2 , . . . , a n ] — стандартный на- бор остатков числа x относительно вектора оснований β = [m 1 , m 2 , . . . , m n ], то запишем x (mod β) = [a 1 , a 2 , . . . , a n ]. Пример 3.9.5. Если n = 3, m 1 = 3, m 2 = 5, m 3 = 7, то в этой системе с помощью остатков можно представить 3· 5 · 7 = 105 различных чисел. Век- тор [2, 3, 1] однозначно определяет десятичное число 8 в неотрицательной системе остатков относительно вектора оснований β = [3, 5, 7]. В симмет- ричной системе число 8 представляется вектором [−1, −2, 1]. Имеем 8 (mod β) = [2, 3, 1]. ¤ Из китайской теоремы об остатках вытекает Теорема 3.9.1. Два целых числа n 1 и n 2 имеют одинаковые стандарт- ные наборы остатков относительно вектора оснований β = [m 1 , m 2 , . . . , m n ] тогда и только тогда, когда n 1 ≡ n 2 (mod m 1 m 2 . . . m n ). ¤ 114 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Пример 3.9.6. Рассмотрим вектор оснований β = [3, 5, 7]. Так как 9 ≡ 114 (mod 3 · 5 · 7), то 9 (mod β) = [0, 4, 2] = 114 (mod β). ¤ Из теоремы 3.9.1 следует существование биекции между множествами Z β {k (mod β) | k ∈ Z} и Z M , где M = m 1 · m 2 · . . . · m n . Более того, из китайской теоремы об остатках следует Теорема 3.9.2. Алгебры hZ β ; +, ·i и hZ M ; +, ·i являются изоморфными конечными коммутативными кольцами. ¤ Следовательно, многомодульная арифметика hZ β ; +, ·i эквивалентна арифметике hZ M ; +, ·i по модулю M. Главное преимущество многомодульной числовой системы состоит в от- сутствии переносов при выполнении операций сложения и умножения. Ариф- метика замкнута в каждой позиции, т. е. арифметические действия выполня- ются покоординатно. Поэтому сложение и умножение длинных целых чисел можно выполнять так же быстро, как и коротких чисел. Для выполнения деления определим элемент b −1 (mod β), обрат- ный к элементу b = [b 1 , b 2 , . . . , b n ] по модулю вектора оснований β = [m 1 , m 2 , . . . , m n ], следующим образом: b −1 (mod β) = [b −1 1 (mod m 1 ), b −1 2 (mod m 2 ), . . . , b −1 n (mod m n )]. Теперь, если a = [a 1 , a 2 , . . . , a n ], то a b (mod β) = a · b −1 (mod β) = = [a 1 · b −1 1 (mod m 1 ), a 2 · b −1 2 (mod m 2 ), . . . , a n · b −1 n (mod m n )]. Как и в случае одного модуля, если b не делит a при соответствующей интерпретации в кольце целых чисел, то результат не может быть проин- терпретирован без дополнительной информации. Однако он допустим в ка- честве промежуточного результата. Основная трудность при работе с многомодульными числовыми систе- мами заключается в сравнении величины целых чисел. Конечно, можно ис- пользовать симметричную систему остатков, вычесть из одного числа другое и затем определить знак разности. К сожалению, проблема этим не решает- ся, поскольку остатки в симметричной системе не несут информации о знаке числа. Один из способов определения знака числа x состоит в обратном пре- образовании к обычному виду, что разрушает саму идею многомодульной 3.9. ТОЧНЫЕ ВЫЧИСЛЕНИЯ 115 арифметики. Задача определения знака числа может быть решена гораз- до лучшим способом с помощью преобразования числа x к так называемому представлению со смешанными основаниями. При этом преобразовании вы- полняем только операции многомодульной арифметики. Все выполняемые действия по вычислению знака основаны на представлении числа x по ки- тайскому алгоритму в виде x = q 1 + q 2 · m 1 + q 3 · m 1 · m 2 + . . . + q n · m 1 · m 2 · . . . · m n−1 , (3.5) где 0 6 q i < |m i |, q 1 — остаток от деления x на m 1 . Коэффициент q n на- зывается старшим членом числа x. В этой форме знак числа x совпадает со знаком его старшего члена. Отметим, что в форме со смешанными основаниями мы имеем x = n P i=1 q i · M i , где M i = m 1 m 2 . . . m i−1 и M 1 = 1; частные M i /M i−1 различны для различных позиций i. Если m 1 = m 2 = . . . = m n = P , то получим представление с фиксированным основанием P — представление в P -ичной системе счисления. При определении знака удобно, чтобы последний модуль m n в векторе оснований был равен 2, поскольку нужно знать, в какой половине множества возможных чисел лежит результат (если q n = 0, то x > 0; если q n = 1, то x < 0). Например, на рис. 3.3 числа 0, 1, 2, 3, 4, 5 образуют нижнюю половину множества возможных чисел, соответствующую значению q n = 0, а числа 6, 7, 8, 9, 10 — верхнюю половину, соответствующую значению q n = 1. Предположим теперь, что нам дано представление x = [a 1 , a 2 , . . . , a n ] от- носительно вектора оснований β = [m 1 , m 2 , . . . , m n ] и требуется определить знак числа x в симметричной системе. Нам нужно преобразовать число x к форме (3.5) и определить знак старшего члена. Для этого необходимо най- ти цифры q 1 , q 2 , . . . , q n , содержащиеся в (3.5). Очевидно, что из (3.5) вытекает x ≡ q 1 (mod m 1 ), следовательно, q 1 = a 1 Мы получили первую цифру. Далее возьмем разность x − q 1 (вычитая q 1 из каждого остатка, представляющего x). Имеем x − q 1 = q 2 · m 1 + q 3 · m 1 · m 2 + . . . + q n · m 1 · m 2 · . . . · m n−1 . Первая цифра (в смешанном представлении) числа x−q 1 равна нулю, следо- вательно, первые цифры всех последующих чисел можно не рассматривать. Будем считать, таким образом, что длина вектора x − q 1 равна n − 1. Затем 116 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ найдем (m 1 ) −1 (mod β r ), где β r = [m 2 , . . . , 2], и вычислим (многомодульное) произведение (x − q 1 )(m 1 ) −1 , для того чтобы получить вторую цифру q 2 Будем продолжать этот процесс до тех пор, пока не вычислим значение q n ∈ {0, 1}, которое является индикатором знака числа x. Пример 3.9.7. Определим знак числа x = [4, 2, 0, 1] с вектором основа- ний β = [7, 5, 3, 2] в симметричной системе относительно β. Очевидно, что q 1 = 4, и x 0 = x − 4 = [0, 3, 2, 1] или, как было объяснено выше, x 0 = [3, 2, 1], поскольку вектор оснований можно сократить до вектора β 0 = [5, 3, 2]. Для того чтобы получить вторую цифру q 2 , вычислим (m 1 ) −1 (mod β 0 ) = 7 −1 (mod β 0 ) = [3, 1, 1]. Умножив x 0 на этот элемент, получим x 0 · (m 1 ) −1 = [4, 2, 1]. Следовательно, q 2 = 4, тогда, вычитая q 2 из последнего модулярного выражения, получим x 00 = [0, 1, 1] или x 00 = [1, 1] для β 00 = [3, 2]. Далее вычисляем (m 2 ) −1 (mod β 00 ) = 5 −1 (mod β 00 ) = [2, 1] и, умножая x 00 на этот элемент, получаем [2, 1]; поэтому q 3 = 2. Вычитая q 3 из последнего модулярного выражения, получаем x 000 = [0, 1], или x 000 = 1 для β 000 = [2]. В заключение вычисляем (m 3 ) −1 (mod β 000 ) = 3 −1 (mod β 000 ) = [1] и, умножая x 000 на этот элемент, получаем [1], откуда следует, что q 4 = 1. Поэтому x является отрицательным числом. Действительно, x = 4 + 4 · 7+ +2 · 7 · 5 + 1 · 7 · 5 · 3 = 207 (mod 7 · 5 · 3 · 2) = 207 (mod 210) = −3. ¤ Задачи и упражнения 1. Найти остаток от деления числа 45 44 + 43 2 + 2 42 на 7. 2. Доказать, что 6 делит n(n + 1)(n + 2) для любого натурального числа n. 3. Доказать, что 5 n+2 + 6 2n+1 делится на 31 при любом натуральном n. 4. На какую цифру оканчивается число 3( 3 3 )? 5. Найдите две последние цифры у числа 7 N , где N — год Вашего рождения. ЗАДАЧИ И УПРАЖНЕНИЯ 117 6. Определить, на сколько нулей оканчивается число 100!. 7. Найти все целые решения уравнения: а) 5x + 3y = 1; б) 47x − 111y = 89. 8. С помощью алгоритма Евклида найти наибольший общий делитель чисел: а) 6188 и 4709; б) 81719, 52003, 33649 и 30107. 9. Найти неприводимое разложение числа 82798848. 10. Составить таблицу простых чисел, меньших 130. 11. Решить сравнение: а) 256x ≡ 179 (mod 337); б) 111x ≡ 75 (mod 321). 12. Составить таблицы Кэли для операций сложения и умножения в кольце Z 2 × Z 3 13. Решить систему сравнений: а) x ≡ 4 (mod 5), x ≡ 6 (mod 7), x ≡ 9 (mod 11); б) x ≡ 2 (mod 3), x ≡ 4 (mod 5), x ≡ 7 (mod 11), x ≡ 3 (mod 13), x ≡ 6 (mod 17). 14. Используя многомодульную арифметику с вектором оснований β = [3, 5, 7], вычислить a + b, a − b, a · b и b −1 (mod β), где a = 9, b = 23. 15. Относительно вектора оснований β = [3, 5, 7] найти многомодульные пред- ставления чисел 127, −127, 537 и −537 в виде симметричной системы остат- ков и системы наименьших неотрицательных остатков. 16. Найти знак числа x = [6, 3, 1, 1] с вектором оснований β = [7, 5, 3, 2] в сим- метричной системе относительно β. 17. Используя многомодульную арифметику с вектором оснований β = [3, 5, 7], вычислить 2 11 − 7 13 Глава 4 ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ § 4.1. Виды и способы задания графов Во многих прикладных задачах изучаются системы связей между раз- личными объектами. Объекты называются вершинами и отмечаются точка- ми, а связи между вершинами называются дугами и отмечаются стрелками между соответствующими точками (рис. 4.1). Такие системы и образуют графы. Граф может изоб- • • • • ¡ ¡ ¡ ¡ ¡ µ H H H H H Y @ @ @ R m µ ª ¸ 1 2 4 3 |