Файл: Учебник издание шестое Рекомендовано Министерством образования и науки Российской Федерации в качестве учебника для студентов высших технических учебных заведений.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2023
Просмотров: 525
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
3.9. ТОЧНЫЕ ВЫЧИСЛЕНИЯ
111
Пример 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 состоит в обратном пре- образовании к обычному виду, что разрушает саму идею многомодульной
112
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
арифметики. Задача определения знака числа может быть решена гораз- до лучшим способом с помощью преобразования числа
1 ... 10 11 12 13 14 15 16 17 ... 29
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. Затем
ЗАДАЧИ И УПРАЖНЕНИЯ
113
найдем (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 — год Вашего рождения.
114
Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ
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
Рис. 4.1
ражать сеть улиц в городе: вершины графа — пере- крестки, а дуги — улицы с разрешенным направлением движения (улицы могут быть с односторонним и дву- сторонним движением). В виде графов можно предста- вить блок-схемы программ (вершины — блоки, а ду- ги — разрешенные переходы от одного блока к друго- му), электрические цепи, географические карты и мо- лекулы химических соединений, связи между людьми и группами людей.
Перейдем к точным определениям.
Графом называется алгебраическая система G = hM; Ri, где R — двух- местный предикатный символ. Элементы носителя M называются вершина-
ми графа G, а элементы бинарного отношения R ⊆ M
2
— дугами. Таким образом, дугами являются пары вершин (a, b) ∈ R. При этом дуга (a, b) на- зывается исходящей из вершины a и заходящей в вершину b.
Изображение графа G = hM; Ri получается путем расположения различ- ных точек на плоскости для каждой вершины a ∈ M, причем если (a, b) ∈ R,
то проводится стрелка (дуга) из вершины a к вершине b.
116
Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ
Пример 4.1.1. Изображение графа
G
с множеством вершин
M = {1, 2, 3, 4} и множеством дуг R = {(1, 1), (1, 2), (2, 3), (3, 4), (4, 3), (4, 1)}
представлено на рис. 4.1. ¤
При задании графа для нас не имеет значения природа
a
b
•
•
¡
¡
¡
¡
¡
µº
:
Рис. 4.2
связи между вершинами a и b, важно только то, что связь существует и информация о связях содержится во множестве дуг R. Однако часто возникают ситуации, при которых та- кой информации оказывается недостаточно, например, в слу- чаях, когда имеется несколько дуг, исходящих из вершины a
и заходящих в вершину b. Такие дуги называются кратными
(рис. 4.2). Тогда используется понятие мультиграфа.
Мультиграфом G называется тройка hM, U, P i, в которой M — множе- ство вершин, U — множество дуг, а P ⊆ M × U × M — трехместный пре- дикат, называемый инцидентором и представляемый следующим образом:
(a, u, b) ∈ P тогда и только тогда, когда дуга u исходит из вершины a и за- ходит в вершину b. Отметим, что любой граф можно представить в виде мультиграфа.
Граф G = hM; Ri называется ориентированным (орграфом), если най- дется дуга (a, b) ∈ R такая, что (b, a) /
∈ R. Если же отношение R симметрич- но, т. е. из (a, b) ∈ R следует (b, a) ∈ R, то граф G называется неориентиро-
ванным (неорграфом). Если одновременно пары (a, b) и (b, a) принадлежат R
(рис. 4.3а), то информацию об этих дугах можно представить множеством
[a, b] {(a, b), (b, a)}, называемым ребром, которое соединяет вершины a и b.
При этом вершины a и b называются концами ребра [a, b]. Ребра изобража- ются линиями (без стрелок), соединяющими вершины (рис. 4.3б ).
•
•
¼
*
a
b
•
•
´
´
´
´
´
´
´
´
´
´
´
a
b
а
б
Рис. 4.3
4.1. ВИДЫ И СПОСОБЫ ЗАДАНИЯ ГРАФОВ
117
Если в мультиграфе вместо дуг рассматриваются ребра, то мультиграф также называется неориентированным. Отметим, что если в орграфе
G = hM; Ri к каждой дуге (a, b) ∈ R добавить пару (b, a), то в результате образуется неорграф , который будем называть соответствующим данному
орграфу G и обозначать через F (G).
Пример 4.1.2. Орграфу G, изображенному на рис. 4.1, соответствует неорграф F (G), изображенный на рис. 4.4. ¤
Введенные в § 2.2 понятия морфизмов алгебраиче-
•
•
•
•
¡
¡
¡
¡
¡
H
H
H
H
H
@
@
@
m
¢
¢
¢
¢
¢
1 2
4 3
Рис. 4.4
ских систем для графов представляются следующим об- разом. Пусть G = hM; Ri, G
0
= hM
0
; R
0
i — графы. Тогда отображение ϕ: M → M
0
является гомоморфизмом, ес- ли для любых вершин a, b ∈ M из (a, b) ∈ R следует
(ϕ(a), ϕ(b)) ∈ R
0
. Биекция ϕ: M ↔ M
0
является изо- морфизмом графов, если (a, b) ∈ R ⇔ (ϕ(a), ϕ(b)) ∈ R
0
.
Пример 4.1.3. Рассмотрим граф G, состоящий из множества вершин {1, 2, 3, 4} и множества дуг [1, 2] ∪ [3, 4] ∪ {(1, 3), (2, 4),
(3, 2), (4, 1)} (рис. 4.5а). Граф G
0
= h{a, b, c}; [a, b] ∪ [b, c] ∪ {(a, c), (b, b)}i
является гомоморфным образом графа G при гомоморфизме ϕ, в кото- ром ϕ(1) = a, ϕ(2) = b, ϕ(3) = c, ϕ(4) = b (рис. 4.5б ). Граф G
00
, по- казанный на рис. 4.5в, изоморфен графу G посредством изоморфизма ψ,
при котором ψ(1) = a, ψ(2) = b, ψ(3) = c, ψ(4) = d. Отображение
χ: {1, 2, 3, 4} ↔ {1, 2, 3, 4}, при котором χ(1) = 2, χ(2) = 1, χ(3) = 4, χ(4) = 3,
является автоморфизмом графа G. ¤
•
•
•
•
¡
¡
¡
¡
¡
¡
¡
¡
¡
µ
¾
¾
@
@
@
@
@
@
@
@
@
R
1 2
4 3
•
•
•
-
¢
¢
¢
¢
¢
¢
¢
¢
¢
A
A
A
A
A
A
A
A
A
±°
²¯
a
c
b
•
•
•
•
-
@
@
@
@
@
@
@
@
@
I
¡
¡
¡
¡
¡
¡
¡
¡
¡
ª
-
b
a
d
c
а
б
в
Рис. 4.5