| (12 год., резервний час – 2 год.) |
|
| Векторний добуток. Напрямок повороту. Визначення площі многокутника. Перетин відрізків. Визначення положення точки відносно простого многокутника. Визначення опуклої оболонки. Визначення пари найближчих і найвіддаленіших точок.
Застосування метода виключення для розв’язання алгоритмічних задач.
| Учні повинні знати:
сутність векторного добутку та напрямку повороту;
сутність умов перетину відрізків;
алгоритми визначення площі простого многокутника, положення точки відносно простого многокутника, опуклої оболонки, пари найближчих точок, пари найвіддаленіших точок;
алгоритм метода виключення для розв’язання алгоритмічних задач.
Учні повинні мати уявлення про: застосування поняття векторного добутку для реалізації алгоритмів розв’язання геометричних задач. Учні повинні вміти:
застосовувати алгоритми визначення площі простого многокутника, положення точки відносно простого многокутника, опуклої оболонки, пари найближчих точок, пари найвіддаленіших точок для реалізації конкретних задач;
застосовувати алгоритм метода виключення для реалізації конкретних задач.
|
|
| Застосування комбінаторики для розв’язання задач (10 год., резервний час – 2 год.) |
|
| Основні поняття та терміни комбінаторики. Задачі повного перебору. Переставлення. Підмножини множин. Сполучення. Розміщення. Способи генерування. | Учні повинні знати:
способи генерування переставлення, підмножин множини, сполучення та розміщення;
способи підрахунку кількості різних варіантів комбінаторних конфігурацій.
Учні повинні мати уявлення про:
найбільш розповсюджені комбінаторні конфігурації: переставлення, підмножин множини, розбиття множини, сполучення та розміщення;
лексикографічний порядок;
оцінку вибраного алгоритму генерування та можливість його застосування для конкретної задачі.
Учні повинні вміти:
визначити доречність використання тієї чи тієї моделі комбінаторної конфігурації для конкретної задачі;
реалізувати алгоритм генерації всіх можливих переставлень;
реалізувати алгоритм генерації всіх можливих сполучень;
реалізувати алгоритм генерації всіх можливих розміщень.
|
|
| Основи теорії графів (30 год., резервний час – 4 год.) |
|
|
Основні поняття теорії графів.
Пошук у ширину та у глибину.
Побудова остового дерева мінімальної довжини. Алгоритми Прима та Краскала.
Визначення найкоротшого шляху в графі. Алгоритм Дейкстри. Алгоритм Флойда-Уоршелла.
Задача комівояжера. Метод гілок і границь.
Дводольні графи. Побудова максимального паросполучення в дводольному графі.
Потоки в мережах. Алгоритм Форда-Фалкерсона побудови максимального потоку в мережі. | Учні повинні знати:
основні поняття теорії графів;
основні способи представлення графів;
алгоритми пошуку у ширину та глибину, побудову остового дерева мінімальної довжини, визначення найкоротшого шляху в графі;
постановку задачі комівояжера;
сутність алгоритму та реалізацію метода гілок і границь;
поняття про паросполучення та дводольні графи;
алгоритм побудови максимального паросполучення у дводольному графі;
поняття потоків у мережах;
алгоритм побудови максимального потоку в мережі.
Учні повинні мати уявлення про:
представлення інформації у вигляді графа;
різні способи представлення графів;
можливість застосування алгоритмів на графах для розв’язання конкретних алгоритмічних задач.
Учні повинні вміти:
визначати клас задач щодо застосування для їх розв’язання алгоритмів на графах;
застосовувати алгоритми на графах для реалізації конкретних задач.
|
|
| Основи лінійного програмування (10 год., резервний час – 2 год.) |
|
|
Загальна задача лінійного програмування. Задача про дієту. Задача про оптимальний асортимент. Геометрична інтерпретація розв’язання задач лінійного програмування.
Знайомство із середовищем автоматизації математичних розрахунків для розв’язання задач лінійного програмування симплекс-методом.
Задача про призначення. | Учні повинні знати:
основні поняття лінійного програмування: системи обмежень і цільової функції;
класичні задачі лінійного програмування (далі ЛП);
геометричну інтерпретацію задач ЛП;
алгоритм розв’язання задачі про призначення.
Учні повинні мати уявлення про:
сутність задач оптимізації і можливості застосування лінійного програмування для розв’язання задач;
симплекс-метод і геометричну інтерпретацію як методи розв’язання задач ЛП.
Учні повинні вміти:
визначати клас задач, що відносяться до ЛП;
складати та розв’язувати геометрично задачі ЛП;
користуватися пакетом програм для автоматизації математичних розрахунків для розв’язання задач оптимізації;
аналізувати результати, отримані геометрично або за допомогою програмного середовища;
складати та реалізовувати алгоритм задачі про призначення.
|
|
| Основи динамічного програмування (20 год., резервний час – 2 год.) |
|
|
Основні поняття задач динамічного програмування. Критерії застосування.
Задача про прокладання оптимального шляху.
Найбільша спільна підпослідовність.
Задача про рюкзак.
Задача про розподіл ресурсів. | Учні повинні знати:
сутність та основні принципи динамічного програмування;
принципи побудови покрокових алгоритмів;
критерії застосування динамічного програмування;
етапи побудови алгоритмів, основаних на принципах динамічного програмування;
ідеї розв’язання класичних задач динамічного програмування.
Учні повинні мати уявлення про:
оптимізацію задач у напрямку застосування динамічного програмування;
поняття незалежних підзадач і підзадач, що перекриваються;
оцінку ефективності алгоритмів динамічного програмування;
використання динамічного програмування при розв’язанні задач на графах.
Учні повинні вміти:
оцінити можливості застосування ДП до розв’язання задач;
розбити задачу на кроки, побудувати рекурентне співвідношення між параметрами підзадач або представити оптимізовані параметри підзадач таблично;
скласти та реалізувати алгоритми класичних задач ДП.
|
|
| “Жадібні” алгоритми (6 год.) |
|
| Критерії застосовування “жадібних” алгоритмів. Задача про центи. Задача про заявки. Неперервна задача про рюкзак. “Жадібні” алгоритми на графах. | Учні повинні знати:
сутність та основні принципи побудови “жадібних” алгоритмів;
критерії застосування “жадібних” алгоритмів;
ідеї розв’язання класичних задач.
Учні повинні мати уявлення про:
різницю у використанні динамічного програмування та “жадібних” алгоритмів;
евристичні алгоритми та доречність їх використання;
доведення коректності застосування “жадібних” алгоритмів до розв’язання задачі;
використання “жадібних” алгоритмів на графах.
|