Программирование в алгоритмах

Окулов С.М.

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

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

Издательство: Бином. Лаборатория знаний, 2007 г.

ISBN 978-5-94774-689-1

Количество страниц: 384.

Содержание книги «Программирование в алгоритмах»:

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