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

Джон Маккормик

ДЕВЯТЬ
АЛГОРИТМОВ,
которые изменили 
мир

Остроумные идеи, лежащие в основе 
современных компьютеров

Nine Algorithms That 
Changed the Future

The Ingenious Ideas That 
Drive Today’s Computers

John MacCormick

with a foreword by Chris Bishop

P R I N C E T O N  U N I V E R S I T Y  P R E S S

P R I N C E T O N  A N D  O X F O R D

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

Остроумные идеи, лежащие в основе 
современных компьютеров

Джон Маккормик

с предисловием Криса Бишопа

Москва, 2023

2-е издание, электронное

УДК 004
ББК 32.97
М15

М15
Маккормик, Джон.
Девять алгоритмов, которые изменили мир. Остроумные идеи, лежащие 
в основе современных компьютеров / Дж. Маккормик ; пер. с англ. А. А. Слин-
кина. — 2-е изд., эл. — 1 файл pdf : 237 с. — Москва : ДМК Пресс, 2023. — 
Систем. требования: Adobe Reader XI либо Adobe Digital Editions 4.5 ; 
экран 10". — Текст : электронный.
ISBN 978-5-89818-568-8

Ежедневно мы используем впечатляющие технологические достижения, даже не 
задумываясь об этом. Мы передаем по сети гигабайты информации, просматриваем 
тысячи документов в поисках необходимого, совершаем покупки в интернет-магазинах. 
Мы архивируем объемные материалы, так чтобы их можно было отправить 
по электронной почте, и пользуемся искусственным интеллектом компьютеров, которые 
автоматически исправляют опечатки в тексте, ретушируют фотографии и 
делают за нас многое другое. 
Все это при нынешнем уровне развития технологий воспринимается как должное. 
Но ведь такие «чудеса» были бы невозможны без величайших идей информатики, 
родившихся в XX веке!
Эта книга — о том, как эти идеи зародились и как воплощались в жизнь.
Издание рассчитано на широкую аудиторию. Предварительного знакомства с 
информатикой от читателей не требуется.

УДК 004 
ББК 32.97

Электронное издание на основе печатного издания: Девять алгоритмов, которые изменили 
мир. Остроумные идеи, лежащие в основе современных компьютеров / Дж. Маккормик ; пер. 
с англ. А. А. Слинкина. — Москва : ДМК Пресс, 2016. — 236 с. — ISBN 978-5-97060-204-1. — 
Текст : непосредственный.

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было 
форме и какими бы то ни было средствами без  письменного разрешения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но поскольку вероятность технических 
ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность 
приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные 
с использованием книги.

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами 
защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации.


ISBN 978-5-89818-568-8
© 2012 by Princeton University Press
©  Оформление, перевод на русский язык 
ДМК Пресс, 2014

Мир созрел до появления дешевых и в то же время сложных, 
и в высшей степени надежных устройств, – что-то должно 
случиться.

— Ванневар Буш 
«Возможный способ нашего мышления», 1945

ОГЛАВЛЕНИЕ

Глава 1. Введение: необычные идеи, каждодневно 
используемые в компьютерах .................................... 11
Алгоритмы – чародейство услужливого джинна ............................. 13
Какой алгоритм считать великим? ................................................. 14
А какое нам, собственно, дело до великих алгоритмов? ................ 19

Глава 2. Индексирование в поисковых системах: 
поиск иголки в самом большом в мире стоге сена ..........21
Сопоставление и ранжирование .................................................... 22
AltaVista: первый алгоритм сопоставления масштаба веб .............. 23
Старое доброе индексирование .................................................... 24
Трюк с позициями слов ................................................................. 26
Ранжирование и близость ............................................................. 29
Трюк с метасловами ...................................................................... 31
Трюки индексирования и сопоставления – это еще не все ...............35

Глава 3. PageRank: технология, породившая Google .......37
Трюк с гиперссылками .................................................................. 38
Трюк с авторитетностью ................................................................ 40
Трюк со случайным посетителем ................................................... 42
Алгоритм PageRank на практике .................................................... 48

Глава 4. Криптография с открытым ключом: отправка 
секретов почтовой открыткой .....................................51
Шифрование с помощью общего секрета ..................................... 53
Открытая выработка общего секрета ............................................ 56
Трюк со смешиванием красок .........................................................56
Числа вместо красок ......................................................................61
Смешивание красок в реальной жизни ...........................................64
Криптография с открытым ключом на практике ............................. 69

Глава 5. Коды, исправляющие ошибки: ошибки, 
которые исправляются сами собой ..............................73
Нужда в обнаружении и исправлении ошибок ............................... 74
Трюк с повторением ...................................................................... 75
Трюк с избыточностью ................................................................... 78
Трюк с контрольной суммой .......................................................... 81

Оглавление

Трюк с указкой ............................................................................... 87
Обнаружение и исправление ошибок в реальном мире ................. 91

Глава 6. Распознавание образов: обучение на опыте ......94
В чем состоит задача? ................................................................... 95
Трюк с ближайшими соседями ...................................................... 98
Различные виды «ближайших» соседей ........................................101
Трюк с двадцатью вопросами: деревья решений ......................... 103
Нейронные сети .......................................................................... 107
Биологические нейронные сети ....................................................108
Нейронная сеть для задачи о зонтике ...........................................109
Нейронная сеть для задачи о солнечных очках ..............................111
Добавление взвешенных сигналов ...............................................113
Настройка нейронной сети посредством обучения .......................114
Использование сети для задачи о солнечных очках ......................117
Распознавание образов: прошлое, настоящее и будущее ........... 118

Глава 7. Сжатие данных: кое-что задаром ...................121
Сжатие без потери информации: бесплатный сыр бывает 
не только в мышеловке ................................................................ 122
Трюк «то же, что и раньше» ...........................................................124
Трюк «более короткий символ» .....................................................126
Резюме: откуда берется бесплатный сыр? ....................................129
Сжатие с потерей информации: не бесплатный сыр, 
но отличная сделка ...................................................................... 131
Трюк с пропуском .........................................................................132
Истоки алгоритмов сжатия .......................................................... 137

Глава 8. Базы данных: в поисках непротиворечивости ..... 139
Транзакции и трюк со списком дел .............................................. 142
Трюк со списком дел .....................................................................146
Атомарность в большом и в малом ...............................................148
Трюк «подготовить и зафиксировать» для реплицированных 
баз данных .................................................................................. 149
Реплицированные базы данных ....................................................149
Откат транзакций .........................................................................151
Трюк «подготовить и зафиксировать» ...........................................154
Реляционные базы данных и трюк с виртуальной таблицей ......... 158
Ключи ...........................................................................................160
Трюк с виртуальной таблицей .......................................................162
Реляционные базы данных ...........................................................164
Базы данных с точки зрения человека ......................................... 165

Глава 9. Цифровые подписи: кто на самом деле 
написал эту программу? ..........................................167
Для чего в действительности применяются цифровые 
подписи? ..................................................................................... 167

Оглавление

Рукописные подписи ................................................................... 169
Подписание с помощью замка .................................................... 171
Подписание с помощью перемножающего замка ........................ 174
Подписание степенным замком .................................................. 181
Безопасность RSA ........................................................................185
Связь между RSA и разложением на множители ...........................186
Связь между RSA и квантовыми компьютерами ............................188
Цифровые подписи на практике .................................................. 189
Парадокс разрешен .................................................................... 191

Глава 10. Что можно вычислить? ...............................192
Ошибки, сбои и надежность программ ........................................ 193
Доказательство ложности чего-либо ........................................... 194
Программы, анализирующие другие программы......................... 196
Некоторые программы невозможны ............................................ 200
Простые программы да–нет .........................................................201
AlwaysYes.exe: программа да–нет, анализирующая другие 
программы ...................................................................................202
YesOnSelf.exe: упрощенный вариант AlwaysYes.exe .......................204
AntiYesOnSelf.exe: противоположность YesOnSelf.exe ....................206
Невозможность обнаружения сбоев ............................................ 210
Проблема остановки и неразрешимость.......................................213
Что следует из невозможности некоторых программ? ................. 214
Неразрешимость и использование компьютеров .........................214
Неразрешимость и мозг ...............................................................215

Глава 11. Послесловие: еще один услужливый джинн? .... 218
О некоторых потенциально великих алгоритмах .......................... 220
Могут ли великие алгоритмы уйти в тень? ................................... 221
Чему мы научились? .................................................................... 222
Конец пути .................................................................................. 223

Благодарности .......................................................225

Источники и литература для дальнейшего чтения ........226

Предметный указатель ............................................230

ПРЕДИСЛОВИЕ

Компьютеры преобразуют наше общество не в меньшей степени, чем 
достижения физики и химии в два предшествующих столетия. Действительно, 
вряд ли остался в нашей жизни уголок, который не затронут – 
а чаще изменен до неузнаваемости – цифровыми технологиями. 
И коль скоро компьютеры так важны для современного общества, 
не странно ли, что люди так мало знают об основополагающих идеях, 
благодаря которым все это стало возможно? Изучение этих идей составляет 
основу информатики, а новая книга Маккормика – одна из 
немногих попыток донести их до широкой аудитории.
Одна из причин недооценки информатики как научной дисциплины 
заключается в том, что ее редко преподают в средней школе. Если 
начальный курс по таким предметам, как физика и химия, принято 
считать обязательным, то информатику как отдельную дисциплину 
обычно изучают только в колледжах или университетах. А если уж 
в школе есть предмет «информатика» или «информационные и телекоммуникационные 
технологии», то сводится он к приобретению 
навыков работы с некоторыми программными пакетами. Неудивительно, 
что ученикам это кажется скучным, а их естественная склонность 
к использованию компьютеров для развлечений и общения 
умеряется впечатлением, будто созданию таких технологий недостает 
интеллектуальной глубины. Есть мнение, что именно такое умонастроение 
стало причиной снижения количества студентов, изучающих 
информатику в университетах, на 50 % за последние 10 лет. Учитывая 
критическое значение цифровых технологий для современного общества, 
крайне важно возродить интерес населения к обаянию информатики.

В 2008 году мне была оказана честь открывать 180 серию рождественских 
лекций Королевского института, начало которым положил 
Майкл Фарадей в 1826 году. Лекции 2008 года впервые были посвящены 
теме информатики. Готовясь к ним, я много размышлял о том, 
как объяснить смысл информатики непрофессиональной аудитории, 
и обнаружил, что существует очень мало ресурсов и почти никаких 

Предисловие

научно-популярных книг на эту тему. Поэтому новая книга Маккор-
мика пришлась очень кстати.
Маккормик проделал великолепную работу и сумел изложить 
сложные идеи информатики в виде, доступном для широкой публики. 
Многие из этих идей необычайно красивы и элегантны, что само 
по себе делает их достойными внимания. Приведу всего один пример: 
бурный рост Интернет-торговли стал реальностью только потому, что 
появилась возможность безопасно посылать по сети конфиденциальную 
информацию (в частности, номера кредитных карт). В течение 
многих десятилетий задача о безопасном обмене данными по «открытым» 
каналам считалась неразрешимой. А когда решение было 
найдено, оно оказалось исключительно элегантным, и Маккормик 
объясняет его с помощью точных аналогий, не требующих предварительного 
знакомства с информатикой. Благодаря таким жемчужинам 
книга займет достойное место на полке с научно-популярной литературой, 
и я ее всячески рекомендую.

Крис Бишоп
заслуженный научный работник, Microsoft Research, Кэмбридж
вице-президент, Королевский институт Великобритании
профессор информатики, Эдинбургский университет

ГЛАВА 1. 
Введение: необычные идеи, 
каждодневно используемые 
в компьютерах

Природа дарования, коим я обладаю, очень-очень проста. Ум мой от 
рождения предрасположен к фантазии, причудливо выражающейся 
в образах, фигурах, формах, предметах, понятиях, представлениях, 
порывах и отступлениях.

— Вильям Шекспир «Бесплодные усилия любви»1

Как появились на свет великие идеи информатики? Вот несколько 
примеров.
• В 1930-х годах, еще до создания первого цифрового компьютера, 
гениальный британский ученый открывает научную дисциплину 
информатики, а затем доказывает, что существуют 
задачи, которые не сможет решить ни один будущий компьютер, 
каким бы он ни был быстрым и мощным и как бы хитроумно 
ни был спроектирован.
• В 1948 году сотрудник телефонной компании публикует статью, 
которая заложила основы теории информации . Эта работа 
доказала, что компьютеры могут передавать сообщения 
без искажения, даже если большая часть данных изменена в 
результате воздействия помех.
• В 1956 году группа ученых приезжает на конференцию в 
Дартмуте с четко осознанной дерзкой идеей основать новую 
науку – искусственный интеллект . После многочисленных 
ярких достижений и не менее многочисленных глубочайших 
разочарований мы все еще ждем появления компьютерной 
программы, обладающей настоящим интеллектом.

1 
Перевод Ю. Корнеева.

Глава 1. Введение: необычные идеи, ...

• В 1969 году исследователь из компании IBM открывает новый 
элегантный способ организовать информацию в базе данных. 
Сегодня эта технология применяется для хранения и извлечения 
информации, участвующей в большинстве сделок, совершаемых 
в онлайновом режиме.
• В 1974 году исследователи из финансируемой Британским 
правительством лаборатории по секретным коммуникациям 
открывают способ безопасного обмена данными между двумя 
компьютерами в ситуации, когда третий компьютер может 
наблюдать за всеми передаваемыми данными. Эти исследователи 
были связаны обязательством хранить государственную 
тайну, но по счастью три американских профессора независимо 
открыли и развили эту идею, которая ныне лежит в основе 
всех безопасных коммуникаций в Интернете.
• В 1996 году два студента Стэнфордского университета, работающих 
над диссертацией, решают объединить усилия и построить 
поисковую систему для веб. Спустя несколько лет они 
создали компанию Google – первый цифровой гигант эпохи 
Интернета.
Сегодня, в 21 веке мы наслаждаемся плодами поражающего воображение 
развития технологий, но никаких вычислительных устройств – 
будь то кластер из самых мощных доступных сегодня машин 
или модный гаджет последней модели – не существовало бы без 
основополагающих идей информатики, возникших в 20 столетии. 
Подумайте: делали ли вы сегодня что-то поразительное? Ответ, конечно, 
зависит от точки зрения. Быть может, вы перелопатили миллиарды 
документов в поисках двух-трех, которые содержат нужные 
сведения? Или сохранили либо передали по сети миллионы единиц 
информации без единой ошибки, несмотря на электромагнитные помехи, 
которым подвержены все электронные устройства? Или благополучно 
купили что-то через Интернет, хотя вместе с вами к тому же 
серверу обращались тысячи других пользователей? Или безопасно 
передали по проводам конфиденциальные данные (к примеру, номер 
своей кредитной карты ), хотя вас могли подслушать десятки других 
компьютеров. А, быть может, вы воспользовались магией сжатия, позволяющий 
уменьшить размер многомегабайтной фотографии до величины, 
позволяющей передать ее по электронной почте ? Или, даже 
не подозревая об этом, прибегли к скрытому в наладонном устройстве 
искусственному интеллекту, который исправляет опечатки, когда вы 
вводите текст с помощью его крохотной клавиатуры? Каждое из этих 

деяний достойно изумления, и все они основаны на замечательных 
открытиях, о которых было сказано выше. Стало быть, любой пользователь 
компьютера каждый день по много раз применяет эти гениальные 
идеи, даже не осознавая этого! Цель этой книги – объяснить 
величайшие идеи информатики максимально широкой аудитории. 
Никакого предварительного знакомства с информатикой не предполагается.


Алгоритмы – чародейство 
услужливого джинна

До сих пор я говорил о великих «идеях» информатики , но сами ученые 
употребляют слово «алгоритм». Так в чем же разница между идеей и 
алгоритмом? Что вообще такое алгоритм? Простейший ответ звучит 
так: алгоритм – это рецепт, в котором описывается точная последовательность 
шагов, приводящая к решению задачи. Один такой алгоритм 
всем нам известен со школьной скамьи: сложение двух больших 
чисел. Пример его применения показан ниже. Описание последовательности 
шагов этого алгоритма начинается так: «Сначала сложить 
две последние цифры, записать последнюю цифру результата и перенести 
избыток в следующий столбец слева; затем сложить цифры в 
следующем столбце и прибавить к ним перенесенный из предыдущего 
столбца избыток…» – и так далее.

                                                                    1                                    1  1
  4844978  Ë

     4844978  Ë

    4844978
+3745945         +3745945         +3745945
                                       3                     23

Первые два шага алгоритма сложения двух чисел.

Обратите внимание, что шаги этого алгоритма почти механические. 
И это одна из важнейших особенностей любого алгоритма: каждый 
шаг должен быть описан абсолютно точно, его выполнение не 
должно требовать от человека догадки или озарения. И тогда эти механические 
шаги можно будет оформить в виде программы для компьютера. 
Еще одна важная особенность алгоритма заключается в том, 
что он должен работать всегда, какие бы данные ни были поданы на 
вход. Алгоритм сложения, который мы учили в школе, обладает этим 
свойством: каковы бы ни были два складываемых числа, этот алго-

Алгоритмы – чародейство услужливого джинна