Ймовірнісний аналіз алгоритмів

Освітня програма: Прикладна Математика

Структурний підрозділ: Факультет комп'ютерних наук та кібернетики

Назва дисципліни
Ймовірнісний аналіз алгоритмів
Код дисципліни
Тип модуля
Вибіркова дисципліна для ОП
Цикл вищої освіти
Перший
Рік навчання
2021/2022
Семестр / Триместр
8 Семестр
Кількість кредитів ЕСТS
6
Результати навчання
РН04. Виконувати математичний опис, аналіз та синтез дискретних об’єктів та систем, використовуючи поняття й методи дискретної математики та теорії алгоритмів. РН15. Уміти організувати власну діяльність та одержувати результат у рамках обмеженого часу. ПРН25.3. Вміти проводити реалізацію відповідних автоматизованих систем, експлуатувати їх, виконуючи потрібні розрахунки.
Форма навчання
Попередні умови та додаткові вимоги
Для успішного опанування курсу «Ймовірнісний аналіз алгоритмів» студент має вільно володіти матеріалом нормативних курсів «Програмування», «Теорія функцій комплексної змінної» та «Теорія ймовірностей». Зокрема, з курсу «Програмування» студент має знати базові алгоритми сортування, пошуку, основні алгоритми на деревах, а також мати елементарні навички оцінки складності алгоритмів. З курсу «Теорія функцій комплексної змінної» студент має володіти поняттями аналітичної функції, особливої точки; вміти застосовувати теорему Коші та формулу Коші для аналітичних функцій, знаходити розклади функцій в ряди Лорана та Тейлора, знаходити лишки. З нормативного курсу «Теорія ймовірностей» студент має знати поняття ланцюга Маркова, різні типи збіжностей випадкових величин, поняття характеристичної функції, вміти обчислювати розподіли та моменти випадкових величин.
Зміст навчальної дисципліни
Класичний аналіз алгоритмів фокусується головним чином на дослідженні середньої або граничної швидкої комп'ютерних алгоритмів. Ймовірнісний аналіз алгоритмів є сучасною дисципліною, що лежить на границі теорії ймовірностей та комп'ютерних наук, та використовується для вивчення більш делікатних характеристик алгоритмів. Під час курсу студент познайомиться з математичним апаратом цієї області, а також з численними застосуваннями, зокрема, з ймовірнісним аналізом алгоритмів сортування, алгоритмів пошуку, алгоритмів на графах, алгоритмів компресії та загальних алгоритмів типу «поділяй-та-володарюй».
Рекомендована та необхідна література
1. Flajolet P., Sedgewick R. (2008). Analytic combinatorics, Cambridge University Press, 689 p. 2. Greene D. H., Knuth D.E. (1990). Mathematics for the analysis of algorithms, Birkhauser, 120 p. 3. Marynych A. (2010). On the asymptotics of moments of linear random recurrences. Theory Stoch. Proc. 16(32), pp. 106–119. 4. Грэкхем Р., Кнут Д., Паташник, О. (1998). Конкретная математика. Основание инфор-матики. М.:Мир, 703 с. 5. Уиттекер Э., Ватсон Дж. (1963). Курс современного анализа, М.:Физ.-мат. лит, 844 с. 6. Abramowitz M., Stegun, I. (1964). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover, New York, 812 p. 7. Aczel J. (1966). Lectures on functional equations and their applications. Academic Press: New York, San Francisco, London, p. 530. 8. Marynych A. (2020). Probabilistic Analysis of Algorithms. http://do.unicyb.kiev.ua/marynych/wp-content/uploads/2021/04/PAA-EN.pdf
Заплановані освітні заходи та методи викладання
Лекції – 56 год., консультації – 4 год., самостійна робота – 120 год. У курсі передбачено 4 змістовні модулі та 2 модульні контрольні роботи. Завершується дисципліна – іспитом в 8 семестрі.
Методи та критерії оцінювання
Семестрове оцінювання: Максимальна кількість балів, які можуть бути отримані студентом: 60 балів: • Контрольна робота №1: 30/18 балів. • Контрольна робота № 2: 30/18 балів. Підсумкове оцінювання (у формі екзамену): Максимальна кількість балів, які можуть бути отримані студентом: 40 балів. Форма проведення: письмова. Види завдань: 4 письмових завдань (2 теоретичних питання та 2 практичних завдання).
Мова викладання
Українська

Кафедри

Наступні кафедри задіяні у викладанні наведеної дисципліни

Дослідження операцій
Факультет комп'ютерних наук та кібернетики