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



Сторінка12/22
Дата конвертації04.11.2016
Розмір4.81 Mb.
1   ...   8   9   10   11   12   13   14   15   ...   22

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

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




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

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


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

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


    • сутність векторного добутку та напрямку повороту;

    • сутність умов перетину відрізків;

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

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

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

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

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


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

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



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




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

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


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

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

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


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

    • лексикографічний порядок;

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

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


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

    • реалізувати алгоритм генерації всіх можливих переставлень;

    • реалізувати алгоритм генерації всіх можливих сполучень;

    • реалізувати алгоритм генерації всіх можливих розміщень.



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





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

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

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

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

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

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


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

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


    • основні поняття теорії графів;

    • основні способи представлення графів;

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

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

    • сутність алгоритму та реалізацію метода гілок і границь;

    • поняття про паросполучення та дводольні графи;

    • алгоритм побудови максимального паросполучення у дводольному графі;

    • поняття потоків у мережах;

    • алгоритм побудови максимального потоку в мережі.

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


    • представлення інформації у вигляді графа;

    • різні способи представлення графів;

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

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


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

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



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





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

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


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

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


    • основні поняття лінійного програмування: системи обмежень і цільової функції;

    • класичні задачі лінійного програмування (далі ЛП);

    • геометричну інтерпретацію задач ЛП;

    • алгоритм розв’язання задачі про призначення.

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


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

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

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


    • визначати клас задач, що відносяться до ЛП;

    • складати та розв’язувати геометрично задачі ЛП;

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

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

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



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

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





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

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

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

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


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

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

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


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

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

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

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

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


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

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

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



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




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

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

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


    • сутність та основні принципи побудови “жадібних” алгоритмів;

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

    • ідеї розв’язання класичних задач.

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


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

    • евристичні алгоритми та доречність їх використання;

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

    • використання “жадібних” алгоритмів на графах.

Каталог: files
files -> Інформація для вступників 2015 року до аспірантури Інституту соціології Національної Академії наук України
files -> Положення про порядок підготовки фахівців ступенів доктора філософії та доктора наук в аспірантурі (ад’юнктурі) та докторантурі вищих навчальних закладів
files -> Відділ аспірантури та докторантури Уманського державного педагогічного університету імені Павла Тичини
files -> Про вступний іспит та реферат при вступі до аспірантури Інституту соціології нан україни
files -> Київський національний університет імені Тараса Шевченка
files -> Програма вступного іспиту до аспірантури зі спеціальності 22. 00. 03 соціальні структури та соціальні відносини Затверджено
files -> Принципи реалізації наукової діяльності університету: активна участь у формуванні та
files -> Портфоліо вчителя


Поділіться з Вашими друзьями:
1   ...   8   9   10   11   12   13   14   15   ...   22


База даних захищена авторським правом ©uchika.in.ua 2019
звернутися до адміністрації

    Головна сторінка