Код: 318363

Назва:

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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