3.13. Основи динамічного програмування (20 год)

Основні поняття задач динамічного програмування. Критерії застосування. Задача про прокладання оптимального шляху. Найбільша спільна підпослідовність.

Задача про рюкзак. Задача про розподіл ресурсів.

Учні повинні знати:

• сутність та основні принципи динамічного програмування;

• критерії застосування динамічного програмування;

• етапи побудови алгоритмів, основаних на принципах динамічного програмування;

• ідеї розв’язування класичних задач динамічного програмування;

• поняття незалежних підзадач та підзадач, що перекриваються;

• різницю у використанні повнопереборного методу, методу “розділяй і володій” та динамічного програмування;

• шляхи використання динамічного програмування при розв’язуванні задач на графах.

Учні повинні вміти:

• оцінити можливості застосування динамічного програмування до розв’язування задач;

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