agent007.htm
Агент007
Рассмотрим школьную задачу, которая лет десять назад была опубликована в журнале "Квант" на страничке для младших школьников. Какое там приводилось решение - не помню, но я эту задачу использую на занятиях со студентами 2 курса, когда по алгебре проходим тему "подстановки". На этой задаче демонстрируются все основные алгебраические понятия.
Задача прекрасная, так как будем решать ее с помощью суперкомпилятора. Задачи подобного типа я отношу к "рекурсивным" задачам - условие закручено само на себя.
Задача.
Шеф разведки, где служит Агент007, в целях полной конспирации и надежности придумал схему взаимной слежки своих агентов.
Агент001 следит за тем агентом, который следит за Агентом002.
Агент002 следит за тем агентом, который следит за Агентом003.
Агент003 следит за тем агентом, который следит за Агентом004.
Агент004 следит за тем агентом, который следит за Агентом005.
Агент005 следит за тем агентом, который следит за Агентом006.
Агент006 следит за тем агентом, который следит за Агентом007.
Агент007 следит за тем агентом, который следит за Агентом001.
Все шло нормально, пока на службу не пришел Агент008. Никак у шефа не получается составить подобную схему взаимной слежки для восьми агентов.
Задача 1. Какая схема взаимной слежки была сначала (за кем следит каждый агент)?
Задача 2. Почему при 8 агентах у шефа ничего не получается ?
Решение с помощью суперкомпилятора.
Возьмем программу из первого параграфа "Подстановки. Подстановочные шифры" Пособия по суперкомпиляции.
Perm {
(e.perm) s.a e.string = <PermS s.a e.perm>
<Perm (e.perm) e.string>;
(e.perm) = ;
}
PermS {
s.a (s.a s.b) e.2 = s.b;
s.a (s.c s.b) e.2 = <PermS s.a e.2>;
}
Eq {
(s.a e.1) (s.a e.2) = <Eq (e.1) (e.2)>;
( ) ( ) = T;
}
|
Программа осуществляет шифрование текста e.string в соответствии с заданным шифром e.perm
Взаимная слежка агентов - это как бы шифрование, запишем неизвестную слежку в виде
( ("001" s.1) ("002" s.2) ("003" s.3) ("004" s.4)
("005" s.5) ("006" s.6) ("007" s.7) )
|
Агент001 следит за неизвестным агентом s.1 и так далее.
По условию задачи, если мы дважды произведем это шифрование (дважды - это сначала один раз, затем еще раз), то это все равно, что один раз применить "последовательный" шифр
("001" "002") ("002" "003") ("003" "004") ("004" "005")
("005" "006") ("006" "007") ("007" "001")
|
Теперь по условию задачи составляем задание на суперкомпиляции (двойное применение неизвестного шифра равняется известному шифру)
<Eq
(<Perm ( ("001" s.1) ("002" s.2) ("003" s.3) ("004" s.4)
("005" s.5) ("006" s.6) ("007" s.7) )
<Perm ( ("001" s.1) ("002" s.2) ("003" s.3) ("004" s.4)
("005" s.5) ("006" s.6) ("007" s.7) )
"001" "002" "003" "004" "005" "006" "007" >>
)
(<Perm ( ("001" "002") ("002" "003") ("003" "004") ("004" "005")
("005" "006") ("006" "007") ("007" "001") )
"001" "002" "003" "004" "005" "006" "007" >
)
>;
|
Подчеркну, что я здесь ничего не программирую, записываю условие задачи - и только. Полученное никак не годится для каких-либо осмысленных пусков на счет при обычном, без использования суперкомпилятора, программировании.
Действительно, сейчас имеется предикат, принимающий значение истина на ответе к задаче, и ложь (отождествление невозможно) - на не ответе. Если я знаю ответ, то могу пустить программу на счет и получу на экране истину, если не знаю ответа, то тоже могу пустить программу на счет и получить на экране, скорее всего, ложь.
С использованием суперкомпилятора все осмысленно.
Суперкомпилирую то, что собираюсь суперкомпилировать, и получаю следующую остаточную программу
* InputFormat: <Agent0071 s.1 s.2 s.3 s.4 s.5 s.6 s.7 >
Agent0071 {
"005" "006" "007" "001" "002" "003" "004" = T ;
}
|
Теперь записываю ответ
Агент001 следит за Агентом005,
Агент002 следит за Агентом006,
Агент003 следит за Агентом007,
Агент004 следит за Агентом001,
Агент005 следит за Агентом002,
Агент006 следит за Агентом003,
Агент007 следит за Агентом004.
Первая задача решена, переходим к решению второй задачи для 8 агентов. Составляю аналогичное задание на суперкомпиляцию, суперкомпилирую и получаю
************************************************************** * Sorry, your program to be transformed has a semantic error. ************************* The End **************************** |
Это и означает, что вторая задача решений не имеет.
Алгебраическое решение.
Запишем искомую схему взаимной слежки в виде подстановки а на 8 символах. По условию задачи a^2 = ( 1 2 3 4 5 6 7 8 ) - запись подстановки в виде одного цикла.
Квадрат любой подстановки является четной подстановкой, но подстановка, которая получилась - ( 1 2 3 4 5 6 7 8 ) - нечетная. Противоречие показывает невозможность решения второй задачи.
В случае первой задачи имеем a^2 = ( 1 2 3 4 5 6 7 ) = b.
Подстановка b обладает свойством b^7 = e - тождественная подстановка, значит,
b^8 = b, при этом b = a^2, поэтому можно взять a = b^4 = ( 1 5 2 6 3 7 4 ).
Ответ :
Агент001 следит за Агентом005,
Агент002 следит за Агентом006,
Агент003 следит за Агентом007,
Агент004 следит за Агентом001,
Агент005 следит за Агентом002,
Агент006 следит за Агентом003,
Агент007 следит за Агентом004.
Дополнение для тех, кто вникнет в суть происходящего и скажет, что суперкомпилятор просто перебирает в этой задаче конечное количество вариантов и выдает в ответе единственный подходящий.
Правильно, в этой задаче в самом деле конечное количество вариантов. Но предложенная технология годится и в случае бесконечных исходных данных. В качестве примеров можно привести гусей, а так же миссионеров и каннибалов - там суперкомпилятор разбирается с бесконечностями.
Хорошо, пусть будет конечное число вариантов, но где я об этом сообщал суперкомпилятору ?
Если относить эту задачу к обычным переборным, то давайте попробуем организовать такой перебор на каком-либо другом из известных языков программирования ! Семь вложенных друг в друга циклов, которые потом надо будет изменять на восемь циклов, или упорядочить лексикографически варианты.
Продолжение (вторую серию) можно посмотреть в agent2.htm , избранные места из переписки с друзьями приведены в letters.htm .