Камень, ножницы, теорема. Фон Нейман. Теория игр

Коллектив авторов

МАНХЭТТЕНСКИЙ ПРОЕКТ

Президент США Франклин Делано Рузвельт подписал 7 декабря 1941 года приказ о создании атомной бомбы. Была образована междисциплинарная команда при участии различных отделений университетов Колумбии, Калифорнии и Чикаго.

Ее целью было создание первой бомбы, основанной на делении ядра. Научным директором проекта был назначен Роберт Оппенгеймер (1904-1967), а ответственным со стороны армии стал генерал Лесли Гровс (1896-1970). Всего в Манхэттенском проекте приняли участие более 125 тысяч человек. Вероятно, одной из главных заслуг Гровса (если не единственной) было обеспечение абсолютной секретности проекта, который стал чуть ли не самой большой тайной в истории. Над ним работали всемирно известные ученые, такие как Ричард Фейнман, Эдвард Теллер, Энрико Ферми, Ричард Уилкинс, Станислав Улам, Луис Злотин, Клаус Фукс, а также фон Нейман, спроектировавший механизм

поджигания.

Фон Нейман, уже давно работавший в области гидродинамики, разработал устройство, которое при детонации производило ударную волну, а та, в свою очередь, вызывала немедленное сжатие ядра плутония. Объем этого ядра был достаточно большим для того, чтобы масса плутония была меньше критической. При равномерном сокращении объема ядро достигало сверхкритической массы. Математическая модель, лежащая в основе изобретения, базировалась на системе конечно-разностных уравнений, а для их решения требовался компьютер, способный производить огромное количество сложных вычислений за кратчайшее время. Фон Нейман разработал алгоритм, необходимый для решения уравнений, но вполне вероятно, что без помощи компьютера его предложение было бы невыполнимым. Манхэттенский проект длился 2 года, 3 месяца и 16 дней. Первая атомная бомба в истории была взорвана в пустыне рядом с городом Аламогордо 16 июля 1945 года.

ENIAC

В июле 1943 года в Электротехнической школе Мура при Пенсильванском университете началось строительство нового компьютера, которому суждено было стать краеугольным камнем в истории вычислительных машин. Его назвали ENIАС (Electronic Numerical Integrator and Computer — электронный числовой интегратор и вычислитель). Это был проект высочайшей секретности, который имел кодовое название РХ. ENIAC считается первым компьютером в истории, хотя некоторые полагают, что пальма первенства принадлежит «Колоссу» (Colossus), запущенному в середине февраля 1944 года в Блетчли-парке — военном объекте, расположенном в графстве Бакингемшир, Англия.

ОК-РИДЖ

В 1942 году правительство США построило секретный город Ок-Ридж (штат Теннесси) площадью более 24 тысяч га, где должны были располагаться все предприятия, необходимые для Манхэттенского проекта, а также жить все сотрудники, включая техников и ученых, — несколько десятков тысяч человек. Объект охраняла американская армия, и очень немногие, в числе которых был и Джон фон Нейман, могли покидать территорию. При въезде в Ок-Ридж висел плакат: «Все, что ты видишь, делаешь или слышишь здесь, должно здесь же и остаться».

Плакат при въезде в Ок-Ридж, призывающий сохранять секретность всего происходящего на этой территории.

Идея «Колосса» была предложена ученым-программистом Аланом Тьюрингом (1912-1954), а проект — математиком Максом Ньюманом (1897-1984). Устройство было использовано для расшифровки кода «Энигмы».

Создание ENIAC спонсировала армия, на него было затрачено примерно 8000 долларов. Устройство имело 30 м в длину и весило 32 тонны. Его 17468 клапанов (вакуумных трубок) излучали так много тепла, что температура в комнате, где находился ENIAC, могла подниматься до 50°С. Компьютер мог держать в памяти всего 20 чисел.

МЕТОД МОНТЕ-КАРЛО

Метод Монте-Карло — группа численных методов, используемых в статистике для апроксимации сложных математических выражений, для которой нет алгоритма вычисления. Он состоит в симуляции случайных переменных. Одно из самых простых известных устройств для генерирования таких случайных чисел — рулетка казино. Именно поэтому данному методу дали имя культовой столицы азартных игр. Дилетанты считают, что метод Монте-Карло помогает выигрывать в рулетку, но на самом деле этот статистический метод никак не связан с азартными играми. Существует простой способ проиллюстрировать идею, на которой он основан. Представим себе квадратную доску со стороной 1, внутри которой находится геометрическая фигура неправильной формы, площадь которой мы хотим вычислить (см. рисунок). Мы могли бы взять для примера любую фигуру с изогнутыми краями и, разумеется, любую фигуру, описываемую математической функцией. Теперь расположим количество N точек случайным образом. Такой сценарий мог бы иметь место в реальной жизни, например когда имеется некое количество градинок, выпавших на огороженное пространство. Сосчитаем количество N' точек, находящихся внутри той фигуры, площадь которой нам надо узнать. Предположим, что N = 40, а N' = 13. Коэффициент /'= 0, 32 будет апроксимацией искомой площади. Легко доказать, что погрешность будет пропорциональна определенной величине, так что для каждой последующей цифры после запятой,

которую мы хотим получить, будет необходимо в сто раз увеличивать объем вычислений. Хотя метод основан на простом алгоритме, для его применения необходимы вычислительные устройства. Фон Нейман опирался на идею, предложенную американским математиком польского происхождения Станиславом Уламом (1909-1984), которого фон Нейман пригласил для работы над Манхэттенским проектом. Улам рассказывал, что мысль пришла ему в голову, когда он во время болезни раскладывал сложный пасьянс. Тогда Улам подумал: вместо того чтобы каждый раз проводить детальный анализ каждого возможного решения, гораздо интересней играть наугад, подсчитывая количество задействованных карт. Фон Нейман применил этот метод для обнаружения нейтронов, порожденных радиоактивным материалом, вдоль радиуса сферы. В 1947 году он отправил официальное предложение по использованию метода в Лос-Аламосскую национальную лабораторию. Этот документ стал первым известным нам формальным описанием метода Монте-Карло.

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

Фон Нейман начал заниматься ENIAC совершенно случайно. Американский математик Герман Хайн Голдстайн (1913-2004) поступил на военную службу в начале Второй мировой войны. Он имел звание лейтенанта и работал в BRL, баллистической лаборатории в Абердине, штат Мериленд. Голдстайн был специалистом по подготовке таблиц стрельбы и прекрасно понимал, что необходимо срочно автоматизировать длинные и утомительные вычисления. Поэтому он согласился быть посредником между школой Мура в Филадельфии, которая занималась созданием ENIAC, и полигоном в Абердине. Летом 1944 года Голдстайн случайно встретился с фон Нейманом на железнодорожном вокзале Абердина. Поскольку у того было множество обязательств перед различными государственными организациями, ему, одному из немногих ученых, разрешалось покидать базу Аламогордо. Голдстайн не был лично знаком с фон Нейманом, но знал его по конференциям, поэтому решил все-таки подойти к ученому.

EDVAC: ШАГ ВПЕРЕД

Несмотря на усовершенствования, сделанные фон Нейманом, возможности ENIAC были очень ограниченны. После войны ученый участвовал в работе над проектом нового компьютера, который должен был учесть ошибки ENIAC. Новая машина, EDVAC (Electronic Discrete Variable Automatic Computer), была гораздо быстрее предыдущей (ENIAC совершал 333 операции в секунду, в то время как EDVAC — 20 тысяч). К тому же он был полностью основан на архитектуре фон Неймана. Ученый не ограничился разработкой структуры компьютера — он также работал над алгоритмами, которые позволили бы совершать более сложные математические операции, чем простые вычисления, доступные до этого компьютерам. Фон Нейману удалось создать алгоритмы для решения различных типов уравнений, вычисления обратной матрицы, нахождения собственного вектора и вычисления соответствующего собственного значения, а также нахождения максимальных и минимальных значений функций с несколькими переменными.

Джон фон Нейман (слева) и Роберт Оппенгеймер перед EDVAC.

Фон Нейман со своей второй женой Кларой Дан в 1954 году.

Два оператора работают с контрольной панелью ENIAC в Электротехнической школе Мура при Пенсильванском университете, 1940-е годы.

Математики любопытны по своей природе и всегда интересуются работой друг друга. Разговор касался малозначительных тем, пока Голдстайн не упомянул, что работает над новым компьютером. Тут поведение фон Неймана изменилось, и, по словам самого Голдстайна, он начал допрос с пристрастием. Вопросы выдавали в нем эксперта, и Голдстайн решил пригласить коллегу в исследовательский центр Мура, чтобы лично познакомить его с инженерами Джоном Мокли и Джоном Преспером Экертом, работавшими над ENIAC. В этой истории, конечно, странно, что двое людей, каждый из которых работал над сверхсекретным проектом, едва познакомившись, стали обсуждать свои исследования в здании железнодорожного вокзала.