Занимательные алгоритмы: чему нас учат истории знаменитых героев
Г-н ЖУРДЕН. Честное слово, я и не подозревал, что вот уже более сорока лет говорю прозой.
— Жан-Батист Мольер, "Мещанин во дворянстве"
Вы всегда считали, что алгоритм — это что-то из мира неопрятных хакеров, освещенных экранами в полутемных помещениях, забитых компьютерами? Что это нечто "не от мира сего", для обычного человека находящееся за гранью понимания?
Вы непростительно ошибаетесь. Вероятно, это одно из наибольших заблуждений нашего времени — особенно непонятное в свете того, что человечество давно и основательно знакомо с алгоритмами. Прочтя эту книгу, вы в этом убедитесь.
В книге применен необычный подход к изложению алгоритмов — с использованием литературных произведений и фильмов. Вы никогда не задумывались о том, что Гензель и Гретель, возвращаясь домой по цепочке камешков, используют простой алгоритм с линейным временем работы? Что Шерлок Холмс, расследуя очередное дело, имеет дело со структурами данных — списком подозреваемых, родословным деревом, очередью с приоритетами наследников жертвы? Что Индиане Джонсу неоднократно приходится иметь дело с сортировкой и поиском? Что события в фильме День Сурка, по сути, являются циклом, а в Назад в будущее — рекурсией?
Перед вами книга по основам информатики и алгоримов — но книга, в которой для иллюстрации тех или иных концепций используются такие знакомые большинству из нас литературные произведения и фильмы, что делает и без того увлекательную тему информатики, алгоритмов и вычислений еще более интересной и увлекательной.
Предисловие 11
Часть I. Алгоритмы 27
Глава 1. Путь к пониманию вычислений 33
Глава 2. От слов к делу: когда действительно происходит вычисление 47
Глава 3. Тайна знаков 65
Глава 4. Записная книжка сыщика 81
Глава 5. Поиск идеальной структуры данных 103
Глава 6. Сортировка алгоритмов сортировки 127
Глава 7. Трудноразрешимые задачи 147
Часть II. Языки 163
Глава 8. Сквозь призму языка 169
Глава 9. Поиск нужного тона: смысл звука 187
Глава 10. Намылить, смыть, повторить 203
Глава 11. Счастливый конец не гарантируется 219
Глава 12. Своевременный стежок вычисляется впрок 237
Глава 13. Все дело в интерпретации 259
Глава 14. Волшебный тип 279
Глава 15. С высоты птичьего полета: от абстракции к деталям 299
Приложение А. Словарь специальных терминов 323
Приложение Б. Примечания 339
Предметный указатель 349