Роман Душкин - Криптографические приключения: таинственные шифры и математические задачи

И отец прочитал нам целую лекцию о том, как некогда для славян составили азбуку, чтобы переписывать христианские книги, и это была глаголица. Потом появилась кириллица — она уже больше походила на современные буквы, но в те далёкие времена в языке были другие звуки, поэтому и букв в кириллице было больше. Постепенно кириллица преобразовывалась, а в XVIII веке появилось русское гражданское письмо, буквы которого выглядели в точности как современные, но в алфавите было четыре буквы, которых нет сейчас — эти пресловутые «и десятеричное», «ять», «фита» и «ижица». Отец даже вспомнил присказку гимназистов: «Ять, фита, ижица — розга к телу ближится».

Дело в том, что эти буквы обозначали звуки «е», «ф» и «и», а в древности они обозначали схожие, но иные звуки, просто с развитием языка в разговорной речи это различие постепенно пропало, а в письменной осталось. И школьникам приходилось просто зубрить слова, где использовались эти буквы, поскольку на слух различить их было невозможно. А буква «и десятеричное» (которая выглядит как латинская i), использовалась только в позиции перед гласными буквами, буквой «Й» и в слове «мир» в значении «Вселенная». А ещё на конце слов, оканчивающихся на твердую согласную, писался твёрдый знак. Это всё было наследие древних времён, когда буквы «Ь» и «Ъ» обозначали специальные гласные звуки.

В общем, это было действительно увлекательно. Мы не заметили, как наступил вечер. К этому времени нам стало понятно, что именно упустил отец, когда первый раз запускал свой генетический алгоритм. Я поехал проводить Катю домой, а папа остался. Когда я вернулся, он сказал:

— Я нашёл дореволюционный текст большого объёма. Роман «Преступленiе и наказанiе» Федора Михайловича Достоевскаго. Нравится мне это произведение, так что я нашёл его текст в старой орфографии. И уже посчитал на нём частоты. В общем, получилось неплохо, так что я оформил всё в новый код генетического алгоритма и запустил его на исполнение. Посмотрим, что можно найти за ночь.

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

Я попросил отца показать мне, что получилось, но на экране были видны только бессмысленные последовательности символов. Ни одного знакомого слова. Папа выгрузил весь журнал своей программы за ночь и попытался найти в нём хоть какие-то намёки на слова, но тщетно. Огромный файл был наполнен абсолютной чепухой. Как сказал отец, его алгоритм выдавал по несколько сотен вариантов в секунду, а это значит, что за ночь он создал порядка десяти миллионов вариантов. И ничего не было найдено.

Я спросил:

— А сколько вообще существует вариантов? Может быть, надо просто запустить перебор, если за десять часов работы просмотрено десять миллионов вариантов, то есть миллион вариантов в час?

Отец задумался, потом взял карандаш с листочком и набросал какие-то формулы. Затем что-то долго считал, делил и умножал. Наконец он сказал:

— Всего есть порядка 10 158 вариантов. Ты представляешь, сколько это? Очень много. Это в невообразимое число раз больше, чем число частиц в нашей Вселенной. Если бы мы просматривали даже миллиард вариантов в секунду, то на все ушло бы время, во много-много-много раз превышающее время жизни нашей Вселенной. Эта ситуация называется «комбинаторным взрывом», когда для небольшого объёма данных имеется очень большое количество вариантов. Такие задачи никогда не решаются полным перебором.

Я запутался в этих цифрах, но понял лишь то, что решить перебором не получится никак. Тогда я спросил:

— Ну а твои генетические алгоритмы чем помогут?

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

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

— А ты можешь дать мне частоты букв из старого алфавита? Хочу сравнить их с частотами современных букв русского языка.

Он нажал на своём ноутбуке несколько клавиш, на экране появились столбцы букв и цифр непременными зелёными буквами на чёрном фоне. Это называется «консоль», и отец использует для решения любой задачи. Я взял блокнот и принялся переписывать данные. Вот что у меня вышло:

После этого я сфотографировал на планшет ту страницу, где были выписаны частоты букв современного русского языка, и стал сравнивать фотографию с новой таблицей. Действительно, было много различий, хотя не таких уж и больших. Для удобства я решил нарисовать гистограмму, на которой были бы отложены частоты каждой буквы для старого и нового алфавитов. Я закрыл глаза и припомнил, как делал это в своём наведённом сне. Потом сел рисовать, и у меня получилась такая красивая гистограмма:

За своим занятием я не заметил, как приехала Катя. Она тихо стояла надо мной и смотрела на мои упражнения. Потом сказала:

— Ты точно учишься в пятом классе?

Я поднял на неё глаза и ответил:

— Ты ведь уже познакомилась с моим папой. Мы с ним давно занимаемся всякими науками.

Катя вздохнула, а потом спросила:

— А что это за график?

— Это гистограмма, которая показывает распределение частот букв в старой орфографии. Помнишь, когда я разгадал твою шифровку, мы применяли частотный анализ для подбора букв. Так вот тут то же самое. Папа нашёл довольно большой текст, примерно один миллион букв, посчитал в нём количества и частоты всех букв, которые в него входят…