Алгоритмы и структуры данных
Покупка
Тематика:
Проектирование баз и банков данных
Издательство:
ДМК Пресс
Автор:
Вирт Никлаус
Перевод:
Ткачев Федор Васильевич
Год издания: 2023
Кол-во страниц: 274
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
Профессиональное образование
ISBN: 978-5-89818-313-4
Артикул: 816350.01.99
В классическом учебнике тьюринговского лауреата Н. Вирта аккуратно, на тщательно подобранных примерах прорабатываются основные темы алгоритмики — сортировка и поиск, рекурсия, динамические структуры данных.
Перевод на русский язык выполнен заново, все рассуждения и программы проверены и исправлены, часть примеров по согласованию с автором переработана с целью максимального прояснения их логики (в том числе за счет использования цикла Дейкстры). Нотацией примеров теперь служит Оберон/Компонентный Паскаль — наиболее совершенный потомок старого Паскаля по прямой линии. Все программы проверены и работают в популярном варианте Оберона — системе Блэкбокс. Большая часть материала книги составляет необходимый минимум знаний по алгоритмике не только для программистов-профессионалов, но и любых других специалистов, активно использующих программирование в работе. Книга может быть использована как учебное пособие при обучении будущих программистов, начиная со старшеклассников в профильном обучении, а также подходит для систематического самообразования. Прилагаемые к книге файлы можно найти на сайте издательства.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 02.03.02: Фундаментальная информатика и информационные технологии
- 09.03.01: Информатика и вычислительная техника
- 09.03.04: Программная инженерия
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Алгоритмы и структуры данных Новая версия для Оберона + CD Ìîñêâà, 2023 Никлаус Вирт Перевод с английского под редакцией доктора физмат. наук Ткачева Ф. В. 3-е издание, электронное
УДК 32.973.26-018.2 ББК 004.438 В52 В52 Вирт, Никлаус. Алгоритмы и структуры данных / Н. Вирт ; пер. с англ. Ф. В. Ткачева. — 3-е изд., эл. — 1 файл pdf : 274 с. — Москва : ДМК Пресс, 2023. — Систем. требования: Adobe Reader XI либо Adobe Digital Editions 4.5 ; экран 10". — Текст : электронный. ISBN 978-5-89818-313-4 В классическом учебнике тьюринговского лауреата Н. Вирта аккуратно, на тщательно подобранных примерах прорабатываются основные темы алгоритмики — сортировка и поиск, рекурсия, динамические структуры данных. Перевод на русский язык выполнен заново, все рассуждения и программы проверены и исправлены, часть примеров по согласованию с автором переработана с целью максимального прояснения их логики (в том числе за счет использования цикла Дейкстры). Нотацией примеров теперь служит Оберон/Компонентный Паскаль — наиболее совершенный потомок старого Паскаля по прямой линии. Все программы проверены и работают в популярном варианте Оберона — системе Блэкбокс. Большая часть материала книги составляет необходимый минимум знаний по алгоритмике не только для программистов-профессионалов, но и любых других специалистов, активно использующих программирование в работе. Книга может быть использована как учебное пособие при обучении будущих программистов, начиная со старшеклассников в профильном обучении, а также подходит для систематического самообразования. Прилагаемые к книге файлы можно найти на сайте издательства. УДК 32.973.26-018.2 ББК 004.438 Электронное издание на основе печатного издания: Алгоритмы и структуры данных / Н. Вирт ; пер. с англ. Ф. В. Ткачева. — 2-е изд., испр. — Москва : ДМК Пресс, 2011. — 272 с. — ISBN 978-594074-734-5. — Текст : непосредственный. В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации. ISBN 978-5-89818-313-4 © N. Wirth, 1985 (Oberon version: August 2004 © Перевод на русский язык, исправления и изменения, Ф. В. Ткачев, 2011 © Оформление, издание, ДМК Пресс, 2011
Содержание О новой версии классического учебника Никлауса Вирта ....................................................................... 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
Содержание 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<trees) ............................................................. 227 4.8. Приоритетные деревья поиска ........................................... 246 Упражнения................................................................................ 250 Литература ................................................................................ 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].
О новой версии классического учебника Никлауса Вирта Что двойное переделывание программ и рассуждений в тексте (с Паскаля на Модулу%2 и затем на Оберон) не прошло безнаказанно, само по себе неудиви% тельно. Однако затруднения, возникшие при верификации программ и текста, хотя и были преодолены, все же показались чрезмерными. Поэтому, и ввиду учеб% ного назначения книги, встал ребром вопрос о необходимости доработки примеров. Предложения переводчика были одобрены автором на совместной рабочей сессии в апреле сего года и реализованы непосредственно в данном переводе (при первой возможности соответствующие изменения будут внесены и в прототип [1]). Во%первых, алгоритмы поиска образца в тексте переписаны в терминах цикла Дейкстры (многоветочный while [4]). Эта фундаментальная и мощная управля% ющая структура поразительным образом до сих пор не представлена в распро% страненных языках программирования, поэтому ей посвящено новое приложение C. Раздел 1.9, в который теперь выделены эти алгоритмы, будет неплохой иллю% страцией реального применения цикла Дейкстры. Вторая группа заметно изме% ненных программ – алгоритмы с возвратом в главе 3, в которых теперь экспли% цировано применение линейного поиска и, благодаря этому, тривиализована верификация. Такое прояснение рекурсивных комбинаторных алгоритмов явля% ется довольно общим. Обсуждались – но были признаны в данный момент неце% лесообразными – модификации и некоторых других программ. Надо заметить, что программистский стиль автора вырабатывался с конца 1950%х гг., когда проблема эффективности программ висела над головами про% граммистов дамокловым мечом, и за несколько лет до того, как Дейкстра опубли% ковал систематический метод построения программ [4]. В старых версиях книги заметна рефлекторная склонность к оптимизации до полного прояснения логики программ, что затрудняло эффективное применение формальной техники. Это легко объяснить: Н. Вирт осваивал только еще формирующиеся систематические методы, непосредственно участвуя в процессе создания программирования как академической дисциплины, версия за версией улучшая свои учебники. Но и через четверть века после последней существенной переделки учебника автором аналогичная склонность к преждевременной оптимизации при не просто не вполне уверенной, а напрочь отсутствующей формальной технике – и, как следствие, запутанные циклы, – характерные черты стиля «широких програм% мистских масс»! В профессиональных интернет%форумах до сих пор можно найти позорные дискуссии о том, нужно ли учиться писать циклы по Дейкстре, – и это в лучшем случае. Если же вообразить себе весь окружающий нас непрерывно рас% тущий массив софта, от которого наша жизнь зависит все больше, то впору впасть в депрессию: Quo usque tandem, Catilina? – Сколько еще нужно десятилетий, что% бы система образования вышла, наконец, на уровень, давным%давно достигнутый наукой? Во всяком случае, ясно, что едва ли не главная причина проблемы – хаос, царящий в системе ИТ%образования, тормозящий создание и распространение качественных методик и поддерживаемый, среди прочего, корыстными интереса% ми «монстров» индустрии. Здесь уместно сказать о языке Оберон/Компонентный Паскаль, пропаганди% руемом в качестве общей платформы для предполагаемой единой системы курсов
О новой версии классического учебника Никлауса Вирта программирования. Оберон – последний большой проект Никлауса Вирта, выда% ющегося инженера, ученого и педагога, вместе с Бэкусом, А. Ершовым, Дейкст% рой, Хоором и другими пионерами компьютерной информатики превратившего программирование в систематическую дисциплину и лучше всего известного со% зданием серии все более совершенных языков программирования – Паскаля (1970), Модулы%2 (1980) и наконец Оберона (1988, 2007). В этих языках отража% лось все более полное понимание проблематики эффективного программирова% ния. Языки эти сохраняют идейную и стилевую преемственность, и коммерсант, озабоченный сохранением доли рынка, не назвал бы их по%разному (ср. зоопарк бейсиков). Чтобы подчеркнуть эту преемственность, самому популярному диа% лекту Оберона было возвращено законное фамильное имя – Компонентный Пас% каль. Оберон/Компонентный Паскаль унаследовал лучшие черты старого доброго Паскаля и добавил к ним промышленный опыт Модулы%2 (на которой програм% мируются, например, российские спутники связи [5]), а также выверенный мини% мум средств объектно%ориентированного программирования. Принципальное до% стижение – удалось наконец добиться герметичности системы типов (теперь ее нельзя обойти средствами языка даже при работе с указателями). Это обеспечило возможность автоматического управления памятью (сбора мусора; до Оберона сбор мусора оставался прерогативой динамических языков – функциональных, скриптовых и т. п.) В результате диапазон эффективного применения Оберона, похоже, шире, чем у любого другого языка: это и вычислительные приложения, и системы управления любого масштаба (от беспилотников весом в 1 кг до гранди% озных каскадов ГЭС), и, например, задачи символической алгебры с предельно динамичными структурами данных. Особо следует остановиться на минимализме Оберона. Традиционно разра% ботчики сосредоточиваются на том, чтобы снабдить свои языки, программы, биб% лиотеки «богатым набором средств» – ведь так легче привлечь клиента, надеюще% гося побыстрее найти готовое решение для своих прикладных нужд. Погоня за «богатым набором средств» оборачивается ущербом качеству и надежности сис% темы. Вместе с коммерческими соображениями это приводит к тому, что полу% чается большая закрытая сложная система с вроде бы богатым набором средств, но хромающей надежностью и ограниченной расширяемостью, так что если поль% зователь сталкивается с нестандартной ситуацией в своих приложениях (что слу% чается сплошь и рядом – ведь разнообразие реального мира превосходит любое воображение писателей библиотек), то он оказывается в тупике. Н. Вирт еще со времен Паскаля, созданного в пику фантазийному Алголу%68 [6], пошел другим путем. Его гамбит заключался в том, чтобы, отказавшись от включения в язык максимума средств на все случаи жизни, тщательнейшим обра% зом выделить минимум реально ключевых средств, – обязательно включив в этот минимум все, что нужно для безболезненной, неограниченной расширяемости программных систем, – и добиться высоконадежной реализации такого ядра. Этот замысел был с блеском реализован Н. Виртом и его соратником Ю. Гуткнех% том в проекте Оберон [7]. Минимализм и уникальная надежность Оберона
О новой версии классического учебника Никлауса Вирта заставляют вспомнить автомат Калашникова. При этом вся мощь Оберона оказы% вается открытой даже программистам%непрофессионалам – физикам, инженерам, лингвистам.., занятым программированием изрядную долю своего рабочего времени. Для преподавателя важно, что в Обероне достигнуты ортогональность и сво% бодная комбинируемость языковых средств, смысловая прозрачность, а также беспрецедентно малый для столь мощного языка размер (см. полное описание синтаксиса в приложении B, а также обсуждение в [8]). В этом отношении Оберон побеждает за явным преимуществом традиционные промышленные языки, пре% словутая избыточная сложность которых оказывается источником своего рода ренты, взимаемой с остального мира. Оберон скромно уходит в тень при рассмо% трении любой языково%неспецифичной темы – от введения в алгоритмику до принципов компиляции и программной архитектуры. А после постановки базо% вой техники программирования на Обероне изучение промышленных языков за% частую сводится к изучению способов обходить дефекты их дизайна. Если уже старый Паскаль оказался настолько удачной платформой для обучения програм% мированию, что принес своему автору высшую почесть в компьютерной инфор% матике – премию им. Тьюринга, то понятно, что буквально вылизанный Оберон/ Компонентный Паскаль называют уже «практически идеальной» платформой для обучения программированию (см. также предисловие к [12]). Имея в виду исключительные педагогические достоинства Оберона, для всех примеров программ, приведенных в книге, обеспечена воспроизводимость в сис% теме программирования для Компонентного Паскаля, известной как Блэкбокс (BlackBox Component Builder [9]). Это пулярный вариант Оберона, созданный для работы в распространенных операционных системах. Конфигурации Блэк% бокса для использования в школе и университете доступны на сайте проекта «Ин% форматика%21» [2]. Открытый, бесплатный и безупречно современный Блэкбокс оказывается естественной заменой устаревшему Турбо Паскалю – заменой тем более привлекательной, что, несмотря на минимализм и благодаря автоматиче% скому управлению памятью, это более мощный инструмент, чем промышленные системы программирования на диалектах старого Паскаля. Краткое описание возможностей Блэкбокса с точки зрения использования в школьных курсах мож% но найти в статье [10]. Важное приложение к книге – полный комплект программ, представленных в тексте учебника, в виде, готовом к выполнению. Программы оформлены в отдель% ных модулях вместе с необходимыми вспомогательными процедурами, и все та% кие модули собраны в папке ADru/Mod/, которая должна лежать внутри основной папки Блэкбокса (следует иметь в виду, что файлы с расширением *.odc должны читаться из Блэкбокса). Читатель без труда разберется с компиляцией и запуском программ по комментариям в модулях, читая модули в том порядке, в каком они встречаются в тексте книги (или в лексикографическом порядке имен файлов). В тексте книги в начальных строках каждого законченного программного приме% ра справа указано имя соответствующего модуля. Например, комментарий (*ADruS18_ *) означает, что данная программа содержится в модуле
О новой версии классического учебника Никлауса Вирта 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 Ф. В. Ткачев
О новой версии классического учебника Никлауса Вирта [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/ [12] А. Шень. Программирование: теоремы и задачи. – МЦРМО, 1995.