Динамическое программирование, Окулов С.М., Пестов О.А., 2020

Динамическое программирование, Окулов С.М., Пестов О.А., 2020.
        
   В данной книге систематизирован материал по одному из методов проектирования алгоритмов в информатике — динамическому программированию. Предлагаемые задачи решаются фактически по одной схеме, основанной на данном методе, однако понять, что задача решается этим методом, очень непросто. Для этого кроме знаний требуется усилие подготовленного к решению таких задач интеллекта. Именно этому способствуют содержание книги и стиль изложения материала в ней.
Разобраны задачи, предлагавшиеся школьникам на всероссийских олимпиадах по информатике разных лет, а также на турнирах и конкурсах.
Для учащихся старших классов, студентов и преподавателей информатики.




Перечисление путей в графе.
Граф обозначается G = (V,E), где V — множество из п элементов (вершины графа, имеющие метки в виде натуральных чисел от 1 до n), а Е — множество ребер (дуг) из m элементов. Ребро — это пара (i,j), где i и j — метки вершин графа. Другими словами, ребра описывают связи между вершинами графа. Граф ориентированный, если, например, в Е есть пара (i,j), но нет пары (j,i). Ребро в этом случае, согласно общепринятому понятийному аппарату, называют дугой. Две вершины, связанные ребром, определяют как смежные. Будем считать, что граф описывается матрицей смежности А[1..n, 1..n]. Элемент A[i,j] равен единице, если в Е есть пара (i,j), и нулю в противном случае. Если ребрам (дугам) графа приписаны некие метки (веса), то вместо единицы в А записывается соответствующий вес.

Определим маршрут как некую последовательность смежных вершин графа. Цепь — это маршрут, в котором ни одно ребро (дуга) не встречается более одного раза. А путь (то, что мы будем искать) — это маршрут, в котором все вершины попарно различны (кроме, возможно, первой и последней). Граф связный, если любая пара его вершин имеет цепь, соединяющую их. Если не оговаривается специально, то рассматриваются только связные неориентированные графы.

ОГЛАВЛЕНИЕ.
Вместо предисловия. 
Введение. 
Глава 1. Простые задачи.
1.1. Числа Фибоначчи. 
1.2. Биномиальные коэффициенты, или Нахождение числа сочетаний.
1.3. Наибольший квадрат.
1.4. Задача о Черепашке. 
Глава 2. Основной принцип и метод реализации на основе рекуррентных соотношений.
2.1. Вводные замечания. 
2.2. Множество решаемых задач, вычисляемая функция и рекуррентные соотношения. 
2.3. Граф зависимостей задач. 
2.4. Общая схема. 
2.5. Пример решения задачи. 
Глава 3. Типы задач по динамическому программированию. 
3.1. Табличный метод решения.
3.2. Задачи на отрезках.
3.3. Задачи на деревьях.
3.4. Задачи на подмножествах. 
3.5. Динамическое программирование по профилю. 
Приложение I. Динамическое программирование как метод решения задач оптимизации.
Введение. 
1. Метод динамического программирования: основные положения. 
2. Примеры задач.
2.1. Задача о распределении ресурсов.
2.2. Задача о рюкзаке. 
2.3. Задачи о критических путях в графе. 
2.3.1. Перечисление путей в графе. 
2.3.2. Кратчайший путь в графе.
2.3.3. Максимальный путь в графе.
Приложение II. Справочные данные о задачах динамического программирования.

Купить .








Теги: учебник по программированию :: программирование :: Окулов :: Пестов :: алгоритм :: числа Фибоначчи