Код: 316128

Назва:

Теорія обчислень

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

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

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

Семестр: 4

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

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

Викладач(і): доц., д. фіз.- мат. н. Олійник Б. В.

Результати навчання: у результаті вивчення дисципліни студент повинен:
- вміти виконувати класичні обчислення предикатів, які належать класам 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с.


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

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

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