Этюды для программистов

Эта задача иллюстрирует также важность документирования для будущей работы. Приведенный здесь алгоритм на самом деле разработан примерно за 6 месяцев до написания главы. Была формально доказана его правильность. Группа программистов, видевших и алгоритм, и доказательство, единодушно признали их совершенно безукоризненными. Но пока автор собирался сесть писать главу, какие-то жулики украли единственную копию алгоритма и доказательства (хотя трудно себе представить, для чего им эти бумаги). Пришлось потратить еще около 5 часов на восстановление первоначального хода мыслей; при этом снова была допущена логическая ошибка. Пусть же поразят компьютер этих жуликов вечные ошибки четности!

Литература

Кнут (Knuth D. E.). Estimating the Efficiency of Backtrack Programs. Mathematics of Computation, 29, 129, pp. 121—136, 1976.

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

Эппл, Хейкен (Appel К., Haken W.). Every Planar Map is Four Colorable. Bulletin of the American Mathematical Society, 82, 5, pp. 711—712, September 1976. Стин (Steen L. A.). Solution of the Four Color Problems. Mathematics Magazine, 49, 4, pp. 219—272, September 1976.

Иссяк еще один источник диссертаций. Эппл и Хейкен объявили о доказательстве истинности гипотезы о четырех красках. В момент написания данной главы доказательство циркулировало в рукописном виде, и несколько видных специалистов по комбинаторике считали, что, по-видимому, оно верно. К моменту выхода в свет нашей книги доказательство наверняка появится в математических журналах. Стин описывает метод доказательства и его значение для математики. ЭВМ интенсивно использовалась для разработки доказательства и для проверки 1936 случаев в окончательном варианте доказательства.

*Яглом И. М. Четырех красок достаточно. «Природа», 1977, № 6, с. 20—25.

*Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. — М.: Мир, 1979.

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

*Н. Вирт. Систематическое программирование. Введение. Пер. с англ. — М.: Мир, 1977. На наш взгляд было бы интересно испытать разные эвристики. Из п. 15 4 книги Н. Вирта читатель увидит, как можно механически получать программы, работающие по голой схеме перебора с возвратами.

* Партия переводчика. В 1978 г. был утвержден новый американский стандарт языка Фортран. Описываемый в нем язык получил название Фортран-77 (см. Катцан Г. Язык Фортран-77. Пер. с англ.— М.: Мир, 1982). Ознакомившись с приводимой ниже программой, читатель, разумеется, легко заметит новые возможности Фортрана. Поскольку программа получена прямолинейным переписыванием авторского варианта, трактовка новых возможностей не вызовет затруднений. По той же причине отсутствуют комментарии. Лишь два момента вызвали небольшие заминки при переписывании программы. Во-первых, в строке 141, видимо, допущена опечатка и вместо OR следует читать AND. Во-вторых, инструкции 232 и 237 GOTO 190 выполняют сразу две функции: завершают условную инструкцию и передают управление на начало цикла. Любопытно сопоставить их с инструкцией 239 GOTO 170, которой автор уделил немало внимания. Небезынтересно также сопоставить авторские замечания с новым вариантом программы (см. с. 254—256).

30. Сжатые строки, или... ПРОГРАММА УПЛОТНЕНИЯ ТЕКСТОВ

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

• Насколько сложны алгоритмы, необходимые для выполнения сравнений в словаре, какова сложность структур данных?

• Как долго придется со всем этим возиться?

• Работа алгоритма определяется наборами параметров. Как эти параметры выбрать?

• В какой степени коэффициент сжатия зависит от вариаций в уплотняемом тексте?

• Ради экономии памяти расходуется процессорное время. Когда можно считать, что овчинка стоит выделки?

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