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

Вид материала

Документы

Подобный материал:

• Особливості навчальної програми для учнів 8 класу загальноосвітніх навчальних закладів, 602.24kb.
• Програми за якими викладається інформатика, 34.45kb.
• Програми для загальноосвітніх навчальних закладів Навчальні програми для профільного, 7256.17kb.
• «Математика в школі», 894.13kb.
• «Математика в школі», 804.81kb.
• Методичні рекомендації щодо викладання математики в 2010-2011 навчальному році, 805.17kb.
• Інструктивно-методичний лист про вивчення математики в 2010-2011 навчальному році, 820.9kb.
• Інструктивно методичний лист про вивчення математики у 2010-2011 навчальному році, 805.27kb.
• Програма для загальноосвітніх навчальних закладів (класів) з поглибленим вивченням, 717.77kb.
• Одним із предметів інваріантної складової навчальних планів є астрономія, яка вивчатиметься, 45.99kb.

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

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

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

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

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

Основні поняття теорії графів.

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

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

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

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

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

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

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

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

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

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

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

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

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

Загальна задача лінійного програмування. Задача про дієту. Задача про оптимальний асортимент. Геометрична інтерпретація розв’язання задач лінійного програмування.

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

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

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

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

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

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

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

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

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

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

Основні поняття задач динамічного програмування. Критерії застосування.

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

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

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