Інфопакет

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

ДВС.3.06

Вибіркова дисципліна для ОП

Перший

2023/2024

8 Семестр

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. https://do.csc.knu.ua/marynych/wp-content/uploads/sites/2/2023/11/PAA-EN.pdf

Лекції – 56 год., консультації – 4 год., самостійна робота – 120 год. У курсі передбачено 4 змістовні модулі та 2 модульні контрольні роботи. Завершується дисципліна – іспитом в 8 семестрі.

Семестрове оцінювання: Максимальна кількість балів, які можуть бути отримані студентом: 60 балів: • Контрольна робота №1: 30/18 балів. • Контрольна робота № 2: 30/18 балів. Підсумкове оцінювання (у формі екзамену): Максимальна кількість балів, які можуть бути отримані студентом: 40 балів. Форма проведення: письмова. Види завдань: 4 письмових завдань (2 теоретичних питання та 2 практичних завдання).

Українська