Код: 316148

Назва:

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

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

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

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

Семестр: 5

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

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

Викладач(і): ст.в., к. фіз.- мат. н. Морозов Д.І.

Результати навчання: у результаті вивчення дисципліни студент повинен:
- знати властивості теорій першого порядку, зокрема числення предикатів;
- розбиратися в теорії алгоритмів, знати концепції Гьоделя та Тюринга і приклади алгоритмічно нерозв'язних проблем;
- вміти оцінювати складність алгоритмів, знати властивості класів алгоритмів P, NP, PSPASE, розуміти поняття NP-повної задачі і наводити приклади таких задач.


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

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

Зміст дисципліни: Формальні мови. Числення висловлювань та числення предикатів, як формальні мови. Формальні теорії, основні поняття. Числення висловлювань, як формальна теорія. Теорема дедукції. Повнота числення висловлювань. Числення предикатів, як формальна теорія. Поняття теорії першого порядку, приклади. Існування несуперечливого повного розширення несуперечливої теорії першого порядку - лема Лінденбаума. Існування зліченної моделі для довільної несуперечливої теорії першого порядку, наслідки. Теорема Гьоделя про повноту числення предикатів. Теорема компактності. Алгоритмічна мова Гьоделя. Поняття про примітивно рекурсивні, загально-рекурсивні та частково-рекурсивні функції, множини, предикати. Теза Чорча. Оператор обмеженої мінімізації та його застосування. Теорема про глибоку рекурсію. Рекурсивно-зліченні множини. Рекурсія другого ступеня. Універсальна функція для класу примітивно-рекурсивних функцій від однієї змінної, як приклад загально рекурсивної але не примітивно рекурсивної функції. Теорема про графік частково рекурсивної функції та наслідки з неї. Теорема Кліні про нормальну форму та її застосування. Існування нерекурсивних, рекурсивно-зліченних множин. Алгоритмічно нерозв'язні проблеми. Алгоритмічна мова Тюрінга. Еквівалентність концепцій Тюрінга та Гьоделя. Поняття про часову та просторову складності алгоритму. Класи алгоритмів P,NP,PSPASE. Поліноміальна звідність, NP-повнота. Теорема Кука.


Рекомендована література: 1. Мендельсон Э. Введение в математическую логику, - М., Наука, 1971
2. Тей А., Грибомон Ж. Логический подход к искусственному интеллекту, - М "Мир", 1990.
3. Мальцев А. Алгоритмы и рекурсивные функции, - М., Наука, 1986
4. Гери, Джонс. ЭВМ и труднорешаемые задачи, - М., 1982.
5. Ахо А. Хопкрофт Дж., Уильамс Дж. Построение и анализ вычислительных алгоритмов - М "Мир", 1979.
6. Глибовець М.М., Олецький О.В. Штучний інтелект, Видавничий дім "КМ Академія " 2002.


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

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

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