Математика жизни и смерти. 7 математических принципов, формирующих нашу жизнь — страница 39 из 54

Глава 6Бесконечная оптимизация: безграничный потенциал алгоритмов – от эволюции до электронной коммерции

«Через сто метров поверните направо… Поверните направо», – инструктировал бесплотный голос спутникового навигатора. Роберто Фархат, только учившийся водить машину, но уже взявший с собой в поездку жену и двух детей, так и поступил. Всего несколько минут назад он сменил за рулем свою жену – опытного водителя с 15-летним стажем. Когда он свернул с шоссе А6, двухтонный Audi, двигавшийся по встречной полосе[151], въехал в пассажирскую дверь машины Фархата со скоростью 45 миль в час. Уделяя пристальное внимание спутниковому навигатору, Фархат пропустил дорожные знаки, запрещавшие правый поворот. Сам он остался невредим. А вот его четырехлетней дочери Амелии не повезло. Она умерла в больнице три часа спустя.

Мы уже привыкли полагаться на гаджеты вроде спутниковых навигаторов, которые призваны облегчить нашу перегруженную стрессами и заботами жизнь. Определяя кратчайший маршрут из пункта А в пункт Б, спутниковые навигационные системы решают сложную задачу, что можно сделать единственным способом – через алгоритмический расчет по требованию. Удержать в памяти все возможные маршруты между двумя удаленными точками – слишком сложная задача для небольшого устройства. Точек, между которыми может потребоваться проложить маршрут, огромное количество, что увеличивает сложность задачи в астрономическом масштабе. Учитывая уровень сложности, впечатляет, что алгоритмы спутниковой навигации очень редко ошибаются. Но когда они делают ошибки, те порой оказываются катастрофическими.

Алгоритм – последовательность инструкций, точно описывающих порядок действий для решения конкретной задачи. Задачей может быть что угодно – от организации музыкальной коллекции до приготовления пищи. Самые ранние записанные алгоритмы, однако, носили строго математический характер. У древних египтян был простой алгоритм перемножения двух чисел, а вавилоняне имели правила вычисления квадратных корней. В III веке до нашей эры древнегреческий математик Эратосфен изобрел свое «решето» – простой алгоритм определения простых чисел в числовом ряду, а Архимед применил метод исчерпывания [152] для вычисления последовательности цифр в числе π.

В Европе накануне эпохи Просвещения развитие навыков механической обработки позволило физически воплотить алгоритмы в таких инструментах, как часы и, позднее, зубчатые вычислители. К середине XIX века мастерство достигло такой степени, что эрудит Чарльз Бэббидж смог построить первый механический компьютер, для которого первопроходец математики Ада Лавлейс написала первые компьютерные программы. В принципе, именно Ада первой поняла, что изобретение Бэббиджа имеет прикладное значение, выходящее далеко за рамки чисто математических вычислений, для которых его вычислитель был изначально разработан: что такие объекты, как ноты или, что, возможно, еще важнее, буквы можно описывать в виде кода и манипулировать ими с помощью машины. Сначала электромеханические, а затем и чисто электрические компьютеры использовались союзниками во время Второй мировой войны для алгоритмической расшифровки немецких шифров. Хотя в принципе эти алгоритмы можно было исполнять вручную, прототипы компьютеров того времени уже делали это со скоростью и точностью, недостижимой для людей – сколько бы тех ни было.

Все более сложные алгоритмы, которыми сейчас руководствуются компьютеры, стали неотъемлемой частью нашей повседневности – от ввода запроса в поисковую систему или фотографирования на телефон до компьютерных игр или вопроса о погоде у персонального цифрового ассистента. Мы уже не довольствуемся многими прежними решениями: мы хотим, чтобы поисковая система выводила наиболее релевантные ответы на наши вопросы, а не только первый, который она находит; мы хотим знать точно, будет ли дождь в пять вечера, чтобы определиться – брать ли с собой на работу плащ; мы хотим, чтобы спутниковая навигация вела нас из точки A в точку Б по самому быстрому маршруту, а не по первому попавшемуся. Примечательно, что в большинстве определений алгоритма (списка инструкций для выполнения задачи) не упоминаются входные и выходные данные, которые обеспечивают соответствие алгоритмов задаче. Так, для рецепта входными данными будут ингредиенты, а выходными – готовое блюдо, которое вы подаете на стол. Для спутниковой навигации входные данные – это начальная и конечная точки, которые вы указываете на карте, хранящейся в памяти прибора. Выходные – маршрут, который он вам предлагает. Без этих привязок к реальному миру алгоритмы являются просто абстрактными наборами правил. Когда сбой алгоритма попадает в новостные ленты, в большинстве случаев этот сбой вызван либо погрешностью при вводе данных, либо неожиданными данными на выходе, но не ошибкой в самих правилах.

В этой главе мы познакомимся с математикой, стоящей за неумолимой оптимизацией алгоритмов в нашей повседневной жизни: от принципов выдачи ответов на поисковые запросы в Google до историй, навязываемых нам на Facebook. Мы покажем обманчиво простые алгоритмы, которые решают сложные задачи и на которые опираются современные технологические гиганты: от навигационной системы Google Maps до маршрутов доставки Amazon. Но мы не будем ограничиваться компьютеризированным миром современных технологий – мы предложим вам некоторые «подручные» алгоритмы оптимизации, с помощью которых можно занять лучшее место в поезде или выбрать самую короткую очередь в супермаркете.

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

Вопросы на миллион долларов

В 2000 году Математический институт Клэя опубликовал список семи «Проблем тысячелетия» – наиболее важных нерешенных математических задач[153]. В него вошли: гипотеза Ходжа, гипотеза Пуанкаре, гипотеза Римана, квантовая теория Янга – Миллса, проблема существования и гладкости решений уравнений Навье – Стокса, гипотеза Бёрча – Свиннертон-Дайера и проблема равенства классов P и NP. Эти имена и названия мало что говорят подавляющему большинству людей – за исключением тех немногих, кто имеет отношение к специфическим разделам математики, – но главный спонсор института Лэндон Клэй четко обозначил исключительную важность этих гипотез, пообещав выплатить 1 миллион долларов за доказательство или опровержение любой из них. На момент написания книги решена была только проблема с гипотезой Пуанкаре. Гипотеза Пуанкаре – это проблема из области математической топологии. Топологию можно представить как геометрию (математику форм), которая имеет дело с тестом для выпечки. В топологии фактические формы самих объектов неважны, объекты группируются по количеству отверстий, которыми они обладают. Так, для тополога нет разницы между теннисным мячом, мячом для регби или даже фрисби. Если бы все они были сделаны из теста, то теоретически их можно было бы раздавить, растянуть или иным образом переконфигурировать, чтобы они выглядели похожими друг на друга, не прокалывая новых дыр в тесте и не закрывая тех, что есть изначально. При этом эти объекты принципиально отличаются от резинового кольца, камеры шины или обруча баскетбольной корзины – каждый из этих объектов имеет отверстие в середине, как бублик. Фигура в виде восьмерки с двумя отверстиями и крендель с тремя – опять же разные топологические объекты.

В 1904 году французский математик Анри Пуанкаре (тот самый Пуанкаре, который вмешался, чтобы прекратить издевательства над математикой и оправдать капитана Альфреда Дрейфуса в третьей главе), предположил, что самой простой формой в четырехмерном пространстве является четырехмерная проекция сферы. Чтобы объяснить, что для Пуанкаре означало понятие «простой», представьте, будто вы пытаетесь обвязать веревку вокруг некоего объекта. Если вы сможете стянуть эту веревку с объекта так, чтобы при этом она не отрывалась от его поверхности, и чтобы на веревке не завязался узел, то с точки зрения топологии объект тождественен сфере. На языке математики это называется односвязность. Если же трюк у вас не удастся, то вы имеете дело с более сложным топологическим объектом. Представьте, что вы протягиваете струну через центр бублика и делаете петлю. Снять эту струну с бублика, не разомкнув петлю, вы не сможете. Бублик, имеющий одно отверстие, принципиально более сложная фигура, чем футбольный мяч, который отверстий не имеет. Результат в трехмерном пространстве был уже хорошо известен, но Пуанкаре предположил, что та же идея окажется верной и в четырех измерениях. Позднее его предположение обобщили – идея должна быть верной в пространстве с любым количеством измерений. Однако к моменту объявления приза за решение «Проблем тысячелетия» верность гипотезы подтвердили для всех других измерений, и только первоначальная гипотеза Пуанкаре о четырехмерном пространстве оставалась недоказанной.