Алгоритмы для жизни. Простые способы принимать верные решения - Том Гриффитс

Бросание тысячи иголок на лист бумаги может показаться кому-то интересным занятием, но для того, чтобы сделать из «пробника» практический метод, потребовались компьютерные технологии. Раньше, когда математики и физики пытались использовать случайность для решения задач, они должны были скрупулезно проводить расчеты вручную, так что трудно было генерировать достаточное количество выборочных проб, чтобы получить точные результаты. Компьютеры же – в частности, компьютер, разработанный в Лос-Аламосе во время Второй мировой войны, – определили исход дела.

Станислав (Стэн) Улам был одним из математиков, принимавших участие в разработке атомной бомбы. Выросший в Польше, он переехал в США в 1939 году и в 1943-м вошел в Манхэттенский проект. После непродолжительного пребывания в научных кругах он вернулся в Лос-Аламос в 1946 году и приступил к работе над созданием ядерного оружия. Но он был болен – заразился энцефалитом, и ему сделали срочную операцию на головном мозге. Едва оправившись от болезни, он начал беспокоиться, удалось ли ему сохранить математические способности.

В процессе выздоровления Улам много играл в карты, в частности раскладывал пасьянс (известный как «Клондайк»). Как знает всякий любитель пасьянсов, некоторые перетасовки колоды делают игру заведомо проигрышной. И в процессе игры Улам не раз задавался вопросом: какова вероятность, что перетасовка колоды приведет к выигрышу в игре?

В такой игре, как пасьянс, попытки спрогнозировать ход игры через пространство вероятностей обречены на провал. Стоит только перевернуть первую карту – и вот уже 52 возможных варианта развития игры; переверните следующую – и вот уже 51 вариант для каждой следующей карты. Таким образом, мы уже вовлечены в тысячи возможных игр еще до того, как начали играть. Фрэнсис Скотт Фитцджеральд однажды сказал: «Лучшее свидетельство высокого интеллекта – умение одновременно удерживать в уме две противоположные идеи, не теряя при этом способности функционировать». Это может быть правдой, но никакой высококлассный интеллект – ни человеческий, ни чей-либо еще – не сможет единовременно удерживать в уме миллионы миллиардов возможных раскладов колоды и надеяться на функционирование.

После попыток произвести некоторые сложные комбинаторные расчеты Улам бросил это дело и нашел другой подход, прекрасный в своей простоте: всего лишь играть в эту игру.

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

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

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

Большинство задач, подобных расчету взаимодействий субатомных частиц или шансов на победу в пасьянсе, сами по себе являются вероятностными, так что их решение с помощью рандомизированного подхода вроде метода Монте-Карло вполне разумно. Но, пожалуй, самым удивительным доказательством важности рандомизированного подхода служит тот факт, что он может быть использован в таких ситуациях, где случайность, казалось бы, вовсе не играет никакой роли. Даже если ваш вопрос предполагает четкий ответ «да» или «нет», «истина» или «ложь» и тут не может быть никаких вероятностей, бросок пары кубиков способен по-прежнему стать частью принятия решения.

Первым человеком, продемонстрировавшим удивительно широкое применение метода рандомизации в информатике, стал Майкл Рабин. Родившийся в 1931 году в Бреслау в Германии (который впоследствии стал польским Вроцлавом в конце Второй мировой войны), Рабин был потомком целой династии раввинов. Его семья переехала из Германии в Палестину в 1935 году, и там он отказался от протоптанной для него отцом раввинской тропы в пользу красоты математики, открыв для себя исследования Алана Тьюринга на заре студенчества в Еврейском университете и эмигрировав в США, где впоследствии он окончил Принстон. Рабин должен был получить премию Тьюринга – аналог Нобелевской премии в сфере информатики – за включение в теоретическую информатику недетерминированных случаев, когда автомат не обязан следовать одному параметру, но имеет несколько возможных путей следования. В 1975 году, находясь в творческом отпуске, Рабин пришел в MIT в поисках нового направления для работы.

Нашел он его в одной из старейших задач: как найти простые числа. Алгоритмами поиска простых чисел интересовались еще в Древней Греции, где математики использовали простой и точный метод, получивший название «решето Эратосфена». Оно работает следующим образом: чтобы найти все простые числа меньше n, начните записывать последовательность чисел от 1 до n по порядку. Затем вычеркните все числа, кратные 2, кроме самого числа 2 (4, 6, 8, 10, 12 и т. д.). Найдите следующее самое маленькое число, которое еще не было вычеркнуто (в данном случае – 3), и вычеркивайте все числа, кратные ему (6, 9, 12, 15). Продолжайте в том же духе, и те числа, что останутся в результате, и будут простыми числами.

На протяжении тысячелетий изучение простых чисел считалось, как выразился Г. Х. Харди, «одним из самых очевидно бесполезных разделов математики». Но оно неожиданно приобрело большую практическую значимость в XX веке, став ключевым моментом в области шифрования и сетевой безопасности. Гораздо проще перемножать простые числа между собой, чем выносить их за скобки. С достаточно большими простыми числами – например, состоящими из тысячи знаков – умножение может быть произведено в долю секунды, в то время как разложение на множители могло бы занять буквально миллионы лет. Это и есть то, что зовется односторонней (необратимой) функцией, обратное значение которой очень трудно вычислить. В современном шифровании данных, к примеру, секретные простые числа, известные только отправителю и получателю, перемножаются между собой, чтобы создать огромные составные числа. Последние могут быть переданы публично без опасений, поскольку обратное разложение зашифрованного послания на множители займет у любого перехватчика слишком много времени, чтобы стоило хотя бы попытаться. Таким образом, любая безопасная онлайн-коммуникация – будь то торговля, банкинг или электронные сообщения – начинается с охоты на простые числа.