Методы программирования: В 2-х томах. 1.2. Пер. с франц. Ю.А. Первина. Под ред. А. П. Ершова.-М.: Мир, 1982 368 с.
Второй том монографии французских ученых, посвященной основным понятиям информатики и трудным проблемам методологии программирования.
В гл. VI-VIII рассматриваются понятие рекурсии и эффективные алгоритмы. Последняя глава посвящена общим аспектам методологии программирования.
Книга рассчитана на профессиональных программистов, желающих овладеть современными методами программирования. Может служить учебным пособием по языкам программирования и алгоритмам.
ОГЛАВЛЕНИЕ
•а VI. Рекурсия *.....................
VI. 1. В защиту рекурсии.................. 6
VI.1.1. Введение.................... 6
VI.1.2. Рекурсивные определения и рекурсивные программы ... 6
VI.1.3. Свойства рекурсивных алгоритмов.......... 8
VI.2. Несколько рекурсивных программ............ 11
VI.2.1. Игра «Ханойская башня».............. 11,
VI.2.2. Численная задача................ 15
VI.2.3. Вычисление стоимости.............. 20
VI.2.4. Сортировка................... 22
VI.3. Практическая реализация рекурсии............ 24
VI.3.1. Рекурсия и языки программирования........ 24
VI.3.2. Задача..................... 25
VI.3.3. Практические правила реализации.......... 28
VI.3.3.1. Предварительная обработка......... 29
VI.3.3.2. Реализация рекурсивных вызовов....... 29
VI.3.3.3. -Перевод возвратов............. 31
и VI.3.3.4. Случай параметров-результатов........ 32
VI.3.3.5. Дополнение: косвенная рекурсия-исключение параметров .........(........ 34
VI.3.4. Представление стеков.....";......... 34
VI.3.4.1. Частный случай.............. 34
i VL3.4.2. Внутренние стеки подпрограммы....... 37
VI.3.4.3. Глобальный стек............. 38
VI.3.4.4. Цепное представление стека......... 41
VI.3.5. Упрощения. Исключение рекурсии.......... 42
VI.3.5.1. Попытка «структурирования»......... 43
VI.3.5.2. Построение обратных функций........ 49
V1.3.5.3. Исключение рекурсии............ 52
VI.4. Восходящее рекурсивное вычисление........... . 57
Последнее решение Ханойской башни........... 61
VI.5. Применение: алгоритмы последовательных испытаний..... 63
VI.5.1. Введение и определения.............. 63
VI.5.2. Алгоритм последовательных испытаний и искусственный
интеллект................... 65
VI.5.2.1. ДЕНДРАЛ, УРЗ.............. 66
V1.5.2.2. Деревья и/илн.............. 67
VI.5.2.3. SAINT................. 70
VI.5.3. Рекурсивная форма^ алгоритмов последовательных испытаний ....... ...... ........ 72
VI.5.4. Обработка простого примера............ 73
VI.5.5. Играющая программа............... 78
....... 83
Глава VII. Алгоритмы..................... g,
VII. 1. Общие сведения. Методы................ д,
VII.1.1. Сложность алгоритмов............. 9(
VII.1.2. Методы поиска эффективных алгоритмов...... д.
VII.1.2.1. «Разделяй и властвуй».......... д.
VII. 1.2.2. Уравновешивание............ д.
VII. 1.2.3. Компиляция и интерпретация....... jg(
VII. 1.2.4. Соотношение пространство-время...... д-
VII.2. Управление таблицами
9!
VII.2.1. Определение и общие сведения .......... 9)
VII.2.2. Последовательная неупорядоченная таблица ..... '10;
VII.2.2.1. Представления ............. До]
VII.2.2.2. Алгоритмы поиска ............ до-
VII.2.2.3. Алгоритм включения. Обсуждение ...... до;
VII.2.3. Упорядоченная последовательная таблица; дихотомиче-
ский поиск ................. . Доц
VII.2.3.1. Последовательный поиск в упорядоченной таб-
лице ............ • ..... 1(Х
VII.2.3.2. Последовательное включение ....... Ш
VII.2.3.3. Дихотомический поиск ...... .... ДО?
VII.2.3.4. Практическая сложность дихотомического поиска 108
VII.2.3.5. Обсуждение и заключение . . . ' ...... llf
VII.2.4. Двоичное дерево поиска . ............ Ш
VII.2.4.1. Метод ................. Ш
VII.2.4.2. Равновесные двоичные деревья ....... 12С
VII.2.5. Ассоциативная адресация ............. 128
VII.2.5.1. Определения и общие сведения ...... -128
VII.2.5.2. Выбор адресной функции ......... 131
VII.2.5.3. Внешнее разрешение коллизий ....... 132
VII.2.5.4. Разрешение коллизий в самом массиве ... 134 VII.2.5.5. Использование упорядоченности ключей в преды-
дущем методе . . ........... 138
VII.2.5.6. Вариации и заключение .......... 139
VII.3. Сортировка ........ ........... , . 140
VII.3.1. Задача .................... 140
VII.3.2. Определения ................. . 141
VII.3.3. Замечания о сложности алгоритмов сортировки . . . 143
VII.3.4. Главные базовые идеи .............. 144
VII.3.4.1. Сортировка включением .......... 144
VII.3.4.2. Сортировка слиянием .......... 145
VII.3.4.3. Сортировка обменами .......... 145
VII.3.4.4. Сортировка извлечением ......... 146
VII.3.4.5. Сортировка распределением ........ 146
VII.3.5. Сортировка включением. Метод Шелла ...... • 146
VII.3.5.1. Сортировка простым включением ...... 146
VII.3.5.2. Метод Шелла .... ....... ... 148
VII.3.6. Сортировка обменами; «Быстрая Сортировка» .... 152
VII.3.6.1. Пузырьковая Сортировка ......... 152
VII.3.6.2. Принцип Быстрой Сортировки ....... 153
VII.3.6.3. Построение эффективной Быстрой Сортировки 155
VII.3.6.4. Хорошая программа Деление ....... 16^)
VII.3.6.5. Исключение рекурсии и эффективная реализация 168
VII.3.7. Сортировка Извлечением: Древесная Сортировка ... ю
VII.3.8. Понятия сортировки распределением........ 183
VII.3.9. Практическое сравнение различных методов..... 184
II.4. Обработка текстов: алгоритм «сопоставления с образцом» ... 186
VII.4.1. Задача и тривиальный алгоритм.......... 186
VII.4.2. Алгоритм сопоставления образцов......... 190
VII.4.3. Алгоритм построения.............. 192
VII.4.4. Временная сложность.............. 197
VII.4.5. Пространственная сложность. Структуры данных . . . 197
библиография....................... 198
Упражнения....................... 199
Глава VIII. На путях к методологии............... 202
VIII.1. Сомнения...................... 203
VHI.2. Причины и цели................... 204
VIII.3. Уровни программирования............... 210
VIII.3.1. Единство программирования........... 211
VIII.3.2. Уровень абстракции. Виртуальные машины..... 212
VIII.3.2.1. Введение и определения......... 212
- —--------—~..ж..«_т ОППТНПОВКИ ..... 213
VIII.3.2.2. Пример: программы сортировки
VIII.3.2.3. Второй пример: транслятор.......215
VHI.3.2.4. Третий пример: бухгалтерия.......
„—„„ ... 217
------„ 216
VHI.3.3. Нисходящая и восходящая концепции....... 217
VIII.3.3.1. Определения.............. 217
VIII.3.3.2. Сложности, возникающие при использовании
нисходящего метода.......... 219
VIII.3.3.3. Проблемы, возникающие при использовании
восходящего метода.......... 222
VIII.3.3.4. Заключение.............. 223
VIII.3.4. Понятие модуля ................ 224
VHI.3.5. Статическое программирование. Язык Z . . . . . . 230
VIII.3.5.1. Определения: язык Z0......... 230
VHI.3.5.2. Уровень Z0.............. 231
VIII.3.5.3. Уровень Zj и его преобразования .... 232
VIII.3.5.4. Пример............... 233
VIII.3.5.5. Обсуждение............. 243
VIII.3.6. Программа и ее преобразования......... 248
VIII.4. Качества программы и возможности программиста..... 249
VIII.4.1. Должна ли программа быть хорошей?...... 249
VIII.4.2. Правильность-Доказательства-Тесты....... 249
Vni.4.2.1. Правильность программы........ 249
VTII.4.2.2. Доказательства: их роль и границы .... 251
VIII.4.2.3, Сравнение с традиционными методами . . . 253
VIII.4.2.4. Оператор ASSERT в АЛГОЛе W..... 254
VIII.4.2.5. Надо ли тестировать программы? .... 256 VIII.4.2.6. Средства диагностики при выполнении . . . 258 VIII.4.3. Читаемость, выражение, стиль, комментарии, документация .......'.............. 261
VIII.4.3.1. Читаемость программ.......... 261
VHI.4.3.2. Стиль и выражение.......... 262
VIII.4.3.3. Комментарии .............267
VIII.4.3.4. Документация.............270
VIII.4.4. Надежность; защищающее прюграммирование .... 272
VIII4.4.1. Надежность............. 272
VIII.4.4.2. Защищающее программирование..... 272
VIII.4.5. Гибкость. Адаптируемость. Универсальность..... 276
VIII.4.6. Переносимость".................277]'
VIII.4.7. Эффективность: оптимизация........Л . . 2-78
VIII.5. Программист и другие................ 283
VIII.5.1. Бригада программистов............. 284
VIII.5.1.1. Задачи................ 284<
VIII.5.1.2. Бригада главного программиста..... 286|
VIII.5.2. Программист. Заказчик. Пользователь........ 288 i
Эскиз библиографии.................... 292i
Ответы к упражнениям и задачам.............. 294!
Глава I........................ 294
Глава II...................... 295
Глава III...................... 296
Глава IV...................... 305
Глава V...........'........... 307
Глава VI...................... 309
Глава VII....................;.. 322
Приложения....................... 330
Приложение А. Алгоритмическая нотация......... 330
Приложение Б. Англо-франко-русский словарь основных терминов программирования.......... 336
Приложение В. Встроенные (стандартные) функции в ФОРТРАНе 341 Приложение Т. Соглашения АЛГОЛа W о типе результата арифметических операций........... 344
Встроенные процедуры и переменные в АЛГОЛе
W.................. 345
Приложение Д. Встроенные функции в ПЛ/1 (частичный список) 349
Библиография.................... 353
Цена: 150руб.
