Дискретная математика Ерош и др

3.2.10. Представление диэдральной группы ............................	53
3.2.11. Скалярное произведение функций, заданных
на группе ..................................................................	54
3.2.12. Задачи для контрольной .............................................	56
Литература ................................................................................	62
4. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ ................................................	63
4.1. Основные понятия и теоремы комбинаторики ..........................	63
4.1.1. Размещения с повторениями ........................................	63
4.1.2. Размещения без повторений .........................................	65
4.1.3. Перестановки без повторений ........................................	66
4.1.4. Перестановки с повторениями ......................................	67
4.1.5. Основные правила комбинаторики .................................	68
4.1.6. Главная теорема комбинаторики (теорема о включениях
и исключениях) ..........................................................	68
4.1.7. Сочетания без повторений ............................................	70
4.1.8. Сочетания с повторениями ...........................................	72
4.1.9. Свойства чисел сочетаний .............................................	73
4.1.10. Основные формулы классической комбинаторики ...........	74
4.2. Комбинаторные задачи с ограничениями ................................	75
4.2.1. Простые задачи с ограничениями .................................	75
4.2.2. «Задачи о смещениях (о беспорядках)» ..........................	76
4.2.3. «Задача о караване» .....................................................	77
4.3. Комбинаторные задачи на раскладки и разбиения ...................	78
4.3.1. Раскладки с указанием числа предметов ........................	78
4.3.2. Раскладка предметов на 2 кучки (в 2 ящика, кармана) .....	79
4.3.3. Раскладка предметов по k ящикам .................................	81
4.3.4. «Флаги на мачтах» ......................................................	82
4.3.5. «Покупка билетов» ......................................................	83
4.4. Рекуррентные соотношения в комбинаторике ..........................	83
4.4.1. «Задача о наклейке марок» ...........................................	84
4.4.2. «Задача об уплате долга» ..............................................	84
4.4.3. «Задача о размене гривенника» .....................................	85
4.5. Задачи для контрольной работы .............................................	85
Литература ................................................................................	89
5. ТЕОРИЯ ГРАФОВ .......................................................................	90
5.1. «Задача о кёнигсбергских мостах» .........................................	90
5.2. Виды графов ........................................................................	91
5.3. Способы задания графов ........................................................	92
5.4. Понятие о плоских графах – «Задача о трех домах и трех
колодцах» ...........................................................................	95
5.5. Теорема Жордана о плоских графах ........................................	96
5.6. Определение числа ребер в графе ...........................................	96
5.7. Теорема о количестве вершин нечетной степени ......................	97
5.8. Графы типа «дерево» – основные соотношения .........................	97
5.9. Цикломатическое число графа ..............................................	97
5.10. «Задача о наименованиях и переименованиях» ........................	98

141

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. Функция Эйлера для натурального числа (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

142

Учебное издание

Ерош Игорь Львович Сергеев Михаил Борисович Соловьев Николай Владимирович

ДИСКРЕТНАЯ МАТЕМАТИКА

Учебное пособие

Редактор А. Г. Ларионова

Компьютерная верстка А. Н. Колешко

Корректор Т. Н. Гринчук

Сдано в набор 07.06.05. Подписано к печати 17.11.05. Формат 60 84 1/16. Бумага офсетная. Печать офсетная. Усл. кр. отт. 9,9. Усл. печ. л. 8,8. Уч. изд. л. 9,5. Тираж 1000 экз. Заказ № 8.

Отдел электронных публикаций и библиографии библиотеки Отдел оперативной полиграфии

ГУАП 190000, Санкт Петербург, ул. Б. Морская, 67

143