Предисловие

В последние годы признано, что умение создавать программы для вычислительных машин является залогом успеха во многих инженерных проектах и что дисциплина программирования может быть объектом научного анализа и допускает систематическое изложение. Программирование из ремесла превратилось в академическую дисциплину. Первые выдающиеся результаты на этом пути получены Дейкстрой (Е. XV. ПуклЫа) и Хоором (С. А Я. Ноаге). «Заметки по структурному программированию» Дейкстры [ 1 ] позволили взглянуть на программирование как на объект научного анализа, бросающий вызов человеческому интеллекту, а слова структурное программирование дали название «революции» в программировании. Работа Хоора «Аксиоматические основы программирования» [2] продемонстрировала, что программы допускают точный анализ, основанный на математических рассуждениях. И обе статьи убедительно доказывают, что многих ошибок в программах можно избежать, если программисты будут систематически применять методы и приемы, которые ранее применялись лишь интуитивно и часто неосознанно. Эти статьи сосредоточили внимание на построении и анализе программ, или, точнее говоря, на структуре алгоритмов, представленных текстом программы. При этом вполне очевидно, что систематический научный подход к построению программ уместен прежде всего в случае больших, непростых программ, работающих со сложными наборами данных. Отсюда следует, что методология программирования должна включать в себя все аспекты структурирования данных. В конце концов, программы суть конкретные формулировки абстрактных алгоритмов, основанные на конкретных представлениях и структурах данных. Выдающийся вклад в наведение порядка в огромном разнообразии терминологии и понятий, относящихся к структурам данных, сделал Хоор в статье «О структурной организации данных» [3]. В этой работе продемонстрировано, что нельзя принимать решения о структуре данных без учета того, какие алгоритмы применяются к данным, и что, обратно, структура и выбор алгоритмов часто сильно зависят от стуктуры обрабатываемых данных. Короче говоря, задачу построения программ нельзя отделять от задачи структурирования данных.

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

На протяжении всей книги, включая главу 1, мы следуем теории и терминологии, развитой Хоором и реализованной в языке программирования Паскаль [4]. Сущность теории - в том, что данные являются прежде всего абстракциями реальных явлений и их предпочтительно формулировать как абстрактные структуры безотносительно к их реализации в распространенных языках программирования. В процессе построения программы представление данных постепенно уточняется - в соответствии с уточнением алгоритма, - чтобы все более и более удовлетворить ограничениям, налагаемым имеющейся системой программирования [5]. Поэтому мы постулируем несколько основных структур данных, называемых фундаментальными. Очень важно, что это конструкции, которые достаточно легко реализовать на реальных компьютерах, ибо только в этом случае их можно рассматривать как истинные элементарные составляющие реального представления данных, появляющиеся как своего рода молекулы на последнем шаге уточнения описания данных. Это запись, массив (с фиксированным размером) и множество. Неудивительно, что эти базовые строительные элементы соответствуют математическим понятиям, которые также являются фундаментальными.

Центральный пункт этой теории структур данных - разграничение фундаментальных и сложных структур. Первые суть молекулы, - сами построенные из атомов, - из которых строятся вторые. Переменные, принадлежащие одному из таких фундаментальных видов структур, меняют только свое значение, но никогда не меняют ни свое строение, ни множество своих допустимых значений. Как следствие - размер занимаемой ими области памяти фиксирован. «Сложные» структуры, напротив, характеризуются изменением во время выполнения программы как своих значений, так и строения. Поэтому для их реализации нужны более изощренные методы. В этой классификации последовательность оказывается гибридом. Конечно, у нее может меняться длина; но такое изменение структуры тривиально. Поскольку последовательности играют поистине фундаментальную роль практически во всех вычислительных системах, их обсуждение включено в главу 1.

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

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

В главе 4 рассматриваются динамические структуры данных, то есть такие, строение которых меняется во время выполнения программы. Показывается, что рекурсивные структуры данных являются важным подклассом часто используемых динамических структур. Хотя рекурсивные определения возможны и даже естественны в этих случаях, на практике они обычно не используются. Вместо них используют явные ссылочные или указательные переменные. Данная книга тоже следует подобному подходу и отражает современный уровень понимания предмета: глава 4 посвящена программированию с указателями, списками, деревьями и содержит примеры с даже еще более сложно организованными данными. Здесь речь идет о том, что обычно (хотя и не совсем правильно) называют обработкой списков. Немало места уделено построению деревьев и, в частности, деревьям поиска. Глава заканчивается обсуждением так называемых хэш-таблиц, которые часто используют вместо деревьев поиска. Это дает возможность сравнить два принципиально различных подхода к решению часто возникающей задачи.

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

Разумеется, здесь возникает проблема поиска нотации, которая одновременно позволяла бы выполнить программу на вычислительной машине и в то же время была бы достаточно машинно независимой, чтобы ее можно было включать в подобный текст. В этом отношении не удовлетворительны ни широко используемые языки, ни абстрактная нотация. Язык Паскаль представляет собой подходящий компромисс; он был разработан именно для этой цели и поэтому используется на протяжении всей книги. Программы будут понятны программистам, знакомым с другими языками высокого уровня, такими как Алгол 60 или PL/1: смысл нотации Паскаля объясняется в книге по ходу дела. Однако некоторая подготовка все же могла бы быть полезной. Книга «Систематическое программирование» [6] идеальна в этом отношении, так как она тоже основана на нотации Паскаля. Однако следует помнить, что настоящая книга не предназначена быть учебником языка Паскаль; для этой цели есть более подходящие руководства [7].

Данная книга суммирует - и при этом развивает - опыт нескольких курсов программирования, прочитанных в Федеральном политехническом институте (ЕТН) в Цюрихе. Многими идеями и мнениями, представленными в этой книге, я обязан дискуссиям со своими коллегами в ЕТН. В частности, я хотел бы поблагодарить г-на Г. Сандмайра за внимательное чтение рукописи, а г-жу Хайди Тайлер и мою жену за тщательную и терпеливую перепечатку текста. Я должен также упомянуть о стимулирующем влиянии заседаний рабочих групп 2.1 и 2.3 ИФИПа, и в особенности многих дискуссий, которые мне посчастливилось иметь с Э. Дейкстрой и Ч. Хоором. Наконец, нужно отметить щедрость ЕТН, обеспечившего условия и предоставившего вычислительные ресурсы, без которых подготовка этого текста была бы невозможной.

Цюрих, август 1975 Н. Вирт

[1] Dijkstra Е. W, in: Dahl O-.J., Dijkstra E. W, Hoare C. A R. Structured Programming. F. Genuys, Ed., New York, Academic Press, 1972. P. 1-82 (имеется перевод: Дейкстра Э. Заметки по структурному программированию, в кн.: Дал У., Дейкстра Э., Хоор К. Структурное программирование. - М.: Мир, 1975. С. 7-97).

[2] Hoare С. A R. Сотт. ЛСМ, 12, No. 10 (1969), 576-83.

[3] Hoare С. A R., in Structured Programming [1]. Р. 83-174 (имеется перевод; Хоор К. О структурной организации данных, в кн. [1]. С. 98-197).

[4] Wirth N. The Programming Language Pascal. Acta lnfomatica, 1, No. 1 (1971), 35-63.

[5] Wirth N. Program Development by Stepwise Refinement. Comm. ACM. 14, No. 4 (1971), 221-27.

[6] Wirth N. Systematic Programming. Englewood Cliffs, N. J. Prentice-Hall, Inc., 1973 (имеется перевод: Вирт H. Систематическое программирование. Введение. - М.: Мир, 1977).

[7] Jensen К. and Wirth N. PASCAL-User Manual and Report. Berlin, Heidelberg, New York; Springer-Verlag, 1974 (имеется перевод: Йенсен К., Вирт Н. Паскаль. Руководство для пользователя и описание языка. - М.: Финансы и статистика, 1988).