Предисловие ............................................................................................. 12
О чем эта книга ......................................................................................... 13
Навыки, которые вы приобретете........................................................... 15
В чем особенность книг этой серии......................................................... 17
Для кого эта книга? .................................................................................. 18
Дополнительные ресурсы........................................................................ 19
Благодарности .......................................................................................... 21
От издательства ..........................................................................................21
Глава 7. Графы: основы ........................................................................... 22
7.1. Термины ...............................................................................................23
7.2. Несколько приложений .........................................................................24
7.3. Измерение размера графа.....................................................................25
7.3.1. Число ребер в графе...................................................................26
7.3.2. Разреженные и плотные графы...................................................27
7.3.3. Решение тестового задания 7.1...................................................28
7.4. Представление графа............................................................................30
7.4.1. Списки смежности ......................................................................30
7.4.2. Матрица смежности ....................................................................31
7.4.3. Сравнение представлений...........................................................33
7.4.4. Решения тестовых заданий 7.2–7.3 .............................................34
Задачи на закрепление материала ..............................................................37
6 Оглавление
Глава 8. Поиск в графе и его применения.............................................. 38
8.1. Краткий обзор ......................................................................................39
8.1.1. Некоторые приложения ..............................................................39
8.1.2. Бесплатные графовые примитивы...............................................42
8.1.3. Обобщенный графовый поиск.....................................................43
8.1.4. Поиск в ширину и в глубину .......................................................47
8.1.5. Правильность алгоритма GenericSearch.......................................49
8.2. Поиск в ширину и кратчайшие пути ......................................................50
8.2.1. Высокоуровневая идея................................................................50
8.2.2. Псевдокод для алгоритма BFS.....................................................52
8.2.3. Пример .......................................................................................53
8.2.4. Правильность и время выполнения.............................................55
8.2.5. Кратчайший путь ........................................................................56
8.2.6. Решение тестового задания 8.1 ..................................................60
8.3. Вычисление связных компонент............................................................61
8.3.1. Связные компоненты ..................................................................61
8.3.2. Применения................................................................................63
8.3.3. Алгоритм UCC .............................................................................63
8.3.4. Пример .......................................................................................65
8.3.5. Правильность и время выполнения.............................................66
8.3.6. Решение тестового задания 8.2 ..................................................67
8.4. Поиск в глубину....................................................................................67
8.4.1. Пример .......................................................................................68
8.4.2. Псевдокод для алгоритма DFS ....................................................70
8.4.3. Правильность и время выполнения.............................................72
8.5. Топологическая сортировка ..................................................................73
8.5.1. Топологические упорядочивания................................................74
8.5.2. Когда есть топологическое упорядочивание?..............................75
8.5.3. Вычисление топологического упорядочивания ...........................78
8.5.4. Топологическая сортировка посредством алгоритма DFS............79
8.5.5. Пример .......................................................................................81
8.5.6. Правильность и время выполнения.............................................82
8.5.7. Решения тестовых заданий 8.3–8.4 .............................................84
Оглавление   7
*8.6. Вычисление сильно связных компонент ..............................................85
8.6.1. Определение сильно связных компонент ....................................85
8.6.2. Почему поиск в глубину? ............................................................88
8.6.3. Почему обратный граф?..............................................................90
8.6.4. Псевдокод для алгоритма Косарайю ...........................................94
8.6.5. Пример .......................................................................................96
8.6.6. Правильность и время выполнения.............................................98
8.6.7. Решения тестовых заданий 8.5–8.6 ............................................99
8.7. Структура Всемирной паутины ............................................................100
8.7.1. Веб-граф...................................................................................100
8.7.2. «Галстук-бабочка» ....................................................................102
8.7.3. Основные выводы.....................................................................103
Задача повышенной сложности .................................................................109
Задача по программированию ...................................................................109
Глава 9. Алгоритм кратчайшего пути Дейкстры .................................. 110
9.1. Задача о кратчайшем пути с единственным истоком...........................111
9.1.1. Определение задачи.................................................................111
9.1.2. Несколько допущений...............................................................113
9.1.3. Почему не поиск в ширину? ......................................................113
9.1.4. Решение тестового задания 9.1 ................................................115
9.2. Алгоритм Дейкстры.............................................................................115
9.2.1. Псевдокод ................................................................................115
9.2.2. Пример .....................................................................................117
*9.3. Почему алгоритм Дейкстры правилен?..............................................118
9.3.1. Фиктивная редукция.................................................................118
9.3.2. Плохой пример алгоритма Дейкстры.........................................119
9.3.3. Правильность с неотрицательными реберными длинами ..........120
9.4. Реализация и время выполнения ........................................................125
Задачи на закрепление материала ............................................................127
Задача повышенной сложности .................................................................130
Задача по программированию ...................................................................130
8 Оглавление
Глава 10. Куча......................................................................................... 131
10.1. Структуры данных: краткий обзор.....................................................132
10.1.1. Выбор правильной структуры данных .....................................132
10.1.2. Переход на следующий уровень..............................................133
10.2. Поддерживаемые операции ..............................................................135
10.2.1. Вставка и извлечение минимума .............................................135
10.2.2. Дополнительные операции .....................................................137
10.3. Применения ......................................................................................138
10.3.1. Применение: сортировка.........................................................138
10.3.2. Применение: событийный менеджер ......................................141
10.3.3. Применение: поддержка медианы...........................................142
10.4. Ускорение алгоритма Дейкстры ........................................................144
10.4.1. Почему именно кучи?..............................................................144
10.4.2. План .......................................................................................145
10.4.3. Поддержание инварианта .......................................................148
10.4.4. Время выполнения..................................................................150
*10.5. Детали реализации ........................................................................151
10.5.1. Кучи в виде деревьев..............................................................151
10.5.2. Кучи в виде массива ...............................................................153
10.5.3. Реализация операции «Вставить» со временем O(log n) .........155
10.5.4. Реализация операции «Извлечь минимум»
со временем O(log n) ........................................................................159
Задачи на закрепление материала ............................................................163
Задачи повышенной сложности .................................................................164
Задача по программированию ...................................................................165
Глава 11. Дерево поиска ........................................................................ 166
11.1. Отсортированные массивы................................................................167
11.1.1. Отсортированные массивы: поддерживаемые операции .........167
11.1.2. Неподдерживаемые операции.................................................170
11.2. Деревья поиска: поддерживаемые операции ....................................171
*11.3. Детали реализации ........................................................................173
11.3.1. Свойство дерева поиска..........................................................173
Оглавление   9
11.3.2. Высота дерева поиска.............................................................175
11.3.3. Реализация операции «Отыскать» со временем O(высота) ....176
11.3.4. Реализация операций «Минимум» и «Максимум» за время
O(высота)..........................................................................................177
11.3.5. Реализация операции «Предшественник»
со временем O(высота) .....................................................................178
11.3.6. Реализация операции «Вывести в отсортированном
порядке» со временем O(n) ...............................................................180
11.3.7. Реализация операции «Вставить» со временем O(высота) ......181
11.3.8. Реализация операции «Удалить» со временем O(высота) ......182
11.3.9. Расширенные деревья поиска для операции «Выбрать»..........186
11.3.10. Решение тестового задания 11.1 ...........................................188
*11.4. Сбалансированные деревья поиска .................................................188
11.4.1. Более напряженные усилия для улучшения баланса...............188
11.4.2. Повороты................................................................................190
Задачи на закрепление материала ............................................................193
Задача по программированию ...................................................................194
Глава 12. Хеш-таблицы и фильтры Блума ........................................... 195
12.1. Поддерживаемые операции ..............................................................196
12.1.1. Решение тестового задания 12.1.............................................199
12.2. Применения ......................................................................................200
12.2.1. Применение: устранение дублирования..................................200
12.2.2. Применение: задача о сумме двух чисел.................................201
12.2.3. Применение: поиск в огромных пространствах состояний.......205
12.2.4. Решение тестового задания 12.2.............................................206
*12.3. Реализация: высокоуровневая идея ................................................206
12.3.1. Два простых решения .............................................................206
12.3.2. Хеш-функции ..........................................................................207
12.3.3. Коллизии неизбежны ..............................................................209
12.3.4. Разрешение коллизий: cцепление...........................................211
12.3.5. Разрешение коллизий: открытая адресация............................212
12.3.6. Что делает хеш-функцию хорошей? ........................................215
12.3.7. Решения тестовых заданий 12.3–12.5 .....................................221
10 Оглавление
*12.4. Дополнительные детали реализации...............................................222
12.4.1. Загрузка против результативности..........................................222
12.4.2. Управление загрузкой вашей хеш-таблицы.............................225
12.4.3. Выбор своей хеш-функции ......................................................226
12.4.4. Выбор стратегии разрешения коллизий ..................................227
12.4.5. Решение тестового задания 12.6.............................................228
12.5. Фильтры Блума: основы....................................................................228
12.5.1. Поддерживаемые операции ....................................................228
12.5.2. Применения ............................................................................231
12.5.3. Реализация .............................................................................232
*12.6. Фильтр Блума: эвристический анализ..............................................235
12.6.1. Эвристические допущения ......................................................236
12.6.2. Доля установленных бит (равных 1) .......................................238
12.6.3. Вероятность ложного утверждения .........................................238
12.6.4. Кульминационный момент.......................................................240
12.6.5. Решение тестового задания 12.7.............................................241
Задачи на закрепление материала ............................................................243
Задача по программированию ...................................................................244
Приложение В. Краткий обзор асимптотической формы записи ....... 245
В.1. Суть....................................................................................................245
В.2. Обозначение O-большое.....................................................................246
В.3. Примеры.............................................................................................248
В.4. Обозначения Омега-большое и Тета-большое.....................................250
Решения отдельных задач..................................................................... 253