Код: 318382

Назва:

Теорія складності алгоритмів

Анотація: "Теорія складності алгоритмів" є важливим курсом при підготовці фахівців з прикладної математики та комп'ютерних наук. Метою даного курсу є ознайомлення та оволодіння сучасними методами теорії складності, застосування теорії алгоритмів у різних задачах математики та комп'ютерних наук.

Тип дисципліни: нормативна

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

Семестр: 1

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

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

Викладач(і): доц. Морозов Д.І.

Результати навчання: у результаті вивчення курсу студенти повинні знати і володіти сучасними методами теорії складності; уміти застосовувати теорію алгоритмів у різних задачах математики та комп'ютерних наук.

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

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

Зміст дисципліни: Інтуїтивне означення алгоритму. Різні підходи до формалізації поняття алгоритму. Машини Тьюрінга. Функції, обчислювальні за Тьюрінгом. Теза Тьюрінга. Загально рекурсивні функції. Теза Чорча. Еквівалентність класу загально рекурсивних функцій і функцій, обчислювальних за Тьюрінгом. Зображення даних. Стрінги. Типи обчислювальних задач, задачі пошуку та існування розв'язку. Асимптотичні оцінки і зв'язки між ними. Часова та просторова складність алгоритму. Приклади обчислення. Класи задач пошуку: PF i PC. Класи задач існування розв'язку: P i NP. Їх приклади. Співвідношення між класами. Оракульний алгорим. Порівняння задач. Зведення класу PC до класу NP. Існування NP-повних і NP-важких задач. Їх приклаи. Задачі SATISFLABILITY, 3SAT, CLIQUE, HC, PARTITION, SAT.


Рекомендована література: 1. Т. Кортмен., Ч. Лейзерсон, Р. Ривест. Алгоритмы, построение и анализ. - М.: МЦНО - 2001.
2. O. Golderich P, NP, and NP- Completeness: The Basics of ComplexityTheory. Cambridge University Press, 2010.
3. M.R. Garey, D.S.Johnsn Computers and Intractability: A Guide to the Theory of NP- Completeness. New York: W.H. Freeman and Company, 1979.
4. Ахо А. Хопкрофт Дж., Уильамс Дж. Построение и анализ вычислительных алгоритмов. М.: Мир 1979.
5. А.И. Мальцев. Алгоритмы и Рекурсивные Функции. М.: Наука, 1986.
6. Глибовець М.М., Олецький О.В. Штучний інтелект. Видавничий дім "КМ Академія", 2002.
7. С.Л. Кривий. Вступ до методів програмних продуктів. Видавничий дім "КМ Академія", 2018.
8. Golderich O.: Introduction to Complexity Theory - notes for a one-semester course. Weizmann Institute of Science, Spring (2002)
9. Golderich O.(2006) On Teaching the Basics of Complexity Theory. In: Golderich O., Rosenberg A.L, Selman A.L. (eds) Theoretical Computer Science. Lecture Notes in Computer Sciense, vol 3895. Springer, Berlin, Heidelberg. https://doi.org/10/1007/11685654_15

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

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

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