УДК 519.85(023) ББК 22.18 052
Работа выполнена при поддержке Министерства образования Российской Федерации, проект Г00—4.1-60.
Окулов С. М. Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. — 341 с: ил. ISBN 5-94774-010-9
Искусство программирования представлено в виде учебного курса, раскрывающего секреты наиболее популярных алгоритмов. Освещены такие вопросы,как комбинаторные алгоритмы, перебор, алгоритмы на графах, алгоритмы вычислительной геометрии. Приводятся избранные олимпиадные задачи по программированию с указаниями к решению. Практические рекомендации по тестированию программ являются необходимым дополнением курса. Предназначен для школьников, студентов и специалистов, серьезно изучающих программирование, а также для преподавателей учебныхзаведений. УДК 519.85(023) ББК 22.18
По вопросам приобретения обращаться в Москве: «БИНОМ. Лаборатория знаний» (095)955-03-98, e-mail: lbz@aha.ru в Санкт-Петербурге: «Диалект» (812)247-93-01, e-mail: dialect@sndlct.ioffe.rssi.ru
ISBN 5-94774-010-9
© Окулов С. М., 2002 © БИНОМ. Лаборатория знаний, 2002
Содержание
Предисловие 1. Арифметика многоразрядных целых чисел 1.1. Основные арифметическиеоперации 1.2. Задачи 2. Комбинаторные алгоритмы 2.1. Классические задачи комбинаторики 2.2. Генерация комбинаторных объектов 2.2.1. Перестановки 2.2.2. Размещения 2.2.3. Сочетания 2.2.4. Разбиение числа на слагаемые 2.2.5. Последовательности из нулей и единиц длины N без двух единиц подряд 2.2.6. Подмножества 2.2.7. Скобочные последовательности 2.3. Задачи 3. Перебор и методы его сокращения 3.1. Переборс возвратом (общая схема) 3.2. Примеры задач для разбора общей схемы перебора 3.3. Динамическое программирование 3.4. Примеры задач для разбора идеи метода динамического программирования 3.5. Метод ветвей и границ 3.6. Метод «решета» 3.7. Задачи 4. Алгоритмы на графах 4.1. Представление графа в памяти компьютера 4.2. Поиск в графе 4.2.1. Поиск в глубину 4.2.2. Поиск в ширину 4.3. Деревья
7 9 9 2125 25 31 31 40 46 53 58 61 65 68 79 79 81 96 98 105 109 113 141 141 142 142 143 144
Содержание
4.3.1. Основные понятия. Стягивающие деревья 4.3.2. Порождение всех каркасов графа 4.3.3. Каркас минимального веса. Метод Дж. Краскала . . 4.3.4. Каркас минимального веса. Метод Р. Прима 4.4. Связность 4.4.1. Достижимость 4.4.2. Определение связности 4.4.3. Двусвязность 4.5. Циклы 4.5.1. Эйлеровыциклы 4.5.2. Гамильтоновы циклы 4.5.3. Фундаментальное множество циклов 4.6. Кратчайшие пути 4.6.2. Алгоритм Дейкстры 4.6.3. Пути в бесконтурном графе 4.6.4. Кратчайшие пути между всеми парами вершин. Алгоритм Флойда 4.7. Независимые и доминирующие множества 4.7.1. Независимые множества 4.7.2. Метод генерации всех максимальных независимых множеств графа 4.7.3. Доминирующие множества 4.7.4. Задача онаименьшем покрытии 4.7.5. Метод решения задачи о наименьшем разбиении . . 4.8. Раскраски 4.8.1. Правильные раскраски 4.8.2. Поиск минимальной раскраски вершин графа . . . . 4.8.3. Использование задачи о наименьшем покрытии при раскраске вершин графа 4.9. Потоки в сетях, паросочетания 4.9.1. Постановка задачи 4.9.2. Метод построения максимального потока в сети . . . 4.9.3. Наибольшее паросочетание в двудольномграфе . . . 4.10. Методы приближенного решения задачи коммивояжера 4.10.1. Метод локальной оптимизации 4.10.2. Алгоритм Эйлера 4.10.3. Алгоритм Кристофидеса 4.11. Задачи 5. Алгоритмы вычислительной геометрии 5.1. Базовые процедуры
144 145 148 150 151 151 153 154 157 157 158 160 161 163 164 166 168 168 169 173 174 175 180 180 181 185 186 186 187 192 195 195 197 200 202 222 222
Содержание
5.2. 5.3.5.4. 5.5. 5.6. 5.7.
Прямая линия и отрезок прямой Треугольник Многоугольник Выпуклая оболочка Задачи о прямоугольниках Задачи
227 232 236 241 251 259 266 318 319 320 328 340
6. Избранные олимпиадные задачи по программированию 7. Заметки о тестировании программ 7.1. О программировании 7.2. Практические рекомендации 7.3. Тестирование программы решения задачи (на примере)...
Работа выполнена при поддержке Министерства образования Российской Федерации, проект Г00—4.1-60.
Окулов С. М. Программирование в алгоритмах / С. М. Окулов. — М.: БИНОМ. Лаборатория знаний, 2002. — 341 с: ил. ISBN 5-94774-010-9
Искусство программирования представлено в виде учебного курса, раскрывающего секреты наиболее популярных алгоритмов. Освещены такие вопросы,как комбинаторные алгоритмы, перебор, алгоритмы на графах, алгоритмы вычислительной геометрии. Приводятся избранные олимпиадные задачи по программированию с указаниями к решению. Практические рекомендации по тестированию программ являются необходимым дополнением курса. Предназначен для школьников, студентов и специалистов, серьезно изучающих программирование, а также для преподавателей учебныхзаведений. УДК 519.85(023) ББК 22.18
По вопросам приобретения обращаться в Москве: «БИНОМ. Лаборатория знаний» (095)955-03-98, e-mail: lbz@aha.ru в Санкт-Петербурге: «Диалект» (812)247-93-01, e-mail: dialect@sndlct.ioffe.rssi.ru
ISBN 5-94774-010-9
© Окулов С. М., 2002 © БИНОМ. Лаборатория знаний, 2002
Содержание
Предисловие 1. Арифметика многоразрядных целых чисел 1.1. Основные арифметическиеоперации 1.2. Задачи 2. Комбинаторные алгоритмы 2.1. Классические задачи комбинаторики 2.2. Генерация комбинаторных объектов 2.2.1. Перестановки 2.2.2. Размещения 2.2.3. Сочетания 2.2.4. Разбиение числа на слагаемые 2.2.5. Последовательности из нулей и единиц длины N без двух единиц подряд 2.2.6. Подмножества 2.2.7. Скобочные последовательности 2.3. Задачи 3. Перебор и методы его сокращения 3.1. Переборс возвратом (общая схема) 3.2. Примеры задач для разбора общей схемы перебора 3.3. Динамическое программирование 3.4. Примеры задач для разбора идеи метода динамического программирования 3.5. Метод ветвей и границ 3.6. Метод «решета» 3.7. Задачи 4. Алгоритмы на графах 4.1. Представление графа в памяти компьютера 4.2. Поиск в графе 4.2.1. Поиск в глубину 4.2.2. Поиск в ширину 4.3. Деревья
7 9 9 2125 25 31 31 40 46 53 58 61 65 68 79 79 81 96 98 105 109 113 141 141 142 142 143 144
Содержание
4.3.1. Основные понятия. Стягивающие деревья 4.3.2. Порождение всех каркасов графа 4.3.3. Каркас минимального веса. Метод Дж. Краскала . . 4.3.4. Каркас минимального веса. Метод Р. Прима 4.4. Связность 4.4.1. Достижимость 4.4.2. Определение связности 4.4.3. Двусвязность 4.5. Циклы 4.5.1. Эйлеровыциклы 4.5.2. Гамильтоновы циклы 4.5.3. Фундаментальное множество циклов 4.6. Кратчайшие пути 4.6.2. Алгоритм Дейкстры 4.6.3. Пути в бесконтурном графе 4.6.4. Кратчайшие пути между всеми парами вершин. Алгоритм Флойда 4.7. Независимые и доминирующие множества 4.7.1. Независимые множества 4.7.2. Метод генерации всех максимальных независимых множеств графа 4.7.3. Доминирующие множества 4.7.4. Задача онаименьшем покрытии 4.7.5. Метод решения задачи о наименьшем разбиении . . 4.8. Раскраски 4.8.1. Правильные раскраски 4.8.2. Поиск минимальной раскраски вершин графа . . . . 4.8.3. Использование задачи о наименьшем покрытии при раскраске вершин графа 4.9. Потоки в сетях, паросочетания 4.9.1. Постановка задачи 4.9.2. Метод построения максимального потока в сети . . . 4.9.3. Наибольшее паросочетание в двудольномграфе . . . 4.10. Методы приближенного решения задачи коммивояжера 4.10.1. Метод локальной оптимизации 4.10.2. Алгоритм Эйлера 4.10.3. Алгоритм Кристофидеса 4.11. Задачи 5. Алгоритмы вычислительной геометрии 5.1. Базовые процедуры
144 145 148 150 151 151 153 154 157 157 158 160 161 163 164 166 168 168 169 173 174 175 180 180 181 185 186 186 187 192 195 195 197 200 202 222 222
Содержание
5.2. 5.3.5.4. 5.5. 5.6. 5.7.
Прямая линия и отрезок прямой Треугольник Многоугольник Выпуклая оболочка Задачи о прямоугольниках Задачи
227 232 236 241 251 259 266 318 319 320 328 340
6. Избранные олимпиадные задачи по программированию 7. Заметки о тестировании программ 7.1. О программировании 7.2. Практические рекомендации 7.3. Тестирование программы решения задачи (на примере)...
Поделиться рефератом
Расскажи своим однокурсникам об этом материале и вообще о СкачатьРеферат