Десять уравнений, которые правят миром. И как их можете использовать вы

Предположим, мой первоначальный список таков: {X,G,A,M}. Сначала мы сливаем буквы {X} и {G}, получая {G,X}, и буквы {A} и {M}, получая {A,M}. Элегантность такого подхода в том, что на всех уровнях используется одна и та же техника. Разделив исходный список на достаточно мелкие части, мы в итоге приходим к списку, который гарантированно будет отсортирован, то есть к отдельным буквам. Затем, используя наше умение сливать два сортированных списка, мы гарантируем, что все создаваемые нами списки также будут отсортированы (см. рис. 10). Сортировка слиянием никогда не ошибается.

Рис. 10. Иллюстрация сортировки слиянием и алгоритма Дейкстры

Еще один пример – алгоритм Дейкстры, определяющий кратчайший путь между двумя точками. Голландский физик и программист Эдсгер Дейкстра разработал свой алгоритм в 1953 году, чтобы продемонстрировать «некомпьютерным людям» (как он их называл), что компьютеры могут быть полезными при расчете самого быстрого маршрута между двумя нидерландскими городами[189]. На придумывание алгоритма у него ушло всего двадцать минут – он сидел в одном из амстердамских кафе. Позже он рассказывал журналу Communications of the ACM[190]: «Одна из причин его красоты – отсутствие у меня карандаша и бумаги. Без них вы практически вынуждены избегать всех сложностей, которых можно избежать».

Представьте, что вы хотите проехать из Роттердама в Гронинген. Алгоритм Дейкстры предписывает вам сначала определить время поездки от Роттердама до всех соседних с ним городов. Процесс показан на рисунке 10. Например, Делфт получит 23 минуты, Гауда – 28, а Схонховен – 35. Следующий шаг – рассмотреть все соседние для этих трех городов и найти кратчайшее время пути до них. Например, от Гауды до Утрехта 35 минут, а от Схонховена до Утрехта – 32 минуты; поэтому кратчайшее общее время пути до Утрехта составляет 28 + 35 = 63 минуты через Гауду (это меньше, чем 35 + 32 = 67 минут через Схонховен). Алгоритм постепенно продвигается по территории Нидерландов, фиксируя кратчайшее расстояние до каждого города. Поскольку он каждый раз вычисляет кратчайший путь до любого города, то при добавлении нового города гарантировано, что до него тоже будет найден кратчайший путь. Алгоритм рассчитан не на конкретный Гронинген, он маркирует расстояния до всех городов; но когда в расчетах дело дойдет до него, алгоритм гарантирует, что нашел кратчайший путь.

Есть множество алгоритмов, похожих на сортировку слиянием Джона фон Неймана или нахождение кратчайшего пути[191]. Вот несколько примеров: алгоритм Краскала для нахождения минимального остовного дерева (например, схема кратчайшей железнодорожной сети, соединяющей все города страны); расстояние Хэмминга для обнаружения разницы между двумя частями текста или данных; алгоритмы построения выпуклой оболочки для изображения фигуры, окружающей некоторое множество точек; алгоритмы обнаружения столкновения в 3D-графике; быстрое преобразование Фурье для обнаружения сигнала. Эти алгоритмы и их вариации – строительные блоки для аппаратного и программного обеспечения компьютеров. Они сортируют и обрабатывают наши данные, перемещают электронные письма, проверяют грамматику и позволяют Сири или Алексе за секунды идентифицировать передаваемую по радио песню.

Математика «Если… то…» всегда дает правильный ответ, и мы всегда знаем, что делать дальше. Возьмите, например, футбольного бота, созданного тремя студентами магистратуры. Я мог задавать ему простые вопросы о футболе, он отвечал; но Антона его ответы не удивляли. Антон закодировал правила, которые определяют, что говорит бот, и программа четко следует им.

Почему я свалил в одно общее уравнение все алгоритмы «если… то…»? Потому что у них есть одно очень важное общее свойство: они универсальные истины. Алгоритм Дейкстры всегда найдет кратчайший путь; сортировка слиянием всегда отсортирует список имен от A до Z; выпуклая оболочка для множества точек всегда имеет одну и ту же конструкцию. Это утверждения, которые истинны независимо от того, что мы говорим или делаем.

В первых девяти главах этой книги мы использовали уравнения для проверки моделей, составления прогнозов и оттачивания нашего понимания реальности. Эти уравнения взаимодействуют с миром: мы позволяем прошлым данным информировать наши модели, а те прогнозируют будущие данные. Но алгоритмы «если… то…» негибкие. Они берут данные – скажем, список имен для сортировки или список точек, между которыми можно вычислить кратчайший путь, – и выдают ответ. Мы не пересматриваем свое знание мира на основе полученных ответов. Точно так же и наши наблюдения не влияют на истинность алгоритмов. Вот почему я называю их универсальными: их истинность доказана, они работают всегда.