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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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