1. Подстановки. Подстановочные шифры

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

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

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

Не будем сейчас останавливаться на недостатках и достоинствах обоих способов с точки зрения надежности защиты от врагов (много примеров приведено в художественной литературе), а перейдем ближе к суперкомпилятору.

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

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

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

Напишем алгоритм шифрования для первого способа. Пусть функция называется Perm1, она имеет два аргумента - шифр (e.P) и строка символов (e.S), которую надо зашифровать. Договоримся шифр записывать последовательностью скобок, в каждой из которых содержатся пары символом - что на что надо заменять. Формат обращения пусть будет такой:

<Perm1 (e.P) e.S >

Программу Perm1 можно написать так:

Если замена не указана, то символ остается без изменения.

Отметим, что в этом примере мы сознательно написали алгоритм без учитывания эффективности его выполнения, а именно шифр многократно дублируется. Мы увидим, как и что суперкомпилятор сделает в этом случае. В качестве самостоятельного упражнения Вы можете попробовать другие варианты программы.

Если суперкомпилятор получит задание

<Perm1 ( ( 'ab' ) ( 'bc' ) ( 'ca' ) ) e.S > ;

то он построит программу

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

Этот пример типичен для суперкомпилятора. В случае общего алгоритма при некоторых фиксированных исходных данных возможно использование информации об этих данных. Если возможны некоторые предварительные вычисления, то суперкомпилятор делает эти вычисления.

При задании шифра в примере Perm1 мы явно указывали парами символов нужные замены. Это соответствует записи подстановки в виде двух строк в курсе алгебры высших учебных заведений. Имеется другой способ записи подстановки - в виде произведения независимых циклов. В каждой скобке указывается циклическая цепочка замен.

Например, подстановка (123)(45) означает, что 1 заменяется на 2, 2 - на 3, 3 - на 1, 4 - на 5, 5 - на 4. Если символ не указан, то он не меняется. Для программы Perm1 последнюю подстановку придется записать так: (12)(23)(31)(45)(54).

В этом параграфе предлагаются две небольшие программы с подстановками : perm.ref и perm1.ref. Вторая соответствует программе в тексте этого параграфа, первая работает с подстановками, записанными в виде произведения циклов. Любопытно, что суперкомпилятор для обоих вариантов строит одинаковые результирующие программы, поэтому мы сейчас прокомментируем демонстрационные пуски для программы perm.ref. Для второй программы надо изменить задания на суперкомпиляцию (MST-схемы), т.е. задать подстановку в виде пар символов.

Подготовлено пять примеров. Количество примеров каждый может намного увеличить.

Пример 1. (MST-схема perm1.mst и результирующая программа r-perm1.ref). Соответствует примеру в тексте этого параграфа, только заменяются не буквы a, b, c, а цифры 1, 2, 3.

Пример 2. (perm2.mst , r-perm2.ref). Чуть более сложные замены.

Пример 3. (perm3.mst , r-perm3.ref). В задании на суперкомпиляцию можно задавать любую комбинацию используемых функций. Здесь происходит суперпозиция трех функций Perm.

Пример 4. (perm4.mst , r-perm4.ref). Здесь в заменах указываются не конкретные символы, а переменные sa, sb. Суперкомпилятору приходится сравнивать заменяемый символ с неизвестными символами sa, sb.

Пример 5. (perm5.mst , r-perm5.ref). Суперпозиция двух обращений к Perm с переменными символами замен. Возникают девять случаев из-за того, что неизвестные символы могут совпадать. На основе этого примера возможны многочисленные эксперименты.

Примеры этого параграфа являются обобщениями классических примеров с функциями Fab , Fbc.

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

УПРАЖНЕНИЯ.

1. Попробуйте в задании на суперкомпиляцию ничего не специализировать, т.е. указывать <Perm e.1> .

2. Попробуйте суперпозицией функций получать тождественную функцию.

3. Реализуйте равенство (1b)(123)(1b) = (23b) или аналогичные, используя алгебраические свойства подстановок.

4. Суперпозиции (sa sb)(sb sc), или (sa sb)(12), или (sa sb sc)(sb sc sd) и множество других, на что хватит фантазии.

5. Предыдущие примеры для второго варианта (Perm1).