Методы Кристобаля Хунты

Исходный вариант статьи (Н. Н. Непейвода, «Методы Кристобаля Хунты») опубликован в журнале «Потенциал».

— Голубчики, — сказал Фёдор Симеонович озабоченно, разобравшись в почерках. — Это же проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения.

— Мы сами знаем, что она не имеет решения, — сказал Хунта, немедленно ощетиниваясь. — Мы хотим знать, как её решать.

— Как-то странно ты рассуждаешь, Кристо… Как же искать решение, когда его нет? Бессмыслица какая-то…

— Извини, Теодор, но это ты очень странно рассуждаешь. Бессмыслица — искать решение, если оно и так есть. Речь идёт о том, как поступать с задачей, которая решения не имеет. Это глубоко принципиальный вопрос…

Аркадий и Борис Стругацкие. Понедельник начинается в субботу

В чём прав и в чём неправ Кристобаль Хозевич?

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

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

Что же делать? Решать! Но решать, зная, а не забывая, что она неразрешима. Намеренное либо самоуверенное невежество в данном случае обязательно приведёт к краху. В своё время автор слышал доклад выдающегося математика Бориса Авраамовича Трахтенброта «Как решать неразрешимые задачи?» (1979 год, город Телави). Когда через пару лет автору пришлось составлять обзор по семантике языков программирования, он натолкнулся на французскую статью под лихим названием «Indecidable? Sur pas!» («Неразрешимо? Наплевать!») и стало ясно, что такие вещи, как решение неразрешимого, формализация неформализуемого и прочее типичны для человеческой деятельности, как и замечали братья Стругацкие устами Кристобаля Хунты.

Первый способ: заранее сделать всё правильно

Допустим, что вам ставится задача построить программу, которая будет проверять, зациклятся ли программы, создаваемые при помощи новой системы программирования для каких-то частных приложений (например, нового языка скриптов для собачьих ошейников). Тогда нужно прежде всего понять, какого же сорта программы будут писать на данной системе, поскольку, как говорилось в прошлой статье, поставленная задача в общем случае неразрешима. Если программы не слишком сложные, достаточно всего-навсего выбросить из создаваемого мини-языка программирования циклы while и рекурсивные процедуры (которые, если явно не протестовать, системные программисты ради общности и крутизны обязательно вставят, поскольку «иначе система не будет универсальной»). Тогда всякая программа будет заканчивать работу (просто по построению не даём мы ей возможности зациклиться!). Если системщики вопят, а начальство смотрит на них как на полубогов, то заставьте их хотя бы выдавать для программистов длинные предупреждения типа:

Использование цикла while может привести программу к зацикливанию.
Уверены ли вы, что нужно использовать цикл while?
(ответ No по умолчанию)

А после ответа Yes вдобавок ещё (в лучших традициях игр, из которых вам хочется выйти побыстрее, чтобы шеф, либо мама, либо преподаватель не застукали, а вам задают кучу вопросов):

В большинстве случаев то, что может сделать цикл while, может cделать и цикл for.
Не хотите ли вы использовать цикл for?
(ответ Yes по умолчанию)

И как финальный аккорд нечто типа:

ОК. Ваша программа помечена как не сертифицируемая на корректность.
Желаем успехов.

Приведённое решение является частным случаем трёх общих принципов.

Принцип 1

Если нельзя решить задачу в полном объёме, разберитесь, что же на самом деле нужно, и решите частную задачу.

Если задачу можно решить в полном объёме, тем не менее подумайте, какого частного случая на самом деле достаточно, и тогда ваше решение станет намного лучше.^[1]

Принцип 2

Если нечто нужно гарантировать для решения, лучший способ — обеспечить это с самого начала, ещё в ходе построения программы. Потом даже проверить будет трудно, а если ещё вдобавок выяснится, что требование нарушено, то переделывать будет ещё труднее, чем писать хорошо сразу.^[2]

Принцип 3

Если вам не удаётся заблокировать неразумное решение, при помощи технических и бюрократических частностей сделайте так, чтобы пользоваться им было как можно более противно.^[3]

Этот способ решения неразрешимых задач можно проиллюстрировать следующим рисунком.

То, что за забором, — наши культурные растения, а снаружи все считается сорняками и там мы просто не сажаем.

Второй способ: ограничить задачу

Приведённый выше принцип 1 сразу же приводит к ещё одному методу решения, на самом деле неразрывно связанному с предыдущим, но не сводящемуся к нему. В частности, если те же программы для собачьих ошейников уже написаны, либо пишутся законченными хакерами, которым хоть кол на голове теши, но от крутизны они не откажутся, то остаётся посмотреть на данную конкретную совокупность программ и строить алгоритм, который будет работать именно на ней^[4]. Главное, чтобы ваш алгоритм успешно искал ошибки в конкретных программах, а то, что он в общем случае некорректен, стоит рассматривать как неизбежное зло.

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

Давление повторно не измерялось перед очередной его проверкой в строке 1221.
Ваша программа зацикливается.

Схематически можно изобразить такой способ работы на следующем рисунке. То, что за колючей проволокой, по определению считается плохим и отстреливается.

Третий способ: работать неправильно

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

Схематически можно изобразить такой способ работы на следующем рисунке. Здесь граница проведена попроще, но возле её могут быть ошибки в две стороны.

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

Если цикл встречается внутри рекурсии, либо рекурсия внутри цикла, то процедура написана некорректно.

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

Четвёртый способ: работать наугад

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

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

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

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

Проблема

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

Судья сообщает игрокам минимально необходимую информацию о ходе. Он произносит примерно такую последовательность фраз в ответ на попытки одного из игроков сделать ход (черные это были или белые, догадайтесь сами):

— Ход невозможен.

— Ход невозможен.

— Ход невозможен.

— Ход сделан. Взята ладья на поле e1. Пешка превратилась в ферзя. Шах.

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

Король-всезнайка против ферзя

Король знает всё, а король и ферзь играют против него по правилам стратегических шахмат. Дать мат.

Король-всезнайка против ладьи

Король знает все, а король и ладья играют против него по правилам стратегических шахмат. Дать мат.

Во второй задаче достаточно просто дать алгоритм и составить программу, которая будет случайно матовать короля таким образом, что с вероятностью 1 в конце концов его заматует (но теоретически король, если он не только всезнайка, но ещё и прорицатель, знающий будущее, может бесконечно избегать мата). Есть и алгоритм, матующий с гарантией, но он намного сложнее и в разработке, и в реализации.

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

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

---

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

Дальнейшее чтение

1. С. Уэллин. Как не нужно программировать на С++. Питер, 2004.

Примечания

^  Данный принцип нельзя применять на практике традиционных олимпиад по программированию. Там задачу обязательно нужно решать в полном объёме, так, чтобы она работала при всех значениях допустимых параметров. Это лишь один из многих случаев, когда практика олимпиад приводит к развитию навыков, которые не просто бесполезны, а прямо вредны для последующей практической деятельности специалиста.

^  Это на самом деле общий принцип, применимый отнюдь не только в программировании. Так же стоит поступать и в жизни. Стоит помнить, что «умный человек — тот, кто с честью выходит из такой ситуации, в которую мудрый не попадает».

^  Последний принцип (с заменой «неразумное» на «ненужное мне, любимому») успешно используют бюрократы в борьбе против всего лучшего; иногда нужно перенимать их методы, поскольку лезть в лобовую атаку — почти всегда худшее решение.

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