Основные темы алгоритмов из настольных книг программиста

Содержания книг для быстрого ознакомления с курсом алгоритмов и поиска.

Т. Кормен  “Алгоритмы: построение и анализ”
Г. Уоррен “Алгоритмические трюки для программистов”
Р. Седжвик “Алгоритмы на C++. Фундаментальные алгоритмы и структуры данных”
Д. Кнут “Искусство программирования, том 1. Основные алгоритмы”
Д. Кнут “Искусство программирования, том 2. Получисленные алгоритмы”
Д. Кнут “Искусство программирования, том 3. Сортировка и поиск”
Н. Вирт “Алгоритмы и структуры данных”
А. Ахо “Структуры данных и алгоритмы”
Род Стивенс Алгоритмы. Теория и практическое применение
Дж. Клейнберг “Алгоритмы. Разработка и применение”
А. Бхаргава “Грокаем алгоритмы. Иллюстированное пособие для программистов и любопытствующих”

Т. Кормен  “Алгоритмы: построение и анализ”

Часть I. Основы 
Глава 1. Роль алгоритмов в вычислениях
Глава 2. Приступаем к изучению
Глава 3. Рост функций
Глава 4. Рекуррентные соотношения
Глава 5. Вероятностный анализ и рандомизированные алгоритмы

Часть II. Сортировка и порядковая статистика 
Глава 6. Пирамидальная сортировка
Глава 7. Быстрая сортировка
Глава 8. Сортировка за линейное время
Глава 9. Медианы и порядковые статистики

Часть III. Структуры данных 
Глава 10. Элементарные структуры данных
Глава 11. Хеш-таблицы
Глава 12. Бинарные деревья поиска
Глава 13. Красно-черные деревья
Глава 14. Расширение структур данных

Часть IV. Усовершенствованные методы разработки и анализа 
Глава 15. Динамическое программирование
Глава 16. Жадные алгоритмы
Глава 17. Амортизационный анализ

Часть V. Сложные структуры данных 
Глава 18. B-деревья
Глава 19. Биномиальные пирамиды
Глава 20. Фибоначчиевы пирамиды
Глава 21. Структуры данных для непересекающихся множеств

Часть VI. Алгоритмы для работы с графами 
Глава 22. Элементарные алгоритмы для работы с графами
Глава 23. Минимальные остовные деревья
Глава 24. Кратчайшие пути из одной вершины
Глава 25. Кратчайшие пути между всеми парами вершин
Глава 26. Задача о максимальном потоке

Часть VII. Избранные темы 
Глава 27. Сортирующие сети
Глава 28. Работа с матрицами
Глава 29. Линейное программирование
Глава 30. Полиномы и быстрое преобразование фурье
Глава 31. Теоретико-числовые алгоритмы
Глава 32. Поиск подстрок
Глава 33. Вычислительная геометрия
Глава 34. Np-полнота
Глава 35. Приближенные алгоритмы

Часть VIII. Приложения: математические основы 
Приложение А. Ряды
Приложение Б. Множества и прочие художества
Приложение В. Комбинаторика и теория вероятности
Библиография
Предметный указатель

Г. Уоррен “Алгоритмические трюки для программистов”

Глава 1. Введение
Глава 2. Основы
Глава 3. Округление к степени
Глава 4. Арифметические границы
Глава 5. Подсчет битов
Глава 6. Поиск в слове
Глава 7. Перестановка битов и байтов
Глава 8. Умножение
Глава 9. Целочисленное деление
Глава 10. Целое деление на константы
Глава 11. Некоторые элементарные функции
Глава 12. Системы счисления с необычными основаниями
Глава 13. Код грея
Глава 14. Циклический избыточный код
Глава 15. Коды с коррекцией ошибок
Глава 16. Кривая гильберта
Глава 17. Числа с плавающей точкой
Глава 18. Формулы для простых чисел

Р. Седжвик “Алгоритмы на C++. Фундаментальные алгоритмы и структуры данных”

Часть I. Анализ
Глава 1. Введение
Глава 2. Принципы анализа алгоритмов

Часть II. Структуры данных
Глава 3. Элементарные структуры данных
Глава 4. Абстрактные типы данных
Глава 5. Рекурсия и деревья

Часть III. Сортировка
Глава 6. Элементарные методы сортировки
Глава 7. Быстрая сортировка
Глава 8. Слияние и сортировка слиянием
Глава 9. Очереди с приоритетами и пирамидальная сортировка
Глава 10. Поразрядная сортировка
Глава 11. Специальные методы сортировки

Часть IV. Поиск
Глава 12. Таблицы символов и деревья бинарного поиска
Глава 13. Сбалансированные деревья
Глава 14. Хеширование
Глава 15. Поразрядный поиск
Глава 16. Внешний поиск

Часть V. Алгоритмы на графах
Глава 17. Виды графов и их свойства
Глава 18. Поиск на графе
Глава 19. Орграфы и DAG-графы
Глава 20. Минимальные остовные деревья
Глава 21. Кратчайшие пути
Глава 22. Потоки в сетях

А. Ахо “Структуры данных и алгоритмы”

Род Стивенс Алгоритмы. Теория и практическое применение

Дж. Клейнберг “Алгоритмы. Разработка и применение”

Предисловие 17
Общие сведения 18
Учебные аспекты и дополнения 19
Краткое содержание 20
Как пользоваться книгой 22
Благодарности 24
Глава 1 Введение: некоторые типичные задачи 
1.1 Первая задача: устойчивые паросочетания 27
Задача 27
Проектирование алгоритма 32
Расширения 35
1.2 Пять типичных задач 39
Интервальное планирование 40
Взвешенное интервальное планирование 41
Двудольные паросочетания 41
Независимое множество 43
Задача конкурентного размещения 45
Упражнения с решениями 46
Упражнение с решением 1 46
Упражнение с решением 2 47
Упражнения 50
Примечания и дополнительная литература 55
Глава 2 Основы анализа алгоритмов 
2.1 Вычислительная разрешимость 56
Первые попытки определения эффективности 57
Худшее время выполнения и поиск методом «грубой силы» 58
Полиномиальное время как показатель эффективности 60
2.2 Асимптотический порядок роста 62
O, Ω и Θ 63
Свойства асимптотических скоростей роста 66
Асимптотические границы для некоторых
распространенных функций 67
2.3 Реализация алгоритма устойчивых паросочетаний
со списками и массивами 70
Массивы и списки 71
Реализация алгоритма устойчивых паросочетаний 73
Оглавление 7
2.4 Обзор типичных вариантов времени выполнения 74
Линейное время 75
Время O(n log n) 77
Квадратичное время 78
Кубическое время 79
Время O(nk) 80
За границами полиномиального времени 81
Сублинейное время 82
2.5 Более сложная структура данных: приоритетная очередь 83
Задача 84
Структура данных для реализации приоритетной очереди 85
Реализация операций с кучей 87
Реализация приоритетной очереди на базе кучи 90
Упражнения с решениями 91
Упражнение с решением 1 91
Упражнение с решением 2 92
Упражнения 93
Примечания и дополнительная литература 96
Глава 3 Графы 
3.1 Основные определения и применения 98
3.2 Связность графа и обход графа 103
Поиск в ширину 104
Связная компонента 106
Поиск в глубину 107
Набор всех компонент связности 110
3.3 Реализация перебора графа с использованием очередей и стеков 111
Представление графов 111
Очереди и стеки 113
Реализация поиска в ширину 114
Реализация поиска в глубину 116
Определение всех компонент связности 117
3.4 Проверка двудольности: практическое применение поиска в ширину 118
Задача 118
Проектирование алгоритма 119
Анализ алгоритма 119
3.5 Связность в направленных графах 121
Представление направленных графов 121
Алгоритмы поиска 121
Сильная связность 122
3.6 Направленные ациклические графы и топологическое упорядочение 123
Задача 124
Проектирование и анализ алгоритма 126
Упражнения с решениями 128
Упражнение с решением 1 128
Упражнение с решением 2 129
Упражнения 131
Примечания и дополнительная литература 136

Глава 4 Жадные алгоритмы 
4.1 Интервальное планирование: жадный алгоритм опережает 138
Проектирование жадного алгоритма 138
Анализ алгоритма 141
Расширения 143
Взаимосвязанная задача: планирование всех интервалов 143
4.2 Планирование для минимизации задержки: метод замены 147
Задача 147
Проектирование алгоритма 148
Анализ алгоритма 149
Расширения 152
4.3 Оптимальное кэширование: более сложный пример замены 153
Задача 153
Разработка и анализ алгоритма 154
Расширения: кэширование в реальных рабочих условиях 157
4.4 Кратчайшие пути в графе 158
Задача 158
Разработка алгоритма 159
Анализ алгоритма 160
4.5 Задача нахождения минимального остовного дерева 163
Задача 163
Разработка алгоритма 164
Анализ алгоритмов 165
Реализация алгоритма Прима 170
Расширения 171
4.6 Реализация алгоритма Крускала: структура Union-Find 172
Задача 172
Простая структура данных для структуры Union-Find 173
Усовершенствованная структура данных Union-Find 175
Дальнейшие улучшения 176
Реализация алгоритма Крускала 178
4.7 Кластеризация 179
Задача 179
Разработка алгоритма 180
Анализ алгоритма 181
4.8 Коды Хаффмана и сжатие данных 182
Задача 183
Разработка алгоритма 187
Анализ алгоритма 194
Расширения 196
4.9.* Ориентированные деревья с минимальной стоимостью:
многофазный жадный алгоритм 197
Задача 198
Разработка алгоритма 199
Анализ алгоритма 202
Упражнения с решениями 203
Упражнение с решением 1 203
Упражнение с решением 2 206
Упражнение с решением 3 207
Оглавление 9
Упражнения 209
Примечания и дополнительная литература 224
Глава 5 Разделяй и властвуй
5.1 Первое рекуррентное отношение: алгоритм сортировки слиянием 227
Методы разрешения рекуррентности 228
Раскрутка рекуррентности в алгоритме сортировки слиянием 229
Подстановка решения в рекуррентное отношение сортировки
слиянием 230
Использование частичной подстановки 230
5.2 Другие рекуррентные отношения 231
Случай q > 2 подзадач 232
Случай одной подзадачи 234
Похожее рекуррентное отношение: T(n) ≤ 2T(n/2) + O(n2) 236
5.3 Подсчет инверсий 238
Задача 238
Разработка и анализ алгоритма 239
5.4 Поиск ближайшей пары точек 242
Задача 242
Разработка алгоритма 242
Анализ алгоритма 247
5.5 Целочисленное умножение 248
Задача 248
Разработка алгоритма 248
Анализ алгоритма 250
5.6 Свертки и быстрое преобразование Фурье 250
Задача 250
Разработка и анализа алгоритма 254
Упражнения с решениями 258
Упражнение с решением 1 258
Упражнение с решением 2 260
Упражнения 262
Примечания и дополнительная литература 265
Глава 6 Динамическое программирование 
6.1 Взвешенное интервальное планирование: рекурсивная процедура 267
Разработка рекурсивного алгоритма 267
Мемоизация рекурсии 271
Анализ мемоизированной версии 271
Вычисление решения помимо его значения 272
6.2 Принципы динамического программирования: мемоизация
или итерации с подзадачами 272
Разработка алгоритма 273
Анализ алгоритма 273
Основная схема динамического программирования 274
6.3 Сегментированные наименьшие квадраты: многовариантный выбор 275
Задача 276
Разработка алгоритма 278
Анализ алгоритма 280
6.4 Задача о сумме подмножеств и задача о рюкзаке:
добавление переменной 281
Задача 281
Разработка алгоритма 282
Анализ алгоритма 284
6.5 Вторичная структура РНК: динамическое программирование
по интервалам 286
Задача 287
Разработка и анализ алгоритма 289
6.6 Выравнивание последовательностей 291
Задача 291
Разработка алгоритма 294
Анализ алгоритма 296
6.7 Выравнивание последовательностей в линейном пространстве
по принципу «разделяй и властвуй» 297
Задача 298
Разработка алгоритма 298
Анализ алгоритма 302
6.8 Кратчайшие пути в графе 303
Задача 303
Разработка и анализ алгоритма 305
Расширения: основные усовершенствования алгоритма 308
6.9 Кратчайшие пути и дистанционно-векторные протоколы 311
Недостатки дистанционно-векторного протокола 313
6.10 Отрицательные циклы в графе 315
Задача 315
Разработка и анализ алгоритма 316
Расширения: улучшенные алгоритмы нахождения кратчайшего
пути и отрицательного цикла 317
Упражнения с решениями 320
Упражнение с решением 1 320
Упражнение с решением 2 322
Упражнения 325
Примечания и дополнительная литература 345
Глава 7 Нахождение потока в сети 
7.1 Задача о максимальном потоке и алгоритм Форда–Фалкерсона 348
Разработка алгоритма 351
Анализ алгоритма: завершение и время выполнения 355
7.2 Максимальные потоки и минимальные разрезы 356
Анализ алгоритма: потоки и разрезы 356
Анализ алгоритма: максимальный поток равен
минимальному разрезу 358
Дальнейший анализ: целочисленные потоки 360
7.3 Выбор хороших увеличивающих путей 362
Разработка ускоренного алгоритма потока 362
Анализ алгоритма 364
Расширения: сильные полиномиальные алгоритмы 366
7.4.* Алгоритм проталкивания предпотока 367
Разработка алгоритма 367
Анализ алгоритма 370
Расширения: улучшенная версия алгоритма 374
Реализация алгоритма проталкивания предпотока 375
7.5 Первое применение: задача о двудольном паросочетании 377
Задача 377
Разработка алгоритма 377
Анализ алгоритма 378
Расширения: структура двудольных графов
без идеального паросочетания 380
7.6 Непересекающиеся пути в направленных и ненаправленных графах 383
Задача 383
Разработка алгоритма 383
Анализ алгоритма 384
Расширения: непересекающиеся пути в ненаправленных графах 387
7.7 Расширения задачи о максимальном потоке 388
Задача: циркуляция с потреблением 388
Разработка и анализ алгоритма для циркуляций 390
Задача: циркуляция с потреблением и нижние границы 392
Разработка и анализ алгоритма с нижними границами 392
7.8 Планирование опроса 394
Задача 395
Разработка алгоритма 396
Анализ алгоритма 396
7.9 Планирование авиаперелетов 397
Задача 397
Разработка алгоритма 399
Анализ алгоритма 400
Расширения: моделирование других аспектов задачи 400
7.10 Сегментация изображений 401
Задача 401
Разработка и анализ алгоритма 403
7.11 Выбор проекта 405
Задача 406
Разработка алгоритма 406
Анализ алгоритма 407
7.12 Выбывание в бейсболе 409
Задача 410
Разработка и анализ алгоритма 411
Характеристика выбывания команды 413
7.13.* Добавление стоимостей в задачу паросочетаний 414
Задача 414
Разработка и анализ алгоритма 415
Расширения: экономическая интерпретация цен 419
Упражнения с решениями 420
Упражнение с решением 1 420
Упражнение с решением 2 421
Упражнения 424
Примечания и дополнительная литература 456
Глава 8 NP-полнота и вычислительная неразрешимость 
8.1 Полиномиальное сведение 459
Первое сведение: независимое множество и вершинное покрытие 461
Сведение к более общему случаю: вершинное покрытие
к покрытию множества 463
8.2 Сведение с применением «регуляторов»: задача выполнимости 466
Задачи SAT и 3-SAT 466
Сведение задачи 3-SAT к задаче о независимом множестве 467
Транзитивность сведения 469
8.3 Эффективная сертификация и определение NP 470
Задачи и алгоритмы 470
Эффективная сертификация 471
NP: класс задач 471
8.4 NP-полные задачи 473
Выполнимость булевой схемы: первая NP-полная задача 473
Пример 475
Доказательство NP-полноты других задач 476
Общая стратегия доказательства NP-полноты новых задач 479
8.5 Задачи упорядочения 480
Задача коммивояжера 480
Задача о гамильтоновом цикле 481
Доказательство NP-полноты задачи о гамильтоновом цикле 482
Доказательство NP-полноты задачи коммивояжера 485
Расширения: задача о гамильтоновом пути 486
8.6 Задачи о разбиении 487
Задача о трехмерном сочетании 487
Доказательство NP-полноты трехмерного сочетания 488
8.7 Задача о раскраске графа 492
Задача о раскраске графа 492
Вычислительная сложность задачи о раскраске графа 493
Доказательство NP-полноты задачи о 3-раскраске 494
Заключение: о проверке гипотезы четырех цветов 497
8.8 Численные задачи 497
Задача о суммировании подмножеств 497
Доказательство NP-полноты задачи о суммировании подмножеств 498
Расширения: сложность некоторых задач планирования 500
Внимание: суммирование подмножеств с полиномиально
ограничиваемыми числами 501
8.9 Co-NP и асимметрия NP 502
Хорошая характеризация: класс NPҏco-NP 503
8.10 Частичная классификация сложных задач 504
Задачи упаковки 505
Задачи покрытия 505
Задачи разбиения 505
Задачи упорядочения 506
Численные задачи 506
Задачи соблюдения ограничений 507
Упражнения с решениями 507
Упражнение с решением 1 507
Упражнение с решением 2 509
Упражнения 511
Примечания и дополнительная литература 532
Глава 9 PSPACE: класс задач за пределамиNP 
9.1 PSPACE 534
9.2 Некоторые сложные задачи из PSPACE 536
Задачи построения плана 536
Кванторы 537
Игры 538
9.3 Решение задач с кванторами и игровых задач в полиномиальном
пространстве 539
Разработка алгоритма для QSAT 539
Анализ алгоритма 540
Расширения: алгоритм для задачи конкурентного размещения 540
9.4 Решение задачи построения плана с полиномиальным пространством 541
Задача 541
Разработка алгоритма 543
Анализ алгоритма 545
9.5 Доказательство PSPACE-полноты задач 546
Связь задач с кванторами с игровыми задачами 546
Доказательство PSPACE-полноты задачи конкурентного
размещения 547
Упражнения с решениями 549
Упражнение с решением 1 549
Упражнения 552
Примечания и дополнительная литература 553
Глава 10 Расширение пределов разрешимости 
10.1 Поиск малых вершинных покрытий 556
Задача 557
Разработка алгоритма 557
Анализ алгоритма 559
10.2 Решение NP-сложных задач для деревьев 559
Жадный алгоритм для задачи о независимом множестве
для деревьев 560
Независимое множество с максимальным весом для деревьев 562
10.3 Раскраска множества дуг 564
Задача 564
Разработка алгоритма 567
Анализ алгоритма 572
10.4.* Декомпозиция графа в дерево 573
Определение древовидной ширины 574
Свойства декомпозиции 576
Динамическое программирование и древовидная декомпозиция 580
10.5.* Построение древовидной декомпозиции 584
Задача 585
Разработка и анализ алгоритма 585
Упражнения с решениями 591
Упражнение с решением 1 591
14 Оглавление
Упражнения 594
Примечания и дополнительная литература 598
Глава 11 Аппроксимирующие алгоритмы 
11.1 Жадные алгоритмы и ограничения оптимума:
задача распределения нагрузки 600
Задача 600
Разработка алгоритма 600
Анализ алгоритма 601
Расширения: улучшенный аппроксимирующий алгоритм 604
11.2 Задача о выборе центров 605
Задача 605
Разработка и анализ алгоритма 606
11.3 Покрытие множества: обобщенная жадная эвристика 611
Задача 611
Разработка алгоритма 612
Анализ алгоритма 612
11.4 Метод назначения цены: вершинное покрытие 616
Задача 617
Разработка алгоритма: метод назначения цены 618
Анализ алгоритма 621
11.5 Максимизация методом назначения цены:
задача о непересекающихся путях 622
Задача 622
Разработка и анализ жадного алгоритма 624
Разработка и анализ алгоритма назначения цены 626
11.6 Линейное программирование и округление: применение к задаче
о вершинном покрытии 629
Линейное программирование как обобщенный метод 629
Задача о вершинном покрытии как целочисленная программа 632
Использование линейного программирования для задачи
вершинного покрытия 634
11.7.* Снова о распределении нагрузки: более сложное применение LP 635
Задача 636
Разработка и анализ алгоритма 637
11.8 Аппроксимации с произвольной точностью: задача о рюкзаке 642
Задача 643
Разработка алгоритма 644
Анализ алгоритма 645
Новый алгоритм динамического программирования для задачи
о рюкзаке 646
Упражнения с решениями 648
Упражнение с решением 1 648
Решение 648
Упражнения 649
Примечания и дополнительная литература 657
Глава 12 Локальный поиск
12.1 Задача оптимизации в перспективе 660
Потенциальная энергия 660
Связь с оптимизацией 662
Локальный поиск в задаче о вершинном покрытии 663
12.2 Алгоритм Метрополиса и имитация отжига 665
Алгоритм Метрополиса 665
Имитация отжига 667
12.3 Применение локального поиска в нейронных сетях Хопфилда 669
Задача 669
Разработка алгоритма 670
Анализ алгоритма 671
12.4 Аппроксимация задачи о максимальном разрезе
с применением локального поиска 674
Задача 674
Разработка алгоритма 675
Анализ алгоритма 675
12.5Выбор соседского отношения 677
Алгоритмы локального поиска при разбиении графов 678
12.6.* Классификация на базе локального поиска 679
Задача 680
Разработка алгоритма 681
Анализ алгоритма 686
12.7 Динамика наилучших ответов и равновесия Нэша 688
Задача 688
Динамика наилучших ответов и равновесия Нэша:
определения и примеры 689
Связь с локальным поиском 691
Два основных вопроса 693
Поиск хорошего равновесия Нэша 694
Упражнения с решениями 698
Упражнение с решением 1 698
Упражнения 700
Примечания и дополнительная литература 703
Глава 13 Рандомизированные алгоритмы 
13.1 Первое применение: разрешение конфликтов 705
Задача 706
Разработка рандомизированного алгоритма 706
Анализ алгоритма 706
13.2 Нахождение глобального минимального разреза 711
Задача 711
Разработка алгоритма 712
Анализ алгоритма 713
Дальнейший анализ: количество глобальных
минимальных разрезов 715
13.3 Случайные переменные и ожидания 716
Пример: ожидание первого успеха 717
Линейность ожидания 717
Пример: угадывание карт 718
Пример: сбор купонов 719
Последнее определение: условное ожидание 721
13.4 Рандомизированный аппроксимирующий алгоритм
для задачи MAX 3-SAT 721
Задача 721
Разработка и анализ алгоритма 722
Дальнейший анализ: поиск хорошего присваивания 723
13.5 Рандомизация принципа ««разделяй и властвуй»:
нахождение медианы и быстрая сортировка 725
Задача: нахождение медианы 725
Разработка алгоритма 725
Анализ алгоритма 728
Второй пример: быстрая сортировка 729
13.6 Хеширование: рандомизированная реализация словарей 731
Задача 732
Разработка структуры данных 733
Универсальные классы хеш-функций 735
Анализ структуры данных 737
13.7 Нахождение ближайшей пары точек: рандомизированный метод 738
Задача 739
Разработка алгоритма 740
Описание алгоритма 743
Анализ алгоритма 743
13.8 Рандомизация кэширования 747
Задача 747
Разработка класса алгоритмом маркировки 748
Анализ алгоритмов маркировки 749
Разработка рандомизированного алгоритма маркировки 751
Анализ рандомизированного алгоритма маркировки 752
13.9 Границы Чернова 754
13.10 Распределение нагрузки 756
Задача 756
Анализ случайного распределения заданий 757
13.11 Маршрутизация пакетов 759
Задача 759
Разработка алгоритма 762
Анализ алгоритма 763
13.12 Основные вероятностные определения 765
Конечные вероятностные пространства 765
Условная вероятность и независимость 767
Бесконечные пространства выборки 770
Упражнения с решениями 772
Упражнение с решением 1 772
Упражнение с решением 2 775
Упражнения 778
Примечания и дополнительная литература 789
Эпилог: алгоритмы, которые работают бесконечно 791
Задача 792
Разработка алгоритма 795
Анализ алгоритма 799
Об авторах 800

А. Бхаргава “Грокаем алгоритмы. Иллюстированное пособие для программистов и любопытствующих”

Предисловие 11
Благодарности 12
О книге 14
Структура книги 15
Как работать с этой книгой 16
Для кого предназначена эта книга 16
Условные обозначения и загружаемые материалы 17
Об авторе 17
От издательства 17
Глава 1 Знакомство с алгоритмами 
Введение 18
Что вы узнаете об эффективности алгоритмов 19
Что вы узнаете о решении задач 19
Бинарный поиск 20
Более эффективный поиск 23
Упражнения 27
Время выполнения 28
«O-большое» 29
Время выполнения алгоритмов растет с разной скоростью 29
Наглядное представление «O-большое» 32
«O-большое» определяет время выполнения в худшем случае 34
Типичные примеры «O-большого» 35
Упражнения 36
Задача о коммивояжере 37
Шпаргалка 39
Глава 2 Сортировка выбором 
Как работает память 41
Массивы и связанные списки 43
Связанные списки 45
Массивы 46
Терминология 47
Упражнения 48
Вставка в середину списка 49
Удаление 50
Упражнения 51
Сортировка выбором 53
Пример кода 57
Шпаргалка 58
Глава 3 Рекурсия 
Рекурсия 60
Базовый случай и рекурсивный случай 63
Стек 65
Стек вызовов 66
Упражнения 68
Стек вызовов с рекурсией 69
Упражнения 73
Шпаргалка 74
Глава 4 Быстрая сортировка 
«Разделяй и властвуй» 76
Упражнения 85
Быстрая сортировка 85
Снова об «O-большом» 92
Сортировка слиянием и быстрая сортировка 93
Средний и худший случай 95
Упражнения 99
Шпаргалка 99
Оглавление  7
Глава 5 Хеш-таблицы 
Хеш-функции 103
Упражнения 107
Примеры использования 107
Использование хеш-таблиц для поиска 108
Исключение дубликатов 110
Использование хеш-таблицы как кэша 112
Шпаргалка 116
Коллизии 116
Быстродействие 119
Коэффициент заполнения 122
Хорошая хеш-функция 124
Упражнения 125
Шпаргалка 126
Глава 6 Поиск в ширину 
Знакомство с графами 128
Что такое граф? 131
Поиск в ширину 132
Поиск кратчайшего пути 135
Очереди 136
Упражнения 137
Реализация графа 138
Реализация алгоритма 141
Время выполнения 146
Упражнения 147
Шпаргалка 150
Глава 7 Алгоритм Дейкстры 
Работа с алгоритмом Дейкстры 152
Терминология 157
История одного обмена 160
Ребра с отрицательным весом 167
Реализация 170
Упражнения 181
Шпаргалка 181
Глава 8 Жадные алгоритмы 
Задача составления расписания 183
Задача о рюкзаке 185
Упражнения 187
Задача о покрытии множества 187
Приближенные алгоритмы 189
Упражнения 196
NP-полные задачи 196
Задача о коммивояжере — шаг за шагом 197
Как определить, что задача является NP-полной? 202
Упражнения 205
Шпаргалка 205
Глава 9 Динамическое программирование 
Задача о рюкзаке 206
Простое решение 207
Динамическое программирование 208
Задача о рюкзаке: вопросы 217
Что произойдет при добавлении элемента? 217
Упражнения 220
Что произойдет при изменении порядка строк? 220
Можно ли заполнять таблицу по столбцам, а не по строкам? 221
Что произойдет при добавлении меньшего элемента? 221
Можно ли взять часть предмета? 221
Оптимизация туристического маршрута 223
Взаимозависимые элементы 224
Может ли оказаться, что решение требует более двух «подрюкзаков»? 225
Возможно ли, что при лучшем решении в рюкзаке остается пустое место? 226
Упражнения 226
Самая длинная общая подстрока 226
Построение таблицы 228
Заполнение таблицы 229
Решение 230
Самая длинная общая подпоследовательность 232
Самая длинная общая подпоследовательность — решение 233
Упражнения 235
Шпаргалка 235
Глава 10 Алгоритм k ближайших соседей 
Апельсины и грейпфруты 236
Построение рекомендательной системы 239
Извлечение признаков 240
Упражнения 245
Регрессия 245
Выбор признаков 248
Упражнения 249
Знакомство с машинным обучением 249
OCR 250
Построение спам-фильтра 251
Прогнозы на биржевых торгах 252
Шпаргалка 252
Глава 11 Что дальше? 
Деревья 254
Инвертированные индексы 258
Преобразование Фурье 259
Параллельные алгоритмы 260
MapReduce 261
Для чего нужны распределенные алгоритмы? 261
Функция map 261
Функция reduce 262
Фильтры Блума и HyperLogLog 263
Фильтры Блума 265
HyperLogLog 265
Алгоритмы SHA 266
Сравнение файлов 267
Проверка паролей 268
Локально-чувствительное хеширование 269
Обмен ключами Диффи—Хеллмана 270
Линейное программирование 272
Эпилог 273
Ответы к упражнениям 274