Динамическое программирование

Методы проектирования алгоритмов.

С. М. Окулов, О. А. Пестов «Динамическое программирование» БИНОМ, 2015 год, 299 стр.2-е изд. ISBN 978-5-9963-2572-6 (13,2 мб. pdf)

В представленной книге сгруппирован материал по одному из методов проектирования алгоритмов в информатике —динамическому программированию (dynamic programming). Данные задачи решаются фактически по одной схеме, с использованием данного метода, однако понять, что задача решается таким способом, очень непросто.

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

Оглавление книги

Вместо предисловия 5
Введение 9

Глава 1. Простые задачи

1.1. Числа Фибоначчи 13
1.2. Биномиальные коэффициенты, или Нахождение числа сочетаний 17
1.3. Наибольший квадрат 20
1.4. Задача о Черепашке 26

Глава 2. Основной принцип и метод реализации на основе рекуррентных соотношений

2.1. Вводные замечания 33
2.2. Множество решаемых задач, вычисляемая функция и рекуррентные соотношения 35
2.3. Граф зависимостей задач 38
2.4. Общая схема 42
2.5. Пример решения задачи 45

Глава 3. Типы задач по динамическому программированию

3.1. Табличный метод решения 49
3.2. Задачи на отрезках 87
3.3. Задачи на деревьях 106
3.4. Задачи на подмножествах 140
3.5. Динамическое программирование по профилю 156

Приложения.

Приложение I. Динамическое программирование как метод решения задач оптимизации 201

Введение 201
1. Метод динамического программирования: основные положения 206
2. Примеры задач 209
2.1. Задача о распределении ресурсов 209

2.2. Задача о рюкзаке 226
2.3. Задачи о критических путях в графе 237
2.3.1. Перечисление путей в графе 238
2.3.2. Кратчайший путь в графе 241
2.3.3. Максимальный путь в графе 249

Приложение II. Справочные данные о задачах динамического программирования 260

 

Скачать техническую литературу бесплатно13,2 мб pdf

Похожая литература