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

И отец довольно подробно рассказал нам, что такое генетические алгоритмы. Оказалось, что они действительно имеют отношение к генетике, так что мой вопрос был вполне резонным, но сами по себе они исполняются на компьютере и помогают поиску решения в плохо описанных областях.

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

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

Всё это было довольно сложно, пока папа рассказывал о генетических алгоритмах абстрактно. Катя уже начала зевать, но тут папа резко встал и сказал:

— А теперь применим эти новые знания к нашей задаче — дешифровке старой тайнописи. Кирилл, как ты считаешь, что должно быть «генами» в нашем случае?

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

— Хорошо. Вот смотрите. У нас есть зашифрованное послание, в котором практически все числа встречаются одинаковое количество раз. Надо найти такое соответствие этих чисел буквам русского алфавита, чтобы итоговые частоты появлений букв были как можно ближе к эталонному значению, которое мы знаем. Понятно?

Мы с Катей одновременно покачали головами. Это действительно было трудно. Отец вздохнул и попытался в третий раз:

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

Теперь мы кивнули. Это как раз было просто. Отец продолжил:

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

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

Отец вздохнул и ответил:

— Но я же сказал, что это заняло бы у нас много-много веков, даже если бы мы сумели просматривать по одному варианту в секунду без перерыва на сон и обед. А компьютер сможет оценивать миллионы вариантов в секунду без нашего вмешательства. Итак, теперь есть идеи, что представляет собой ген в нашем случае?

Катя подняла руку, и отец кивнул ей. Она заявила:

— Я думаю, что ген в нашем случае — сопоставление чисел и букв.

Отец похвалил её, но сказал, что это не совсем так. Геном является одно сопоставление между числом из шифровки и буквой. А то, что назвала Катя, то есть весь набор таких сопоставлений, — это одна особь, которую можно подвергнуть отбору. Критерием будет близость частот к эталонному варианту.

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

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

— Ладно, на сегодня хватит. Давайте я займусь программированием, а вы катайтесь на велосипедах и изучайте окрестности.

Так и решили. Мы с Катей поехали к тёте Кате, выпили у неё по стакану простокваши и отправились по Конторской улице до самого конца. Честно говоря, я был немного напряжён: наведённая память усиленно мне подсказывала, что это опасно. Но это была реальность, а потому я решил проверить, что же там на самом-то деле. Кате я ничего не сказал, поэтому она ехала весёлая и о чём-то болтала. Я же был погружён в свои мысли.

Мы доехали до того места, где по моим воспоминаниям должно было быть лесничество. Там действительно были какие-то старые дома, не похожие на жилые. Но в них давно никто не работал: окна были заколочены досками, всё заросло бурьяном. Конторская улица вела в лес, и здесь дорога действительно расходилась на три стороны. Как я помнил, мы с Марком шли вдоль ручья, когда наткнулись на то ужасное место. А ручей был слева, так что надо было повернуть на левую дорогу. Мы так и сделали.

Буквально через пару сотен метров показался ручей. Я остановился и сказал Кате, что здесь надо оставить велосипеды и пройтись по лесу вдоль ручья. Она спросила зачем, но я не мог объяснить.

Мы стали продираться по зарослям вдоль Раёва. Лес здесь был не то чтобы дремучий, но около ручья растительности было много. Мы шли и шли, и я действительно стал чувствовать себя первооткрывателем. Правда, никаких оврагов мы не обнаружили — ручей просто тёк по лесу. Ничего похожего на то жуткое место, которое, по словам отца, навелось из его древних страхов.

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

Мы ещё покатались, доехали до Гаретого, проверили наш плот, потом съездили на Кошеляевский пруд за школой и вернулись к тёте Кате. Она нас немного поругала, что мы не приехали к обеду, и упомянула, что мой отец тоже не приезжал. Это было странно. Я поел и поехал проведать папу. Интересно, что это он себе позволяет.

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

Из дневника Кирилла: