Навчальні програми для профільного навчання Програми факультативів, спецкурсів, пропедевтичних курсів, гуртків

Обчислювальна геометрія та числові методи

(12 год., резервний час – 2 год.)

Векторний добуток. Напрямок повороту. Визначення площі многокутника. Перетин відрізків. Визначення положення точки відносно простого многокутника.

Визначення опуклої оболонки. Визначення пари найближчих і найвіддаленіших точок.

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

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

Учні повинні мати уявлення про:

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

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

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

Застосування комбінаторики для розв’язання задач (10 год., резервний час – 2 год.)

Основні поняття та терміни комбінаторики. Задачі повного перебору. Переставлення. Підмножини множин. Сполучення. Розміщення. Способи генерування.

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

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

• 
  способи підрахунку кількості різних варіантів комбінаторних конфігурацій.
  

Учні повинні мати уявлення про:

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

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

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

Основи теорії графів (30 год., резервний час – 4 год.)

Пошук у ширину та у глибину.

Побудова остового дерева мінімальної довжини. Алгоритми Прима та Краскала.

Визначення найкоротшого шляху в графі. Алгоритм Дейкстри. Алгоритм Флойда-Уоршелла.

Задача комівояжера. Метод гілок і границь.

Дводольні графи. Побудова максимального паросполучення в дводольному графі.

Потоки в мережах. Алгоритм Форда-Фалкерсона побудови максимального потоку в мережі.

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

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

Учні повинні мати уявлення про:

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

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

• 
  визначати клас задач щодо застосування для їх розв’язання алгоритмів на графах;
  
• 
  застосовувати алгоритми на графах для реалізації конкретних задач.
  

Основи лінійного програмування (10 год., резервний час – 2 год.)

Знайомство із середовищем автоматизації математичних розрахунків для розв’язання задач лінійного програмування симплекс-методом.

Задача про призначення.

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

• 
  основні поняття лінійного програмування: системи обмежень і цільової функції;
  
• 
  класичні задачі лінійного програмування (далі ЛП);
  
• 
  геометричну інтерпретацію задач ЛП;
  
• 
  алгоритм розв’язання задачі про призначення.
  

Учні повинні мати уявлення про:

• 
  сутність задач оптимізації і можливості застосування лінійного програмування для розв’язання задач;
  
• 
  симплекс-метод і геометричну інтерпретацію як методи розв’язання задач ЛП.
  

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

• 
  визначати клас задач, що відносяться до ЛП;
  
• 
  складати та розв’язувати геометрично задачі ЛП;
  
• 
  користуватися пакетом програм для автоматизації математичних розрахунків для розв’язання задач оптимізації;
  
• 
  аналізувати результати, отримані геометрично або за допомогою програмного середовища;
  
• 
  складати та реалізовувати алгоритм задачі про призначення.
  

Основи динамічного програмування

(20 год., резервний час – 2 год.)

Задача про прокладання оптимального шляху.

Найбільша спільна підпослідовність.

Задача про рюкзак.

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

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

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

Учні повинні мати уявлення про:

• 
  оптимізацію задач у напрямку застосування динамічного програмування;
  
• 
  поняття незалежних підзадач і підзадач, що перекриваються;
  
• 
  оцінку ефективності алгоритмів динамічного програмування;
  
• 
  використання динамічного програмування при розв’язанні задач на графах.
  

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

• 
  оцінити можливості застосування ДП до розв’язання задач;
  
• 
  розбити задачу на кроки, побудувати рекурентне співвідношення між параметрами підзадач або представити оптимізовані параметри підзадач таблично;
  
• 
  скласти та реалізувати алгоритми класичних задач ДП.
  

“Жадібні” алгоритми (6 год.)

Критерії застосовування “жадібних” алгоритмів. Задача про центи. Задача про заявки. Неперервна задача про рюкзак.

“Жадібні” алгоритми на графах.

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

• 
  сутність та основні принципи побудови “жадібних” алгоритмів;
  
• 
  критерії застосування “жадібних” алгоритмів;
  
• 
  ідеї розв’язання класичних задач.
  

Учні повинні мати уявлення про:

• 
  різницю у використанні динамічного програмування та “жадібних” алгоритмів;
  
• 
  евристичні алгоритми та доречність їх використання;
  
• 
  доведення коректності застосування “жадібних” алгоритмів до розв’язання задачі;
  
• 
  використання “жадібних” алгоритмів на графах.