ISBN 5-272-00183-4
В учебнике изложены основные разделы дискретной математики и описаны важнейшие алгоритмы на дискретных структурах данных. Основу книги составляет материал лекционного курса, который автор читает в Санкт-Петербургском государственном техническом университете последние полтора десятилетия.
Для студентов вузов, практикующих программистов и всех желающих изучить дискретную математику.
Содержание
Вступительное слово ..................................................12
i Введение.............,.............................................. 13
ГЛАВА 1. Множества и отношения.................................;.....19
1.1. Множества.......................................................... 19
1.1.1. Элементы и множества .......................................... 20
1.1.2. Задание множеств.............................................. 21
1.1.3. Парадокс Рассела ..................................-............ 21
1.2. Операции над множествами............................................ 22
1.2.1. Сравнение множеств ............................................ 22
1.2.2. Операции над множествами....................................... 23
1.2.3. Разбиения и покрытия ........................................... 23
1.3. Алгебра подмножеств................................................. 24
1.3.1. Булеан.......................................................25
1.3.2. Свойства операций над множествами ...............................25
1.4. Представление множеств в ЭВМ ........................................26
1.4.1. Реализация операций над подмножествами заданного универсума U........27
1.4.2. Генерация всех подмножеств универсума.............................27
1.4.3. Алгоритм построения бинарного кода Грея............................28
1.4.4. Представление множеств упорядоченными списками....................29
1.4.5. Проверка включения слиянием . . . :.................................30
1.4.6. Вычисление объединения слиянием.................................30
1.4.7. Вычисление пересечения слиянием.................................32
1.5. Отношения.........................................................33
1.5.1. Упорядоченные пары .............................................33
1.5.2. Прямое произведение множеств ....................................33
1.5.3. Отношения.....................................................34
1.5.4. Композиция отношений ............................,..............34
1.5.5. Степень отношения .............................................35
1.5.6. Ядро отношения................................................35
1.5.7. Свойства отношений ............................................36
1.5.8. Представление отношений в ЭВМ..................................37
1.6. Функции...........................................................38
1.6.1. Определения.................................................. 38
1.6.2. Инъекция, сюръекция и биекция.................................... 39
1.6.3. Индуцированная функция......................................... 40
1.6.4. Представление функций в ЭВМ .................................... 41
1.7. Отношения эквивалентности .........,................................. 41
•' 1.7.1. Определения.................................................. 42
Содержание
1.7.2. Классы эквивалентности.........................................42
1.7.3. Фактормножества.................. .............................43
1.7.4. Ядро функции .................................................44
1.8. Отношения порядка..................................................44
1.8.1. Определения ..................................................45
1.8.2. Минимальные элементы..........................................45
1.8.3. Алгоритм топологической сортировки ................................46
1.8.4. Монотонные функции............................................47
1.9. Замыкание отношений................................................47
1.9.1. Замыкание отношения относительно свойства.........................47
1.9.2. Транзитивное и рефлексивное транзитивное замыкания........,......... 48
1.9.3. Алгоритм Уоршалла .............................'.... . .'. ....... .г.<48
Комментарии...........................................................49
Упражнения...........................................................49
ГЛАВА 2. Алгебраические структуры...................................... . 51
2.1. Операции и алгебры.................................................. 51
2.1.1. Алгебраические структуры....................................... ... 51
2.1.2. Замыкания и подалгебры...................................... ... 52
2.1.3. Алгебра термов.................................................53
2.1.4. Система образующих............................................53
2.1.5. Свойства операций . .'...........................................54
2.2. Морфизмы.........................................................54
2.2.1. Гомоморфизм...................................................54
2.2.2. Изоморфизм ..................................................55
2.3. Алгебры с одной операцией............................................56
2.3.1. Полугруппы.....................................,............. 57
2.3.2. Моноиды..................................................... 58
2.3.3. Группы.......................................................59
2.4. Алгебры с двумя операциями...........................................60
2.4.1. Кольца...................................................... . 61
2.4.2. Области целостности............................................ 62
2.4.3. Поля......................................................... 62
2.5. Векторные пространства............................................... 63
2.5.1. Определения ..........• . •..................................... 64
2.5.2. Свойства нуль-вектора........................................... 64
2.5.3. Линейные комбинации........................................... 65
2.5.4. Базис и размерность............................................ 66
2.6. Решетки........................................................... 67
2.6.1. Определения......,...........................................67
2.6.2. Ограниченные решетки..........................................68
2.6.3. Решетка с дополнением..........................................68
2.6.4. Частичный порядок в решетке.....................................69
2.6.5. Булевы алгебры................................................70
2.7. Матроиды.........................................................71
2.7.1. Определения..................................................71
2.7.2. Максимальные независимые подмножества...........................72
2.7.3. Базисы....................................................... 73
2.7.4. Ранг...................................................",..... 73
2.7.5. Жадный алгоритм.......................................'........74
2.7.6. Примеры матроидов.............................................77
Комментарии.......................................................... 77
Упражнения........................................................... 78
ГЛАВА 3. Булевы функции ..........................,,.,.......-...:.......79
3.1. Элементарные булевы функции.......................................... 79
.• 3.1.1. Функции алгебры логики ....................t..............'......79
- 3.1.2. Существенные и несущественные переменные . . . .г..................... 80
3.1.3. Булевы функций одной переменной.................................81
3.1.4. Булевы функции двух переменных .............м.....................81
3:2. Формулы............................................................. 81
3.2.1. Реализация функций формулами .............и...................... . 82
3.2.2. Равносильные формулы..........................................84
3.2.3. Подстановка и замена..............................;.............84
3.2.4. Алгебра булевых функций.........................................85
3.3. Принцип двойственности........................+•...........>..........86
3.4. Нормальные формы..................................................88
3.4.1. Разложение булевых функций по переменным..................".......88
3.4.2. Совершенные нормальные формы..................................89
3.4.3. Построение СДНФ..............................................90
3.4.4. Алгоритм вычисления значения булевой функции.......................91
3.4.5. Эквивалентные преобразования..................................k . 92
3.5. Замкнутые классы ...................................................94
3.5.1. Замыкание множества булевых функций .............................94
3.5.2. Некоторые замкнутые классы.....................,..:.............94
3.6. Полнота...........................................................96
Комментарии ..........................................................98
Упражнения........................................................... 98
ГЛАВА 4. Логические исчисления .......................................100
4.1. Логические связки...................................................101
4.1.1. Высказывания.................................................101
4.1.2. Формулы . . ...................................................101
4.1.3. Интерпретация.................................................102
4.1.4. Логическое следование и логическая эквивалентность...................103
4.1.5. Подстановки...................................................104
4.2. Формальные теории..................................................105
4.2.1. Определение формальной теории ..................................105
4.2.2. Выводимость.........................................:........106
4.2.3. Интерпретация.........................................>.......106
4.2.4. Общезначимость и непротиворечивость.........\.....•................107
4.2.5. Полнота, независимость и разрешимость.............................107
4.3. Исчисление высказываний..............................................108
4.3.1. Классическое определение исчисления высказываний...................108
4.3.2. Частный случай формулы.........................................109
4.3.3. Алгоритм унификации ...........................................109
4.3.4. Конструктивное определение исчисления высказываний .................110
4.3.5. Производные правила вывода.....................................111
4.3.6. Дедукция................................................xjXT.112.
. 4.3.7. Некоторые теоремы теории С......................................114
4.3.8. Множество теорем теории ? ..................'.....................116
4.3.9. Другие аксиоматизации исчисления высказываний........ ... ...........118
4.4. Исчисление предикатов . . , „i ..-.-.-................................. .^ ..... .118
4.4.1. Определения................................................. .119
4.4.2. Интерпретация.................................................121
4.4.3. Общезначимость...............................................122
4.4.4. Полнота чистого исчисления предикатов .............................122
Содержание
4.4.5. Логическое следование и логическая эквивалентность................. . .123
4.4.6. Теория равенства...............................................123
4.4.7. Формальная арифметика.........................................124
4.4.8. Теория (абелевых) групп......................................... .124
4.4.9. Теоремы Гёделя о неполноте ......................................126
4.5. Автоматическое доказательство теорем...................................127
4.5.1. Постановка задачи..............................................127
4.5.2. Доказательство от противного.....................................128
4.5.3. Сведение к предложениям.................•.......................128
4.5.4. Правило резолюции для исчисления высказываний .....................130
4.5.5. Правило резолюции для исчисления предикатов...................... .131
4.5.6. Опровержение методом резолюций.................................131
4.5.7. Алгоритм метода резолюций ......................................132
Комментарии ..........................................................133
Упражнения...........................................................133
ГЛАВА 5. Комбинаторика..............................................134
5.1. Комбинаторные конфигурации..........................................135
5.1.1. Комбинаторные задачи...........................................135
5.1.2. Размещения................................................. . .135
5.1.3. Размещения без повторений..................................... .136
5.1.4. Перестановки..................................................136
5.1.5. Сочетания....................................................137
5.1.6. Сочетания с повторениями........................................138
5.2. Подстановки........................................................138
5.2.1. Группа подстановок.............................................139
5.2.2. Графическое представление подстановок............................. 140
5.2.3. Циклы........................................'...............140
5.2.4. Подстановки и перестановки.......................................141
5.2.5. Инверсии..................................................... 141
5.2.6. Генерация перестановок..........................................142
5.3. Биномиальные коэффициенты......................................... . 144
5.3.1. Элементарные тождества....................................... . .144
5.3.2. Бином Ньютона.................................................145
5.3.3. Свойства биномиальных коэффициентов............................ .146
5.3.4. Треугольник Паскаля............................................146
5.3.5. Генерация подмножеств......................................... .147
5.4. Разбиения ._........................................................148
5.4.1. Определения................................................. .148
5.4.2. Числа Стирлинга второго рода.................................... .149
5.4.3. Числа Стирлинга первого рода.................................... .150
5.4.4. Число Белла.........................................:........ .150
5.5. Принцип включения и исключения...................................... .151
5.5.1. Объединение конфигураций....................................... .151
5.5.2. Принцип включения и исключения................................. .152
5.5.3. Число булевых функций, существенно зависящих от всех своих переменных . . 153
5.6. Формулы обращения............................................... . .153
5.6.1. Теорема обращения..........................,................. .153
5.6.2. Формулы обращения для биномиальных коэффициентов.................154
5.6.3. Формулы для чисел Стирлинга.................................... .155
5.7. Производящие функции........................г . .-г-,................. .156
5.7.1. Основная идея.................................................156
5.7.2. Метод неопределенных коэффициентов............................. . 157
8 Содержание
Комментарии..........................................................157
Упражнения...........................................................157
ГЛАВА 6. Кодирование................................................159
6.1. Алфавитное кодирование..............................................161
6.1.1. Префикс и постфикс слова..................г.....................161
6.1.2. Таблица кодов .................................................161
6.1.3. Разделимые схемы..............................................162
6.1.4. Префиксные схемы............................................; 162
6.1.5. Неравенство Макмиллана..........................................163
6.2. Кодирование с минимальной избыточностью...............................165
6.2.1. Минимизация длины кода сообщения................................165
6.2.2. Цена кодирования ..............................................166
6.2.3. Алгоритм фано.................................................167
6.2.4. Оптимальное кодирование........................................168
6.2.5. Алгоритм Хаффмена...................................,..........170
6.3. Помехоустойчивое кодирование.........................................172
6.3.1. Кодирование с исправлением ошибок ...............................172
6.3.2. Классификация ошибок ........•..............,....................173
6.3.3. Возможность исправления всех ошибок..............................173
6.3.4. Кодовое расстояние..............................................174
6.3.5. Код Хэмминга для исправления одного замещения .....................175
6.4. Сжатие данных......................................................177
6.4.1. Сжатие текстов ................................................177
6.4.2. Предварительное построение словаря...............................178
6.4.3. Алгоритм Лемпела—Зива.........................................179
6.5. Шифрование.......................................................180
6.5.1. Криптография .................................................181
6.5.2. Шифрование с помощью случайных чисел............................181
6.5.3. Криптостойкость ...............................................182
6.5.4. Модулярная арифметика .........................................183
6.5.5. Шифрование с открытым ключом....................................185
6.5.6. Цифровая подпись...............................................187
Комментарии ..........................................................188
Упражнения ...........................................................188
ГЛАВА 7. Графы ......................................................189
7.1. Определения графов .................................................189
7.1.1. История теории графов..........................................190
7.1.2. Основное определение ..........................................191
7.1.3. Смежность....................................................191
7.1.4. Диаграммы ...................................................192
7.1.5. Другие определения.............................................192
7.1.6. Изоморфизм графов ............................................193
7.2. Элементы графов....................................................194
7.2.1. Подграфы ....................................................194
7.2.2. Валентность...................................................194
7.2.3. Маршруты, цепи, циклы.......................................... .195
7.2.4. Расстояние между вершинами......................................196
7.2.5. Связность ....................................................197
7.3. Виды графов и операции над графами....................................197
7.3.1. Тривиальные и полные графы......................................197
7.3.2. Двудольные графы..............................................197
Содержание 9
7.3.3. Направленные орграфы и сети..................................... 199
7.3.4. Операции над графами..........................................199
7.4. Представление графов в ЭВМ..........................................201
7.4.1. Требования к представлению графов.................................201
7.4.2. Матрица смежности.........................,.................< .201
7.4.3. Матрица инциденций ."............................................202
7.4.4. Списки смежности...............................................202
7.4.5. Массив дуг.....................................................203
7.4.6. Обходы графов.............................. . <.................203
7.5. Орграфы и бинарные отношения........................................206
7.5.1. Графы и отношения...................................:.........206
7.5.2. Достижимость и частичное упорядочение.............................206
7.5.3. Транзитивное замыкание....................................... . .207
Комментарии......................................................... .208
Упражнения.......................................................... .209
ГЛАВА 8. Связность................................................. . .210
8.1. Компоненты связности.............................................. . .210
8.1.1. Объединение графов и компоненты связности.........................210
8.1.2. Точки сочленения...................................•............211
8.1.3. Оценка числа ребер через число вершин и число компонент связности......211
8.2. Вершинная и реберная связность....................................... .212
8.2.1. Мосты и блоки.................................................212
8.2.2. Меры связности.....'...........................................214
8.3. Теорема Менгера....................................................214
8.3:1. Непересекающиеся цепи и разделяющие множества....................215
8.3.2. Теорема Менгера в «вершинной форме» .............................215
8.3.3. Варианты теоремы Менгера.......................................217
8.4. Теорема Холла......................................................218
8.4.1. Задача о свадьбах ..............................................218
8.4.2. Трансверсаль..................................................218
8.4.3. Совершенное паросо,четание.................................... . .218
8.4.4. Теорема Холла — формулировка и доказательство......................218
8.5. Потоки в сетях......................................................220
8.5.1. Определение потока............................................ .221
8.5.2. Разрезы......................................................221
8.5.3. Теорема Форда и Фалкерсона ....................,..............; .222
8.5.4. Алгоритм нахождения максимального потока......................... .223
8.5.5. Связь между теоремой Менгера и теоремой Форда и Фалкерсона..........225
8.6. Связность в орграфах..............................................-. .226
8.6.1. Сильная, односторонняя и слабая связность......................... .226
8.6.2. Компоненты сильной связности....................................226
8.6.3. Выделение компонент сильной связности........................... .227
8.7. Кратчайшие пути....................................................228
8.7-1. Длина дуг.....................................................228
8.7.2. Алгоритм Флойда...............................................229
8.7.3. Алгоритм Дейкстры .............................................230
Комментарии ..........................................................232
Упражнения.......................................................... .232
ГЛАВА 9. Деревья.....................................................234
9.1. Свободные деревья..................................................234
9.1.1. Определения..................................................234
10 Содержание
9.1.2. Основные свойства деревьев......................................235
9.2. Ориентированные, упорядоченные и бинарные деревья.......................238
. 9.2.1. Ориентированные деревья........................................238
9.2.2. Эквивалентное определение ордерева...............................240
9.2.3. Упорядоченные деревья..........................................241
9.2.4. Бинарные деревья..............................................242
9.3. Представление деревьев в ЭВМ.........................................243
9.3.1. Представление свободных, ориентированных и упорядоченных деревьев.....243
9.3.2. Представление бинарных деревьев..............................'. . .244
9.3.3. Обходы бинарных деревьев .......................................244
9.3.4. Алгоритм симметричного обхода бинарного дерева.....................245
9.4. Деревья сортировки..................................................246
9.4.1. Ассоциативная память...........................................246
9.4.2. Способы реализации ассоциативной памяти ..........................247
9.4.3. Алгоритм бинарного (двоичного) поиска..............................248
9.4.4. Алгоритм поиска в дереве сортировки...............................248
9.4.5. Алгоритм вставки в дерево сортировки ..............................249
9.4.6. Алгоритм удаления из дерева сортировки ............................250
9.4.7. Вспомогательные алгоритмы для дерева сортировки....................251
9.4.8. Сравнение пред
Цена: 150руб.
