Мир программирования - McConnell J.J. / Макконнелл Дж. - Analysis of Algorithms. An Active Learning Approach / Анализ алгоритмов. Вводный курс [2002, DjVu, RUS]

Предисловие 9

1. Основы анализа алгоритмов 12
1.1. Что такое анализ? 14
1.1.1. Классы входных данных 19
1.1.2. Сложность по памяти 20
1.1.3. Упражнения 21
1.2. Что подсчитывать и что учитывать 22
1.2.1. Упражнения 25
1.3. Необходимые математические сведения 26
1.3.1. Логарифмы 26
1.3.2. Бинарные деревья 27
1.3.3. Вероятности 28
1.3.4. Упражнения 31
1.4. Скорости роста 32
1.4.1. Классификация скоростей роста 34
1.4.2. Упражнения 36
1.5. Алгоритмы вида «разделяй и властвуй» 37
1.5.1. Метод турниров 41
1.5.2. Нижние границы 42
1.5.3. Упражнения 44
1.6. Рекуррентные соотношения 45
1.6.1. Упражнения 50
1.7. Анализ программ 51

2. Алгоритмы поиска и выборки 53
2.1. Последовательный поиск 55
2.1.1. Анализ наихудшего случая 56
2.1.2. Анализ среднего случая 56
2.1.3. Упражнения 58
2.2. Двоичный поиск 59
2.2.1. Анализ наихудшего случая 61
2.2.2. Анализ среднего случая 62
2.2.3. Упражнения 64
2.3. Выборка 66
2.3.1. Упражнения 68
2.4. Упражнение по программированию 69

3. Алгоритмы сортировки 70
3.1. Сортировка вставками 72
3.1.1. Анализ наихудшего случая 73
3.1.2. Анализ среднего случая 74
3.1.3. Упражнения 76
3.2. Пузырьковая сортировка 77
3.2.1. Анализ наилучшего случая 78
3.2.2. Анализ наихудшего случая 78
3.2.3. Анализ среднего случая 79
3.2.4. Упражнения 81
3.3. Сортировка Шелла 82
3.3.1. Анализ алгоритма 84
3.3.2. Влияние шага на эффективность 86
3.3.3. Упражнения 87
3.4. Корневая сортировка 87
3.4.1. Анализ 90
3.4.2. Упражнения 91
3.5. Пирамидальная сортировка 92
3.5.1. Анализ наихудшего случая 95
3.5.2. Анализ среднего случая 97
3.5.3. Упражнения 98
3.6. Сортировка слиянием 98
3.6.1. Анализ алгоритма MergeLists 101
3.6.2. Анализ алгоритма MergeSort 102
3.6.3. Упражнения 104
3.7. Быстрая сортировка 105
3.7.1. Анализ наихудшего случая 107
3.7.2. Анализ среднего случая 108
3.7.3. Упражнения 110
3.8. Внешняя многофазная сортировка
слиянием 112
3.8.1. Число сравнений при построении отрезков 116
3.8.2. Число сравнений при слиянии отрезков 116
3.8.3. Число операций чтения блоков 117
3.8.4. Упражнения 118
3.9. Дополнительные упражнения 118
3.10. Упражнения по программированию 120

4. Численные алгоритмы 123
4.1. Вычисление значений многочленов 125
4.1.1. Схема Горнера 126
4.1.2. Предварительная обработка коэффициентов 127
4.1.3. Упражнения 129
4.2. Умножение матриц 130
4.2.1. Умножение матриц по Винограду 131
4.2.2. Умножение матриц по Штрассену 133
4.2.3. Упражнения 135
4.3. Решение линейных уравнений 135
4.3.1. Метод Гаусса-Жордана 136
4.3.2. Упражнения 138

5. Алгоритмы сравнения с образцом 139
5.1. Сравнение строк 140
5.1.1. Конечные автоматы 143
5.1.2. Алгоритм Кнута-Морриса-Пратта 143
5.1.3. Алгоритм Бойера-Мура 147
5.1.4. Упражнения 154
5.2. Приблизительное сравнение строк 155
5.2.1. Анализ 157
5.2.2. Упражнения 157
5.3. Упражнения по программированию 158

6. Алгоритмы на графах 159
6.1. Основные понятия теории графов 162
6.1.1. Терминология 163
6.1.2. Упражнения 164
6.2. Структуры данных для представления
графов 165
6.2.1. Матрица примыканий 166
6.2.2. Список примыканий 167
6.2.3. Упражнения 168
6.3. Алгоритмы обхода в глубину и по уровням 169
6.3.1. Обход в глубину 170
6.3.2. Обход по уровням 171
6.3.3. Анализ алгоритмов обхода 172
6.3.4. Упражнения 173
6.4. Алгоритм поиска минимального остовного дерева 175
6.4.1. Алгоритм Дейкстры-Прима 175
6.4.2. Алгоритм Крускала 179
6.4.3. Упражнения 182
6.5. Алгоритм поиска кратчайшего пути 183
6.5.1. Алгоритм Дейкстры 184
6.5.2. Упражнения 187
6.6. Алгоритм определения компонент
двусвязности 189
6.6.1. Упражнения 192
6.7. Разбиения множеств 192
6.8. Упражнения по программированию 195

7. Параллельные алгоритмы 197
7.1. Введение в параллелизм 199
7.1.1. Категории компьютерных систем 199
7.1.2. Параллельные архитектуры 201
7.1.3. Принципы анализа параллельных алгоритмов 203
7.1.4. Упражнения 203
7.2. Модель PRAM 204
7.2.1. Упражнения 206
7.3. Простые параллельные операции 206
7.3.1. Распределение данных в модели CREW PRAM 206
7.3.2. Распределение данных в модели EREW PRAM 207
7.3.3. Поиск максимального элемента списка 208
7.3.4. Упражнения 210
7.4. Параллельный поиск 210
7.4.1. Упражнения 212
7.5. Параллельная сортировка 212
7.5.1. Сортировка на линейных сетях 213
7.5.2. Чётно-нечётная сортировка перестановками 214
7.5.3. Другие параллельные сортировки 217
7.5.4. Упражнения 218
7.6. Параллельные численные алгоритмы 219
7.6.1. Умножение матриц в параллельных сетях 219
7.6.2. Умножение матриц в модели CREW PRAM 224
7.6.3. Решение систем линейных уравнений алгоритмом SIMD 225
7.6.4. Упражнения 226
7.7. Параллельные алгоритмы на графах 227
7.7.1. Параллельный алгоритм поиска кратчайшего пути 227
7.7.2. Параллельный алгоритм поиска минимального
остовного дерева 229
7.7.3. Упражнения 231

8. Недетерминированные алгоритмы 233
8.1. Что такое NP? 235
8.1.1. Сведение задачи к другой задаче 237
8.1.2. NP-полные задачи 238
8.2. Типичные NP задачи 239
8.2.1. Раскраска графа 240
8.2.2. Раскладка по ящикам 241
8.2.3. Упаковка рюкзака 241
8.2.4. Задача о суммах элементов подмножеств 242
8.2.5. Задача об истинности КНФ-выражения 242
8.2.6. Задача планирования работ 242
8.2.7. Упражнения 243
8.3. Какие задачи относятся к классу NP? 243
8.3.1. Выполнено ли равенство P=NP? 245
8.3.2. Упражнения 245
8.4. Проверка возможных решений 246
8.4.1. Задача о планировании работ 247
8.4.2. Раскраска графа 248
8.4.3. Упражнения 249

9. Другие алгоритмические инструменты 250
9.1. Жадные приближённые алгоритмы 251
9.1.1. Приближения в задаче о коммивояжере 252
9.1.2. Приближения в задаче о раскладке по ящикам 254
9.1.3. Приближения в задаче об упаковке рюкзака 255
9.1.4. Приближения в задаче о сумме элементов
подмножества 256
9.1.5. Приближения в задаче о раскраске графа 258
9.1.6. Упражнения 259
9.2. Вероятностные алгоритмы 260
9.2.1. Численные вероятностные алгоритмы 260
9.2.2. Алгоритмы Монте Карло 264
9.2.3. Алгоритмы Лас Вегаса 267
9.2.4. Шервудские алгоритмы 270
9.2.5. Сравнение вероятностных алгоритмов 271
9.2.6. Упражнения 272
9.3. Динамическое программирование 273
9.3.1. Программирование на основе массивов 274
9.3.2. Динамическое умножение матриц 276
9.3.3. Упражнения 278
9.4. Упражнения по программированию 279

A. Таблица случайных чисел 281

Б. Генерация псевдослучайных чисел 283
Б.1. Случайная последовательность
в произвольном интервале 284
Б.2. Пример применения 284
Б.2.1. Первый способ 284
Б.2.2. Второй способ 285
Б.2.3. Третий способ 286
Б.З. Итоги 286

B. Ответы к упражнениям 287

Литература 298