Алгоритмы и структуры данных. Новая версия для Оберона (3000,00 руб.)

Стр.3

Стр.4

Стр.5

УДК 32.973.26018.2 ББК 004.438 В52 В52 Алгоритмы и структуры данных. Новая версия для Оберона + CD / Пер. с англ. Ткачев Ф. В. – М.: ДМК Пресс, 2011. – 272 с.: ил. Никлаус Вирт ISBN 9785940747345 В классическом учебнике тьюринговского лауреата Н.Вирта аккуратно, на тщательно подобранных примерах прорабатываются основные темы алго ритмики – сортировка и поиск, рекурсия, динамические структуры данных. Перевод на русский язык выполнен заново, все рассуждения и програм мы проверены и исправлены, часть примеров по согласованию с автором переработана с целью максимального прояснения их логики (в том числе за счет использования цикла Дейкстры). Нотацией примеров теперь служит Оберон/Компонентный Паскаль – наиболее совершенный потомок старого Паскаля по прямой линии. Все программы проверены и работают в популярном варианте Оберона – системе Блэкбокс, и доступны в исходниках на прилагаемом CD вместе с самой системой и дополнительными материалами. Большая часть материала книги составляет необходимый минимум знаний по алгоритмике не только для программистовпрофессионалов, но и любых других специалистов, активно использующих программирование в работе. Книга может быть использована как учебное пособие при обучении буду щих программистов, начиная со старшеклассников в профильном обуче нии, а также подходит для систематического самообразования. Содержание компактдиска: Базовая конфигурация системы Блэкбокс с коллекцией модулей, реализующих программы из книги. Базовые инструкции по работе в системе Блэкбокс. Полный перевод документации системы Блэкбокс на русский язык. Конфигурация системы Блэкбокс для использования во вводных курсах програм мирования в университетах. Конфигурация системы Блэкбокс для использования в школах (полная русифика ция меню, сообщений компилятора, с возможностью использования ключевых слов на русском и других национальных языках). Доклады участников проекта Информатика21 по опыту использования системы Блэкбокс в обучении программированию. Оригинальные дистрибутивы системы Блэкбокс 1.5 (основной рабочий) и 1.6rc6. Инструкции по работе в Блэкбоксе под Linux/Wine. Дистрибутив оптимизирующего компилятора XDS Oberon (версии Linux и MS Windows). OberonScript – аналог JavaScript для использования в Webприложениях. ISBN 0130220059 (анг.) ISBN 9785940747345 © N. Wirth, 1985 (Oberon version: August 2004) © Перевод на русский язык, исправления и изменения, Ф. В. Ткачев, 2011 © Оформление, издание, ДМК Пресс, 2011

Стр.3

Содержание О новой версии классического учебника Никлауса Вирта ....................................................................... 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

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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

Стр.5