• ознайомити з принципами:
  • динамічного програмування;
  • жадібності алгоритму;
• описати процес розробки алгоритмів:
  • динамічного програмування;
  • жадібного алгоритму;
• ознайомити з програмним втіленням розглянутих алгоритмів;
• виробити навички програмного втіленням розглянутих алгоритмів.

Після вивчення матеріалу учень:

• пояснює: визначення й умови застосування принципів динамічного програ­мування;

• знає зміст понять: процес розробки, опис структури оптимального розв'язку, критерії застосування;

• розпізнає: задачі, що розв'язують з використанням динамічного програ­мування та жадібного алгоритму;

• уміє:
  • аналізувати та формулювати постановку задачі;
  • записувати коди розв'язання за алгоритмом;
  • розбивати завдання на підзадачі;
  • обчислювати оптимальні значення параметрів для всієї задачі;
  • створювати програми;
  • аналізувати результати виконання програм;
  • налагоджувати програму.

Обладнання: комп'ютери зі встановленими ОС і браузером.

Структура уроку

1. Організаційний момент.
2. Актуалізація опорних знань.
3. Вивчення нового матеріалу.
4. Інструктаж з ТБ.
5. Вироблення практичних навичок.
6. Підбиття підсумків уроку.
7. Домашнє завдання.

1. Як записати умовний оператор?
2. Які є форми запису операторів повторення (циклу)
3. Як упорядкувати масив представників одного класу за функцією порівняння розробника? — див. приклад упорядкування інтервалів числової прямої за довжиною.

3. Вивчення нового матеріалу

Динамічне програмування — розділ математики, який присвячено теорії і методам розв'язання багатокрокових задач оптимального управління на основі використання рекурентних співвідношень.

Поняття рекурентного співвідношення розглянемо на прикладі такої задачі.

Задача 1. Порахувати число послідовностей нулів і одиниць довжини n, в яких не зустрічаються дві одиниці, що йдуть підряд.

Виведення рекурентного співвідношення. Позначимо через K_n шукану кількість. Розглянемо довільну прийнятну послідовність довжини n. Якщо останній її символ дорівнює 0, то перші (n − 1) символ утворюють довільну прийнятну послідовність довжини (n − 1). Кількість таких послідовностей, згідно із запровадженим позначенням, дорівнює всього K_{n − 1}. Якщо останній символ дорівнює 1, то передостанній символ дорівнює 0 (інакше буде дві одиниці підряд), а перші n − 2 символи — довільна прийнятна послідовність довжини n − 2. Число таких послідовностей дорівнює K_{n − 2}. Тому при n > 2 справджується рівність:

K_n = K_{n − 1} + K_{n − 2};
K₁ = 2;
K₂ = 3.

Отримана рівність (зауважте: та сама, що задає послідовність чисел Фібоначчі) виражає залежність члена послідовності K_n для даного значення параметра n через розв'язки для попередніх значень (n − 1) і (n − 2). Таке співвідношення називають рекурентним.

Подамо приклади двовимірного динамічного програмування — задачі про маршрути на прямокутному полі: порахувати число маршрутів або знайти маршрут, які (який) є кращими в деякому сенсі. Для цих завдань характерним є те, що кожний маршрут не може пройти двічі або більше разів однією і тією самою клітиною.

Задача 2. Дано прямокутне поле розміром n × m клітин. Дозволено рухатися полем на одну клітину праворуч або вниз. Порахувати, скількома способами можна потрапити з лівої верхньої клітини у праву нижню.

Виведення рекурентного співвідношення. У клітину поля з координатами (i, j) можна безпосередньо потрапити лише згори або зліва, тобто з клітин з координатами (i − 1, j ) і (i, j − 1). Позначимо через A_ij кількість маршрутів, що ведуть у клітину з координатами (i, j ). Ця величина дорівнює 0 для індексів i, j, що вказують за межі поля. Маємо:

A_ij = A_{(i − 1) j} + A_{i (j − 1)};
A₀₀ = 1.

Задача 3. Дано прямокутний поле розміром n × m клітин. Дозволено рухатися полем на одну клітину праворуч, вниз або по діагоналі праворуч-вниз. У кожній клітині записано деяке натуральне число. Рух розпочинають з верхньої лівої клітки і закінчують у правій нижній. Вагу маршруту обчислюють як суму чисел з усіх відвіданих клітин. Необхідно знайти маршрут з мінімальною вагою.

Виведення рекурентного співвідношення. Позначимо через B_ij найменшу вагу маршруту, що веде у клітину з координатами (i, j ), через с_ij — число, записане у цій клітині. Вважаємо, що B_ij = 0 для індексів i, j, що вказують за межі поля. У клітину з координатами (i, j) можна безпосередньо потрапити лише з клітин з координатами (i − 1, j ), (i − 1, j − 1) і (i, j − 1). Тому маємо:

B_ij = min(B_{(i − 1) j} , B_{(i − 1) (j − 1)} , B_{i (j − 1)}) + c_ij .

Для знаходження оптимального маршруту в окремий масив для кожної клітини потрібно записувати, з якого боку до неї буде зроблено хід. А після визначення значень елементів матриці B маршрут відновити «з кінця».

На наступному малюнку подано приклад вихідних даних і одного з кроків алгоритму. Ліворуч зображено таблицю записаних чисел c, праворуч створювану таблицю B. Стрілки вказують, з якого боку необхідно прийти у клітину, щоб отримати мінімальну вагу маршруту у цю клітину.

Розглянемо умову задачі «Банківська справа». Це одна з найпростіших задач, що ілюструє метод динамічного програмування, запропонований Р.Беллманом у 1955 році для задач оптимізації з адитивною цільовою функцієї — функцією зиску для пошуку максимума, функцією втрат для пошуку мінімума. Надалі розглянемо функцію зиску (для пошуку максимума) зі скінченою кількістю варіантів управління. Скінченність забезпечує існування оптимальної рішення.

Адитивність цільової функції означає можливість подання її у такому вигляді:

Тут:

• p_j — певне управлінське рішення. У нашому випадку — скільки монет було дано банкіру j;

• q_j — стан системи після прийняття управлінського рішення p_{j – 1}. У нашому випадку:

  • q₁ = m;
  • q_j = q_{j – 1} – p_{j – 1} при 1 < j;

• значення f_j(q_j, p_j) задано відповідним числом вхідного файлу.

Позначимо через F_n(q₁) максимум цільової функції, записаної вище. Маємо:

У другому рядку внутрішній максимум потрібно шукати за p₁, p₂, …, p_{n – 1}, а зовнішній — за p_n.

У третьому рядку максимум потрібно шукати за q_n і p_n за умови, що стан q_n отримано у результаті прийняття оптимальних управлінських рішень p₁, p₂, …, p_{n – 1}.

Адитивність цільової функції означає можливість подати прийняття рішення про оптимальне керування у вигляді послідовності прийняття рішень p₁, p₂, …, p_{n – 1}, p_n. Інакше кажучи, розв'язання задачі можна розбити на окремі етапи з дотриманням принципу: довільне оптимальне рішення є продовженням оптимального рішення.

Кожний з етапів є окремою частиною поставленої загальної задачі. Їх розв'язують одним і тим самим оптимізаційним алгоритмом. Але розв'язання кожної наступної підзадачі залежить від розв'язків попередньої.

Процес розробки алгоритмів динамічного програмування має такі етапи:

1. Опис структури оптимального розв’язку.
2. Рекурентне визначення оптимального розв’язку підзадач.
3. Обчислення значення цільової функції для оптимального рішення.
4. Отримання оптимального розв’язку.

Динамічне програмування надає математичний апарат для планування багато­крокових керованих процесів чи процесів, які розвиваються у часі. Таким чином, динамічне програмування не є окремим методом розв’язування задач. Це теорія, що поєднує ряд однотипних ідей та прийомів, які застосовують для розв’язування досить різних за змістом задач: оптимальний розподіл капіталовкладень, розподілом продукції між різними регіонами, визначенням найкоротшого шляху завезення товарів споживачам, задачі щодо заміни устаткування, оптимального управління запасами тощо.

Завдання 1. Проаналізувати словесний алгоритм і код розв'язання задачі «Банківська справа». Проаналізувати дію алгоритму (програми) на прикладі вхідних даних з умови і отримати правильні вихідні дані.

Для багатьох оптимізаційних задач є простіші й швидші алгоритми. Наприклад, жадібні алгоритми (Greedy algorithm).

Жадібні алгоритми — це загальна назва підходу до вирішення завдань оптимізації. Їх (як і метод динамічного програмування) застосовують у випадках, коли початкову задачу можна розбити на послідовність простіших підзадач, щоб у результаті отримати рішення початкової. У таких алгоритмах роблять вибір, який є найкращим у поточний момент прийняття рішення. Інакше кажучи, здійснюють локально оптимальний вибір, сподіваючись, що він приведе до оптимального рішення глобального завдання. При цьому на кожному кроці вибір повинен бути:

• допустимим, тобто задовольняти обмеженням завдання;
• локально оптимальним;
• остаточним (його не змінюють подальшими кроками алгоритму).

Схема доведення оптимальності отриманого розв'язання:

Розглянемо програмування жадібного алгоритму на прикладі задачі про вибір заявок.

Задача 4. Є n заявок на проведення занять в деякій аудиторії. У заявці з номером j вказано два числа s_j і f_j — початок і кінець заняття (у хвилинах від початку доби). Заявки з номерами j та k сумісні, якщо проміжки [s_j , f_j ) і [s_k , f_k ) не перетинаються, тобто справджується одна з нерівностей: f_j ≤ s_k або f_k ≤ s_j. Перший рядок файлу input.txt містить запис числа n. Кожний з наступних n рядків містить записи двох чисел: початку й кінця заняття. Потрібно записати у файл output.txt:

• у перший рядок максимальну кількість сумісних між собою заявок;
• у другий рядок номери відповідних заяв у порядку виконання.

Алгоритм розв'язання задачі про вибір заявок

1. Упорядкувати заявки за зростанням часу закінчення.

2. Надати множині заяв (відповіді) значення порожньої множини.

3. До множини заяв відповіді включити першу (після упорядкування) заявку.

4. Знайти у переліку першу заявку, що починається не раніше закінчення останньої, включеної у відповідь.

5. Включити знайдену заявку до множині заяв (відповіді).

6. Два попередні кроки повторювати доти, поки при пошуку чергової заявки не буде досягнуто кінця переліку заяв.

Зауважимо: після відкидання усіх заявок, що суперечать останній, долученій до списку, отримаємо початкову задачу з меншою кількістю заявок. Використавши індукцію, приходимо до висновку про оптимальність розв'язку.

Завдання 2. Проаналізувати код розв'язання задачі «Вибір заяв» та його дію на прикладі вхідних даних з умови і отримати правильні вихідні дані.

4. Інструктаж з ТВ
5. Вироблення практичних навичок

Завдання 3. Розв'язати задачу «Сходинки», умову якої опубліковано на сайті e-olymp.com/uk/.

На кожній з n + 2 сходинок сходів написане ціле число, причому на першій та на останній сходинках записано число 0. На першій сходинці стоїть людина, якій потрібно піднятися на останню сходинку. За один крок вона може підніматись на довільну кількість сходинок, що не перевищує k. Знайти найбільше можливе значення цієї суми всіх чисел, написаних на сходинках, на які наступила людина.

Вхідні дані. У першому рядку міститься число n (0 ≤ n ≤ 1000). У другому рядку записано n цілих чисел, які не перевищують за модулем 1000, відкремлених пропусками — числа, написані на сходинках у порядку підйому (за виключенням першої та останньої сходинки, на яких написані нулі). У третьому рядку записано максимальну величину кроку людини k (1 ≤ k ≤ n).

Вихідні дані. Вивести максимально можливу суму чисел, написаних на сходинках, на які наступила людина.

Ліміт часу 1 секунда.
Ліміт використання пам'яті 122.17 MB
Приклад вхідних даних

3
1 -1 1
2

Приклад вихідних даних

2

Завдання 4. Розв'язати задачу «Приватні інтереси», використавши жадібний алгоритм. Пересвідчитися у тому, що для деяких тестів відповідь хибна. Тести запозичити з архіву. Проаналізувати причину розбіжності, уважно перечитавши умову та дію правильного алгоритву для відповідних тестів.

Завдання 5. Дати відповідь на такі питання:

1. Що таке рекурентне співвідношення?
2. Що таке динамічне програмування?
3. До яких задач застосовують динамічне програмування?
4. Що таке жадібний алгоритм?

6. Підбиття підсумків уроку
Виставлення оцінок.

7. Домашнє завдання

1. Вивчити матеріал уроку.
2. При потребі доробити завдання 3, 4.

Демонстраційні розв'язання завдань 1-2 створив Олександр Рудик.