Новини

Тематичний план для підготовки до олімпіади інформатики
2016-02-01 21:46:02

1. Поняття складності алгоритму. Визначення складності. Класи задач P і NP. NP-повні задачі.
2. Алгоритми пошуку і сортування. Пошук елемента в невпорядкованих масивах. Двійковий пошук по ключу у впорядкованому масиві (дихотомія). Пошук методом Фібоначчі. Пошук у впорядкованому n-вимірному масиві. Пошук k-го за величиною елемента масиву. Прості методи сортування ("бульбашка", "вибірка", "вставка", "підрахунок"). Швидкі методи ("швидка", "злиттям", "пірамідальна"), балансування двійкових дерев. Сортування методом черпака.
3. Розв’язування задач методом перебору варіантів. Застосування рекурсії для перебору. Генерація сполучень, розміщень, перестановок і булеан множини. Повний перебір. Відсікання варіантів (евристики). Метод гілок і меж.
4. Обчислювальна геометрія та чисельні методи. Довжина відрізка. Рівняння прямої. Скалярний і векторний добуток. Точка перетину відрізків. Належність точки фігурі на площині. Площа опуклого багатокутника. Опукла оболонка множини точок: алгоритми Грехема, Джарвіса, "розділяй і володарюй". Найближча пара точок. Метод Гауса для розв’язування системи лінійних рівнянь. Знаходження коренів рівняння.
5. Принцип динамічного програмування. Поняття, застосовність. Порівняння з перебором.
6. Жадібні алгоритми. Поняття, застосовність. Порівняння з перебором і динамічним програмуванням.
7. Теорія графів. Алгоритми на графах. Поняття графа. Визначення теорії графів. Структури даних для представлення графа у програмі. Алгоритми обходу графа (пошуки в ширину і глибину). Лабіринт (метод хвилі). Ейлером цикл. Найкоротший шлях у зваженому графі (алгоритми Дейкстри і Мінті). Транзитивне замикання графа (алгоритм Флойда-Уоршила). Мінімальне кістякове дерево (алгоритми Прима і Краскала). Топологічне сортування графа. Потоки в мережах (алгоритм Форда-Фалкерсона). Паросполучення в дводольному графі (метод подовжуючого ланцюжка, потоковий розв’язок). Задача про призначення, призначення на вузьке місце (угорський алгоритм). Ігри на графах. Розмальовка графа. Укладення графа на площині. Сильна зв'язність і двохзв’язний граф. Ізоморфізм графів. K-кліка. Гамільтонів цикл.
8. Лексичний і синтаксичний аналіз. Задача "Калькулятор". Синтаксичні діаграми. Форми Бекуса-Наура. Стекова і рекурсивна модель синтаксичного розбору. Кінцеві автомати. Граматики.


назад у розділ "Новини"