Иванов Б. Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие/ Б. Н. Иванов. — М., 2003. — 288 с: ил. - серия "Технический университет"
Теоретические основы курса сопровождаются практически значимыми алгоритмами, реализованными в конкретных компьютерных программах. Книгу можно рассматривать в качестве хорошего справочника методов и алгоритмов дискретной математики, широко применяемых в практическом программировании. Пособие рассчитано в первую очередь на математиков-прикладников, а также программистов, занятых разработкой прикладного программного обеспечения.
Содержание
Предисловие.............................6
Глава 1. Комбинаторные схемы....................8
1.1. Правило суммы........................8
1.2. Правило прямого произведения................9
1.3. Размещения с повторениями.................9
1.4. Размещения без повторений.................10
1.5. Перестановки........................11
1.6. Сочетания..........................11
1.7. Сочетания с повторениями.................12
1.8. Перестановки с повторениями, мультимножества......14
1.9. Упорядоченные разбиения множества............15
1.10. Неупорядоченные разбиения множества..........16
1.11. Полиномиальная формула.................18
1.12. Бином Ньютона......................19
1.13. Инверсии..........................20
1.14. Обратные перестановки...................21
Глава 2. Представление абстрактных объектов............24
2.1. Представление последовательностей.............24
2.1.1. Смежное представление.................24
2.1.2. Характеристические векторы..............25
2.1.3. Связанное размещение.................26
2.2. Представление деревьев...................31
2.2.1. Представление деревьев на связанной памяти......32
2.2.2. Представление деревьев на смежной памяти......33
2.3. Представление множеств..................37
Глава 3. Методы подсчета и оценивания...............39
3.1. Производящие функции...................39
3.1.1. Линейные операции...................41
3.1.2. Сдвиг начала вправо...................41
3.1.3. Сдвиг начала влево...................42
3.1.4. Частичные суммы....................42
3.1.5. Дополнительные частичные суммы...........42
3.1.6. Изменение масштаба..................43
3.1.7. Свертка..............................................44
3.2. Линейные рекуррентные соотношения...........49
3.3. Неоднородные линейные рекуррентные соотношения. ... 51
3.4. Обобщенное правило произведения.............53
3.5. Принцип включения и исключения.............56
3.6. Ладейные многочлены и многочлены попаданий......59
3.6.1. Ладейные многочлены..................60
3.6.2. Многочлены попаданий.................63
Глава 4. Генерация комбинаторных объектов............66
4.1. Поиск с возвращением...................66
4.2. Перестановки различных элементов.............68
4.3. Эффективное порождение перестановок...........71
4.4. Порождение подмножеств множества............76
4.5. Генерация размещений с повторениями...........79
4.6. Порождение сочетаний...................80
4.7. Порождение композиций и разбиений............83
4.8. Генерация случайных перестановок.............89
Глава 5. Сортировка и поиск....................91
5.1. Сортировка вставками....................92
5.2. Пузырьковая сортировка...................93
5.3. Сортировка перечислением.................94
5.4. Сортировка всплытием Флойда...............95
5.5. Последовательный поиск..................102
5.6. Логарифмический поиск..................104
5.7. Сортировка с вычисляемыми адресами...........106
Глава 6. Введение в теорию графов. Алгоритмы на графах......110
6.1. Основные понятия и определения.............110
6.2. Представления графов...................114
6.2.1. Матрица смежности графа...............114
6.2.2. Матрица инцидентности графа.............115
6.2.3. Матрица весов графа..................116
6.2.4. Список ребер графа..................116
6.2.5. Структура смежности графа..............117
6.3. Метод поиска в глубину..................117
6.4. Отношение эквивалентности................124
6.5. Связные компоненты....................125
6.6. Выделение компонент связности..............126
6.7. Эйлеровы графы......................130
6.8. Остовные деревья......................137
6.8.1. Жадный алгоритм построения минимального остовного дерева....................139
6.8.2. Алгоритм ближайшего соседа построения
остовного дерева....................145
6.9. Кратчайшие пути на графе.................151
6.10. Потоки в сетях.......................156
6.11. Клики, независимые множества..............160
6.12. Циклы, фундаментальные множества циклов.......172
6.13. Листы и блоки.......................177
6.13.1. Листы.........................178
6.13.2. Блоки.........................180
6.13.3. Поиск блоков в глубину................182
6.14. Двудольные графы.....................185
6.14.1. Условия существования двудольных графов......185
6.14.2. Паросочетания....................186
6.14.3. Алгоритм определения максимального паросочетания....................186
6.14.4. Системы различных представителей.........189
6.14.5. Связь системы различных представителей
и двудольных графов.................189
6.14.6. Задача о назначениях.................190
6.15. Хроматические графы...................194
6.16. Диаметр, радиус и центры графа.............196
Глава 7. Введение в теорию групп. Приложения...........197
7.1. Определение группы....................197
7.2. Гомоморфизм групп....................198
7.3. Смежные классы......................199
7.4. Строение коммутативных (абелевых) групп.........203
7.5. Строение некоммутативных групп.............207
7.6. Симметрическая группа подстановок............208
7.7. Действие групп на множестве................212
7.8. Цикловой индекс группы..................217
7.9. Теория перечисления Пойа.................218
7.10. Цикловая структура групп подстановок..........223
7.10.1. Цикловой индекс группы, действующей на себе . . . 224
7.10.2. Цикловой индекс циклической группы........224
7.10.3. Цикловой индекс симметрической группы......225
Глава 8. Элементы теории чисел..................227
8.1. Наибольший общий делитель................227
8.2. Наименьшее общее кратное................228
8.3. Простые числа.......................228
8.4. Сравнения, свойства сравнений..............232
8.5. Полная система вычетов..................233
8.6. Приведенная система вычетов...............234
8.7. Функция Эйлера......................234
8.8. Функция Мёбиуса. Формула обращения Мёбиуса.....238
Задачи и упражнения.......................240
Ответы..............................281
Литература............................285
Предметный указатель.......................286
