Код: 365449

Назва:

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

Анотація: Курс присвячено вивченню класичних алгоритмів на графах: пошук в глибину, пошук в ширину, алгоритм Дейкстри, пошук найкоротшої відстані, метод релаксації, пошук мінімального остовного дерева, алгоритм розбиття орієнтовного графа на сильнозв'язні компоненти, алгоритм Беллмана-Форда. Обговорюються плюси та мінуси кожного з алгоритмів, їх коректність, обговорюється сфера застосування і їх складність.

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

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

Семестр: 3 (осінній)

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

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

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

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

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

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

Зміст дисципліни: Пошук в глибину. Пошук в ширину. Алгоритм Дейкстри. Пошук найкоротшої відстані. Метод релаксації. Пошук мінімального остовного дерева. Алгоритм розбиття орієнтовного графа на сильнозв'язні компоненти. Алгоритм Беллмана-Форда.


Рекомендована література:
1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. 4th ed. MIT Press, 2022. — 1312 p.
2. Sedgewick R., Wayne K. Algorithms. 4th ed. Addison-Wesley, 2011. — 955 p.
3. Diestel R. Graph Theory. 5th ed. Springer, 2017. — 429 p.
4. Bondy J. A., Murty U. S. R. Graph Theory. Springer, 2008. — 651 p.
5. Skiena S. S. The Algorithm Design Manual. 3rd ed. Springer, 2020. — 793 p.
6. Vazirani V. V. Approximation Algorithms. Springer, 2001
7. Spielman D. A. Spectral and Algebraic Graph Theory. 2025. Доступ онлайн http://cs-www.cs.yale.edu/homes/spielman/sagt/sagt.pdf
8. Williamson D. P., Shmoys D. B. The Design of Approximation Algorithms. Cambridge University Press, 2011. https://www.designofapproxalgs.com/book.pdf



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

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

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