Главная Структуры данных и алгоритмы

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

, , , , ,
0 / 0
Насколько вам понравилась эта книга?
Какого качества скаченный файл?
Скачайте книгу, чтобы оценить ее качество
Какого качества скаченные файлы?
В этой книге подробно рассмотрены структуры данных и алгоритмы, которые являются фундаментом современной методологии разработки программ. Показаны разнообразные реализации абстрактных типов данных, начиная от стандартных списков, стеков, очередей и заканчивая множествами и отображениями, которые используются для неформального описания и реализации алгоритмов. Две главы книги посвящены методам анализа и построения алгоритмов; приведено и исследовано множество различных алгоритмов для работы с графами, внутренней и внешней сортировки, управления памятью. Книга не требует от читателя специальной подготовки, только предполагает его знакомство с какими-либо языками программирования высокого уровня, такими как Pascal. Вместе с тем она будет полезна специалистам по разработке программ и алгоритмов и может быть использована как учебное пособие для студентов и аспирантов, специализирующихся в области компьютерных наук.
Категории:
Год:
2000
Издательство:
Вильямс
Язык:
russian
Страницы:
382
ISBN 10:
0201000237
ISBN 13:
9785845901224
Файл:
DJVU, 4,05 MB
Скачать (djvu, 4,05 MB)

Возможно Вас заинтересует Powered by Rec2Me

 

Ключевые слова

 
0 comments
 

Чтобы оставить отзыв, пожалуйста, войдите или зарегистрируйтесь
Вы можете оставить отзыв о книге и поделиться своим опытом. Другим читателям будет интересно узнать ваше мнение о прочитанных книгах. Независимо от того, пришлась ли вам книга по душе или нет, если вы честно и подробно расскажете об этом, люди смогут найти для себя новые книги, которые их заинтересуют.
2

Программирование игр и головоломок

سال:
1990
زبان:
russian
فائل:
DJVU, 2.45 MB
0 / 0
СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ АЛЬФРЕД В. АХО Bell Laboratories Муррей-Хилл, Нью-Джерси ДЖОН Э. ХОПКРОФТ Корнеллскийуниверситет Итака, Нью-Йорк ДЖЕФФРИ Д. УЛЬМАН Станфордский университет Станфорд, Калифорния Издательский дом "Вильяме" Москва ¦ Санкт-Петербург ¦ 2000

DATA STRUCTURES AMD ALGORITHMS ALFRED V. AHO Bell Laboratories Murray Hill, New Jersey JOHN E. HOPKROFT Cornell University Ithaca, New York JEFFREY D. ULLMAN Stanford University Stanford, California TT ADDISON-WESLEY PUBLISHING COMP Reading, Massachusetts ¦ Menlo Park, G London ¦ Amsterdam ¦ Don Mills, Ontari

ББК 32.973.26-018.2я75 А95 УДК 681.3.07 Издательский дом "Вильяме" Зав. редакцией С. Н. Тригуб Перевод с английского и редакция канд. физ.-матп. наук А. А. Минько По общим вопросам обращайтесь в Издательский дом "Вильяме" по адресу. info@williamspublishing.com, http://www.williamspublishing.com Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. А95 Структуры данных и алгоритмы. : Пер. с англ. : Уч. пос. — М. : Из- Издательский дом "Вильяме", 2000. — 384 с. : ил. — Парал. тит. англ. ISBN 5-8459-0122-7 (рус.) В этой книге подробно рассмотрены структуры данных и алгоритмы, кото- которые являются фундаментом современной методологии разработки программ. Показаны разнообразные реализации абстрактных типов данных, начиная от стандартных списков, стеков, очередей и заканчивая множествами и отображе- отображениями, которые используются для неформального описания и реализации алго- алгоритмов. Две главы книги посвящены методам анализа и построения алгоритмов; приведено и исследовано множество различных алгоритмов для работы с графа- графами, внутренней и внешней сортировки, управления памятью. Книга не требует от читателя специальной подготовки, только предполагает его знакомство с какими-либо языками программирования высокого уровня, та- такими как Pascal. Вместе с тем она будет полезна специалистам по разработке программ и алгоритмов и может быть использована как учебное пособие для студентов и аспирантов,;  специализирующихся в области компьютерных наук. ББК 32.973.26-018.2я75 Все названия программных продуктов являются зарегистрированными торговыми марка- марками соответствующих фирм. Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, будь то электронные или ме- механические, включая фотокопирование и запись на магнитный носитель, если на это нет письменного разрешения издательства Addison-Wesley Publishing Company, Inc. Rights to this book were obtained by arrangement with Addison-Wesley Longman, Inc. Russian language edition published by Williams Publishing House according to the Agreement with R&I Enterprises International, Copyright © 2000 Издательство выражает признательность Дмитрию Владимировичу Виленскому за ин- информационную поддержку ISBN 5-8459-0122-7 (рус.) © Издательский дом "Вильяме", 2000 ISBN 0-201-00023-7 (англ.) © Addison-Wesley Publishing Company, Inc.

Оглавление ГЛАВА 1. Построение и анализ алгоритмов 15 ГЛАВА 2. Основные абстрактные типы данных 45 ГЛАВА 3. Деревья 77 ГЛАВА 4. Основные операторы множеств 103 ГЛАВА 5. Специальные методы представления множеств 146 ГЛАВА 6. Ориентированные графы 183 ГЛАВА 7. Неориентированные графы 208 ГЛАВА 8. Сортировка 228 ГЛАВА 9. Методы анализа алгоритмов 265 ГЛАВА 10. Методы разработки алгоритмов 276 ГЛАВА 11. Структуры данных и алгоритмы для внешней памяти 311 ГЛАВА 12. Управление памятью 339 Список литературы 369

Содержание Предисловие 12 Представление алгоритмов 12 Содержание книги 12 Упражнения 13 Благодарности 14 ГЛАВА 1. Построение и анализ алгоритмов 15 1.1. От задачи к программе 15 Алгоритмы 16 Псевдоязык и пошаговая "кристаллизация" алгоритмов 20 Резюме 22 1.2. Абстрактные типы данных 23 Определение абстрактного типа данных 23 1.3. Типы данных, структуры данных и абстрактные типы данных 25 Указатели и курсоры 26 1.4. Время выполнения программ 28 Измерение времени выполнения программ 28 Асимптотические соотношения 29 Ограниченность показателя степени роста 30 Немного соли 32 1.5. Вычисление времени выполнения программ 32 Вызовы процедур 35 Программы с операторами безусловного перехода 36 Анализ программ на псевдоязыке 37 1.6. Практика программирования 37 1.7. Расширение языка Pascal 39 Упражнения 40 Библиографические замечания 44 ГЛАВА 2. Основные абстрактные типы данных 45 2.1. Абстрактный тип данных "Список" 45 2.2. Реализация списков 48 Реализация списков посредством массивов 48 Реализация списков с помощью указателей 50 Сравнение реализаций 53 Реализация списков на основе курсоров 54 Дважды связные списки 57 2.3. Стеки 58 Реализация стеков с помощью массивов 60 2.4. Очереди 61 Реализация очередей с помощью указателей 62 Реализация очередей с помощью циклических массивов 63 2.5. Отобрав ния 66 Реализация отображений посредством массивов 67 Реализация отображений посредством списков 68 2.6. Стеки и рекурсивные процедуры 69 Исключение "концевых" рекурсий 70 6 СОДЕРЖАНИЕ

Полное исключение рекурсий 70 Упражнения 72 Библиографические примечания 76 ГЛАВА 3. Деревья 77 3.1. Основная терминология 77 Порядок узлов 78 Прямой, обратный и симметричный обходы дерева 79 Помеченные деревья и деревья выражений 81 Вычисление "наследственных" данных 82 3.2. Абстрактный тип данных TREE 83 3.3. Реализация деревьев 85 Представление деревьев с помощью массивов 85 Представление деревьев с использованием списков сыновей 86 Представление левых сыновей и правых братьев 88 3.4. Двоичные деревья 91 Представление двоичных деревьев 92 Пример: коды Хаффмана 92 Реализация двоичных деревьев с помощью указателей 98 Упражнения 99 Библиографические замечания 102 ГЛАВА 4. Основные операторы множеств 103 4.1. Введения в множества 103 Система обозначений для множеств 104 Операторы АТД, основанные на множествах 105 4.2. АТД с операторами множеств 105 4.3. Реализация множеств посредством двоичных векторов 109 4.4. Реализация множеств посредством связанных списков 110 4.5. Словари 113 4.6. Реализации словарей 115 4.7. Структуры данных, основанные на хеш-таблицах 116 Открытое хеширование 117 Закрытое хеширование 120 4.8. Оценка эффективности хеш-функций 122 Анализ закрытого хеширования 124 "Случайные" методики разрешения коллизий 126 Реструктуризация хеш-таблиц 128 4.9. Реализация АТД для отображений 128 4.10. Очереди с приоритетами 129 4.11. Реализация очередей с приоритетами 131 Реализация очереди с приоритетами посредством частично упорядоченных деревьев 133 Реализация частично упорядоченных деревьев посредством массивов 135 4.12. Некоторые структуры сложных множеств 137 Отношения "многие-ко-многим" и структура мультисписков 137 Структуры мультисписков 139 Эффективность двойных структур данных 142 Упражнения 143 Библиографические примечания 145 ГЛАВА 5. Специальные методы представления множеств 146 5.1. Деревья двоичного поиска 146 5.2. Анализ времени выполнения операторов 150 Эффективность деревьев двоичного поиска 152 СОДЕРЖАНИЕ 7

5.3. Нагруженные деревья 152 Узлы нагруженного дерева как АТД 154 Представление узлов нагруженного дерева посредством списков 156 Эффективность структуры данных нагруженных деревьев 157 5.4. Реализация множеств посредством сбалансированных деревьев 158 Вставка элемента в 2-3 дерево 159 Удаление элемента из 2-3 дерева 161 Типы данных для 2-3 деревьев 162 Реализация оператора INSERT 162 Реализация оператора DELETE 166 5.5. Множества с операторами MERGE и FIND 167 Простая реализация АТД MFSET 168 Быстрая реализация АТД MFSET 169 Реализация АТД MFSET посредством деревьев 172 Сжатие путей 173 Функция а(л) 174 5.6. АТД с операторами MERGE и SPLIT 175 Задача наибольшей общей подпоследовательности 175 Анализ времени выполнения алгоритма нахождения НОП 177 Упражнения 179 Библиографические примечания 181 ГЛАВА 6. Ориентированные графы 183 6.1. Основные определения 183 6.2. Представления ориентированных графов 184 АТД для ориентированных графов 186 6.3. Задача нахождения кратчайшего пути 187 Обоснование алгоритма Дейкстры 189 Время выполнения алгоритма Дейкстры 191 6.4. Нахождение кратчайших путей между парами вершин 191 Сравнение алгоритмов Флойда и Дейкстры 193 Вывод на печать кратчайших путей 193 Транзитивное замыкание 194 Нахождение центра ориентированного графа 195 6.5. Обход ориентированных графов 196 Анализ процедуры поиска в глубину 197 Глубинный остовный лес 198 6.6. Ориентированные ациклические графы 200 Проверка ацикличности орграфа 201 Топологическая сортировка 202 6.7. Сильная связность 203 Упражнения 205 Библиографические примечания 207 ГЛАВА 7. Неориентированные графы 208 7.1. Основные определения 208 Представление неориентированных графов 210 7.2. Остовные деревья минимальной стоимости 211 Свойство остовных деревьев минимальной стоимости 211 Алгоритм Прима 212 Алгоритм Крускала 214 7.3. Обход неориентированных графов 217 Поиск в глубину 217 Поиск в ширину 218 7.4. Точки сочленения и двусвязные компоненты 220 8 СОДЕРЖАНИЕ

7.5. Паросочетания графов 222 Упражнения 225 Библиографические примечания 227 ГЛАВА 8. Сортировка 228 8.1. Модель внутренней сортировки 228 8.2. Простые схемы сортировки 229 Сортировка вставками 231 Сортировка посредством выбора 232 Временная сложность методов сортировки 233 Подсчет перестановок 233 Ограниченность простых схем сортировки 234 8.3. Быстрая сортировка 235 Временная сложность быстрой сортировки 238 Время выполнения быстрой сортировки в среднем 240 Реализация алгоритма быстрой сортировки 243 8.4. Пирамидальная сортировка 244 Анализ пирамидальной сортировки 246 8.5. "Карманная" сортировка 247 Анализ "карманной" сортировки 249 Сортировка множеств с большими значениями ключей 250 Общая поразрядная сортировка 252 Анализ поразрядной сортировки 253 8.6. Время выполнения сортировок сравнениями 254 Деревья решений 254 Размер дерева решений 256 Анализ времени выполнения в среднем 257 8.7. Порядковые статистики 258 Вариант быстрой сортировки 258 Линейный метод нахождения порядковых статистик 259 Случай равенства некоторых значений ключей 261 Упражнения 261 Библиографические примечания 264 ГЛАВА 9. Методы анализа алгоритмов 265 9.1. Эффективность алгоритмов 265 9.2. Анализ рекурсивных программ 266 9.3. Решение рекуррентных соотношений 267 Оценка решений рекуррентных соотношений 268 Оценка решения рекуррентного соотношения методом подстановки 269 9.4. Общее решение большого класса рекуррентных уравнений 270 Однородные и частные решения 271 Мультипликативные функции 271 Другие управляющие функции 272 Упражнения ,27? Библиографические примечания 275 ГЛАВА 10. Методы разработки алгоритмов 276 10.1. Алгоритмы "разделяй и властвуй" 276 Умножение длинных целочисленных значений 277 Составление графика проведения теннисного турнира 279 Баланс подзадач 280 10.2. Динамическое программирование 280 Вероятность победы в спортивных турнирах 281 Задача триангуляции 283 СОДЕРЖАНИЕ 9

Поиск решений на основе таблицы 288 10.3. "Жадные" алгоритмы 288 "Жадные" алгоритмы как эвристики 289 10.4. Поиск с возвратом 291 Функции выигрыша 293 Реализация поиска с возвратом 294 Альфа-бета отсечение 295 Метод ветвей и границ 296 Ограничения эвристических алгоритмов 298 10.5. Алгоритмы локального поиска 302 Локальные и глобальные оптимальные решения 303 Задача коммивояжера 303 Размещение блоков 306 Упражнения 308 Библиографические примечания 310 ГЛАВА 11. Структуры данных и алгоритмы для внешней памяти 311 11.1. Модель внешних вычислений 311 Стоимость операций со вторичной памятью 312 11.2. Внешняя сортировка 313 Сортировка слиянием 313 Ускорение сортировки слиянием 316 Минимизация полного времени выполнения 316 Многоканальное слияние 317 Многофазная сортировка 318 Когда скорость ввода-вывода не является "узким местом" 319 Схема с шестью входными буферами 320 Схема с четырьмя буферами 321 11.3. Хранение данных в файлах 323 Простая организация данных 324 Ускорение операций с файлами 325 Хешированные файлы 325 Индексированные файлы 327 Несортированные файлы с плотным индексом 328 Вторичные индексы 329 11.4. Внешние деревья поиска 330 Разветвленные деревья поиска 330 В-деревья 330 Поиск записей 331 Вставка записей 331 Удаление записей 332 Время выполнения операций с В-деревом 333 Сравнение методов 334 Упражнения 335 Библиографические примечания 338 ГЛАВА 12. Управление памятью 339 12.1. Проблемы управления памятью 339 12.2. Управление блоками одинакового размера 343 Контрольные счетчики 344 12.3. Алгоритмы чистки памяти для блоков одинакового размера 344 Сборка на месте 346 Алгоритм Дойча : Шорра : Уэйта без использования поля back 351 10 СОДЕРЖАНИЕ

12.4. Выделение памяти для объектов разного размера 352 Фрагментация и уплотнение пустых блоков 353 Выбор свободных блоков 357 12.5. Методы близнецов 359 Распределение блоков 360 Выделение блоков 361 Возврат блоков в свободное пространство 362 12.6. Уплотнение памяти 363 Задача уплотнения памяти 364 Алгоритм Морриса 365 Упражнения 366 Библиографические примечания 368 Список литературы 369 Предметный указатель 375 СОДЕРЖАНИЕ 11

Предисловие В этой книге описаны структуры данных и алгоритмы, которые являются фундамен- фундаментом современного компьютерного программирования. Основу данной книги состав- составляют первые шесть глав нашей ранее изданной книги The Design and Analysis of Computer Algorithms1. Мы расширили ее содержание, включив материал по алгорит- алгоритмам внешнего хранения и управлению памятью. Как и предыдущая, эта книга мо- может составить основу учебного курса по структурам данным и алгоритмам. Мы не требуем от читателя специальной подготовки, только предполагаем его знакомство с какими-либо языками программирования высокого уровня, такими как Pascal. Мы попытались осветить структуры данных и алгоритмы в более широком кон- контексте решения задач с использованием вычислительной техники, а также использо- использовали абстрактные типы данных для неформального описания и реализации алгорит- алгоритмов. И хотя сегодня абстрактные типы данных только начинают применять в совре- современных языках программирования, авторы считают, что они являются полезным инструментом при разработке программ независимо от применяемого языка про- программирования . Мы также постоянно подчеркиваем и внедряем идею вычисления и оценки вре- времени выполнения алгоритмов (временную сложность алгоритмов) как составную часть процесса компьютерного решения задач. В этом отражается наша надежда на то, что программисты осознают, что при решении задач прогрессирующе больших размеров особое значение имеет временная сложность выбранного алгоритма, а не возможности новых поколений вычислительных средств. Представление алгоритмов Мы используем язык Pascal для представления описываемых алгоритмов и структур данных просто потому, что это широко известный язык программирова- программирования. В начале книги алгоритмы часто будут представлены как в абстрактной фор- форме, так и на языке Pascal. Это сделано для того, чтобы показать весь спектр про- проблем при решении практических задач: от проблемы формализации задачи до про- проблем, возникающих во время выполнения законченной программы. Алгоритмы, которые мы представляем, можно реализовать на любых языках программирова- программирования высокого уровня. Содержание книги В главе 1 содержатся вводные замечания и обсуждаются реализации процесса ис- исходная задача — готовая программа и роль абстрактных типов данных в этом про- процессе. Здесь также можно познакомиться с математическим аппаратом, необходи- необходимым для оценивания времени выполнения алгоритмов. В главе 2 рассматриваются традиционные структуры списков, стеков и очередей, а также отображения, которые являются абстрактным типом данных, основанным на математическом понятии функции. В главе 3 вводятся деревья и основные структу- структуры данных, которые эффективно поддерживают различные операторы, выполняемые над деревьями. В главах 4, 5 рассмотрено большое количество абстрактных типов данных, основанных на математической модели множеств. Достаточно глубоко исследо- исследованы словари и очереди с приоритетами. Рассмотрены стандартные реализации этих абстрактных типов данных, такие как хеш-таблицы, двоичные деревья по- 1 Существует перевод этой книги на русский язык: Построение и анализ вычислительных алгоритмов. — М., "Мир", 1979. — Прим. ред. 12 ПРЕДИСЛОВИЕ

«ска, частично упорядоченные деревья, 2-3 деревья и др. Более сложный мате- материал помещен в главу 5. Главы 6, 7 содержат материал, относящийся к графам; ориентированные графы рассмотрены в главе 6, а неориентированные — в главе 7. Эти главы начинают раз- раздел книги, который больше посвящен алгоритмам, чем структурам данных, хотя мы продолжаем обсуждать основные структуры данных, подходящие для Представления графов. Б этих главах представлено большое количество алгоритмов для работы с графами, включая алгоритмы поиска в глубину, нахождения минимального остовно- го дерева, кратчайших путей и максимальных паросочетаний. В главе 8 рассмотрены основные алгоритмы внутренней сортировки: быстрая сор- сортировка, пирамидальная сортировка, "карманная" сортировка, а также более про- простые (и менее эффективные) методы, например метод Сортировки вставками. В конце главы описаны алгоритмы с линейным временем выполнения для нахождения меди- медиан и других порядковых статистик. В главе 9 обсуждаются асимптотические методы анализа рекурсивных программ. Здесь, конечно же, рассмотрены методы решения рекуррентных соотношений. В главе 10 сравнительно кратко (без глубокого анализа) рассмотрены методы разра- разработки алгоритмов, включая методы декомпозиции, динамическое программирование, алгоритмы локального поиска и различные формы организации деревьев поиска. Последние две главы посвящены организации внешнего хранения И управлению памятью. Глава 11 охватывает методы внешней сортировки и организацию внешнего хранения данных, включая В-деревья и индексные структуры. Материал по управлению памятью, содержащийся в главе 12, условно Можно раз- разбить на четыре части, в зависимости от того, являются ли блоки памяти фиксиро- фиксированной или переменной длины, а также от того, явно или неявно осуществляется очистка памяти. Материал этой книги авторы использовали в программе лекционных курсов по структурам данным и алгоритмам в Колумбийском, Корнеллском и Станфордском университетах как для студентов, так и для аспирантов. Например, предваритель- предварительную версию этой книги использовали в Станфордском университете как основу 10- недельного курса по структурам данных для студентов первого года обучения. Этот курс включал материал глав 1-4, 9, 10, 12 и частично из глав 5-7. Упражнения В конце каждой главы приведено много упражнений различной степени сложно- сложности. С помощью многих из них можно просто проверить усвоение изложенного мате- материала. Некоторые упражнения требуют дополнительных усилий и размышлений, они помечены одной звездочкой. Упражнения, помеченные двумя звездочками, рассчитаны на студентов старших курсов и аспирантов. Библиографические приме- примечания в конце каждой главы предлагают ссылки на дополнительную литературу. ПРЕДИСЛОВИЕ 13

Благодарности Мы хотим выразить благодарность компании Bell Laboratories за предоставление превосходных коммуникационных средств и средств подготовки текстов (основанных на UNIX™), которые позволили легко подготовить рукопись географически разде- разделенным авторам. Многие наши коллеги, прочитав различные части рукописи, сдела- сделали ценные замечания. Особенно мы хотим поблагодарить за полезные предложения Эда Бекхама (Ed Beckham), Джона Бентли (Jon Bentley), Кеннета Чу (Kenneth Chu), Джанет Кореи (Janet Coursey), Хенка Кокса (Hank Сох), Нейла Иммермана (Neil Im- merman), Брайана Кернигана (Brian Kernighan), Стива Мехени (Steve Mahaney), Крейга Мак-Мюррей (Craig McMurray), Альберто Мендельзона (Alberto Mendelzon), Элистер Моффат (Alistair Moffat), Джеффа Нотона (Jeff Naughton), Керри Нимови- чер (Kerry Nemovicher), Пола Ниэмки (Paul Niamkey), Ёшио Оно (Yoshio Ohno), Роба Пайка (Rob Pike), Криса Руэна (Chris Rouen), Мориса Шлумбергера (Maurice Schlum- berger), Стенли Селкова (Stanley Selkow), Ченгай Ши (Chengya Shih), Боба Тарьяна (Bob Tarjan), В. Ван Снайдера (W. Van Snyder), Питера Вейнбергера (Peter Wein- Weinberger) и Энтони Брекериса (Anthony Yeracaris). Наконец, мы хотим принести ог- огромную благодарность г-же Клейр Мецгер -(Claire Metzger) за профессиональную по- помощь при подготовке рукописи к печати. A.V.A. J.E.H. J.D.U. 14 ПРЕДИСЛОВИЕ

ГЛАВА 1 Построение и анализ алгоритмов Процесс создания компьютерной программы для решения какой-либо практиче- практической задачи состоит из нескольких этапов; формализация и создание техниче- технического задания на исходную задачу; разработка алгоритма решения задачи; напи- написание, тестирование, отладка и документирование программы; получение реше- решения исходной задачи путем выполнения законченной программы. В данной главе мы покажем подходы к реализации этих этапов, а в последующих рассмотрим алгоритмы и структуры данных как строительные блоки создаваемых компью- компьютерных программ. 1.1. От задачи к программе Половина дела сделана, если знать, что исходная задача имеет решение. В первом приближении большинство задач, встречающихся на практике, не имеют четкого и однозначного описания. Определенные задачи, такие как разработка рецепта вечной молодости или сохранение мира во всем мире, вообще невозмож- невозможно сформулировать в терминах, допускающих компьютерное решение. Даже если мы предполагаем, что наша задача может быть решена иа компьютере, обычно для ее формального описания требуется огромное количество разнообразных па- параметров. И часто только в ходе дополнительных экспериментов можно найти интервалы изменения этих параметров. Если определенные аспекты решаемой задачи можно выразить в терминах ка- какой-либо формальной модели, то это, безусловно, необходимо сделать, так как в этом случае в рамках формальной модели мы можем узнать, существуют ли мето- методы и алгоритмы решения нашей задачи. Даже если такие методы и алгоритмы не существуют на сегодняшний день, то привлечение средств и свойств формальной модели поможет в построении "подходящего" решения исходной задачи. Практически любую область математики или других иаук можно привлечь к построению модели определенного круга задач. Для задач, числовых по своей природе, можно построить модели на основе общих математических конструк- конструкций, таких как системы линейных уравнений (например, для задач расчета электрических цепей или напряжений в закрепленных балках), Дифференциаль- Дифференциальные уравнения (задачи прогноза роста популяций или расчета скорости протека- протекания химических реакций). Для задач с символьными или текстовыми данными можно применить модели символьных последовательностей или формальных грамматик. Решение таких задач содержит этапы компиляции (преобразование программ, написанных на языке высокого уровня, в программы на машинно- ориентированных языках) и информационного поиска (распознавание определен- определенных слов в списках заголовков каких-либо библиотек и т.п.).

Алгоритмы Когда построена (подобрана) подходящая модель исходной задачи, то естествен- естественно искать решение в терминах этой модели. На этом этапе основная цель заключа- заключается в построении решения в форме алгоритма, состоящего из конечной последо- последовательности инструкций, каждая из которых имеет четкий смысл и может быть выполнена с конечными вычислительными затратами за конечное время. Целочис- Целочисленный оператор присваивания х := у + z — пример инструкции, которая будет выполнена с конечными вычислительными затратами. Инструкции могут выпол- выполняться в алгоритме любое число раз, при этом они сами определяют число повто- повторений. Однако мы требуем, чтобы при любых входных данных алгоритм завер- завершился после выполнения конечного числа инструкций. Таким образом, программа, написанная на основе разработанного алгоритма, при любых начальных данных никогда не должна приводить к бесконечным циклическим вычислениям. Есть еще один аспект определения алгоритмов, о котором необходимо сказать. Выше мы говорили, что алгоритмические инструкции должны иметь "четкий смысл" и выполняться с "конечными вычислительными затратами". Естественно, то, что понятно одному человеку и имеет для него "четкий смысл", может совер- совершенно иначе представляться другому. То же самое можно сказать о понятии "конечных затрат": на практике часто трудно доказать, что при любых исходных данных выполнение последовательности инструкций завершится, даже если мы четко понимаем смысл каждой инструкции. В этой ситуации, учитывая все аргу- аргументы за и против, было бы полезно попытаться достигнуть соглашения о "конечных затратах" в отношении последовательности инструкций, составляющих алгоритм. Однако кажущаяся сложность подобных доказательств может быть об- обманчивой. В разделе 1.5 мы оценим время выполнения основных структур языков программирования, что докажет конечность времени их выполнения и соответст- соответственно конечность вычислительных затрат. Кроме программ на языке Pascal, мы часто будем представлять алгоритмы с помощью псевдоязыка программирования, который комбинирует обычные конструк- конструкции языков программирования с выражениями на "человеческом" языке. Мы ис- используем Pascal как язык программирования, но практически любой другой язык программирования может быть использован вместо него для представления алгорит- алгоритмов, рассматриваемых в этой книге. Следующие примеры иллюстрируют основные этапы создания компьютерной программы. Пример 1.1. Рассмотрим математическую модель, используемую для управления светофорами на сложном перекрестке дорог. Мы должны создать программу, которая в качестве входных данных использует множество всех допустимых поворотов на пере- перекрестке (продолжение прямой дороги, проходящей через перекресток, также будем считать "поворотом") и разбивает это множество на несколько групп так, чтобы все по- повороты в группе могли выполняться одновременно, не создавая проблем друг для дру- друга. Затем мы сопоставим с каждой группой поворотов соответствующий режим работы светофоров на перекрестке. Желательно минимизировать число разбиений исходного множества поворотов, поскольку при этом минимизируется количество режимов рабо- работы светофоров на перекрестке. Для примера на рис. 1.1 показан перекресток возле Принстонского университета, известный сложностью его преодоления. Обратите внимание, что дороги С и Е одно- односторонние, остальные — двухсторонние. Всего на этом перекрестке возможно 13 по- поворотов. Некоторые из этих поворотов, такие как АВ (поворот с дороги А на дорогу В) и ЕС, могут выполняться одновременно. Трассы других поворотов, например AD и ЕВ, пересекаются, поэтому их нельзя выполнять одновременно. Режимы работы све- светофоров должны учитывать эти обстоятельства и не допускать одновременного вы- выполнения таких поворотов, как AD и ЕВ, но могут разрешать совместное выполнение поворотов, подобных АВ и ЕС. 16 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

Рис. 1.1. Сложный перекресток Для построения модели этой задачи можно применить математическую структуру, известную как граф. Граф состоит из множества точек, которые называются вершина- вершинами, и совокупности линий (ребер), соединяющих эти точки. Для решения задачи управления движением по перекрестку можно нарисовать граф, где вершины будут представлять повороты, а ребра соединят ту часть вершин-поворотов, которые нельзя выполнить одновременно. Для нашего перекрестка (рис. 1.1) соответствующий граф показан на рис. 1.2, а в табл. 1.1 дано другое представление графа — в виде, таблицы, где на пересечении строки I и столбца у стоит 1 тогда и только тогда, когда существует ребро между вершинами i и у. Рис. 1.2. Граф, показывающий несо- несовместимые повороты Модель в виде графа поможет в решении исходной задачи управления светофора- светофорами. В рамках этой модели можно использовать решение, которое дает математиче- математическая задача раскраски графа: каждой вершине графа надо так задать цвет, чтобы никакие две соединенные ребром вершины не имели одинаковый цвет, и при этом по возможности использовать минимальное количество цветов. Нетрудно видеть, что при такой раскраске графа несовместимым поворотам будут соответствовать верши- вершины, окрашенные в разные цвета. Проблема раскраски графа изучается математиками уже несколько десятиле- десятилетий, но теория алгоритмов мало что может сказать о решении этой проблемы. К сожалению, задача раскраски произвольного графа минимальным количеством 1.1. ОТ ЗАДАЧИ К ПРОГРАММЕ 17

цветов принадлежит классу задач, которые называются NP-полными задачами и для которых все известные решения относятся к типу "проверь все возможности" или "перебери все варианты". Для раскраски графа это означает, что сначала для закраски вершин используется один цвет, затем — два цвета, потом — три и т.д., пока не будет получена подходящая раскраска вершин. В некоторых частных слу- случаях можно предложить более быстрое решение, но в общем случае не существует более эффективного (в значительной степени) алгоритма решения задачи раскрас- раскраски, чем алгоритм полного перебора возможных вариантов. Таблица 1.1. Таблица несовместимых поворотов АВ АС AD ВА ВС BD DA DB DC ЕА ЕВ ЕС ED Таким образом, поиск оптимального решения задачи раскраски графа требует больших вычислительных затрат. В этой ситуации можно воспользоваться одним из следующих трех подходов. Если граф небольшой, можно попытаться найти оптимальное решение, перебрав все возможные варианты раскраски. Однако этот подход не приемлем для больших графов», так как программно трудно организо- организовать эффективный перебор всех вариантов. Второй подход предполагает исполь- использование дополнительной информации об исходной задаче. Желательно найти ка- какие-то особые свойства графа, которые исключали бы необходимость полного пе- перебора всех вариантов раскраски для нахождения оптимального решения. В третьем подходе мы немного изменяем постановку задачи и ищем не оптималь- оптимальное решение, а близкое к оптимальному. Если мы откажемся от требования ми- минимального количества цветов раскраски графа, то можно построить алгоритмы раскраски, которые работают значительно быстрее, чем алгоритмы полного пере- перебора. Алгоритмы, которые быстро находят "подходящее", но не оптимальное ре- решение, называются эвристическими. Примером рационального эвристического алгоритма может служить следующий "жадный" алгоритм раскраски графа. В этом алгоритме сначала мы пытаемся рас- раскрасить как можно больше вершин в один цвет, затем закрашиваем во второй цвет также по возможности максимальное число оставшихся вершин, и т.д. При закраске вершин в новый цвет мы выполняем следующие действия. 1. Выбираем произвольную незакрашенную вершину и назначаем ей новый цвет. 2. Просматриваем список незакрашенных вершин и для каждой из них определя- определяем, соединена ли она ребром с вершиной, уже закрашенной в новый цвет. Если не соединена, то к этой вершине также применяется новый цвет. АВ 1 1 1 1 АС 1 1 1 1 1 AD 1 1 1 ВА ВС 1 1 1 BD 1 1 1 1 1 DA 1 1 1 1 1 DB 1 1 1 DC ЕА 1 1 1 ЕВ 1 1 1 1 1 ЕС 1 1 1 1 ED 18 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

Этот алгоритм назван "жадным" из-за того, что каждый цвет применяется к максимально большому числу вершин, без возможности пропуска некоторых из них или перекраски ранее закрашенных. Возможны ситуации, когда, будь алго- алгоритм Менее "жадным" и пропустил бы некоторые вершины при закраске новым цветом, мы получили бы раскраску графа меньшим количеством цветов. Напри- Например, для раскраски графа на рис. 1.3 можно было бы применить два цвета, за- закрасив вершину 1 в красный цвет, а затем, пропустив вершину 2, закрасить в красный цвет вершины 3 и 4. Но "жадный" алгоритм, основываясь на порядко- порядковой очередности вершин, закрасит -в красный цвет вершины 1 и 2, для закраски остальных вершин потребуются еще два цвета. Рис. 1.3. Граф Применим описанный алгоритм для закраски вершин графа нашей задачи (рис.1.2), при этом первой закрасим вершину АВ в синий цвет. Также можно закра- закрасить в синий цвет вершины AC, AD и ВА, поскольку никакие из этих четырех вер- вершин не имеют общих ребер. Вершину ВС нельзя закрасить в этот цвет, так как су- существует ребро между вершинами АВ и ВС. По этой же причине мы не можем за- закрасить в синий цвет вершины BD, DA и DB — все они имеют хотя бы по одному ребру, связывающему их с уже закрашенными в синий цвет вершинами. Продолжая перебор вершин, закрашиваем вершины DC и ED в синий цвет, а вершины ЕА, ЕВ и ЕС оставляем незакрашенными. Теперь применим второй цвет, например красный. Закраску этим цветом начнем с вершины ВС. Вершину BD можно закрасить красным цветом, вершину DA — нель- нельзя, так как есть ребро между вершинами BD и DA. Продолжаем перебор вершин: вершину DB нельзя закрасить красным цветом, вершина DC уже закрашена синим цветом, а вершину ЕА можно закрасить красным. Остальные незакрашенные верши- вершины имеют общие ребра с вершинами, окрашенными в красный цвет, поэтому к ним нельзя применить этот цвет. Рассмотрим незакрашенные вершины DA, DB, ЕВ и ЕС. Если вершину DA мы закрасим в зеленый цвет, то в этот цвет также можно закрасить и вершину DB, но вершины ЕВ и ЕС в зеленый цвет закрасить нельзя. К последним двум вер- вершинам применим четвертый цвет, скажем, желтый. Назначенные вершинам цве- цвета приведены в табл. 1.2. В этой таблице "дополнительные" повороты совмести- совместимы с соответствующими поворотами из столбца "Повороты", хотя алгоритмом они окрашены в разные цвета. При задании режимов работы светофоров, осно- основанных на одном из цветов раскраски, вполне безопасно включить в эти режимы и дополнительные повороты. Данный алгоритм не всегда использует минимально возможное число цветов. Можно использовать результаты из общей теории графов для оценки качества полу- полученного решения. В теории графов k-кликой называется множество из k вершин, в котором каждая пара вершин соединена ребром. Очевидно, что для закраски fe-клики необходимо k цветов, поскольку в клике никакие две вершины не могут иметь оди- одинаковый цвет. 1.1..ОТ ЗАДАЧИ К ПРОГРАММЕ 19

Таблица 1.2. Раскраска графа, представленного на рис. 1.2 Цвет Повороты Дополнительные повороты Синий Красный Зеленый Желтый АВ, AC, AD, BA, DC, ED ВС, BD, EA DA,DB ЕВ, ЕС — BA, DC, ED AD, BA, DC, ED BA, DC, EA, ED В графе рис. 1.2 множество из четырех вершин AC, DA, BD и ЕВ является 4- кликой. Поэтому не существует раскраски этого графа тремя и менее цветами, и, следовательно, решение, представленное в табл. 1.2, является оптимальным в том смысле, что использует минимально возможное количество цветов для раскраски графа. В терминах исходной задачи это означает, что для управления перекрестком, показанным на рис. 1.1, необходимо не менее четырех режимов работы светофоров. Итак, для управления перекрестком построены четыре режима работы светофо- светофорами, которые соответствуют четырем цветам раскраски графа (табл. 1.2). П Псевдоязык и пошаговая „кристаллизация" алгоритмов Поскольку для решения исходной задачи мы применяем некую математическую модель, то тем самым можно формализовать алгоритм решения в терминах этой мо- модели. В i-ачальных версиях алгоритма часто применяются обобщенные операторы, которые гатем переопределяются в виде более мелких, четко определенных инструк- инструкций. Например, при описании рассмотренного выше алгоритма раскраски графа мы использовали такие выражения, как "выбрать произвольную незакрашенную верши- вершину". Мы надеемся, что читателю совершенно ясно, как надо понимать такие инст- инструкции. Но для преобразования таких неформальных алгоритмов в компьютерные программы необходимо пройти через несколько этапов формализации (этот процесс можно назвать пошаговой кристаллизацией), пока мы не получим программу, пол- полностью состоящую из формальных операторов языка программирования. Пример 1.2. Рассмотрим процесс преобразования "жадного" алгоритма раскраски графа в программу на языке Pascal. Мы предполагаем, что есть граф G, вершины кото- которого необходимо раскрасить. Программа greedy (жадный) определяет множество вер- вершин, названное newclr (новый цвет), все вершины которого можно окрасить в новый цвет. Эта программа будет вызываться на повторное выполнение столько раз, сколько необходимо для закраски всех вершин исходного графа. В самом первом грубом при- приближении программа greedy на псевдоязыке показана в следующем листинге. Листинг 1.1. Первое приближение программы greedy procedure greedy ( var G: GRAPH; var newclr: SET ) ; P { greedy присваивает переменной newclr множество вершин графа G, которые можно окрасить в один цвет} begin A) леигс2г:= 01; B) for для каждой незакрашенной вершины v из G do C) if v не соединена с вершинами из newclr then begin D) пометить v цветом; E) добавить v в newclr end end; { greedy } 1 Символ 0 — стандартное обозначение пустого множества. 20 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

В листинге 1.1 вы легко выделите средства нашего псевдоязыка. Мы применяем полужирное начертание для зарезервированных ключевых слов языка Pascal, кото- которые имеют тот же смысл, что и в стандартном языке Pascal. Написание строчными буквами таких слов, как GRAPH (Граф) и SET1 (Множество), указывает на имена аб- абстрактных типов данных. Их можно определить с помощью объявления типов языка Pascal и операторов, соответствующих абстрактным типам данных, которые задаются посредством процедур языка Pascal (эти процедуры должны входить в окончательный вариант программы). Более детально абстрактные типы данных мы рассмотрим в следующих двух разделах этой главы. Управляющие конструкции языка Pascal, такие как if, for и while, могут приме- применяться в операторах псевдоязыка, но условные выражения в них (как в строке C)) могут быть неформальными, в отличие от строгих логических выражений Pascal. Также и в строке A) в правой части оператора присваивания применяется нефор- неформальный символ. Еще отметим, что оператор цикла for в строке B) проводит повтор- повторные вычисления по элементам множества. Чтобы стать исполняемой, программа на псевдоязыке должна быть преобразована в программу на языке Pascal. В данном случае мы не будем приводить все этапы такого преобразования, а покажем только пример преобразования оператора if (строка C)) в более традиционный код. Чтобы определить, имеет ли вершина v соединение с какой-либо вершиной из newclr, мы рассмотрим каждый элемент w из newclr и по графу G проверим, существу- существует ли ребро между вершинами v и w. Для этого используем новую булеву переменную found (поиск), которая будет принимать значение true (истина), если такое ребро суще- существует. Листинг 1.2 показывает частично преобразованную программу листинга 1.1. Листинг 1.2. Частично преобразованная программа greedy procedure greedy ( var G: GRAPH; var newclr: SET ) ; begin A) newclr:= 0; B) for для каждой незакрашенной вершины v из G do begin C.1) found:= false; C.2) for для каждой вершины w из newclr do C.3) if существует ребро между v и w then C.4) found:= true; C.5) if found = false then begin { v не соединена ни с одной вершиной из newclr } D) пометить v цветом; E) добавить v в newclr end end end; { greedy } Обратите внимание, что наш алгоритм работает с двумя множествами вершин. Внешний цикл (строки B) - E)) выполняется над множеством незакрашенных вер- вершин графа G. Внутренний цикл (строки C.2) - C.4)) работает с текущим множест- множеством вершин newclr. Оператор строки E) добавляет новые вершины в это множество. Существуют различные способы представления множеств в языках программирова- программирования. В главах 4 и 5 мы изучим несколько таких представлений. В этом примере мы можем представить каждое множество вершин посредством абстрактного типа LIST (Список), который можно выполнить в виде обычного списка целых чисел, ограничен- ограниченного специальным значением null (для обозначения которого мы будем использовать число 0). Эти целые числа могут храниться, например, в массиве, но есть и другие спо- способы представления данных типа LIST, которые мы рассмотрим в главе 2. 1 Мы отличаем абстрактный тип данных SET от встроенного типа данных set языка Pascal. 1.1. ОТ ЗАДАЧИ К ПРОГРАММЕ 21

Теперь можно записать оператор for в строке C.2) в виде стандартного цикла по условию, где переменная w инициализируется как первый элемент списка newclr и затем при каждом выполнении цикла принимает значение следующего элемента из newclr. Мы также преобразуем оператор for строки B) листинга 1.1. Измененная процедура greedy представлена в листинге 1.3. В этом листинге есть еще операторы, которые необходимо преобразовать в стандартный код языка Pascal, но мы пока ог- ограничимся сделанным. D Листинг 1.3. Измененная программа greedy procedure greedy ( var G: GRAPH; var newclr: LIST ) ; { greedy присваивает переменной newclr множество вершин графа G, которые можно окрасить в один цвет } var found: boolean; v, w: integer; begin newclr:= 0; v:= первая незакрашенная вершина из G; while v <> null do begin found:= false; w-.= первая вершина из newclr while w <> null do begin if существует ребро между v и w then found:= true; w:= следующая вершина из newclr; end; if found = false then begin пометить v цветом; добавить v в newclr end v:= следующая незакрашенная вершина из G; end; end; { greedy } Резюме На рис. 1.4 схематически представлен процесс программирования так, как он трактуется в этой книге. На первом этапе создается модель исходной задачи, для че- чего привлекаются соответствующие подходящие математические модели (такие как теория графов в предыдущем примере). На этом этапе для нахождения решения также строится неформальный алгоритм. На следующем этапе алгоритм записывается на псевдоязыке — композиции (смеси) конструкций языка Pascal и менее формальных и обобщенных операторов на простом "человеческом" языке. Продолжением этого этапа является замена нефор- неформальных операторов последовательностью более детальных и формальных операто- операторов. С этой точки зрения программа на псевдоязыке должна быть достаточно подроб- подробной, так как в ней фиксируются (определяются) различные типы данных, над кото- которыми выполняются операторы. Затем создаются абстрактные типы данных для каждого зафиксированного типа данных (за исключением элементарных типов дан- данных, таких как целые и действительные числа или символьные строки) путем зада- задания имен процедурам для каждого оператора, выполняемого над данными абстракт- абстрактного типа, и замены их (операторов) вызовом соответствующих процедур. Третий этап процесса программирования обеспечивает реализацию каждого абст- абстрактного типа данных и создание процедур для выполнения различных операторов над данными этих типов. На этом этапе также заменяются все неформальные операторы 22 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

псевдоязыка на код языка Pascal. Результатом этого этапа должна быть выполняемая программа. После ее отладки вы получите работающую программу, и мы надеемся, что, используя пошаговый подход при разработке программ, схема которого показана на рис. 1.4, процесс отладки конечной программы будет небольшим и безболезненным. Математическая модель Неформальный алгоритм Абстрактные типы данных Программа на псевдоязыке Структуры данных Программа на языке Pascal Рис. 1.4. Схема процесса создания программ для решения прикладных задач 1.2. Абстрактные типы данных Большинство понятий, введенных в предыдущем разделе, обычно излагаются в начальном курсе программирования и должны быть знакомы читателю. Новыми мо- могут быть только абстрактные типы данных, поэтому сначала обсудим их роль в про- процессе разработки программ. Прежде всего сравним абстрактный тип данных с таким знакомым понятием, как процедура. Процедуру, неотъемлемый инструмент программирования, можно рассматривать как обобщенное понятие оператора. В отличие от ограниченных по своим возможно- возможностям встроенных операторов языка программирования (сложения, умножения и т.п.), с помощью процедур программист может создавать собственные операторы и применять их к операндам различных типов, не только базовым. Примером такой процедуры- оператора может служить стандартная подпрограмма перемножения матриц. Другим преимуществом процедур (кроме способности создавать новые операторы) является возможность использования их для инкапсулирования частей алгоритма путем помещения в отдельный раздел программы всех операторов, отвечающих за определенный аспект функционирования программы. Пример инкапсуляции: ис- использование одной процедуры для чтения входных данных любого типа и проверки их корректности. Преимущество инкапсуляции заключается в том, что мы знаем, какие инкапсулированные операторы необходимо изменить в случае возникновения проблем в функционировании программы. Например, если необходимо организовать проверку входных данных на положительность значений, следует изменить только несколько строк кода, и мы точно знаем, где эти строки находятся. Определение абстрактного типа данных Мы определяем абстрактный тип данных (АТД) как математическую модель с совокупностью операторов, определенных в рамках этой модели. Простым примером АТД могут служить множества целых чисел с операторами объединения, пересече- пересечения и разности множеств. В модели АТД операторы могут иметь операндами не только данные, определенные АТД, но и данные других типов: стандартных типов языка программирования или определенных в других АТД. Результат действия опе- оператора также может иметь тип, отличный от определенных в данной модели АТД. Но мы предполагаем, что по крайней мене один операнд или результат любого опера- оператора имеет тип данных, определенный в рассматриваемой модели АТД. Две характерные особенности процедур — обобщение и инкапсуляция, — о кото- которых говорилось выше, отлично характеризуют абстрактные типы данных. АТД мож- можно рассматривать как обобщение простых типов данных (целых и действительных чисел и т.д.), точно так же, как процедура является обобщением простых операторов (+, - и т.д.). АТД инкапсулирует типы данных в том смысле, что определение типа и 1.2. АБСТРАКТНЫЕ ТИПЫ ДАННЫХ 23

все операторы, выполняемые над данными этого типа, помещаются в один раздел программы. Если необходимо изменить реализацию АТД, мы знаем, где найти и что изменить в одном небольшом разделе программы, и можем быть уверенными, что это не приведет к ошибкам где-либо в программе при работе с этим типом данных. Более того, вне раздела с определением операторов АТД мы можем рассматривать типы АТД как первичные типы, так как объявление типов формально не связано с их реа- реализацией. Но в этом случае могут возникнуть сложности, так как некоторые опера- операторы могут инициироваться для более одного АТД и ссылки на эти операторы долж- должны быть в разделах нескольких АТД. Для иллюстрации основных идей, приводящих к созданию АТД, рассмотрим про- процедуру greedy из предыдущего раздела (листинг 1.3), которая использует простые операторы над данными абстрактного типа LIST (список целых чисел). Эти операто- операторы должны выполнить над переменной newclr типа LIST следующие действия. 1. Сделать список пустым. 2. Выбрать первый элемент списка и, если список пустой, возвратить значение null. 3. Выбрать следующий элемент списка и возвратить значение null, если следующе- следующего элемента нет. 4. Вставить целое число в список. Возможно применение различных структур данных, с помощью которых можно эффективно выполнить описанные действия. (Подробно структуры данных будут рас- рассмотрены в главе 2.) Если в листинге 1.3 заменить соответствующие операторы вы- выражениями MAKENULL(newdr); w := FlRST(newclr); w := NEXT(newclr); INSERTS, newclr); то будет понятен один из основных аспектов (и преимуществ) абстрактных типов данных. Можно реализовать тип данных любым способом, а программы, использую- использующие объекты этого типа, не зависят от способа реализации типа — за это отвечают процедуры, реализующие операторы для этого типа данных. Вернемся к абстрактному типу данных GRAPH (Граф). Для объектов этого типа необходимы операторы, которые выполняют следующие действия. 1. Выбирают первую незакрашенную вершину. 2. Проверяют, существует ли ребро между двумя вершинами. 3. Помечают вершину цветом. 4. Выбирают следующую незакрашенную вершину. Очевидно, что вне поля зрения процедуры greedy остаются и другие операторы, такие как вставка вершин и ребер в граф или помечающие все вершины графа как незакрашенные. Различные структуры данных, поддерживающие этот тип данных, будут рассмотрены в главах 6 и 7. Необходимо особо подчеркнуть, что количество операторов, применяемых к объ- объектам данной математической модели, не ограничено. Каждый набор операторов оп- определяет отдельный АТД. Вот примеры операторов, которые можно определить для абстрактного типа данных SET (Множество). 1. MAKENULL(A). Эта процедура делает множество Л пустым множеством. 2. UNION(A, В, С). Эта процедура имеет два "входных" аргумента, множества А и В, и присваивает объединение этих множеств "выходному" аргументу — множеству С. 3. SIZE(A). Эта функция имеет аргумент-множество А и возвращает объект целого типа, равный количеству элементов множества Л. 24 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

Термин реализация АТД подразумевает следующее: перевод в операторы языка программирования объявлений, определяющие переменные этого абстрактного типа данных, плюс процедуры для каждого оператора, выполняемого над объектами АТД. Реализация зависит от структуры данных, представляющих АТД. Каждая структу- структура данных строится на основе базовых типов данных применяемого языка програм- программирования, используя доступные в этом языке средства структурирования данных. Структуры массивов и записей — два важных средства структурирования данных, возможных в языке Pascal. Например, одной из возможных реализаций переменной ¦S типа SET может служить массив, -содержащий элементы множества S. Одной из основных причин определения двух различных АТД в рамках одной мо- модели является то, что над объектами этих АТД необходимо выполнять различные действия, т.е. определять операторы разных типов. В этой книге рассматривается только несколько основных математических моделей, таких как теория множеств и теория графов, но при различных реализациях на основе этих моделей определенных АТД будут строиться различные наборы операторов. В идеале желательно писать программы на языке, базовых типов данных и опера- операторов которого достаточно для реализации АТД. С этой точки зрения язык Pascal не очень подходящий язык для реализации различных АТД, но, с другой стороны, трудно найти иной язык программирования, в котором можно было бы так непосред- непосредственно декларировать АТД. Дополнительную информацию о таких языках про- программирования см. в библиографических примечаниях в конце главы. 1.3. Типы данных, структуры данных и абстрактные типы данных Хотя термины тип данных (или просто тип), структура данных и абстракт- абстрактный тип данных звучат похоже, но имеют они различный смысл. В языках про- программирования тип данных переменной обозначает множество значений, которые может принимать эта переменная. Например, переменная булевого (логического) ти- типа может принимать только два значения: значение true (истина) и значение false (ложь) и никакие другие. Набор базовых типов данных отличается в различных язы- языках: в языке Pascal это типы целых (integer) и действительных (real) чисел, булев (boolean) тип и символьный (char) тип. Правила конструирования составных типов данных (на основе базовых типов) также различаются в разных языках программи- программирования: как мы уже упоминали, Pascal легко и быстро строит такие типы. Абстрактный тип данных — это математическая модель плюс различные опера- операторы, определенные в рамках этой модели. Как уже указывалось, мы можем раз- разрабатывать алгоритм в терминах АТД, но для реализации алгоритма в конкретном языке программирования необходимо найти способ представления АТД в терминах типов данных и операторов, поддерживаемых данным языком программирования. Для представления АТД используются структуры данных, которые представляют собой набор переменных, возможно, различных типов данных, объединенных оп- определенным образом. Базовым строительным блоком структуры данных является ячейка, которая предназначена для хранения значения определенного базового или составного типа данных. Структуры данных создаются путем задания имен совокупностям (агрегатам) ячеек и (необязательно) интерпретации значения некоторых ячеек как представителей (т.е. указателей) других ячеек. В качестве простейшего механизма агрегирования ячеек в Pascal и большинстве других языков программирования можно применять (одномерный) массив, т.е. по- последовательность ячеек определенного типа. Массив также можно рассматривать как отображение множества индексов (таких как целые Числа 1, 2, ..., л) в множество ячеек. Ссылка на ячейку обычно состоит из имени массива и значения из множества индексов данного массива. В Pascal множество индексов может быть нечислового ти- 1.3. ТИПЫ ДАННЫХ, СТРУКТУРЫ ДАННЫХ И АБСТРАКТНЫЕ ТИПЫ ДАННЫХ 25

па, например (север, восток, юг, запад), или интервального типа (как 1..10). Значе- Значения всех ячеек массива должны иметь одинаковый тип данных. Объявление имя: array[ТипИндекса] of ТипЯчеек; задает имя для последовательности ячеек, тип для элементов множества индексов и тип содержимого ячеек. Кстати, Pascal необычайно богат на типы индексов. Многие языки программиро- программирования позволяют использовать в качестве индексов только множества последователь- последовательных целых чисел. Например, чтобы в языке Fortran в качестве индексов массива можно было использовать буквы, надо все равно использовать целые индексы, заме- заменяя "А" на 1, "В" на 2, и т.д. Другим общим механизмом агрегирования ячеек в языках программирования яв- является структура записи. Запись (record) можно рассматривать как ячейку, со- состоящую из нескольких других ячеек (называемых полями), значения в которых мо- могут быть разных типов. Записи часто группируются в массивы; тип данных опреде- определяется совокупностью типов полей записи. Например, в Pascal объявление var reclist: array[1..4] of record data: real; next: integer end задает имя reclist (список записей) 4-элементного массива, значениями которого яв- являются записи с двумя полями: data (данные) и next (следующий). Третий метод агрегирования ячеек, который можно найти в Pascal и некоторых других языках программирования, — это файл. Файл, как и одномерный массив, является последовательностью значений определенного типа. Однако файл не имеет индексов: его элементы доступны только в том порядке, в каком они были записаны в файл. В отличие от файла, массивы и записи являются структурами с "произвольным доступом", подразумевая под этим, что время доступа к компонентам массива или записи не зависит от значения индекса массива или указателя поля за- записи. Достоинство агрегирования с помощью файла (частично компенсирующее опи- описанный недостаток) заключается в том, что файл не имеет ограничения на количест- количество составляющих его элементов и это количество может изменяться во время выпол- выполнения программы. Указатели и курсоры В дополнение к средствам агрегирования ячеек в языках программирования можно использовать указатели и курсоры. Указатель (pointer) — это ячейка, чье значение указывает на другую ячейку. При графическом представлении структуры данных в виде схемы тот факт, что ячейка А является указателем на ячейку В, по- показывается с помощью стрелки от ячейки А к ячейке В. В языке Pascal с помощью следующего объявления можно создать переменную- указатель prt, указывающую на ячейку определенного типа, например ТипЯчейки: var prt: t ТипЯчейки Постфикс в виде стрелки, направленной вверх, в Pascal используется как оператор разыменования, т.е. выражение prtT обозначает значение (типа ТипЯчейки) в ячей- ячейке, указанной prt. Курсор (cursor) — это ячейка с целочисленным значением, используемая для ука- указания на массив. В качестве способа указания курсор работает так же, как и указа- указатель, но курсор можно использовать и в языках (подобных Fortran), которые не имеют явного типа указателя. Интерпретировав целочисленную ячейку как индекс- 26 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

ное значение для массива, можно эффективно реализовать указания на ячейки мас- массива. К сожалению, этот прием подходит только для ячеек массива и не позволяет организовать указание на ячейки, не являющиеся частью массива. В схемах структур данных мы будем рисовать стрелку из ячейки курсора к ячей- ячейке, на которую указывает курсор. Иногда мы также будем показывать целое число в ячейке курсора, напоминая тем самым, что это не настоящий указатель. Читатель может заметить, что механизм указателя Pascal разрешает ячейкам массива только "быть указанными" с помощью курсора, но не быть истинным указателем. Другие языки программирования, подобные PL/1 или С, позволяют компонентам массивов быть истинными указателями и, конечно, "быть указанным" с помощью курсора. В отличие от этих языков, в языках Fortran и Algol, где нет типа указателя, можно использовать только курсоры. Пример 1.3. На рис. 1.5 показана структура данных, состоящая из двух частей. Она имеет цепочку ячеек, содержащих курсоры для массива reclist (список записей), определенного выше.. Назначение поля next (следующий) заключается в указании на следующую запись в массиве reclist. Например, reclist[4].next равно 1, поэтому за- запись 4 предшествует записи 1. Полагая первой запись 4, в соответствии со значения- значениями поля next получим следующий порядок записей: 4, 1, 3, 2. Отметим, что значе- значение поля next в записи 2, равное 0, указывает на то, что нет следующей записи. Це- Целесообразно принять соглашение, что число 0 будет обозначать нуль-указатель при использовании курсоров и указателей. Но, чтобы не возникали проблемы при реали- реализации этого соглашения, необходимо также условиться, что массивы, на которые указывают курсоры, индексируются начиная с 1, а не с 0. header 2 т 1.2 3.4 5.6 7.8 з ч 0 2 - 1 " data next reclist Рис. 1.5. Пример структуры данных Ячейки в цепочке на рис. 1.5 имеют тип type recordtype = record cursor: integer; prt: t recordtype end На цепочку можно ссылаться с помощью переменной header (заголовок), имею- имеющей тип Т recordtype, header указывает на анонимную запись типа recordtype1. 1 Запись анонимна (не имеет имени), так как создается с помощью вызова new(header), где header указывает на вновь создаваемую запись. В памяти компьютера, конечно, есть адрес, по которому можно локализовать ячейку с записью. 1.3. ТИПЫ ДАННЫХ, СТРУКТУРЫ ДАННЫХ И АБСТРАКТНЫЕ ТИПЫ ДАННЫХ 27

Эта запись имеет значение 4 в поле cursor. Мы рассматриваем 4 как индекс мас- массива reclist. Эта запись имеет истинный указатель в поле ptr на другую аноним- анонимную запись, которая, в свою очередь, указывает на индекс 4 массива reclist и имеет нуль-указатель в поле prt. П 1.4. Время выполнения программ В процессе решения прикладных задач выбор подходящего алгоритма вызывает определенные трудности. В самом деле, на чем основывать свой выбор, если алго- алгоритм должен удовлетворять следующим противоречащим друг другу требованиям. 1. Быть простым для понимания, перевода в программный код и отладки. 2. Эффективно использовать компьютерные ресурсы и выполняться по возможно- возможности быстро. Если написанная программа должна выполняться только несколько раз, то первое требование наиболее важно. Стоимость рабочего времени программиста обычно значи- значительно превышает стоимость машинного времени выполнения программы, поэтому стоимость программы оптимизируется по стоимости написания (а не выполнения) про- программы. Если мы имеем дело с задачей, решение которой требует значительных вы- вычислительных затрат, то стоимость выполнения программы может превысить стои- стоимость написания программы, особенно если программа должна выполняться много- многократно. Поэтому, с финансовой точки зрения, более предпочтительным может стать сложный комплексный алгоритм (в надежде, что результирующая программа будет выполняться существенно быстрее, чем более простая программа). Но и в этой ситуа- ситуации разумнее сначала реализовать простой алгоритм, чтобы определить, как должна себя вести более сложная программа. При построении сложной программной системы желательно реализовать ее простой прототип, на котором можно провести необходимые измерения и смоделировать ее поведение в целом, прежде чем приступать к разработке окончательного варианта. Таким образом, программисты должны быть осведомлены не только о методах построения быстрых программ, но и знать, когда их следует приме- применить (желательно с минимальными программистскими усилиями). Измерение времени выполнения программ На время выполнения программы влияют следующие факторы. 1. Ввод исходной информации в программу. 2. Качество скомпилированного кода исполняемой программы. 3. Машинные инструкции (естественные и ускоряющие), используемые для выпол- выполнения программы. 4. Временная сложность алгоритма соответствующей программы.1 Поскольку время выполнения программы зависит от ввода исходных данных, его можно определить как функцию от исходных данных. Но зачастую время выполне- выполнения программы зависит не от самих исходных данных, а от их "размера". В этом от- отношении хорошим примером являются задачи сортировки, которые мы подробно рассмотрим в главе 8. В задачах сортировки в качестве входных данных выступает 1 Здесь авторы, не акцентируя на этом внимания и не определяя его особо, вводят термин "временная сложность алгоритма". Под временной сложностью алгоритма понимается "время" выполнения алгоритма, измеряемое в "шагах" (инструкциях алгоритма), которые необходимо вы- выполнить алгоритму для достижения запланированного результата. В качестве синонима для этого термина авторы часто используют выражение "время выполнения алгоритма". Отметим, что в первой части книги (до главы 6) авторами чаще используется последнее выражение, а во второй — чаще термин "временная сложность". В этой связи заметим, что необходимо разли- различать "время выполнения алгоритма" и "время выполнения программы". — Прим. ред. 28 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

список элементов, подлежащих сортировке, а в качестве выходного результата — те же самые элементы, отсортированные в порядке возрастания или убывания. Напри- Например, входной список 2, 1, 3, 1, 5, 8 будет преобразован в выходной список 1, 1, 2, 3, 5, 8 (в данном случае список отсортирован в порядке возрастания). Естественной мерой объема входной информации для программы сортировки будет число элемен- элементов, подлежащих сортировке, или, другими словами, длина входного списка. В об- общем случае длина входных данных — подходящая мера объема входной информа- информации, и если не будет оговорено иное, то в качестве меры объема входйой информации мы далее будем понимать именно длину входных данных. Обычно говорят, что время выполнения программы имеет порядок Т(п) от входных данных размера л. Например, некая программа имеет время выполнения Т(п) = ел2, где с — константа. Единица измерения Т(п) точно не определена, но мы будем понимать Г(л) как количество инструкций, выполняемых на идеализированном компьютере. Для многих программ время выполнения действительно является функцией вход- входных данных, а не их размера. В этой ситуации мы определяем Т(п) как время выпол- выполнения в наихудшем случае, т.е. как максимум времени выполнения по всем входным данным размера л. Мы также будем рассматривать Тср(п) как среднее (в статистиче- статистическом смысле) время выполнения по всем входным данным размера л. Хотя Тср(п) явля- является достаточно объективной мерой времени выполнения, но часто нельзя предполагать (или обосновать) равнозначность всех входных данных. На практике среднее время вы- выполнения найти сложнее, чем наихудшее время выполнения, так как математически это трудноразрешимая задача и, кроме того, зачастую не имеет простого определения понятие "средних" входных данных. Поэтому в основном мы будем использовать наи- наихудшее время выполнения как меру временной сложности алгоритмов, но не будем за- забывать и о среднем времени выполнения там, где это возможно. Теперь сделаем замечание о втором и третьем факторах, влияющих на время вы- выполнения программ: о компиляторе, используемом для компиляции программы, и машине, на которой выполняется программа. Эти факторы влияют на то, что для измерения времени выполнения Т(п) мы не можем применить стандартные единицы измерения, такие как секунды или миллисекунды. Поэтому мы можем только делать заключения, подобные "время выполнения такого-то алгоритма пропорционально л2". Константы пропорциональности также нельзя точно определить, поскольку они зависят от компилятора, компьютера и других факторов. Асимптотические соотношения Для описания скорости роста функций используется О-символика. Например, ко- когда мы говорим, что время выполнения Т(п) некоторой программы имеет порядок О(л2) (читается "о-большое от л в квадрате" или просто "о от л в квадрате"), то под- подразумевается, что существуют положительные константы с и л0 такие, что для всех л, больших или равных л0, выполняется неравенство Т(п) < сп2. Пример 1.4. Предположим, что Т@) = 1, ТA) = 4 и в общем случае Т(п) = (л + IJ. Тогда Г(л) имеет порядок О(л2): если положить л0 = 1 и с = 4, то легко по- показать, что для л > 1 будет выполняться неравенство (л + IJ < 4л2. Отметим, что нельзя положить л0 = 0, так как Т@) = 1 и, следовательно, это значение при любой константе с больше еО2 = 0. ? Подчеркнем: мы предполагаем, что все функции времени выполнения определены на множестве неотрицательных целых чисел и их значения также неотрицательны, но необязательно целые. Будем говорить, что Т(п) имеет порядок О(/(л)), если суще- существуют константы с и л0 такие, что для всех л > л0 выполняется неравенство Т(п) < cf(n). Для программ, у которых время выполнения имеет порядок О(/(л)), го- говорят, что они имеют порядок (или степень) роста /(л). Пример 1.5. Функция Т(п) = Зл3 + 2л2 имеет степень роста О(л3). Чтобы это пока- показать, надо положить л0 = 0 и с = 5, так как легко видеть, что для всех целых л > 0 вы- выполняется неравенство Зл3 + 2л2 < 5л3. Можно, конечно, сказать, что Т(п) имеет поря- порядок О(л4), но это более слабое утверждение, чем то, что Г(л) имеет порядок роста О(л ). 1.4. ВРЕМЯ ВЫПОЛНЕНИЯ ПРОГРАММ 29

В качестве следующего примера докажем, что функция 3" не может иметь поря- порядок 0B"). Предположим, что существуют константы с и л0 такие, что для всех л > л0 выполняется неравенство 3" < е2". Тогда с > C/2)" для всех л > л0. Но C/2)" прини- принимает любое, как угодно большое, значение при достаточно большом л, поэтому не существует такой константы с, которая могла бы мажорировать C/2)" для всех л. ? Когда мы говорим, что Г(л) имеет степень роста O(f(n)), то подразумевается, что Дл) является верхней границей скорости роста Г(л). Чтобы указать нижнюю границу скоро- скорости роста Т(п), используется обозначение: Т(п) есть Cl(g(n)) (читается "омега-большое от gin)" или просто "омега от g(n)"), это подразумевает существование такой константы с, что бесконечно часто (для бесконечного числа значений л) выполняется неравенство Г(л) > cg(n)} Пример 1.6. Для проверки того, что Т(п) = л3 + 2л2 есть Q(n3), достаточно поло- положить с = 1. Тогда Г(л) > ел3 для л = О, 1,... . Для другого примера положим, что Г(л) = л для нечетных л > 1 и Т(п) = л2/Ю0 — для четных л > 0. Для доказательства того, что Т(п) есть ?2(л2), достаточно положить с = 1/100 и рассмотреть множество четных чисел л = 0,2,4,6,... .П Ограниченность показателя степени роста Итак, мы предполагаем, что программы можно оценить с помощью функций вре- времени выполнения, пренебрегая при этом константами пропорциональности. С этой точки зрения программа с временем выполнения О(л2), например, лучше программы с временем выполнения О(л ). Константы пропорциональности зависят не только от используемых компилятора и компьютера, но и от свойств самой программы. Пусть при определенной комбинации компилятор-компьютер одна программа выполняется за 100л2 миллисекунд, а вторая — за 5л3 миллисекунд. Может ли вторая программа быть предпочтительнее, чем первая? Ответ на этот вопрос зависит от размера входных данных программ. При размере входных данных л < 20 программа с временем выполнения 5л завершится быстрее, чем программа с временем выполнения ЮОга2. Поэтому, если программы в основном выполняются с входными данными небольшого размера, предпочтение необходимо отдать программе с временем выполнения О(п3). Однако при возрастании л отноше- отношение времени выполнения 5п3/100п2 = л/20 также растет. Поэтому при больших п программа с временем выполнения О(п2) становится предпочтительнее программы с временем выполнения О(п3). Если даже при сравнительно небольших п, когда время выполнения обеих программ примерно одинаково, выбор лучшей программы пред- представляет определенные затруднения, то естественно для большей надежности сделать выбор в пользу программы с меньшей степенью роста. Другая причина, заставляющая отдавать предпочтение программам с наименьшей степенью роста времени выполнения, заключается в том, что чем меньше степень роста, тем больше размер задачи, которую можно решить на компьютере. Другими словами, если увеличивается скорость вычислений компьютера, то растет также и размер задач, решаемых на компьютере. Однако незначительное увеличение скорости вычислений компьютера приводит только к небольшому увеличению размера задач, решаемых в течение фиксированного промежутка времени, исключением из этого правила являются программы с низкой степенью роста, как О(п) и О(п logn). Пример 1.7. На рис. 1.6 показаны функции времени выполнения (измеренные в секундах) для четырех программ с различной временной сложностью для одного и 1 Отметим асимметрию в определениях О- и ii-символики. Такая асимметрия бывает по- полезной, когда алгоритм работает быстро на достаточно большом подмножестве, Но не на всем множестве входных данных. Например, есть алгоритмы, которые работают значительно бы- быстрее, если длина входных данных является простым числом, а не (к примеру) четным чнс- м. В этом случае невозможно получить хорошую нижнюю границу времени выполнения, справедливую для всех п > по. 30 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

того же сочетания компилятор-компьютер. Предположим, что можно использовать 1 000 секунд (примерно 17 минут) машинного времени для решения задачи. Какой максимальный размер задачи, решаемой за это время? За 10 секунд каждый из че- четырех алгоритмов может решить задачи примерно одинакового размера, как показа- показано во втором столбце табл. 1.3. Предположим, что получен новый компьютер (без дополнительных финансовых затрат), работающий в десять раз быстрее. Теперь за ту же цену можно использо- использовать 104 секунд машинного времени — ранее 103 секунд. Максимальный размер задачи, которую может решить за это время каждая из четырех программ, показан в третьем столбце табл. 1.3. Отношения значений третьего и второго столбцов при- приведены в четвертом столбце этой таблицы. Здесь мы видим, что увеличение скоро- скорости компьютера на 1 000% приводит к увеличению только на 30% размера задачи, решаемой с помощью программы с временем выполнения ОB"). Таким образом, 10-кратное увеличение производительности компьютера дает в процентном отно- отношении значительно меньший эффект увеличения размера решаемой задачи. В дей- действительности, независимо от быстродействия компьютера, программа с временем выполнения ОB") может решать только очень небольшие задачи. Рис. 1.6. Функции.времени выполнения четырех программ Таблица 1.3. Эффект от 10-кратного увеличения быстродействия компьютера Время Максимальный размер Максимальный размер Увеличение выполнения Tfn) задачи для 103 секунд задачи для 104 секунд максимального размера задачи 100/1 5п2 па/2 2" 10 14 12 10 100 45 27 13 10.0 3.2 2.3 1.3 1.4. ВРЕМЯ ВЫПОЛНЕНИЯ ПРОГРАММ 31

Из третьего столбца табл. 1.3 ясно видно преимущество программ с временем вы- выполнения О(п): 10-кратное увеличение размера решаемой задачи при 10-кратном увеличении производительности компьютера. Программы с временем выполнения О(п3) и О(п2) при увеличении быстродействия компьютера на 1 000% дают увеличе- увеличение размера задачи соответственно на 230% и 320%. Эти соотношения сохранятся и при дальнейшем увеличении производительности компьютера. ? Поскольку существует необходимость решения задач все более увеличивающегося размера, мы приходим к почти парадоксальному выводу. Так как машинное время все время дешевеет, а компьютеры становятся более быстродействующими, мы наде- надеемся, что сможем решать все большие по размеру и более сложные задачи. Но вместе с тем возрастает значимость разработки и использования эффективных алгоритмов именно с низкой степенью роста функции времени выполнения. Немного соли Мы хотим еще раз подчеркнуть, что степень роста наихудшего времени выполне- выполнения — не единственный или самый важный критерий оценки алгоритмов и про- программ. Приведем несколько соображений, позволяющих посмотреть на критерий времени выполнения с других точек зрения. 1. Если создаваемая программа будет использована только несколько раз, тогда стоимость написания и отладки программы будет доминировать в общей стоимо- стоимости программы, т.е. фактическое время выполнения не окажет существенного влияния на общую стоимость. В этом случае следует предпочесть алгоритм, наи- наиболее простой для реализации. 2. Если программа будет работать только с "малыми" входными данными, то сте- степень роста времени выполнения будет иметь меньшее значение, чем константа, присутствующая в формуле времени выполнения. Вместе с тем и понятие "малости" входных данных зависит от точного времени выполнения конкури- конкурирующих алгоритмов. Существуют алгоритмы, такие как алгоритм целочисленно- целочисленного умножения (см. [96]), асимптотически самые эффективные, но которые нико- никогда не используют на практике даже для больших задач, так как их константы пропорциональности значительно превосходят подобные константы других, более простых и менее "эффективных" алгоритмов. 3. Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих про- программ. Будем надеяться, что принципиальные моменты технологии создания эффективных алгоритмов широко известны, и достаточно сложные алгоритмы свободно применяются на практике. Однако необходимо предусмотреть возмож- возможность того, что эффективные, но "хитрые" алгоритмы не будут востребованы из- за их сложности и трудностей, возникающих при попытке в них разобраться. 4. Известно несколько примеров, когда эффективные алгоритмы требуют таких больших объемов машинной памяти (без возможности использования более мед- медленных внешних средств хранения), что этот фактор сводит на нет преимущество "эффективности" алгоритма. 5. В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность. 1.5. Вычисление времени выполнения программ Теоретическое нахождение времени выполнения программ (даже без определения констант пропорциональности) — сложная математическая задача. Однако на прак- практике определение времени выполнения (также без нахождения значения констант) является вполне разрешимой задачей — для этого нужно знать только несколько ба- базовых принципов. Но прежде чем представить эти принципы, рассмотрим, как вы- выполняются операции сложения и умножения с использованием О-символики. 32 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

Пусть Ti(n) и Т2(п) — время выполнения двух программных фрагментов Рх и Р2, Ti(n) имеет степень роста O(f(n)), а Т2(п) — O(g(n)). Тогда Ti(n) + Т2(п), т.е. время последовательного выполнения фрагментов Рг и Р2, имеет степень роста O(max(/(n), g(n))). Для доказательства этого вспомним, что существуют константы съ с2, пх и п2 такие, что при п> пх выполняется неравенство Тг(п) < Cif(n), и, ана- аналогично, Т2(п) < c2g(n), если п > п2. Пусть по = тах(п!, п2). Если п > п0, то, оче- очевидно, что Тг(п) + Т2(п) < Cif(n) + c2g(n). Отсюда вытекает, что при п > п0 справедли- справедливо неравенство Тг(п) + Т2(п) < (ci + c2)max(/(n), g(n)). Последнее неравенство и озна- означает, что Тг(п) + Т2(п) имеет порядок роста O(max(/(n), g(n))). Пример 1.8. Правило сумм, данное выше, используется для вычисления времени последовательного выполнения программных фрагментов с циклами и ветвлениями. Пусть есть три фрагмента с временами выполнения соответственно О(п2), О(п3) и О(п logn). Тогда время последовательного выполнения первых двух фрагментов име- имеет порядок O(max(n2, n3)), т.е. О(п3). Время выполнения всех трех фрагментов имеет порядок O(max(n3, n logn)), это то же самое, что О(п3). ? В общем случае время выполнения конечной последовательности программных фрагментов, без учета констант, имеет порядок фрагмента с наибольшим временем вы- выполнения. Иногда возможна ситуация, когда порядки роста времен нескольких фраг- фрагментов несоизмеримы (ни один из них не больше, чем другой, но они и не равны). Для примера рассмотрим два фрагмента с временем выполнения O(f(n)) и O(g(n)), где п4,еслипчетное; , ч Гп2,еслипчетное; S(n) = < 2 S(n) 3 п ,еслипнечетное, \п ,еслип нечетное. В данном случае правило сумм можно применить непосредственно и получить время выполнения O(max(/(n), g(n)), т.е. п4 при п четном и п3, если п нечетно. Из правила сумм также следует, что если g(n) < f(n) для всех п, превышающих п0, то выражение O(f(h) + g(n)) эквивалентно O(f(n)). Например, О(п2 + п) то же са- самое, что О(п2). Правило произведений заключается в следующем. Если Тг(п) и Т2(п) имеют сте- степени роста O(f(n)) и O(g(n)) соответственно, то произведение Ту(п)Т2(п) имеет степень роста O{f(n)g(n)). Читатель может самостоятельно доказать это утверждение, исполь- используя тот же подход, который применялся при доказательстве правила сумм. Из пра- правила произведений следует, что O(cf(n)) эквивалентно O(f(n)), если с — положитель- положительная константа. Например, О(п2/2) эквивалентно О(п2). Прежде чем переходить к общим правилам анализа времени выполнения про- программ, рассмотрим простой пример, иллюстрирующий процесс определения времени выполнения. Пример 1.9. Рассмотрим программу сортировки bubble (пузырек), которая упоря- упорядочивает массив целых чисел в возрастающем порядке методом "пузырька" (листинг 1.4). За каждый проход внутреннего цикла (операторы C)-F)) "пузырек" с наи- наименьшим элементом "всплывает" в начало массива. Листинг 1.4. Сортировка методом „пузырька" procedure bubble ( var A: array [1..л] of integer ); { Процедура упорядочивает массив А в возрастающем порядке } var i, j, temp: integer; begin A) for i:= 1 ton- ldo B) for j:= n downto i + 1 do C) if A[j - 1] > A[j] then begin { перестановка местами A[j-1] и A[j] } D) temp:= A[j - 1] ,- 1.5. ВЫЧИСЛЕНИЕ ВРЕМЕНИ ВЫПОЛНЕНИЯ ПРОГРАММ 33

E) Alj - 1] : = F) A[j]:= temp; end end; { bubble } Число элементов п, подлежащих сортировке, может служить мерой объема вход- входных данных. Сначала отметим, что все операторы присваивания имеют некоторое постоянное время выполнения, независящее от размера входных данных. Таким об- образом, операторы D) - F) имеют время выполнения порядка ОA). Запись ОA) озна- означает "равнозначно некой константе". В соответствии с правилом сумм время выпол- выполнения этой группы операторов равно О(тахA, 1, 1)) = ОA). Теперь мы должны подсчитать время выполнения условных и циклических опе- операторов. Операторы if и for вложены друг в друга, поэтому мы пойдем от внутренних операторов к внешним, последовательно определяя время выполнения условного опе- оператора и каждой итерации цикла. Для оператора if проверка логического выражения занимает время порядка ОA). Мы не знаем, будут ли выполняться операторы в теле условного оператора (строки D) - F)), но поскольку мы ищем наихудшее время вы- выполнения, то, естественно, предполагаем, что они выполняются. Таким образом, по- получаем, что время выполнения группы операторов C) - F) имеет порядок ОA). Далее рассмотрим группу B) - F) операторов внутреннего цикла. Общее правило вычисления времени выполнения цикла заключается в суммировании времени вы- выполнения каждой итерации цикла. Для операторов B) - F) время выполнения на каждой итерации имеет порядок ОA). Цикл выполняется п — i раз, поэтому по пра- правилу произведений общее время выполнения цикла имеет порядок О((п - i) х 1), что равно О(п - О- Теперь перейдем к внешнему циклу, который содержит все исполняемые операто- операторы программы. Оператор A) выполняется п — 1 раз, поэтому суммарное время вы- выполнения программы ограничено сверху выражением которое имеет порядок О(п2). Таким образом, программа "пузырька" выполняется за время, пропорциональное квадрату числа элементов, подлежащих упорядочиванию. В главе 8 мы рассмотрим программы с временем выполнения порядка О(п logn), которое существенно меньше О(л2), поскольку при больших п logn1 значительно меньше п. ? Перед формулировкой общих правил анализа программ позвольте напомнить, что на- нахождение точной верхней границы времени выполнения программ только в редких слу- случаях так же просто, как в приведенном выше примере, в общем случае эта задача являет- является интеллектуальным вызовом исследователю. Поэтому не существует исчерпывающего множества правил анализа программ. Мы можем дать только некоторые советы и проил- проиллюстрировать их с разных точек зрения примерами, приведенными в этой книге. Теперь дадим несколько правил анализа программ. В общем случае время выпол- выполнения оператора или группы операторов можно параметризовать с помощью размера входных данных и/или одной или нескольких переменных. Но для времени выпол- выполнения программы в целом допустимым параметром может быть только п, размер входных данных. 1. Время выполнения операторов присваивания, чтения и записи обычно имеет по- порядок ОA). Есть несколько исключений из этого правила, например в языке PL/1, где можно присваивать большие массивы, или в любых других языках, допускающих вызовы функций в операторах присваивания. 2. Время выполнения последовательности операторов определяется с помощью пра- правила сумм. Поэтому степень роста времени выполнения последовательности опе- 1 Если не указано другое, то будем считать, что все логарифмы определены по основанию 2. Однако отметим, что выражение O(logn) не зависит от основания логарифма, поскольку logo" = clog(,n, где с = logab. 34 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

раторов без определения констант пропорциональности совпадает с наибольшим временем выполнения оператора в данной последовательности. 3. Время выполнения условных операторов состоит из времени выполнения условно исполняемых операторов и времени вычисления самого логического выражения. Время вычисления логического выражения обычно имеет порядок ОA). Время для всей конструкции if-then-else состоит из времени вычисления логического выражения и наибольшего из времени, необходимого для выполнения операто- операторов, исполняемых при значении логического выражения true (истина) и при значении false (ложь). 4. Время выполнения цикла является суммой времени всех исполняемых итераций цикла, в свою очередь состоящих из времени выполнения операторов тела цикла и времени вычисления условия прекращения цикла (обычно последнее имеет по- порядок ОA)). Часто время выполнения цикла вычисляется, пренебрегая определе- определением констант пропорциональности, как произведение количества выполненных итераций цикла на наибольшее возможное время выполнения операторов тела цикла. Время выполнения каждого цикла, если в программе их несколько, должно определяться отдельно. Вызовы процедур Для программ, содержащих несколько процедур (среди которых нет рекурсив- рекурсивных), можно подсчитать общее время выполнения программы путем последователь- последовательного нахождения времени выполнения процедур, начиная с той, которая не имеет вызовов других процедур. (Вызов процедур мы определяем по наличию оператора call.) Так как мы предположили, что все процедуры нерекурсивные, то должна су- существовать хотя бы одна процедура, не имеющая вызовов других процедур. Затем можно определить время выполнения процедур, вызывающих эту процедуру, исполь- используя уже вычисленное время выполнения вызываемой процедуры. Продолжая этот процесс, найдем время выполнения всех процедур и, наконец, время выполнения всей программы. Если есть рекурсивные процедуры, то нельзя упорядочить все процедуры таким образом, чтобы каждая процедура вызывала только процедуры, время выполнения которых подсчитано на предыдущем шаге. В этом случае мы должны с каждой ре- рекурсивной процедурой связать временную функцию Т(п), где п определяет объем ар- аргументов процедуры. Затем мы должны получить рекуррентное соотношение для Т(п), т.е. уравнение (или неравенство) для Т(п), где участвуют значения T(k) для различных значений k. Техника решения рекуррентных соотношений зависит от вида этих соотношений, некоторые приемы их решения будут показаны в главе 9. Сейчас же мы проанализи- проанализируем простую рекурсивную программу. Пример 1.10. В листинге 1.5 представлена программа вычисления факториала п\, т.е. вычисления произведения целых чисел от 1 до и включительно. Листинг 1.5. Рекурсивная программа вычисления факториала function fact ( n: integer ): integer; { fact{n) вычисляет nl } begin A) if л <= 1 then B) fact:- 1 else C) fact:- n * factin - 1) end; { fact } Естественной мерой объема входных данных для функции fact является значение п. Обозначим через Т(п) время выполнения программы. Время выполнения для строк 1.5. ВЫЧИСЛЕНИЕ ВРЕМЕНИ ВЫПОЛНЕНИЯ ПРОГРАММ 35

A) и B) имеет порядок ОA), а для строки C) — ОA) + Т(п - 1). Таким образом, для некоторых констант с и d имеем Г(и) =к + Г(»1). в«и*>1. [d, если п < 1. Полагая, что п > 2, и раскрывая в соответствии с соотношением A.1) выражение Т(п - 1) (т.е. подставляя в A.1) п-1 вместо п), получим Т"(п) = 2с + Т"(п - 2). Аналогично, если п > 3, раскрывая Г(л - 2), получим !Г(п) = Зс + !Г(л - 3). Продолжая этот процесс, в общем случае для некоторого i, n > i, имеем Т(п) = ic + Т(п - 0- Положив в последнем выражении i = п - 1, окончательно получаем Т(п) = с(п - 1) + 741) = с(п - 1) + d. A.2) Из A.2) следует, что Т(п) имеет порядок О(п). Отметим, что в этом примере анализа программы мы предполагали, что операция перемножения двух целых чисел имеет порядок ОA). На практике, однако, программу, представленную в листинге 1.5, нельзя использовать для вычисления факториала при больших значений п, так как размер получаемых в процессе вычисления целых чисел может превышать длину машинного слова. ? Общий метод решения рекуррентных соотношений, подобных соотношению из примера 1.10, состоит в последовательном раскрытии выражений T(k) в правой части уравнения (путем подстановки в исходное соотношение k вместо п) до тех пор, пока не получится формула, у которой в правой части отсутствует Т (как в формуле A.2)). При этом часто приходится находить суммы различных последовательностей; если значения таких сумм нельзя вычислить точно, то для сумм находятся верхние границы, что позволяет, в свою очередь, получить верхние границы для Т(п). Программы с операторами безусловного перехода При анализе времени выполнения программ мы неявно предполагали, что все ветвления в ходе выполнения процедур осуществлялись с помощью условных опера- операторов и операторов циклов. Мы останавливаемся на этом факте, так как определяли время выполнения больших групп операторов путем применения правила сумм к этом группам. Однако операторы безусловного перехода (такие как goto) могут поро- порождать более сложную логическую групповую структуру. В принципе, операторы без- безусловного перехода можно исключить из программы. Но, к сожалению, язык Pascal не имеет операторов досрочного прекращения циклов, поэтому операторы перехода по необходимости часто используются в подобных ситуациях. Мы предлагаем следующий подход для работы с операторами безусловного пере- перехода, выполняющих выход из циклов, который гарантирует отслеживание всего цикла. Поскольку досрочный выход из цикла скорее всего осуществляется после вы- выполнения какого-нибудь логического условия, то мы можем предположить, что это условие никогда не выполняется. Но этот консервативный подход никогда не позво- позволит уменьшить время выполнения программы, так как мы предполагаем полное вы- выполнение цикла. Для программ, где досрочный выход из цикла не исключение, а правило, консервативный подход значительно переоценивает степень роста времени выполнения в наихудшем случае. Если же переход осуществляется к ранее выпол- выполненным операторам, то в этом случае вообще нельзя игнорировать оператор безус- безусловного перехода, поскольку такой оператор создает петлю в выполнении програм- программы, что приводит в нарастанию времени выполнения всей программы. Нам не хотелось бы, чтобы у читателя сложилось мнение о невозможности анали- анализа времени выполнения программ, использующих операторы безусловного перехода, создающих петли. Если программные петли имеют простую структуру, т.е. о любой паре петель можно сказать, что они или не имеют общих элементов, или одна петля вложена в другую, то в этом случае можно применить методы анализа времени вы- выполнения, описанные в данном разделе. (Конечно, бремя ответственности за пра- 36 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

вильное определение структуры петли ложится на того, кто проводит анализ.) Мы без колебаний рекомендуем применять описанные методы для анализа программ, на- написанных на таких языках, как Fortran, где использование операторов безусловного перехода является естественным делом, но для анализируемых программ допустимы петли только простой структуры. Анализ программ на псевдоязыке Если мы знаем степень роста времени выполнения операторов, записанных с по- помощью неформального "человеческого" языка, то, следовательно, сможем проанали- проанализировать программу на псевдоязыке (такие программы будем называть псевдопро- псевдопрограммами). Однако часто мы не можем в принципе знать время выполнения той час- части псевдопрограммы, которая еще не полностью реализована в формальных операторах языка программирования. Например, если в псевдопрограмме имеется неформальная часть, оперирующая абстрактными типами данных, то общее время выполнение программы в значительной степени зависит от способа реализации АТД. Это не является недостатком псевдопрограмм, так как одной из причин написания программ в терминах АТД является возможность выбора реализации АТД, в том числе по критерию времени выполнения. При анализе псевдопрограмм, содержащих операторы языка программирования и вызовы процедур, имеющих неформализованные фрагменты (такие как операторы для работы с АТД), можно рассматривать общее время выполнения программы как функцию пока не определенного времени выполнения таких процедур. Время вы- выполнения этих процедур можно параметризовать с помощью "размера" их аргумен- аргументов. Так же, как и "размер входных данных", "размер" аргументов — это предмет для обсуждения и дискуссий. Часто выбранная математическая модель АТД подска- подсказывает логически обоснованный размер аргументов. Например, если АТД строится на основе множеств, то часто количество элементов множества можно принять за пара- параметр функции времени выполнения. В последующих главах вы встретите много примеров анализа времени выполнения псевдопрограмм. 1.6. Практика программирования Приведем несколько рекомендаций и соображений, которые вытекают из нашего практического опыта построения алгоритмов и реализации их в виде программ. Не- Некоторые из этих рекомендаций могут показаться очевидными или даже банальными, но их полезность можно оценить только при решении реальных задач, а не исходя из теоретических предпосылок. Читатель может проследить применение приведенных рекомендаций при разработке программ в этой книге, а также может проверить их действенность в собственной практике программирования. 1. Планируйте этапы разработки программы. Мы описывали в разделе 1.1 этапы разработки программы: сначала черновой набросок алгоритма в неформальном стиле, затем псевдопрограмма, далее — последовательная формализация псевдо- псевдопрограммы, т.е. переход к уровню исполняемого кода. Эта стратегия организует и дисциплинирует процесс создания конечной программы, которая будет простой в отладке и в дальнейшей поддержке и сопровождении. 2. Применяйте инкапсуляцию. Все процедуры, реализующие АТД, поместите в од- одно место программного листинга. В дальнейшем, если возникнет необходимость изменить реализацию АТД, можно будет корректно и без особых затрат внести какие-либо изменения, так как все необходимые процедуры локализованы в од- одном месте программы. 3. Используйте и модифицируйте уже существующие программы. Один из неэф- неэффективных подходов к процессу программирования заключается в том, что каж- каждый новый проект рассматривается "с нуля", без учета уже существующих про- 1.6. ПРАКТИКА ПРОГРАММИРОВАНИЯ 37

грамм. Обычно среди программ, реализованных на момент начала проекта, мож- можно найти такие, которые если решают не всю исходную задачу, то хотя бы ее часть. После создания законченной программы полезно оглянуться вокруг и по- посмотреть, где еще ее можно применить (возможно, вариант ее применения ока- окажется совсем непредвиденным). 4. Станьте "кузнецом" инструментов. На языке программистов инструмент (tool) — это программа с широким спектром применения. При создании про- программы подумайте, нельзя ли ее каким-либо образом обобщить, т.е. сделать бо- более универсальной (конечно, с минимальными программистскими усилиями). Например, предположим, что вам необходимо написать программу, составляю- составляющую расписание экзаменов. Вместо заказанной программы можно написать про- программу-инструмент, раскрашивающий вершины обычного графа (по возможно- возможности минимальным количеством цветов) таким образом, чтобы любые две верши- вершины, соединенные ребром, были закрашены в разные цвета. В контексте расписания экзаменов вершины графа — это классы, цвета — время проведения экзаменов, а ребра, соединяющие две вершины-класса, обозначают, что в этих классах экзамены принимает одна и та же экзаменационная комиссия. Такая программа раскраски графа вместе с подпрограммой перевода списка классов в множество вершин графа и цветов в заданные временные интервалы проведения экзаменов составит расписание экзаменов. Программу раскраски можно исполь- использовать для решения задач, совсем не связанных с составлением расписаний, на- например для задания режимов работы светофоров на сложном перекрестке, как было показано в разделе 1.1. 5. Программируйте на командном уровне. Часто бывает, что в библиотеке про- программ не удается найти программу, необходимую для выполнения именно нашей задачи, но мы можем адаптировать для этих целей ту или иную программу- инструмент. Развитые операционные системы предоставляют программам, раз- разработанным для различных платформ, возможность совместной работы в сети вовсе без модификации их кода, за исключением списка команд операционной системы. Чтобы сделать команды компонуемыми, как правило, необходимо, что- чтобы каждая из них вела себя как фильтр, т.е. как программа с одним входным и одним выходным файлом. Отметим, что можно компоновать любое количество фильтров, и, если командный язык операционной системы достаточно интеллек- интеллектуален, достаточно просто составить список команд в том порядке, в каком они будут востребованы программой. Пример 1.11. В качестве примера рассмотрим программу spell, написанную Джон- Джонсоном (S.C. Johnson) с использованием команд UNIX . На вход этой программы по- поступает файл /х, состоящий из текста на английском языке, на выходе получаем все слова из fx, не совпадающие со словами из небольшого словаря2. Эта программа вос- воспринимает имена и правильно написанные слова, которых нет в словаре, как орфо- орфографические ошибки. Но обычно выходной список ошибок достаточно короткий, по- поэтому его можно быстро пробежать глазами и определить, какие слова в нем не яв- являются ошибками. Первый фильтр, используемый программой spell, — это команда translate, кото- которая имеет соответствующие параметры и заменяет прописные буквы на строчные, пробелы — на начало новых строк, а остальные символы оставляет без изменений. На выходе этой команды мы получаем файл /2, состоящий из тех же слов, что и файл fx, но каждое слово расположено в отдельной строке. Далее выполняется ко- команда sort, упорядочивающая строки входного файла в алфавитном порядке. Резуль- Результатом выполнения этой команды является файл /з, содержащий отсортированный список (возможно, с повторениями) слов из файла f2. Затем команда unique удаляет 1 UNIX — торговая марка Bell Laboratories. 2 Мы могли бы использовать полный словарь, но многие орфографические ошибки совпа- совпадают со словами, которые почти никогда не применяются. 38 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

повторяющиеся строки в своем входном файле /3, создавая выходной файл /4, содер- содержащий слова из исходного файла (без прописных букв и повторений), упорядоченные в алфавитном порядке. Наконец, к файлу /4 применяется кбманда dlff, имеющая па- параметр, который указывает на файл f5, содержащий в алфавитном порядке слова из словаря, расположенные по одному в строке. Результатом этой команды будет список слов из файла /4, которые не совпадают со словами из файла /5, т.е. те слова из ис- исходного списка, которых нет в словаре. Программа spell состоит из следующей по- последовательности команд: spell: translate [A-Z] —> [a-z] , пробел —» новая строка sort unique diff словарь Командный уровень программирования требует дисциплины от команды про- программистов. Они должны писать программы как фильтры везде, где это возможно, и создавать программы-инструменты вместо узкоспециализированных программ все- всегда, когда для этого есть условия. Существенным вознаграждением за это будет зна- значительное повышение вашего коэффициента отношения результата к затраченным усилиям. ? 1.7. Расширение языка Pascal Большинство программ в этой книге написаны на языке Pascal. Чтобы сделать листинги программ более читабельными, мы иногда будем применять три конструк- конструкции, которые вы не найдете в стандартном Pascal, но которые легко трансформиру- трансформируются в операторы языка Pascal. Одна из таких конструкций — нечисловые метки. Если в программе необходимо использовать несколько меток, то нечисловые метки значительно облегчат понимание программы. Например, оператор goto выход, оче- очевидно, более понятен, чем goto 561. Для преобразования программы с нечисловыми метками в "чистую" программу Pascal, надо заменить все нечисловые метки различ- различными числами и затем объявить их метками (label) в начале программы. Этот про- процесс можно полностью автоматизировать. Другой нестандартной конструкцией является оператор возврата return, который позволяет писать более понятные программы без использования операторов goto. Оператор возврата будем использовать в следующей форме: гНигп(выражение), где скобка (выражение) необязательна. Преобразовать процедуру с операторами возврата в стандартную программу Pascal очень просто. Сначала надо объявить новую метку, скажем 999, и затем поместить ее на последний оператор end процедуры. Например, оператор return(x) в некой функции zap заменяется следующим блоком: begin zap:= x; goto 999 end Оператор return, не имеющий аргументов, просто заменяется на оператор goto 999. Пример 1.12. В листинге 1.6 представлена программа, вычисляющая факториал, в которой использованы операторы возврата. В листинге 1.7 показана та же про- программа после замены операторов return стандартными операторами Pascal. ? Листинг 1.6. Программа вычисления факториала с операторами возврата function fact ( n: integer ): integer; begin if n <= 1 then 1.7. РАСШИРЕНИЕ ЯЗЫКА PASCAL 39

returnA) else return(л * fact(л - 1)) end; { fact } Листинг 1.7. Программа вычисления факториала на языке Pascal function fact ( п: integer ): integer; label 999; begin if n <= 1 then begin fact:= 1; goto 999 end else begin fact:= n * factin - 1) ; goto 999 end 999; end; { fact } Третье расширение языка Pascal, которое мы будем применять, заключается в посто- постоянном использовании выражений, описывающих типы, в качестве имен типов. Напри- Например, выражения, подобные Т celltype, мы считаем допустимыми в качестве имен типов, но недопустимыми для типов параметров процедур или значений, возвращаемых функ- функциями. Технически Pascal требует, чтобы мы использовали имена для типов данных, на- например prtocell (указатель на ячейку). В этой книге мы будем допускать такие описы- описывающие выражения в качестве имен типов, надеясь, что читатель сможет придумать имя для типа данных и механически заменить описывающее тип выражение именем типа.1 Другими словами, мы будем использовать операторы, подобные function zap( A: array[l..10] of integer ): T celltype подразумевая под этим следующий оператор (здесь arrayof integer обозначает "массив целых чисел"): function zap( A: arrayofinteger ): prtocell Наконец, замечание о применяемых нами соглашениях в отношении листингов программ. Зарезервированные слова Pascal выделяются полужирным начертанием, типы данных пишутся обычным начертанием, а имена процедур, функций и пере- переменных — курсивом. Мы различаем строчные и прописные буквы. Упражнения 1.1. В состязаниях футбольной лиги участвуют шесть команд: Соколы, Львы, Ор- Орлы, Бобры, Тигры и Скунсы. Соколы уже сыграли с Львами и Орлами. Львы также сыграли с Бобрами и Скунсами. Тигры сыграли с Орлами и Скунсами. Каждая команда играет одну игру в неделю. Найдите расписание матчей, что- чтобы все команды сыграли по одному разу друг с другом в течение минимально- минимального количества недель. Совет. Создайте граф, где вершины будут соответство- 1 Чтобы по возможности не плодить в листингах смесь "английского с нижегородским", мы будем применять русский язык только в псевдопрограммах, оставляя названия типов данных на английском языке и давая их перевод или в тексте, или иногда непосредственно в листин- листингах. — Прим. ред. 40 ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВ

вать парам команд, которые еще не играли между собой. Что должны обозна- обозначать ребра в таком графе, если при правильной раскраске графа каждый цвет соответствует матчам, сыгр