Код: 316204

Назва:

Алгоритми на графах

Анотація: Курс містить основні алгоритми на графах та деревах, оцінки складності алгоритмів, зокрема: коренева ідея, графи та їх представлення. Пошук в глибину, пошук в ширину. Алгоритми пошуку найкоротшого шляху в графі. Бінарні дерева пошуку, збалансовані бінарні дерева пошуку. Splay-дерева, амортизаційний аналіз. Перзистентні бінарні дерева пошук. Дерева швидких запитів на відрізках (RMQ, LCA). Задача про максимальний потік, мінімальний переріз. Суфіксне дерево.

Тип дисципліни: вибіркова

Рік навчання: 4

Семестр: 8 (весняний)

Кількість кредитів: 4

Форма контролю: залік

Викладач(і): доц., к.ф-м.н. Крюкова Г.В.

Результати навчання: Демонструвати знання й розуміння основних концепцій, принципів, теорій прикладної математики і використовувати їх на практиці. Формалізувати задачі, сформульовані мовою певної предметної галузі; формулювати їх математичну постановку та обирати раціональний метод вирішення; розв'язувати отримані задачі аналітичними та чисельними методами, оцінювати точність та достовірність отриманих результатів. Виконувати математичний опис, аналіз та синтез дискретних об'єктів та систем, використовуючи поняття й методи дискретної математики та теорії алгоритмів. Уміти розробляти та використовувати на практиці алгоритми, пов'язані з апроксимацією функціональних залежностей, чисельним диференціюванням та інтегруванням, розв'язанням систем алгебраїчних, диференціальних та інтегральних рівнянь, розв'язанням крайових задач, пошуком оптимальних рішень. Поєднувати методи математичного та комп'ютерного моделювання з неформальними процедурами експертного аналізу для пошуку оптимальних рішень. Будувати ефективні щодо точності обчислень, стійкості, швидкодії та витрат системних ресурсів алгоритми для чисельного дослідження математичних моделей та розв'язання практичних задач.
Володіти методиками вибору раціональних методів та алгоритмів розв'язання математичних задач оптимізації, дослідження операцій, оптимального керування і прийняття рішень, аналізу даних. Вміти застосовувати сучасні технології програмування та розроблення програмного забезпечення, програмної реалізації чисельних і символьних алгоритмів.
Розв'язувати окремі інженерні задачі та/або задачі, що виникають принаймні в одній предметній галузі: в соціології, економіці, екології та медицині. Використовувати в практичній роботі спеціалізовані програмні продукти та програмні системи комп'ютерної математики. Виявляти здатність до самонавчання та продовження професійного розвитку. Уміти організувати власну діяльність та одержувати результат у рамках обмеженого часу. Демонструвати навички взаємодії з іншими людьми, уміння працювати в команді. Уміти здійснювати збір, опрацювання, аналіз, систематизацію науковотехнічної інформації, уникаючи при цьому академічної недоброчесності. Ефективно спілкуватися з питань інформації, ідей, проблем та рішень зі спеціалістами та суспільством загалом. Збирати та інтерпретувати відповідні дані й аналізувати складності в межах своєї спеціалізації для донесення суджень, які відбивають відповідні соціальні та етичні проблеми. Демонструвати навички професійного спілкування, включаючи усну та письмову комунікацію українською мовою та принаймні однією з офіційних мов ЄС. Знати основні поняття, засоби і методи математичної логіки, їх застосування в інформатиці й програмуванні. Обгрунтовувати власний погляд на задачу та спосіб її розв'язання, спілкуватися з колегами з питань застосування апарату математичної логіки.

Спосіб навчання: дистанційний

Необхідні обовязкові попередні й супутні модулі: лінійна алгебра

Зміст дисципліни: Основні поняття, алгоритми на графах та деревах, оцінки складності алгоритмів, зокрема: коренева ідея, графи та їх представлення. Пошук в глибину, пошук в ширину. Алгоритми пошуку найкоротшого шляху в графі. Бінарні дерева пошуку, збалансовані бінарні дерева пошуку. Splay-дерева, амортизаційний аналіз. Перзистентні бінарні дерева пошуку. Дерева швидких запитів на відрізках (RMQ, LCA). Задача про максимальний потік, мінімальний переріз. Суфіксне дерево.


Рекомендована література: 1. Крістофідес Н. Теорія графів. Алгоритмічний підхід. М.: Мир, 1978. 429.
2. Кормен Т.Х. та ін. Частина IV. Алгоритми для роботи з графами // Алгоритми: побудова й аналіз = Introduction to Algorithms - 2-е изд. - М.: Вільямс, 2006. - с.1296. - ISBN 0-07-013151-1.
3. Свамі М., Тхулаліраман К. Графи, мережі та алгоритми. М.: Світ, 1984. 455 с.

Форми та методи навчання: лекції, практичні заняття, виконання індивідуальних завдань, обговорення методів і прикладів, побудова математичних конструкцій, опрацювання літератури, розв'язування задач.

Методи й критерії оцінювання: рейтингова система оцінювання за 100-бальною шкалою: - за роботу в семестрі (контрольні роботи, індивідуальні завдання ) - 60%; - залік - 40%.

Мова навчання: українська