Інфопакет

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

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

Перший

2021/2022

4 Семестр

5

РН1.1 Знати основні формальні моделі алгоритмів та обчислюваних функцій, їх властивості, тезу Чорча, знати кодування та нумерації, універсальні функції та програми. РН1.2 Знати властивості рекурсивних та рекурсивно перелічних множин, рекурсивних та частковорекурсивних предикатів, мати уявлення про розв’язність і нерозв’язність масових проблем, звідності масових проблем. РН1.3 Знати арифметичну ієрархію, ефективні операції на функціях та множинах, теореми про нерухому точку, мати уявлення про складність обчислень.

Очна форма

Знати: базові поняття дискретної математики (основи теорії множин, теорії відношень, теорії булевих функцій, теорії автоматів), основи математичної логіки. Вміти: встановлювати базові теоретико-множинні співвідношення, використовувати апарат пропозиційної логіки та логіки предикатів для опису предметних областей, побудови логічних виведень.

Мета дисципліни – засвоєння базових знань з основ теорії алгоритмів, включаючи вивчення формальних моделей алгоритмів та алгоритмічно обчислюваних функцій, питань обчислюваності, розв’язності та нерозв’язності масових проблем. В результаті вивчення навчальної дисципліни студент повинен: знати основні поняття, засоби і методи теорії алгоритмів та їх застосування; основні формальні моделі алгоритмів та обчислюваних функцій; властивості рекурсивних та рекурсивно перелічних множин, рекурсивних та частково-рекурсивних предикатів, арифметичних множин та предикатів; мати сучасні уявлення про розв’язність, часткову розв’язність та нерозв’язність масових проблем, звідності масових проблем, складність обчислень, про ефективні операції на функціях та множинах, вміти будувати формальні моделі алгоритмів та обчислюваних функцій, використовувати тезу Чорча; встановлювати клас множини та предиката, їх місце в арифметичній ієрархії; використовувати теореми про нерухому точку.

1. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М., 1983. 2. Мальцев А.И. Алгоритмы и рекурсивные функции. – М., 1965. 3. Нікітченко М.С., Шкільняк О.С., Шкільняк С.С. Теорія алгоритмів. – K., 2015. 4. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів. – К., 2008. 5. Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М., 1972. 6. Шкільняк С.С. Математична логіка. Приклади і задачі. – К., 2007. 7. Шкільняк С.С. Tеорія алгоритмів. Приклади й задачі. – К., 2012.

Лекція, практичні заняття, самостійна робота, домашнє контрольне завдання, контрольна робота, іспит.

- семестрове оцінювання (максимальна кількість балів): 1. Контрольна робота 1: РН 1.1, РН 2.1 – 15 балів / 9 балів 2. Контрольна робота 2: РН 1.2, РН 2.2 – 13 балів / 7 балів 3. Контрольна робота 3: РН 1.3, РН 2.3 – 12 балів / 7 балів 4. Домашнє контрольне завдання 1: РН 1.1, РН 2.1 – 5 балів/ 3 бали 5. Домашнє контрольне завдання 2: РН 1.2, РН 2.2 – 6 балів/ 3 бали 4. Домашнє контрольне завдання 1: РН 1.3, РН 2.3 – 5 балів/ 3 бали 5. Pобота студентів на заняттях: РН 3.1 – 4 бали / 2 бали – підсумкове оцінювання (у формі іспиту): – максимальна кількість балів які можуть бути отримані студентом: 40 балів; – результати навчання які будуть оцінюватись: PH 1.1 – PH 1.3, PH 2.1 – PH 2.3 – форма проведення і види завдань: письмова форма

Українська