Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
Алгоритмы и структуры данных Новая версия для Оберона + CD Москва, 2010 Никлаус Вирт Перевод с английского под редакцией доктора физ мат. наук, Ткачева Ф. В. УДК 32.973.26018.2 ББК 004.438 В52 Никлаус Вирт В52 Алгоритмы и структуры данных. Новая версия для Оберона + CD / Пер. с англ. Ткачев Ф. В. – М.: ДМК Пресс, 2010. – 272 с.: ил. ISBN 9785940745846 В классическом учебнике тьюринговского лауреата Н.Вирта аккуратно, на тщательно подобранных примерах прорабатываются основные темы алго% ритмики – сортировка и поиск, рекурсия, динамические структуры данных. Перевод на русский язык выполнен заново, все рассуждения и програм% мы проверены и исправлены, часть примеров по согласованию с автором переработана с целью максимального прояснения их логики (в том числе за счет использования цикла Дейкстры). Нотацией примеров теперь служит Оберон/Компонентный Паскаль – наиболее совершенный потомок старого Паскаля по прямой линии. Все программы проверены и работают в популярном варианте Оберона – системе Блэкбокс, и доступны в исходниках на прилагаемом CD вместе с самой системой и дополнительными материалами. Большая часть материала книги составляет необходимый минимум знаний по алгоритмике не только для программистов%профессионалов, но и любых других специалистов, активно использующих программирование в работе. Книга может быть использована как учебное пособие при обучении буду% щих программистов, начиная со старшеклассников в профильном обуче% нии, а также подходит для систематического самообразования. Содержание компактдиска: Базовая конфигурация системы Блэкбокс с коллекцией модулей, реализующих программы из книги. Базовые инструкции по работе в системе Блэкбокс. Полный перевод документации системы Блэкбокс на русский язык. Конфигурация системы Блэкбокс для использования во вводных курсах програм% мирования в университетах. Конфигурация системы Блэкбокс для использования в школах (полная русифика% ция меню, сообщений компилятора, с возможностью использования ключевых слов на русском и других национальных языках). Доклады участников проекта Информатика%21 по опыту использования системы Блэкбокс в обучении программированию. Оригинальные дистрибутивы системы Блэкбокс 1.5 (основной рабочий) и 1.6rc6. Инструкции по работе в Блэкбоксе под Linux/Wine. Дистрибутив оптимизирующего компилятора XDS Oberon (версии Linux и MS Windows). OberonScript – аналог JavaScript для использования в Web%приложениях. ISBN 0%13%022005%9 (анг.) © N. Wirth, 1985 (Oberon version: August 2004). © Перевод на русский язык, исправления и изменения, Ф. В. Ткачев, 2010. ISBN 978%5%94074%584%6 © Оформление, издание, ДМК Пресс, 2010 Содержание О новой версии классического учебника Никлауса Вирта ....................................................................... 5 Предисловие .......................................................................... 11 Предисловие к изданию 1985 года ............................. 15 Нотация ..................................................................................... 16 Глава 1. Фундаментальные структуры данных ..... 11 1.1. Введение .............................................................................. 18 1.2. Понятие типа данных ............................................................ 20 1.3. Стандартные примитивные типы .......................................... 22 1.4. Массивы ............................................................................... 26 1.5. Записи .................................................................................. 29 1.6. Представление массивов, записей и множеств .................... 31 1.7. Файлы или последовательности ........................................... 35 1.8. Поиск .................................................................................... 49 1.9. Поиск образца в тексте (string search) .................................. 54 Упражнения.................................................................................. 65 Литература .................................................................................. 67 Глава 2. Сортировка ........................................................... 69 2.1. Введение .............................................................................. 70 2.2. Сортировка массивов ........................................................... 72 2.3. Эффективные методы сортировки ....................................... 81 2.4. Сортировка последовательностей ....................................... 97 Упражнения................................................................................ 128 Литература ................................................................................ 130 Глава 3. Рекурсивные алгоритмы .............................. 131 3.1. Введение ............................................................................ 132 3.2. Когда не следует использовать рекурсию .......................... 134 3.3. Два примера рекурсивных программ ................................. 137 3.4. Алгоритмы с возвратом ...................................................... 143 3.5. Задача о восьми ферзях ..................................................... 149 Содержание 4 3.6. Задача о стабильных браках ............................................... 154 3.7. Задача оптимального выбора ............................................. 160 Упражнения................................................................................ 164 Литература ................................................................................ 166 Глава 4. Динамические структуры данных ........... 167 4.1. Рекурсивные типы данных .................................................. 168 4.2. Указатели ........................................................................... 170 4.3. Линейные списки ................................................................ 175 4.4. Деревья .............................................................................. 191 4.5. Сбалансированные деревья ............................................... 210 4.6. Оптимальные деревья поиска ............................................. 220 4.7. Б<деревья (B Литература ................................................................................ 254 Глава 5. Хэширование ..................................................... 255 5.1. Введение ............................................................................ 256 5.2. Выбор хэш<функции ........................................................... 257 5.3. Разрешение коллизий ........................................................ 257 5.4. Анализ хэширования .......................................................... 261 Упражнения................................................................................ 263 Литература ................................................................................ 264 Приложение A. Множество символов ASCII .......... 265 Приложение B. Синтаксис Оберона ......................... 266 Приложение C. Цикл Дейкстры ................................... 269 О новой версии классического учебника Никлауса Вирта Новая версия учебника Н. Вирта «Алгоритмы и структуры данных» отличается от английского прототипа [1] сильнее, чем просто исправлением многочисленных опечаток и огрехов, накопившихся в процессе тридцатилетней эволюции книги. Объясняется это целями автора и переводчика при работе над книгой в контексте проекта «Информатика%21» [2], который, опираясь на обширный совокупный опыт ряда высококвалифицированных специалистов (см. списки консультантов и участников на сайте проекта [2]), ставит задачу создания единой системы ввод% ных курсов информатики и программирования, охватывающей учащихся пример% но от 5%го класса общей средней школы по 3%й курс университета. Такая система должна иметь образцом и дополнять уникальную российскую систему матема% тического образования. Это предполагает наличие стержня общих курсов, состав% ляющих единство без внутренних технологических барьеров (которые приводят, среди прочего, к недопустимым потерям дефицитного учебного времени) и лишь варьирующихся в зависимости от специализации, вместе с надстройкой из профессионально ориентированных курсов, опирающихся на этот стержень в от% ношении базовых знаний учащихся. Такая система подразумевает наличие каче% ственных учебников (первым из которых имеет шанс стать данная книга), «говорящих» на общем образцовом языке программирования. Естественный кан% дидат на роль такого общего языка – Оберон/Компонентный Паскаль. Подроб% ней об Обероне речь пойдет ниже, здесь только скажем, что Паскаль (использо% ванный в первом издании данной книги 1975 г.), Модулу%2 (использованную во втором издании, переведенном на русский язык в 1989 г. [3]) и Оберон (использо% ванный в данной версии) логично рассматривать соответственно как альфа%, бета% и окончательную версию одного и того же языка. Использование Оберона – самое очевидное отличие данной версии книги от предыдущего издания. В контекст идеи о единой системе вводных курсов вписывается и узкая задача, решавшаяся новой версией учебника, – дать небольшое продуманное пособие, в котором аккуратно, но не топя читателя в болоте второстепенных деталей, прора% батывались бы традиционные темы классической алгоритмики, для полного обсуждения которых нет времени в спецкурсе, читаемом переводчиком с 2001 г. на физфаке МГУ в попытке обеспечить хотя бы минимум культуры программиро% вания у будущих аспирантов. Здесь требуется «отлаженный» текст, пригодный для самостоятельной работы студентов. С точки зрения содержания, лучшим кандидатом на эту роль оказался прототип [1]. О новой версии классического учебника Никлауса Вирта 6 Что двойное переделывание программ и рассуждений в тексте (с Паскаля на Модулу%2 и затем на Оберон) не прошло безнаказанно, само по себе неудиви% тельно. Однако затруднения, возникшие при верификации программ и текста, хотя и были преодолены, все же показались чрезмерными. Поэтому, и ввиду учеб% ного назначения книги, встал ребром вопрос о необходимости доработки примеров. Предложения переводчика были одобрены автором на совместной рабочей сессии в апреле сего года и реализованы непосредственно в данном переводе (при первой возможности соответствующие изменения будут внесены и в прототип [1]). Во%первых, алгоритмы поиска образца в тексте переписаны в терминах цикла Дейкстры (многоветочный while [4]). Эта фундаментальная и мощная управля% ющая структура поразительным образом до сих пор не представлена в распро% страненных языках программирования, поэтому ей посвящено новое приложение C. Раздел 1.9, в который теперь выделены эти алгоритмы, будет неплохой иллю% страцией реального применения цикла Дейкстры. Вторая группа заметно изме% ненных программ – алгоритмы с возвратом в главе 3, в которых теперь экспли% цировано применение линейного поиска и, благодаря этому, тривиализована верификация. Такое прояснение рекурсивных комбинаторных алгоритмов явля% ется довольно общим. Обсуждались – но были признаны в данный момент неце% лесообразными – модификации и некоторых других программ. Надо заметить, что программистский стиль автора вырабатывался с конца 1950%х гг., когда проблема эффективности программ висела над головами про% граммистов дамокловым мечом, и за несколько лет до того, как Дейкстра опубли% ковал систематический метод построения программ [4]. В старых версиях книги заметна рефлекторная склонность к оптимизации до полного прояснения логики программ, что затрудняло эффективное применение формальной техники. Это легко объяснить: Н. Вирт осваивал только еще формирующиеся систематические методы, непосредственно участвуя в процессе создания программирования как академической дисциплины, версия за версией улучшая свои учебники. Но и через четверть века после последней существенной переделки учебника автором аналогичная склонность к преждевременной оптимизации при не просто не вполне уверенной, а напрочь отсутствующей формальной технике – и, как следствие, запутанные циклы, – характерные черты стиля «широких програм% мистских масс»! В профессиональных интернет%форумах до сих пор можно найти позорные дискуссии о том, нужно ли учиться писать циклы по Дейкстре, – и это в лучшем случае. Если же вообразить себе весь окружающий нас непрерывно рас% тущий массив софта, от которого наша жизнь зависит все больше, то впору впасть в депрессию: Quo usque tandem, Catilina? – Сколько еще нужно десятилетий, что% бы система образования вышла, наконец, на уровень, давным%давно достигнутый наукой? Во всяком случае, ясно, что едва ли не главная причина проблемы – хаос, царящий в системе ИТ%образования, тормозящий создание и распространение качественных методик и поддерживаемый, среди прочего, корыстными интереса% ми «монстров» индустрии. Здесь уместно сказать о языке Оберон/Компонентный Паскаль, пропаганди% руемом в качестве общей платформы для предполагаемой единой системы курсов О новой версии классического учебника Никлауса Вирта 7 программирования. Оберон – последний большой проект Никлауса Вирта, выда% ющегося инженера, ученого и педагога, вместе с Бэкусом, А. Ершовым, Дейкст% рой, Хоором и другими пионерами компьютерной информатики превратившего программирование в систематическую дисциплину и лучше всего известного со% зданием серии все более совершенных языков программирования – Паскаля (1970), Модулы%2 (1980) и наконец Оберона (1988, 2007). В этих языках отража% лось все более полное понимание проблематики эффективного программирова% ния. Языки эти сохраняют идейную и стилевую преемственность, и коммерсант, озабоченный сохранением доли рынка, не назвал бы их по%разному (ср. зоопарк бейсиков). Чтобы подчеркнуть эту преемственность, самому популярному диа% лекту Оберона было возвращено законное фамильное имя – Компонентный Пас% каль. Оберон/Компонентный Паскаль унаследовал лучшие черты старого доброго Паскаля и добавил к ним промышленный опыт Модулы%2 (на которой програм% мируются, например, российские спутники связи [5]), а также выверенный мини% мум средств объектно%ориентированного программирования. Принципальное до% стижение – удалось наконец добиться герметичности системы типов (теперь ее нельзя обойти средствами языка даже при работе с указателями). Это обеспечило возможность автоматического управления памятью (сбора мусора; до Оберона сбор мусора оставался прерогативой динамических языков – функциональных, скриптовых и т. п.) В результате диапазон эффективного применения Оберона, похоже, шире, чем у любого другого языка: это и вычислительные приложения, и системы управления любого масштаба (от беспилотников весом в 1 кг до гранди% озных каскадов ГЭС), и, например, задачи символической алгебры с предельно динамичными структурами данных. Особо следует остановиться на минимализме Оберона. Традиционно разра% ботчики сосредоточиваются на том, чтобы снабдить свои языки, программы, биб% лиотеки «богатым набором средств» – ведь так легче привлечь клиента, надеюще% гося побыстрее найти готовое решение для своих прикладных нужд. Погоня за «богатым набором средств» оборачивается ущербом качеству и надежности сис% темы. Вместе с коммерческими соображениями это приводит к тому, что полу% чается большая закрытая сложная система с вроде бы богатым набором средств, но хромающей надежностью и ограниченной расширяемостью, так что если поль% зователь сталкивается с нестандартной ситуацией в своих приложениях (что слу% чается сплошь и рядом – ведь разнообразие реального мира превосходит любое воображение писателей библиотек), то он оказывается в тупике. Н. Вирт еще со времен Паскаля, созданного в пику фантазийному Алголу%68 [6], пошел другим путем. Его гамбит заключался в том, чтобы, отказавшись от включения в язык максимума средств на все случаи жизни, тщательнейшим обра% зом выделить минимум реально ключевых средств, – обязательно включив в этот минимум все, что нужно для безболезненной, неограниченной расширяемости программных систем, – и добиться высоконадежной реализации такого ядра. Этот замысел был с блеском реализован Н. Виртом и его соратником Ю. Гуткнех% том в проекте Оберон [7]. Минимализм и уникальная надежность Оберона О новой версии классического учебника Никлауса Вирта 8 заставляют вспомнить автомат Калашникова. При этом вся мощь Оберона оказы% вается открытой даже программистам%непрофессионалам – физикам, инженерам, лингвистам.., занятым программированием изрядную долю своего рабочего времени. Для преподавателя важно, что в Обероне достигнуты ортогональность и сво% бодная комбинируемость языковых средств, смысловая прозрачность, а также беспрецедентно малый для столь мощного языка размер (см. полное описание синтаксиса в приложении B, а также обсуждение в [8]). В этом отношении Оберон побеждает за явным преимуществом традиционные промышленные языки, пре% словутая избыточная сложность которых оказывается источником своего рода ренты, взимаемой с остального мира. Оберон скромно уходит в тень при рассмо% трении любой языково%неспецифичной темы – от введения в алгоритмику до принципов компиляции и программной архитектуры. А после постановки базо% вой техники программирования на Обероне изучение промышленных языков за% частую сводится к изучению способов обходить дефекты их дизайна. Если уже старый Паскаль оказался настолько удачной платформой для обучения програм% мированию, что принес своему автору высшую почесть в компьютерной инфор% матике – премию им. Тьюринга, то понятно, что буквально вылизанный Оберон/ Компонентный Паскаль называют уже «практически идеальной» платформой для обучения программированию. Имея в виду исключительные педагогические достоинства Оберона, для всех примеров программ, приведенные в книге, обеспечена воспроизводимость в сис% теме программирования для Компонентного Паскаля, известной как Блэкбокс (BlackBox Component Builder [9]). Это пулярный вариант Оберона, созданный для работы в распространенных операционных системах. Конфигурации Блэк% бокса для использования в школе и университете доступны на сайте проекта «Ин% форматика%21» [2]. Открытый, бесплатный и безупречно современный Блэкбокс оказывается естественной заменой устаревшему Турбо Паскалю – заменой тем более привлекательной, что, несмотря на минимализм и благодаря автоматиче% скому управлению памятью, это более мощный инструмент, чем промышленные системы программирования на диалектах старого Паскаля. Краткое описание возможностей Блэкбокса с точки зрения использования в школьных курсах мож% но найти в статье [10]. Важное приложение к книге – полный комплект программ, представленных в тексте учебника, в виде, готовом к выполнению. Программы оформлены в отдель% ных модулях вместе с необходимыми вспомогательными процедурами, и все та% кие модули собраны в папке ADru/Mod/ , которая должна лежать внутри основной папки Блэкбокса (следует иметь в виду, что файлы с расширением *.odc должны читаться из Блэкбокса). Читатель без труда разберется с компиляцией и запуском программ по комментариям в модулях, читая модули в том порядке, в каком они встречаются в тексте книги (или в лексикографическом порядке имен файлов). В тексте книги в начальных строках каждого законченного программного приме% ра справа указано имя соответствующего модуля. Например, комментарий (*ADruS18_*) означает, что данная программа содержится в модуле О новой версии классического учебника Никлауса Вирта 9 ADruS18_ , который в соответствии с правилами Блэкбокса хранится в фай% ле ADru/Mod/S18_.odc . При этом речь идет о программе из раздела 1.8, а необязательный суффикс "_" служит удобству ориентации. Вся папка ADru в составе Блэкбокса имеется на диске, если диск приложен к книге, либо может быть скачана с адреса [11]. Наконец, несколько слов о собственно переводе. Старый перевод [3] был вы% полнен, что называется, из общих соображений. Но совсем другое дело – иметь в виду конкретных студентов, не обязательно будущих профессиональных программистов, пытающихся за минимальное время овладеть основами програм% мирования. Поэтому в новом переводе были предприняты особые усилия, чтобы избежать размывания смысла из%за неточностей, неизбежно вкрадывающихся при неполном понимании переводчиком оригинала (ср. примечание на с. 110 в главе о сортировках в [3], где выражена надежда, что «сам читатель разберется, что хотел сказать автор»). Например, при более%менее прямолинейной пофразо% вой интерпретации малейшая неточность способна развалить смысл лаконичного текста Вирта из%за того, например, что после перевода могут перестать быть одно% коренными слова, благодаря которым только и обеспечивалась смысловая связь между предложениями в оригинале. Поэтому добиться полного сохранения смыс% ла при переводе оказалось проще, выполнив его с нуля. В отношении терминологии переводам специалистов было отдано должное. Вслед за Д. Б. Подшиваловым [3] мы используем прилагательные «массивовый», «последовательностный» и «записевый». Решающий довод в пользу таких прила% гательных – они естественно вписываются в грамматическую систему русского языка, чем обеспечивается необходимая гибкость выражения. Однако даже в отношении терминологии переводы по компьютерной тематике часто демонстрируют неполное понимание существенных деталей английской грамматики. Например, при использовании существительного в качестве опреде% ления в препозиции (что, кстати, не эквивалентно русской конструкции, выража% емой родительным падежом) множественное число может нейтрализоваться, и при переводе на русский его иногда нужно восстанавливать. Так, path length дол% жно переводиться не как «длина пути», а как «длина путей», что, между прочим, прямо соответствует математическому определению и ощутимо помогает пони% мать рассуждения. Optimal search tree – «оптимальное дерево поиска», а не «дере% во оптимального поиска». Advanced sort algorithms – «эффективные алгоритмы сортировки», потому что буквальное значение advanced в данном случае давно нейтрализовано. Переводить на русский язык двумя словами специфичные для стилистики английского языка синонимичные пары вроде «methods and tech% niques» обычно неразумно. И так далее. Масса подобных неточностей снижает удобочитаемость текста и затемняет и без того непростой смысл оригинала. Хотя по конкретным стилистическим вопросам копья можно ломать до беско% нечности, все же хочется надеяться, что предпринятые усилия в основном достиг% ли цели – не потерять точный смысл английского «исходника» этого выдержав% шего проверку временем прекрасного учебника. Троицк, Московская обл., июль 2009 Ф. В. Ткачев О новой версии классического учебника Никлауса Вирта 10 [1] Wirth N. Algorithms and Data Structures. Oberon version: 2004 //http://www. inr.ac.ru/info21/pdf/AD.pdf [2] Информатика%21: Международный общественный научно%образователь% ный проект // http://www.inr.ac.ru/info21/ [3] Н. Вирт. Алгоритмы и структуры данных / пер. с англ. Д. Б. Подшивалова. – М.: Мир, 1989. [4] Дейкстра Э. Дисциплина программирования. – М.: Мир, 1978. [5] Koltashev A. A., in: Lecture Notes in Computer Science 2789. – Springer%Verlag, 2003. [6] Кто такой Никлаус Вирт? // http://www.inr.ac.ru/info21/wirth/wirth.htm [7] Wirth N. and Gutknecht J. Project Oberon. – Addison%Wesley, 1992. [8] Свердлов С. В. Языки программирования и методы трансляции. – СПб.: Питер, 2007. [9] http://www.oberon.ch/blackbox.html [10] Ильин А. С. и Попков А. И. Компонентный Паскаль в школьном курсе ин% форматики // http://inf.1september.ru/article.php?ID=200800100 [11] http://www.inr.ac.ru/info21/ADru/ Предисловие В последние годы признано, что умение создавать программы для вычислитель% ных машин является залогом успеха во многих инженерных проектах и что дис% циплина программирования может быть объектом научного анализа и допускает систематическое изложение. Программирование из ремесла превратилось в ака% демическую дисциплину. Первые выдающиеся результаты на этом пути получе% ны Дейкстрой (E. W. Dijkstra) и Хоором (C. A. R. Hoare). «Заметки по структурно% му программированию» Дейкстры [1] позволили взглянуть на программирование как на объект научного анализа, бросающий вызов человеческому интеллекту, а слова структурное программирование дали название «революции» в програм% мировании. Работа Хоора «Аксиоматические основы программирования» [2] продемонстрировала, что программы допускают точный анализ, основанный на математических рассуждениях. И обе статьи убедительно доказывают, что мно% гих ошибок в программах можно избежать, если программисты будут систе% матически применять методы и приемы, которые ранее применялись лишь инту% итивно и часто неосознанно. Эти статьи сосредоточили внимание на построении и анализе программ, или, точнее говоря, на структуре алгоритмов, представленных текстом программы. При этом вполне очевидно, что систематический научный подход к построению программ уместен прежде всего в случае больших, непрос% тых программ, работающих со сложными наборами данных. Отсюда следует, что методология программирования должна включать в себя все аспекты структури% рования данных. В конце концов, программы суть конкретные формулировки аб% страктных алгоритмов, основанные на конкретных представлениях и структурах данных. Выдающийся вклад в наведение порядка в огромном разнообразии тер% минологии и понятий, относящихся к структурам данных, сделал Хоор в статье «О структурной организации данных» [3]. В этой работе продемонстрировано, что нельзя принимать решения о структуре данных без учета того, какие алгорит% мы применяются к данным, и что, обратно, структура и выбор алгоритмов часто сильно зависят от стуктуры обрабатываемых данных. Короче говоря, задачу пост% роения программ нельзя отделять от задачи структурирования данных. Но данная книга начинается главой о структурах данных, и для этого есть две причины. Во%первых, интуитивно ощущается, что данные предшествуют алгорит% мам: нужно иметь некоторые объекты до того, как можно будет что%то с ними де% лать. Во%вторых, эта книга предполагает, что читатель знаком с основными поня% тиями программирования. Однако в соответствии с разумной традицией вводные курсы программирования концентрируют внимание на алгоритмах, работающих с относительно простыми структурами данных. Поэтому уместно посвятить ввод% ную главу структурам данных. На протяжении всей книги, включая главу 1, мы следуем теории и термино% логии, развитой Хоором и реализованной в языке программирования Паскаль [4]. Сущность теории – в том, что данные являются прежде всего абстракциями реальных явлений и их предпочтительно формулировать как абстрактные струк% Предисловие 12 туры безотносительно к их реализации в распространенных языках программиро% вания. В процессе построения программы представление данных постепенно уточняется – в соответствии с уточнением алгоритма, – чтобы все более и более удовлетворить ограничениям, налагаемым имеющейся системой программи% рования [5]. Поэтому мы постулируем несколько основных структур данных, на% зываемых фундаментальными. Очень важно, что это конструкции, которые дос% таточно легко реализовать на реальных компьютерах, ибо только в этом случае их можно рассматривать как истинные элементарные составляющие реального представления данных, появляющиеся как своего рода молекулы на последнем шаге уточнения описания данных. Это запись, массив (с фиксированным разме% ром) и множество. Неудивительно, что эти базовые строительные элементы соответствуют математическим понятиям, которые также являются фундамен% тальными. Центральный пункт этой теории структур данных – разграничение фундамен тальных и сложных структур. Первые суть молекулы, – сами построенные из ато% мов, – из которых строятся вторые. Переменные, принадлежащие одному из таких фундаментальных видов структур, меняют только свое значение, но никогда не ме% няют ни свое строение, ни множество своих допустимых значений. Как следствие – размер занимаемой ими области памяти фиксирован. «Сложные» структуры, на% против, характеризуются изменением во время выполнения программы как своих значений, так и строения. Поэтому для их реализации нужны более изощренные методы. В этой классификации последовательность оказывается гибридом. Конеч% но, у нее может меняться длина; но такое изменение структуры тривиально. По% скольку последовательности играют поистине фундаментальную роль практичес% ки во всех вычислительных системах, их обсуждение включено в главу 1. Во второй главе речь идет об алгоритмах сортировки. Там представлено не% сколько разных методов, решающих одну и ту же задачу. Математическое изу% чение некоторых из них показывает их преимущества и недостатки, а также под% черкивает важность теоретического анализа при выборе хорошего решения для конкретной задачи. Разделение на методы сортировки массивов и методы сорти% ровки файлов (их часто называют внутренней и внешней сортировками) демон% стрирует решающее влияние представления данных на выбор алгоритмов и на их сложность. Теме сортировки уделяется такое внимание потому, что она пред% ставляет собой идеальную площадку для иллюстрации очень многих принципов программирования и ситуаций, возникающих в большинстве других приложе% ний. Похоже, что курс программирования можно было бы построить, используя только примеры из темы сортировки. Другая тема, которую обычно не включают во вводные курсы программиро% вания, но которая играет важную роль во многих алгоритмических решениях, – это рекурсия. Поэтому третья глава посвящена рекурсивным алгоритмам. Здесь показывается, что рекурсия есть обобщение понятия цикла (итерации) и что она является важным и мощным понятием программирования. К сожалению, во мно% гих учебниках программирования она иллюстрируется примерами, для которых было бы достаточно простой итерации. Мы в главе 3, напротив, сосредоточим внимание на нескольких задачах, для которых рекурсия дает наиболее естествен% ную формулировку решения, тогда как использование итерации привело бы к за% Предисловие 13 путанным и громоздким программам. Класс алгоритмов с возвратом – отличное применение рекурсии, но самые очевидные кандидаты для применения рекур% сии – это алгоритмы, работающие с данными, структура которых определена ре% курсивно. Эти случаи рассматриваются в последних двух главах, для которых, таким образом, третья закладывает фундамент. В главе 4 рассматриваются динамические структуры данных, то есть такие, строение которых меняется во время выполнения программы. Показывается, что рекурсивные структуры данных являются важным подклассом часто использу% емых динамических структур. Хотя рекурсивные определения возможны и даже естественны в этих случаях, на практике они обычно не используются. Вместо них используют явные ссылочные или указательные переменные. Данная книга тоже следует подобному подходу и отражает современный уровень понимания предме% та: глава 4 посвящена программированию с указателями, списками, деревьями и содержит примеры с даже еще более сложно организованными данными. Здесь речь идет о том, что обычно (хотя и не совсем правильно) называют обработкой списков. Немало места уделено построению деревьев и, в частности, деревьям по% иска. Глава заканчивается обсуждением так называемых хэш%таблиц, которые ча% сто используют вместо деревьев поиска. Это дает возможность сравнить два принципиально различных подхода к решению часто возникающей задачи. Программирование – это конструирование. Как вообще можно учить изобре% тательному конструированию? Можно было бы попытаться из анализа многих примеров выделить элементарные композиционные принципы и представить их систематическим образом. Но программирование имеет дело с задачами огромно% го разнообразия и часто требует серьезных интеллектуальных усилий. Ошибочно думать, что обучить ему можно, просто дав некий список рецептов. Но тогда в на% шем арсенале методов обучения остаются только тщательный подбор и изложе% ние образцовых примеров. Естественно, не следует ожидать, что изучение приме% ров будет равно полезным для разных людей. При таком подходе многое зависит от самого учащегося, от его прилежания и интуиции. Это особенно справедливо для относительно сложных и длинных примеров программ. Такие примеры включены в книгу не случайно. Длинные программы доминируют в практике программирования, и они гораздо больше подходят для демонстрации тех труд% но определяемых, но существенных свойств, которые называют стилем и хоро% шей структурой. Они также должны послужить упражнениями в искусстве чте% ния программ, которым часто пренебрегают в пользу написания программ. Это главная причина того, почему в качестве примеров используются целиком до% вольно большие программы. Читатель имеет возможность проследить постепен% ную эволюцию программы и увидеть ее состояние на разных шагах, так что про% цесс разработки предстает как пошаговое уточнение деталей. Считаю, что важно показать программу в окончательном виде, уделяя достаточно внимания деталям, так как в программировании дьявол прячется в деталях. Хотя изложение общей идеи алгоритма и его анализ с математической точки зрения могут быть увлека% тельными для ученого, по отношению к инженеру%практику ограничиться только этим было бы нечестно. Поэтому я строго придерживался правила давать оконча% тельные программы на таком языке, на котором они могут быть реально выполне% ны на компьютере. Предисловие 14 Разумеется, здесь возникает проблема поиска нотации, которая одновременно позволяла бы выполнить программу на вычислительной машине и в то же время была бы достаточно машинно независимой, чтобы ее можно было включать в по% добный текст. В этом отношении не удовлетворительны ни широко используемые языки, ни абстрактная нотация. Язык Паскаль представляет собой подходящий компромисс; он был разработан именно для этой цели и поэтому используется на протяжении всей книги. Программы будут понятны программистам, знакомым с другими языками высокого уровня, такими как Алгол 60 или PL/1: смысл нота% ции Паскаля объясняется в книге по ходу дела. Однако некоторая подготовка все же могла бы быть полезной. Книга «Систематическое программирование» [6] идеальна в этом отношении, так как она тоже основана на нотации Паскаля. Одна% ко следует помнить, что настоящая книга не предназначена быть учебником язы% ка Паскаль; для этой цели есть более подходящие руководства [7]. Данная книга суммирует – и при этом развивает – опыт нескольких курсов программирования, прочитанных в Федеральном политехническом институте (ETH) в Цюрихе. Многими идеями и мнениями, представленными в этой книге, я обязан дискуссиям со своими коллегами в ETH. В частности, я хотел бы поблагодарить г%на Г. Сандмайра за внимательное чтение рукописи, а г%жу Хайди Тайлер и мою жену за тщательную и терпеливую перепечатку текста. Я должен также упомянуть о стимулирующем влиянии заседаний рабочих групп 2.1 и 2.3 ИФИПа, и в особенности многих дискуссий, которые мне посчастливилось иметь с Э. Дейкстрой и Ч. Хоором. Наконец, нужно отметить щедрость ETH, обеспечив% шего условия и предоставившего вычислительные ресурсы, без которых подго% товка этого текста была бы невозможной. Цюрих, август 1975 Н. Вирт [1] Dijkstra E. W., in: Dahl O%.J., Dijkstra E. W., Hoare C. A. R. Structured Prog% ramming. F. Genuys, Ed., New York, Academic Press, 1972. Р. 1–82 (имеется перевод: Дейкстра Э. Заметки по структурному программированию, в кн.: Дал У., Дейкстра Э., Хоор К. Структурное программирование. – М.: Мир, 1975. С. 7–97). [2] Hoare C. A. R. Comm. ACM, 12, No. 10 (1969), 576–83. [3] Hoare C. A. R., in Structured Programming [1]. Р. 83%174 (имеется перевод: Хоор К. О структурной организации данных, в кн. [1]. С. 98–197). [4] Wirth N. The Programming Language Pascal. Acta Informatica, 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 (имеется перевод: Вирт Н. Систематическое программирование. Вве% дение. – М.: Мир, 1977). [7] Jensen K. and Wirth N. PASCAL%User Manual and Report. Berlin, Heidelberg, New York; Springer%Verlag, 1974 (имеется перевод: Йенсен К., Вирт Н. Пас% каль. Руководство для пользователя и описание языка. – М.: Финансы и ста% тистика, 1988). Предисловие к изданию 1985 года В этом новом издании сделано много улучшений в деталях, а также несколько бо% лее серьезных модификаций. Все они мотивированы опытом, приобретенным за десять лет после первого издания. Однако основное содержание и стиль текста не изменились. Кратко перечислим важнейшие изменения. Главное изменение, повлиявшее на весь текст, касается языка программирова% ния, использованного для записи алгоритмов. Паскаль был заменен на Модулу%2. Хотя это изменение не оказывает серьезного влияния на представление алгорит% мов, выбор оправдан большей простотой и элегантностью синтаксиса Модулы%2, что часто приводит к большей ясности представления структуры алгоритма. Кро% ме того, было сочтено полезным использовать нотацию, которая приобретает по% пулярность в довольно широком сообществе по той причине, что она хорошо под% ходит для разработки больших программных систем. Тем не менее тот очевидный факт, что Паскаль является предшественником Модулы, облегчает переход. Для удобства читателя синтаксис Модулы суммирован в приложении. Как прямое следствие замены языка программирования был переписан раз% дел 1.11 о последовательной файловой структуре. В Модуле%2 нет встроенного файлового типа. В пересмотренном разделе 1.11 понятие последовательности как структуры данных представлено в более общем виде, и там также вводится набор программных модулей, которые явно реализуют идею последовательности конк% ретно в Модуле%2. Последняя часть главы 1 является новой. Она посвящена теме поиска и, начи% ная с линейного и двоичного поиска, подводит к некоторым недавно изобретен% ным быстрым алгоритмам поиска строк. В этом разделе подчеркивается важность проверок промежуточных состояний (assertions) и инвариантов цикла для дока% зательства корректности представляемых алгоритмов. Новый раздел о приоритетных деревьях поиска завершает главу, посвященную динамическим структурам данных. Эта разновидность деревьев была неизвестна во время выхода первого издания. Такие деревья допускают экономное представление и позволяют выполнять быстрый поиск по множествам точек на плоскости. Целиком исключена вся пятая глава первого издания. Это сделано потому, что тема построения компиляторов стоит несколько в стороне от остальных глав и заслуживает более подробного обсуждения в отдельной книге. Наконец, появление нового издания отражает прогресс, глубоко повлиявший на издательское дело в последние десять лет: применение компьютеров и изощ% ренных алгоритмов для подготовки и автоматического форматирования докумен% тов. Эта книга была набрана и сформатирована автором с помощью компьютера Lilith и редактора документов Lara. Без этих инструментов книга не только стала бы дороже, но, несомненно, даже еще не была бы закончена. Пало Альто, март 1985 г. Н. Вирт Нотация В книге используются следующие обозначения, взятые из работ Дейкстры. В логических выражениях литера & обозначает конъюнкцию и читается как «и». Литера обозначает отрицание и читается как «не». Комбинация литер or обозначает дизъюнкцию и читается как «или». Литеры A A A A A и E E E E E , набранные жирным шрифтом, обозначают кванторы общности и существования. Нижеследующие формулы определяют смысл нотации в левой части через выражение в правой. Интерпретация символа «...» в правых частях оставлена интуиции читателя. A A A A Ai: m ≤ i < n : P i P m & P m+1 & ... & P n–1 Здесь P i – некоторые предикаты, а формула утверждает, что выполняются все P i для значений индекса i из диапазона от m до n , но не включая само n E E E E Ei: m ≤ i < n : P i P m or P m+1 or ... or P n–1 Здесь P i – некоторые предикаты, а формула утверждает, что выполняются некоторые из P i для каких%то значений индекса i из диапазона от m до n , но не включая само n S S S S Si: m ≤ i < n : x i = x m + x m+1 + ... + x n–1 MIN i: m ≤ i < n : x i = минимальное среди значений (x m , ... , x n–1 ) MAX i: m ≤ i < n : x i = максимальное среди значений (x m , ... , x n–1 ) |