Предисловие 9
1. Разница курсов акций 19
1.1. Алгоритмы 22
1.2. Время выполнения работы и сложность 27
1.3. Используем стек для разницы курсов акций 36
Примечания 44
Упражнения 45
2. Исследуя лабиринты 47
2.1. Графы 49
2.2. Представление графов 55
2.3. Обход графа в глубину 64
2.4. Поиск в ширину 76
Примечания 82
Упражнения 83
3. Сжатие 86
3.1. Сжатие 90
3.2. Деревья и очереди с приоритетом 94
3.3. Код Хаффмана 97
3.4. Сжатие Лемпеля — Зива — Велча 107
Примечания 122
Упражнения 123
4. Секреты 126
4.1. Попробуйте расшифровать 127
4.2. Шифрование одноразовым ключом, или одноразовый блокнот 133
4.3. AES-шифрование 138
4.4. Обмен ключами по методу Диффи — Хеллмана 148
4.5. Быстрое возведение в степень и возведение в степень по модулю 153
Примечания 159
Упражнения 161
5. Делимся секретами 162
5.1. Шифрование с открытым ключом 163
5.2. Криптосистема RSA 167
5.3. Хеширование сообщения 179
5.4. Анонимизация интернет-трафика 180
Примечания 188
Упражнения 189
6. Все по порядку 190
6.1. Топологическая сортировка 192
6.2. Взвешенные графы 198
6.3. Критические пути 200
Примечания 209
Упражнения 210
7. Строки, абзацы, пути 211
7.1. Кратчайшие пути 215
7.2. Алгоритм Дейкстры 218
Примечания 227
Упражнения 229
8. Маршрутизация, арбитраж 230
8.1. Маршрутизация Интернета 235
8.2. Алгоритм Беллмана — Форда (— Мура) 241
8.3. Отрицательные веса и циклы 249
8.4. Арбитраж 253
Примечания 258
9. Что важнее всего 259
9.1. Суть пейдж-ранка 260
9.2. Матрица гиперссылок 262
9.3. Степенной метод 265
9.4. Матрица «Гугла» 270
Примечания 275
10. Прочность голосования 276
10.1. Система голосования 277
10.2. Метод Шульце 281
10.3. Алгоритм Флойда — Уоршелла 295
Примечания 297
11. Методы перебора, невесты и дихотомии 298
11.1. Последовательный поиск 299
11.2. Соответствие, сравнение, записи, ключи 301
11.3. Эффект Матфея и степенные законы 304
11.4. Самоорганизующийся поиск 311
11.5. Задача о разборчивой невесте 316
11.6. Бинарный поиск 320
11.7. Представление целых чисел на компьютере 325
11.8. И снова к бинарному поиску 331
11.9. Деревья сравнений 333
Примечания 339
12. Сортировочный компот 342
12.1. Сортировка методом выбора 343
12.2. Сортировка методом вставок 348
12.3. Сортировка кучей 354
12.4. Сортировка слиянием 364
12.5. Быстрая сортировка 377
12.6. Богатство выбора 386
Примечания 390
Упражнения 390
13. Гардероб, коллизия и слот 393
13.1. Соотнесение ключей и значений 394
13.2. Хеширование 399
13.3. Функции хеширования 402
13.4. Представление чисел с плавающей запятой и хеширование 411
13.5. Коллизии 415
13.6. Цифровые отпечатки 426
13.7. Фильтры Блума 431
Примечания 445
Упражнения 447
14. Биты и деревья 449
14.1. Предсказание как проблема коммуникации 450
14.2. Информация и энтропия 453
14.3. Классификация 460
14.4. Деревья решений 463
14.5. Выбор атрибутов 468
14.6. Алгоритм ID3 474
14.7. Основные принципы работы 482
14.8. Бритва Оккама 490
14.9. Затраты, проблемы, улучшения 492
Примечания 496
Упражнения 498
15. Немного построчим 500
15.1. Сравнение строк перебором 504
15.2. Алгоритм Кнута — Морриса — Пратта 507
15.3. Алгоритм Бойера — Мура — Хорспула 520
Примечания 529
Упражнения 530
16. Предоставим дело случаю 532
16.1. Случайные числа 535
16.2. Случайная выборка 545
16.3. Борьба за власть 553
16.4. В поисках простых чисел 566
Примечания 577
Упражнения 579
Библиография 581
Предметный указатель 595