Предисловие ........................................................................................................... 3
Часть 1. Графы и алгоритмы .................................................................................. 5
Глава 1. Элементы теории графов ............................................................................. 5
1.1. Нач альные понятия .............................................................................. 5
1.1.1. Опр еделение графа ..................................................................... 5
1.1.2. Гра фы и бинарные отношения ..................................................8
1.1.3. Отк уда берутся графы ................................................................9
1.1.4. Чис ло графов ............................................................................. 10
1.1.5. Сме жность, инцидентность, степени ......................................10
1.1.6. Нек оторые специальные графы ..............................................11
1.1.7. Гра фы и матрицы ...................................................................... 11
1.1.8. Взве шенные графы ...................................................................13
1.2. Изо морфизм ........................................................................................ 13
1.2.1. Опр еделение изоморфизма ......................................................13
1.2.2. Инв арианты ............................................................................... 14
1.3. Опе рации над графами ....................................................................... 15
1.3.1. Лок альные операции ................................................................15
1.3.2. Под графы .................................................................................. 16
1.3.3. Алг ебраические операции .......................................................17
1.4. Мар шруты, связность, расстояния .................................................... 20
1.4.1. Мар шруты, пути, циклы ..........................................................20
1.4.2. Свя зность и компоненты .........................................................21
1.4.3. Мет рические характеристики графов .....................................22
1.4.4. Мар шруты и связность в орграфах .........................................24
1.5. Дер евья ................................................................................................ 25
1.5.1. Опр еделение и элементарные свойства ..................................25
1.5.2. Цен тр дерева ............................................................................. 26
1.5.3. Кор невые деревья ..................................................................... 27
1.5.4. Кар касы ..................................................................................... 28
1.6. Эйл еровы графы ................................................................................. 29
1.7. Дву дольные графы ............................................................................. 31
1.8. Пла нарные графы ............................................................................... 34
Задачи .......................................................................................................... 38
Глава 2. Анализ графов ............................................................................................ 42
2.1. Пои ск в ширину................................................................................... 42
2.1.1. Мет од поиска в ширину ...........................................................42
2.1.2. BFS -дерево и вычисление расстояний ...................................45
2.2. Пои ск в глубину ................................................................................. 48
2.2.1. Мет од поиска в глубину ..........................................................48
2.2.2. DFS -дерево ................................................................................ 50
2.2.3. Дру гие варианты алгоритма поиска в глубину ......................51
2.2.4 Шар ниры .................................................................................... 53
2.3. Бло ки .................................................................................................... 55
2.3.1. Дву связность ............................................................................. 55
2.3.2. Бло ки и BC-деревья .................................................................. 57
2.3.3. Выя вление блоков .................................................................... 59
2.4. База циклов .......................................................................................... 61
2.4.1. Про странство подграфов .........................................................61
2.4.2. Ква зициклы ............................................................................... 63
2.4.3. Фун даментальные циклы .........................................................64
2.4.4. Пос троение базы циклов ..........................................................65
2.4.5. Рац ионализация ........................................................................ 67
2.5. Эйл еровы циклы ................................................................................. 67
2.6. Гам ильтоновы циклы ......................................................................... 70
Задачи и упражнения ................................................................................. 73
Глава 3. Экстремальные задачи на графах ............................................................. 75
3.1. Нез ависимые множества, клики, вершинные покрытия .................75
3.1.1. Три за дачи ................................................................................. 75
3.1.2. Страте гия перебора для задачи о независимом множестве ..77
3.1.3. Рацио нализация ........................................................................ 78
3.1.4. Хорда льные графы ...................................................................79
3.1.5. Эврис тики для задачи о независимом множестве .................80
3.1.6. Прибл иженный алгоритм для задачи о вершинном покры-
тии ............................................................................................. 82
3.1.7. Переб ор максимальных независимых множеств ...................82
3.2. Рас краски ............................................................................................. 85
3.2.1. Раскра ска вершин ..................................................................... 85
3.2.2. Переб орный алгоритм для раскраски .....................................86
3.2.3. Рацио нализация ........................................................................ 87
3.2.4. Хорда льные графы ...................................................................88
3.2.5. Раскра ска ребер ........................................................................ 90
3.3. Пар осочетания .................................................................................... 93
3.3.1. Парос очетания и реберные покрытия ....................................93
3.3.2. Метод увеличивающих цепей .................................................94
3.3.3. Парос очетания в двудольных графах .....................................96
3.3.4. Парос очетания в произвольных графах
алгори(тм Эдмондса) ..............................................................99
3.4. Опт имальные каркасы ...................................................................... 101
3.4.1. Задача об оптимальном каркасе и алгоритм Прима ............101
3.4.2. Алгор итм Краскала ................................................................104
3.5. Жад ные алгоритмы и матроиды ...................................................... 105
3.5.1. Матро иды ................................................................................ 106
3.5.2. Теоре ма Радо – Эдмондса ......................................................107
3.5.3. Взвеш енные паросочетания ..................................................109
Упражнения ................................................................................................. 110
Часть 2. Модели вычислений ............................................................................. 112
Исторические сведения ........................................................................................... 112
Глава 1. Тьюрингова модель переработки информации ..................................... 114
1.1. Алг ебра тьюринговых программ ....................................................116
1.2. Нач альное математическое обеспечение .......................................118
1.3. Мет одика доказательства правильности программ ......................120
1.4. Выч ислимость и разрешимость ...................................................... 121
1.5. Выч исление числовых функций .....................................................122
1.6. Час тично-рекурсивные функции ....................................................123
1.7. Уни версальная тьюрингова программа и пример невычислимой
функции ............................................................................................. 127
1.8. Об измерении алгоритмической сложности задач ........................129
Глава 2 Абак ........................................................................................................... 132
2.1. Осн овные определения .................................................................... 132
2.2. При меры неразрешимости .............................................................. 134
Глава 3. Алгорифмы Маркова ............................................................................... 138
Глава 4. Равнодоступная адресная машина .......................................................... 141
Глава 5. Формальные языки .................................................................................. 145
5.1. Осн овные понятия и обозначения ..................................................145
5.2. Спо собы задания формальных языков ...........................................147
5.3. Рег улярные выражения .................................................................... 148
5.4. Реш ение уравнений в словах ........................................................... 149
5.5. Авт оматное задание языков ............................................................ 151
5.6. При менение конечных автоматов в программировании ..............157
Глава 6. Логическое программирование .............................................................. 163
6.1. Язы к предикатов ............................................................................... 163
6.2. Нек оторые сведения из математической логики ...........................167
6.3. При меры формальных доказательств .............................................170
6.4. Эле менты языка Пролог .................................................................. 174
Часть 3. Структуры данных ................................................................................... 176
Введение ................................................................................................... 176
Глава 1. Списки ....................................................................................................... 184
1.1. Общ ие сведения о списках .............................................................. 184
1.2. Спи ски с прямым доступом ............................................................. 188
1.3. Спи ски с последовательным доступом ..........................................190
1.4. Нек оторые дополнительные операции со связными списками ...195
1.5. Мод елирование списков с последовательным доступом при по-
мощи массивов ................................................................................. 196
1.6. Дер евья и графы ............................................................................... 198
Глава 2. Разделенные множества .......................................................................... 202
2.1. Опе рации над разделенными множествами ...................................202
2.2. Примеры использования разделенных множеств ......................... 204
2.3. Представление разделенных множеств с помощью массива .......206
2.4. П редставление разделенных множеств с помощью древовид-
ной структуры ................................................................................... 206
2.5. П редставление разделенных множеств с использованием ран-
гов вершин ........................................................................................ 210
2.6. П редставление разделенных множеств с использованием ран-
гов вершин и сжатия путей .............................................................. 214
2.7. А нализ трудоемкости ....................................................................... 215
Глава 3. Приоритетные очереди ............................................................................ 221
3.1. Осн овные определения .................................................................... 221
3.2. П редставление приоритетной очереди с помощью d-кучи ..........222
3.3. При менение приоритетных очередей в задаче сортировки .........234
3.4. Нах ождения кратчайших путей в графе .........................................237
Глава 4. Объединяемые приоритетные очереди .................................................. 239
4.1. Лев осторонние кучи ......................................................................... 239
4.2. Лен ивая левосторонняя и самоорганизующиеся кучи ..................253
4.3. Бин омиальные и фибоначчиевы кучи ............................................258
4.4. Тон кие кучи ...................................................................................... 263
4.5. Тол стые кучи ..................................................................................... 271
Глава 5. Поисковые деревья .................................................................................. 288
5.1. Дво ичные деревья поиска ................................................................ 288
5.2. Кра сно-черные деревья .................................................................... 293
5.3. Б-де ревья ........................................................................................... 297
Список литературы .................................................................................................. 302