Книга: Окулов С. М. «Программирование в алгоритмах»

Серия: "Развитие интеллекта школьников"

Искусство программирования представлено в виде учебного курса, раскрывающего секреты наиболее популярных алгоритмов. Освещены такие вопросы, как комбинаторные алгоритмы, перебор, алгоритмы на графах, алгоритмы вычислительной геометрии. Приводятся избранные олимпиадные задачи по программированию с указаниями к решению. Практические рекомендации по тестированию программ являются необходимым дополнением курса.
Для школьников, студентов и специалистов, серьезно изучающих программирование, а также для преподавателей учебных заведений.

Содержание:

Предисловие...... 6 1. Арифметика многоразрядных целых чисел...... 8 1. 1. Основные арифметические операции...... 8 1. 2. Задачи...... 22 2. Комбинаторные алгоритмы...... 27 2. 1. Классические задачи комбинаторики...... 27 2. 2. Генерация комбинаторных объектов...... 34 2. 2. 1. Перестановки...... 34 2. 2. 2. Размещения...... 44 2. 2. 3. Сочетания...... 50 2. 2. 4. Разбиение числа на слагаемые...... 58 2. 2. 5. Последовательности из нулей и единиц длины N без двух единиц подряд...... 64 2. 2. 6. Подмножества...... 67 2. 2. 7. Скобочные последовательности...... 71 2. 3. Задачи...... 76 3. Перебор и методы его сокращения...... 87 3. 1. Перебор с возвратом (общая схема)...... 87 3. 2. Примеры задач для разбора общей схемы перебора...... 89 3. 3. Динамическое программирование...... 106 3. 4. Примеры задач для разбора идеи метода динамического программирования...... 108 3. 5. Метод ветвей и границ...... 116 3. 6. Метод «решета»...... 121 3. 7. Задачи...... 126 4. Алгоритмы на графах...... 158 4. 1. Представление графа в памяти компьютера...... 158 4. 2. Поиск в графе...... 159 4. 2. 1. Поиск в глубину...... 159 4. 2. 2. Поиск в ширину...... 161 4. 3. Деревья...... 162 4. 3. 1. Основные понятия. Стягивающие деревья...... 162 4. 3. 2. Порождение всех каркасов графа...... 163 4. 3. 3. Каркас минимального веса. Метод Дж. Краскала...... 165 4. 3. 4. Каркас минимального веса. Метод Р. Прима...... 168 4. 4. Связность...... 170 4. 4. 1. Достижимость...... 170 4. 4. 2. Определение связности...... 172 4. 4. 3. Двусвязность...... 173 4. 5. Циклы...... 176 4. 5. 1. Эйлеровы циклы...... 176 4. 5. 2. Гамильтоновы циклы...... 177 4. 5. 3. Фундаментальное множество циклов...... 179 4. 6. Кратчайшие пути...... 180 4. 6. 1. Постановка задачи. Вывод пути...... 180 4. 6. 2. Алгоритм Дейкстры...... 182 4. 6. 3. Пути в бесконтурном графе...... 183 4. 6. 4. Кратчайшие пути между всеми парами вершин. Алгоритм Флойда...... 186 4. 7. Независимые и доминирующие множества...... 188 4. 7. 1. Независимые множества...... 188 4. 7. 2. Метод генерации всех максимальных независимых множеств графа...... 189 4. 7. 3. Доминирующие множества...... 194 4. 7. 4. Задача о наименьшем покрытии...... 195 4. 7. 5. Метод решения задачи о наименьшем разбиении...... 196 4. 8. Раскраски...... 202 4. 8. 1. Правильные раскраски...... 202 4. 8. 2. Поиск минимальной раскраски вершин графа...... 203 4. 8. 3. Использование задачи о наименьшем покрытии при раскраске вершин графа...... 207 4. 9. Потоки в сетях, паросочетания...... 208 4. 9. 1. Постановка задачи...... 208 4. 9. 2. Метод построения максимального потока в сети...... 210 4. 9. 3. Наибольшее паросочетание в двудольном графе...... 215 4. 10. Методы приближенного решения задачи коммивояжера...... 219 4. 10. 1. Метод локальной оптимизации...... 219 4. 10. 2. Алгоритм Эйлера...... 222 4. 10. 3. Алгоритм Кристофидеса...... 225 4. 11. Задачи...... 227 5. Алгоритмы вычислительной геометрии...... 249 5. 1. Базовые процедуры...... 249 5. 2. Прямая линия и отрезок прямой...... 255 5. 3. Треугольник...... 262 5. 4. Многоугольник...... 266 5. 5. Выпуклая оболочка...... 272 5. 6. Задачи о прямоугольниках...... 284 5. 7. Задачи...... 293 6. Избранные олимпиадные задачи по программированию...... 300 7. Заметки о тестировании программ...... 358 7. 1. О программировании...... 359 7. 2. Практические рекомендации...... 360 7. 3. Тестирование программы решения задачи (на примере)...... 370 Библиографический указатель...... 382

Издательство: "БИНОМ. Лаборатория знаний" (2017)

ISBN: 9785001014492