Шифрованные письма и Монте-Карло: чему учат школьников на «Больших вызовах»

В «Сириусе» начались «Большие вызовы».  Для участия в этой масштабной научно-технологической программе на первую федеральную территорию съехались более 400 старшеклассников со всей России. Они работают над актуальными  современными задачами и открывают новые для себя направления. Их наставники — выдающиеся преподаватели. Повезло ребятам и с лекторами. В их числе — профессор, доктор физико-математических наук и ректор университета «Иннополис» Александр Гасников. Он рассказал школьникам, как в общих чертах устроена теория вероятностей и как эта наука помогает разобраться в устройстве нашего мира.

Александр Гасников Фото: Пресс-служба «Сириуса»

 Элементарно, Ватсон!

Рассказ Артура Конан Дойла «Пляшущие человечки» был опубликован в 1903 году. В нем бандит Аб Слени посылает зашифрованные послания в виде танцующих человечков бывшей возлюбленной Илси Патрик, пытаясь ее вернуть. Она его отвергает, а он в ответ присылает ей угрозу смерти. Но понять смысл этого сообщения могут только эти двое. Муж Илси просит Шерлока Холмса расшифровывать послания. Конечно, знаменитый сыщик с этим справляется, а потом посылает отправителю зашифрованное сообщение о встрече. Так преступник попадает в ловушку.  

По одной из версий, идея с шифром пришла в голову писателю, когда он оказался в небольшом городке в Восточной Англии. Конан Дойла попросили подписать книгу, и он увидел, что имя и адрес владельца были изображены на титульном листе в виде пляшущих человечков. Каждый из них соответствовал определенной букве английского алфавита. Такую запись сделал маленький сын хозяина гостиницы, где остановился автор детективов.

Расшифровка изображений пляшущих человечков Фото: © sh-topia.com

Правда, эксперты утверждают, что подобные дешифровки встречались и раньше — в книгах других писателей. Про похожий случай рассказал Александр Гасников.

«Однажды в английской тюрьме перехватили письмо, в котором на целом листе бумаги были нарисованы пляшущие человечки. Задача была расшифровать это письмо, содержащее примерно пять тысяч символов. Что сделали ученые? Они взяли некий большой текст, например „Войну и мир“ на английском языке, и посмотрели частоты встречаемости буквы „А“ после буквы „B“ и другие возможные пары. Дальше определили, как часто в английских текстах попадаются разные буквы. Например, „А“ встречалась чаще всего. Затем они частотным образом представили предварительную гипотезу, которая помогала понять, какой человечек соответствует той или иной букве», — поясняет математик.

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

Фото: Пресс-служба «Сириуса»

«Что касается ребер графа, то они соединяли такие вершины, в которых отличие соответствия букв человечкам имело место ровно в двух позициях. Вероятности на ребрах выбирались таким образом, чтобы если долго случайно блуждать на таком графе, вероятность оказаться в той или иной вершине как раз равнялась или стремилась к тем вероятностям, которые были приписаны вершинам. Оказывается, это можно очень просто сделать (например, алгоритмом Метрополиса — Хастингса). Далее на таком графе было организовано случайное блуждание (согласно вероятностям перехода на ребрах). Таким образом, после достаточно большого числа шагов случайного блуждания, каждый шаг которого приводил  к перестановке двух букв, отвечающих рассматриваемой на этом шаге паре человечков, ученым удалось расшифровать все письмо», — рассказывает Александр Гасников.

Описанный выше способ решения задачи стали называть марковским методом Монте-Карло — в честь выдающегося российского ученого Андрея Маркова и знаменитого казино в графстве Монако. Этот метод в некотором смысле игра в рулетку, которая случайно выбирает на каждом шаге то ребро графа, по которому пойдет блуждание.

«Выходит, если у вас есть страничка текста с иероглифами, вы можете с помощью предварительного анализа книжки Льва Толстого определить, что это за шифр. Это очень мощно звучит! Лет 15 назад этот метод произвел настоящую революцию в шифровании», — отмечает профессор.  

При чем здесь пасьянс?

История метода Монте-Карло зародилась в 1930-х годах в Италии благодаря физику-теоретику Энрико Ферми. Позже математики Джон фон Нейман и Станислав Улам развили эту идею. Последний экспериментировал с игральными картами. Улам хотел понять, какова вероятность того, что пасьянс сложится, если просто раскладывать его большое количество раз, а затем просто подсчитать число удачных исходов. По сути, в этом методе создается множество случайных событий и идет наблюдение за результатами. 

С появлением первых компьютеров метод Монте-Карло стал широко использоваться. Он применяется и по сей день в различных областях науки, позволяя упростить сложные задачи и сделать их более управляемыми.

История с расшифровкой писем и математическим методом не оставила школьников равнодушными. После лекции они буквально засыпали Александра Гасникова вопросами, а потом поделились с «Сириус(Журналом» ожиданиями от «Больших вызовов».

Артем Вороненко Фото: Пресс-служба «Сириуса»

«До этого я интересовался теорией вероятностей. Было интересно послушать про метод Монте-Карло. Понял, как это связано с языковыми моделями. Были и другие, более сложные примеры. Но в этом и состоит уникальность „Сириуса“. Здесь ты встречаешь людей, у которых можешь перенимать опыт и знания», — рассказал краснодарский школьник Артем Вороненко.

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

«Все делала сама: рисовала сцены, подбирала музыку с учетом авторских прав исполнителя, писала тексты. Теперь я приехала на программу, где буду заниматься проектом в направлении „Умный туризм“», — рассказала она.

Кристина Нетылева и Азами Эрадж Аъламджон Фото: Пресс-служба «Сириуса»

Азами Эрадж Аъламджон из маленького сибирского городка Урай активно участвует в проекте «Уралхима» — партнера Университета «Сириус».

«Компания использует VR-технологии для обучения своих сотрудников. Надев очки дополненной реальности, они в формате игры учатся работать с различным оборудованием, изучают технику безопасности и отрабатывают новые навыки. Я один из тех, кто создает такой тренажер. От „Больших вызовов“ жду новых задач», — отметил он.

Партнерами «Больших вызовов» в этом году выступают Газпромбанк, Курчатовский институт, «Генериум», Центральный банк России, Научно-технологический университет «Сириус», Всероссийский институт генетических ресурсов растений имени Н. И. Вавилова, Институт глобального климата и экологии имени Ю. А. Израэля, Океанографический институт имени Зубова, «Геоскан» и многие другие.

Важно, что по окончании программы совместную работу участников и компаний не сворачивают. Команды поддерживают связь и получают возможность продолжить работу над проектом. Итогом такого сотрудничества зачастую становятся прототипы устройств, научные статьи и готовые продукты.