Битнер, Рейнгольд (Bitner J. R., Reingold E. M.). Backtrack Programming Techniques. С ACM, 18, 11, pp. 651–656, November 1975.

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

Ope (Ore О.). The Four Color Problem. Academic Press, New York, 1967.

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

* Ершов А. П. Введение в теоретическое программирование. — М.: Наука, 1977.

* Абрамов С. А. Математические построения и программирование. М.: Наука, 1978.

* Харари Ф. Теория графов, гл. 12. Пер. с англ. — М.: Мир, 1973.

Известно вам или нет, но с недавних пор еще одно тяжкое бремя свалилось с плеч человечества. Заботу о создании и размещении опечаток в тексте взяли на себя компьютеры. Там, где раньше линотипы отливали горячий свинец в строки, теперь небольшие, вполне доступные по цене компьютеры методами фотонабора выдают нескончаемые потоки готовых текстов. Жаль только, что с появлением новых эффективных методов уходит очарование доброго старого времени. Ну какой, скажите, интерес выискивать опечатки в воскресном номере Нью-Йорк Таймс, в которых и заключается весь юмор этого обширного собрания важных скучностей, если вы знаете, что компьютер способен делать ошибки в сотни раз быстрее, чем человек? Такова цена, которую приходится платить за прогресс.

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

Система подготовки публикаций состоит из четырех компонентов. Во-первых, необходима хорошая файловая система, в которой можно хранить готовящиеся и архивные текстовые файлы. Обычно память для хранения файлов предоставляется операционной системой, но известен случай, когда в качестве такой памяти использовался шкаф для перфокарт в кабинете автора. Конечно, перфокарты не самый практичный носитель, когда речь идет об операциях над большими объемами информации, например при издании газет. Во-вторых, нужен редактор текстов, для того чтобы вносить изменения и поправки в файлы перед выдачей на печать. Редакторы текстов также имеются, в большинстве операционных систем, но может понадобиться специальный редактор издания, обладающий именно теми возможностями, которые требуются при подготовке публикаций. Третий элемент — форматор, который умеет размещать заголовки, выбирать размер страницы, располагать материал в таблицах, выделять абзацы и т. п. Форматор работает с такими элементами текста, как слова, предложения, абзацы, т. е. уже на том уровне, на котором текст воспринимается человеком. Наконец, имеется программа-наборщик, которая преобразует форматированный текст в его образ на внешнем носителе. Работа этой программы связана в первую очередь с особенностями шрифтов, физическими размерами, командами выводного устройства, отдельными литерами и тому подобными вещами. Программа-наборщик, так же как и оператор линотипа, готова выдать на печать любой вздор, лишь бы он поместился в отведенное ему место. Функционально файловая система и редактор текстов заботятся о содержании текста, а форматор и наборщик — о том, как он будет выглядеть. Этот этюд посвящен форматированию[8] текстов.

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

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

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