Девять алгоритмов, которые изменили мир : остроумные идеи, лежащие в основе современных компьютеров

Содержание книги "Девять алгоритмов, которые изменили мир : остроумные идеи, лежащие в основе современных компьютеров"

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