Код: 315451

Назва:

Теорія складності обчислень

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

Тип дисципліни: вибіркова (професійно-орієнтована)

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

Семестр: 6

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

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

Викладач(і): проф., д.н. Олійник Б. В.

Результати навчання: У результаті вивчення дисципліни студент повинен:
- вміти виконувати класичні обчислення предикатів, які належать класам P, NP, ?k, Pk, PSPASE;
- розбиратися в квантових схем обчислень;
- розуміти поняття повної задачі для даного класу узагальненнях.


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

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

Зміст дисципліни: Машина Тюринга як модель механічних обчислень. Часова та просторова складності алгоритмів, символіка О(f(n)). Булева схема, схемна складність, клас P / poly. Співвідношення між класами P та . P / poly. Клас NP: звідність та повнота. Теорема Кука. Ймовірносні алгоритми, клас BPP та схемна складність. Класи складностей ,?k,Pk як підкласи PSPACE. Квантові схеми обчислень. Поняття оборотної класичної схеми. Точна реалізація, поняття повного базису. Означення квантового обчислення, приклади.


Рекомендована література: 1. Китаев А., Шень А., Вялый А. Классические и квантовые вычисления - М. МЦИМО ЧеРо, 1999.
2. Koblitz N. Algebraic aspects of cryptography. Algorithms Comput. Math., vol. 3, Springer-Verlag, Berlin, 1999.
3. Глибовець М.М. Основи комп'ютерних алгоритмів. - К.: Вид. дім. "КМ Академія", 2003. - 450с.


Форми та методи навчання: лекції, практичні заняття, індивідуальні завдання

Методи й критерії оцінювання: оцінювання здійснюється за 100-бальною рейтинговою системою: - поточний контроль на семінарських та практичних заняттях (30 %); - проміжний контроль (40 %); - підсумковий контроль (30 % ).

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