Развитие темы. Наиболее очевидное расширение — это изменение множества цифр, из которых составляется код, или количество цифр в коде. Более развитая версия великого комбинатора допускает коды из пяти цифр от 1 до 8. Слишком большое значение любого из двух параметров может привести к непомерному росту времени работы, однако ни один из алгоритмов не зависит сколько-нибудь существенно от чисел 6 и 4. Программа без всякого труда могла бы читать объем словаря (число различных цифр) и длину кода в качестве исходных данных и соответствующим образом изменять свои алгоритмы анализа.
Алеф0 (Aleph0). Computer Recreations, Software — Practice and Experience, 1, pp. 201–204, 1971.
Mastermind. Invicta Plastics, Ltd. Oadby, Leicester, England.
Описывается исходная игра. Она сильно похожа на некоторые традиционные игры; вся Англия увлечена этой игрой из-за ее простоты.
Кнут (Knuth D. E.). The Computer as Master Mind. He опубликовано, 1976.
Кнут утверждает, что путем исчерпывающего анализа различных случаев можно показать оптимальность его стратегии в указанном выше смысле. Однако останется ли она оптимальной при изменении объема словаря и длины кода? И какая стратегия будет оптимальной, если мы стремимся свести к минимуму ожидаемое число проб, а не максимальное?
Таненбаум (Tanenbaum A. S). Computer Recreations: A Heuristic for Playing Jotto, Software — Practice and Experience, 3, pp. 397–399, 1973.
В обеих статьях из журнала Software — Practice and Experience рассматриваются игры, аналогичные великому комбинатору; описываются реальные программы и предлагаются некоторые стратегии машинной игры. Было бы, наверное, очень интересно организовать турнир между различными эвристиками.
Уэллс (Wells D.). Mastermind. Games and Puzzles, 23, pp. 10–11, March/April 1974.
Games and Puzzles — широко известный английский журнал, посвященный играм, головоломкам и всевозможным интеллектуальным развлечениям. По стилю он далек от математического издания: в нем вы скорее найдете исторический, тематический, эстетический и стратегический разбор абсолютно любого приятного времяпрепровождения (ну, почти любого), не требующего ничего, кроме обыкновенного стола. Постоянно публикуются новые и старые игры. А из головоломок вы почерпнете немало глубоких алгоритмических проблем. Короче говоря, это весьма ценное приобретение для любителей убить время.
24.
Секрет фирмы
или Математический подход к раскрытию шифров
Представьте себе такую ситуацию. Благодаря выдающимся профессиональным познаниям и незаурядным программистским способностям вас выдвинули на должность руководителя большой группы сотрудников, занимающихся разработкой суперновейшего и пока еще секретного Мини-компилятора для ЭВМ УМ-1 (см. гл. 27 и 25). Как-то раз, уходя со службы около часу ночи (руководитель должен подавать хороший пример), вы замечаете торчащий в дверях измятый клочок бумаги (содержание которого воспроизведено на рис. 24.1). Сначала вы решаете, что это запись содержимого памяти машины, и уже собираетесь выбросить бумажку. Но, присмотревшись повнимательнее, замечаете, что буквы собраны в группы по пять, — очень странно для УМ-1. Что бы это могло быть?
ЖНФЖП ЕЕЫШВ ЛПЖАТ ГФБЦМ КЖЬЗА ЮЪИВУ ЩЖРСЮ БЬЬКЬ ЫЕСУУ ЦТЮБШ УНЭДДО ЭЭШЮЗ УЬЕКН АУЕЫЩ ШЖРЬЙ ЛЮПКН ДЙЯГЭ ЪНЫГЖ ОУШИШ УФГБР ШМАГВ ВУВОС ЗХЧИУ ГНЛАЯ ЬЬКИЯ РЦЖРЫ АХЪБИ ЖГЭЯЦ СЪУЫФ ЯРМЭФ ЧФЬЩС ЬФШВЕ ОМКТИ МБЭВЪ КФХЙЦ ХНЪЮЪ МФЛБИ МРУЛМ ЯЗФЧЪ ЪЧЗНК ЗНИВЯ НШГЛЩ ИЛЗНФ ФУЖКН ДЙЯГЭ ЕУЮЛЛ ЮЖНЯИ ЕМДЙШ ГЯУГВ ЦФЩВЮ МФАГЯ ВХМЭВ ВФПГФ ФЖККГ ЦМЛЫБ ШМПУЕ ШЖЯЯЮ ЯРЧВЪ ЖУПВМ КЛЫЭС ЭЧИРЫ ГЫЩЗЗ ЗКЖЛЕ ШВРЪЧ ЪААЖЗ ДХЪФС БРНМЪ КЫБЪФ УНЦЮБ ТЖУНЯ ЕШИМУ КФВГВ ГЧМЗВ ЗРВМЪ ЪЕЕТО ЯЦБЖГ ВИЖМД КЗЗПА ФЯВНР ЫГЮЩЭ ЯЫДОЪ ЧНГВЫ АХЪВЛ НШАПВ ЧОЬОЙ КЮАШО КЗЛЩУ ШЯРНЗ ГХЛТЮ ЖЫШШГ ППЬЫШ АЬФМА ФЕЙЗА ЙШЕУЭ ЖЛЗИЗ НЖККР ЦЯДЧК НДЙЯГ ЭБФЬА ВБЭКЗ ФКЫТВ ЛЕЪЭЯ ЛЭЩЗН ФХГЧК ТКЫЮЗ ЗЪУЖА ПВЧОЬ ОЙКЕС ЛЗАЮЪ ИВУНЫ БКЗВЯ ЪГОСЩ ЛБЬГМ ЯВЗГЬ КШЪГЙ ЕНПСМ ЭВГОГ ЧСОРГ ЩОЦМВ ДГЩКЧ ЮЗВЗК ЦЧЯРЧ ВЪЖФЫ ЕЛЖАЪ УССХР УОЬЫЕ ЙГЫОТ УЕАГЖ ГЫСЩИ ЯРВТЮ ДЖНЛГ ЦМЗЬЪ ЯИЦТР ЕМИКЦ ЩВЦОР ЛХМХЖ БРЬПУ ГВЯРЬ ПМЯЖЖ РЧПШЪ ЧУВГЧ СЕЕГЦ ЬПЗДМ ОЬОЧЗ КВУФЯ УПОХЪ ГЪЭЯЖ ВЖФ
Рисунок 24.1. Таинственная записка, найденная в вычислительном центре. Случайное вкрапление русских слов, например ШИШ или ОЙ, по-видимому, ничего не означает. Но обратите внимание на повторение сочетаний ЗАЮЪИВУ, ЬЬК, других коротких сочетаний, а особенно на повторяющуюся группу букв КНДЙЯГЭ.
Снова возвращаетесь в свой кабинет, пытаясь решить загадку. Бумага отменная, слегка пахнет мускусом; почерк явно женский и веет от него этаким французским шармом. Теперь, по здравом размышлении, новая сотрудница мисс Хари начинает казаться вам, пожалуй, немножко слишком экзотичной. Ее французский акцент, неизменное черное платье для коктейля, нитка черного жемчуга, подчеркивающая декольте, и этот будоражащий запах мускуса, наполняющий комнату, когда она туда входит… Она говорит, что работала раньше в региональном вычислительном центре Мак-Дональда в Киокаке. Что-то тут не так. Подождите… Неужели мисс Хари шпионит в пользу знаменитой французской фирмы И Бей Эм? А эта записка — шифровка, в которой все секреты вашего новейшего чудо-компилятора? Чтобы уличить мисс Хари, записку нужно расшифровать. Но как? Может, обратимся за помощью к компьютеру?