Составители:
Рубрика:
142
5.11. «Задача коммивояжера» и «Задача о минимальной сети дорог» 99
5.12. Построение турнирной таблицы ........................................... 101
5.13. Теорема Куратовского о плоских графах ............................... 102
5.14. Проецирование графа на сферу ............................................ 103
5.15. Теорема Эйлера о соотношении числа вершин, ребер и граней
плоского графа .................................................................. 104
5.16. Правильные многогранники ................................................ 106
5.17. Мозаики ............................................................................ 107
5.18. «Задача о четырех красках» ................................................. 108
5.19. Теорема о направленных графах ........................................... 108
5.20. Задачи для контрольной ...................................................... 110
6. ТЕОРИЯ ЧИСЕЛ И НЕКОТОРЫЕ ЕЕ ПРИЛОЖЕНИЯ .................... 113
6.1. Основные понятия и определения ........................................... 114
6.1.1. Делимость целых чисел ............................................... 114
6.1.2. Свойства сравнений ...................................................... 115
6.1.3. Решение сравнений ..................................................... 116
6.1.4. Наименьшее общее кратное и наибольший общий
делитель .................................................................... 116
6.1.5. Простые числа. Разложение на простые сомножители.
Каноническая форма числа........................................... 117
6.1.6. Определение НОК И НОД чисел .................................... 117
6.1.7. Функция Эйлера для натурального числа j(m) ................ 118
6.1.8. Сравнимость чисел и классы вычетов ............................ 119
6.1.9. Теоремы Ферма и Эйлера ............................................. 119
6.1.10. Показатели чисел по модулю и примитивные корни ....... 120
6.1.11. Конечные поля (поля Галуа) .......................................... 121
6.1.12. Квадратичные вычеты. Символ Лежандра.
Символ Якоби ............................................................. 126
6.2. Использование теории чисел в криптографии и коррекции
ошибок при передаче сообщений ........................................... 129
6.2.1. Использование теории чисел при открытом распределе
нии секретных ключей ................................................ 130
6.2.2. Линейные коды для коррекции ошибок при передаче
сообщений.................................................................. 135
6.2.3. Арифметические коды ................................................. 136
6.3. Задачи для контрольной ........................................................ 137
Литература ................................................................................ 138
Заключение ................................................................................... 139
