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

Эппл, Хейкен (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 был рассмотрен полезный алгоритм, предназначенный для сжатия текстовой информации. И работай вы программистом, скажем в библиотеке или в газете, то были бы вправе ожидать, что шеф выложит вам на стол одиннадцатую главу и предложит попытаться подключить описанный в ней алгоритм к уже работающей системе. А поскольку кажется вполне правдоподобным, что этот алгоритм мог бы обеспечить значительную экономию памяти, то и задача выглядит на первый взгляд привлекательной. Сомнения приходят позже.

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

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

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

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

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

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

• Можно ли в исходном проекте предусмотреть возможность внесения изменений и дополнений без больших переделок?

• И наконец, сколько времени стоит потратить на эту задачу, чтобы считать, что она выполнена достаточно хорошо?

Примерно те же вопросы должны возникнуть и у начальника, да еще наряду с сомнениями, тот ли вы программист, который осилит поставленную задачу. Тем не менее, нельзя допустить, чтобы сомнения вас парализовали. Энергично беритесь за дело, невзирая на отдельные трудности (но и не забывая о них) и сконцентрируйте все свои усилия на тех вопросах, которые кажутся легко разрешимыми. В данной работе мы в свою очередь испробуем, прежде всего, программу, использующую простые структуры данных и алгоритмы. А после того, как программа заработает правильно, постараемся ее улучшить, внося различные усовершенствования. Вполне может так случиться, что свойства программы будут зависеть от неких параметров, поэтому постараемся сделать так, чтобы их можно было легко менять; в первом варианте программы, однако, мы будем просто пробовать возможные значения. Для того чтобы исследовать, как влияют на результаты вносимые в программу изменения, исходная информация или параметры программы, мы будем разрабатывать ее как автономную, не являющуюся частью какой-либо большей системы,— и тогда эффективность интересующей нас программы не будет скрыта за накладными расходами ее окружения.

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