Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Алгоритмы и структуры данных

Покупка
Артикул: 816350.01.99
Доступ онлайн
183 ₽
В корзину
В классическом учебнике тьюринговского лауреата Н. Вирта аккуратно, на тщательно подобранных примерах прорабатываются основные темы алгоритмики — сортировка и поиск, рекурсия, динамические структуры данных. Перевод на русский язык выполнен заново, все рассуждения и программы проверены и исправлены, часть примеров по согласованию с автором переработана с целью максимального прояснения их логики (в том числе за счет использования цикла Дейкстры). Нотацией примеров теперь служит Оберон/Компонентный Паскаль — наиболее совершенный потомок старого Паскаля по прямой линии. Все программы проверены и работают в популярном варианте Оберона — системе Блэкбокс. Большая часть материала книги составляет необходимый минимум знаний по алгоритмике не только для программистов-профессионалов, но и любых других специалистов, активно использующих программирование в работе. Книга может быть использована как учебное пособие при обучении будущих программистов, начиная со старшеклассников в профильном обучении, а также подходит для систематического самообразования. Прилагаемые к книге файлы можно найти на сайте издательства.
Вирт, Н. Алгоритмы и структуры данных : учебное пособие / Н. Вирт ; пер. с англ. Ф. В. Ткачева. - 3-е изд. - Москва : ДМК Пресс, 2023. - 274 с. - ISBN 978-5-89818-313-4. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2102600 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Алгоритмы и структуры данных
Новая версия для Оберона + 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.


Доступ онлайн
183 ₽
В корзину