Девять алгоритмов, которые изменили будущее

Глава 1. Введение: необычные идеи,
каждодневно используемые в компьютерах
Алгоритмы - чародейство услужливого джинна
Какой алгоритм считать великим?
А какое нам, собственно, дело до великих
алгоритмов?
Глава 2. Индексирование в поисковых системах:
поиск иголки в самом большом в мире стоге сена
Сопоставление и ранжирование
AltaVista: первый алгоритм сопоставления
масштаба веб
Старое доброе индексирование
Трюке позициями слов
Ранжирование и близость
Трюк с метасловами
Трюки индексирования и сопоставления - это еще
не все
Глава 3. PageRank: технология, породившая
Google
Трюк с гиперссылками
Трюк с авторитетностью
Трюк со случайным посетителем
Алгоритм PageRank на практике
Глава 4. Криптография с открытым ключом:
отправка
секретов почтовой открыткой
Шифрование с помощью общего секрета
Открытая выработка общего секрета
Трюк со смешиванием красок
Числа вместо красок
Смешивание красок в реальной жизни
Криптография с открытым ключом на практике
Глава 5. Коды, исправляющие ошибки: ошибки,
которые исправляются сами собой
Нужда в обнаружении и исправлении ошибок
Трюке повторением
Трюк с избыточностью
Трюк с контрольной суммой
Трюк с указкой
Обнаружение и исправление ошибок в реальном
мире
Глава 6. Распознавание образов: обучение на
опыте
В чем состоит задача?
Трюке ближайшими соседями
Различные виды "ближайших" соседей
Трюк с двадцатью вопросами: деревья решений
Нейронные сети
Биологические нейронные сети
Нейронная сеть для задачи о зонтике
Нейронная сеть для задачи о солнечных очках
Добавление взвешенных сигналов
Настройка нейронной сети посредством обучения
Использование сети для задачи о солнечных очках
Распознавание образов: прошлое, настоящее и
будущее
Глава 7. Сжатие данных: кое-что задаром,
Сжатие без потери информации: бесплатный сыр
бывает не только в мышеловке
Трюк "то же, что и раньше"
Трюк "более короткий символ"
Резюме: откуда берется бесплатный сыр?
Сжатие с потерей информации: не бесплатный
сыр, но отличная сделка
Трюк с пропуском
Истоки алгоритмов сжатия
Глава 8. Базы данных: в поисках
непротиворечивости
Транзакции и трюк со списком дел
Трюк со списком дел
Атомарность в большом и в малом
Трюк "подготовить и зафиксировать" для
реплицированных
баз данных
Реплицированные базы данных
Откат транзакций
Трюк "подготовить и зафиксировать"
Реляционные базы данных и трюк с виртуальной
таблицей
Ключи
Трюк с виртуальной таблицей
Реляционные базы данных
Базы данных с точки зрения человека
Глава 9. Цифровые подписи: кто на самом деле
написал эту программу?
Для чего в действительности применяются
цифровые подписи?
Рукописные подписи
Подписание с помощью замка
Подписание с помощью перемножающего замка
Подписание степенным замком
Безопасность RSA
Связь между RSAM разложением на множители
Связь между RSAn квантовыми компьютерами
Цифровые подписи на практике
Парадокс разрешен
Глава 10. Что можно вычислить?
Ошибки, сбои и надежность программ
Доказательство ложности чего-либо
Программы, анализирующие другие программы
Некоторые программы невозможны
Простые программы да-нет
AlwaysYes.exe: программа да-нет, анализирующая
другие программы
YesOnSelf.exe: упрощенный вариант AlwaysYes.exe
AntiYesOnSelf.exe: противоположность
YesOnSelf.exe
Невозможность обнаружения сбоев
Проблема остановки и неразрешимость
Что следует из невозможности некоторых
программ?
Неразрешимость и использование компьютеров
Неразрешимость и мозг
Глава 11. Послесловие: еще один услужливый
джинн?
О некоторых потенциально великих алгоритмах
Могут ли великие алгоритмы уйти в тень?
Чему мы научились?
Конец пути
Благодарности
Источники и литература для дальнейшего чтения
Предметный указатель