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

Освітня програма: Інформатика (перший (бакалаврський) рівень вищої освіти)

Структурний підрозділ: Факультет комп'ютерних наук та кібернетики

Назва дисципліни
Теорія алгоритмів
Код дисципліни
ОК.15
Тип модуля
Обов’язкова дисципліна для ОП
Цикл вищої освіти
Перший
Рік навчання
2023/2024
Семестр / Триместр
4 Семестр
Кількість кредитів ЕСТS
5
Результати навчання
ПРН1. Застосовувати знання основних форм і законів абстрактнологічного мислення, основметодології наукового пізнання, форм і методів вилучення, аналізу, обробки та синтезу інформації в предметній області комп'ютерних наук. ПРН5. Проектувати, розробляти та аналізувати алгоритми розв’язання обчислювальних та логічних задач, оцінювати ефективність та складність алгоритмів на основі застосування формальних моделей алгоритмів та обчислюваних функцій.
Форма навчання
Дистанційне навчання
Попередні умови та додаткові вимоги
Знати: базові поняття дискретної математики (основи теорії множин, теорії відношень, теорії булевих функцій, теорії автоматів), основи математичної логіки. Вміти: встановлювати базові теоретико-множинні співвідношення, використовувати апарат пропозиційної логіки та логіки предикатів для опису предметних областей, побудови логічних виведень.
Зміст навчальної дисципліни
Мета дисципліни – засвоєння базових знань з основ теорії алгоритмів, включаючи вивчення формальних моделей алгоритмів та алгоритмічно обчислюваних функцій, питань обчислюваності, розв’язності та нерозв’язності масових проблем. Навчальна дисципліна “Теорія алгоритмів” є складовою освітньо-професійної програми підготовки фахівців за першим (бакалаврським) рівнем вищої освіти галузі знань 12 „Інформаційні технології” зі спеціальності 122 „Комп’ютерні науки”, освітньо-професійної програми „Інформатика”. Дана дисципліна є обов’язковою навчальною за програмою “Інформатика”. Викладається у 4 семестрі 2 курсу в обсязі – 150 год. (5 кредитів ECTS), зокрема: лекції – 38 год., практичні заняття – 34 год., консультації – 2 год., самостійна робота – 76 год. У курсі передбачено 3 контрольні роботи. Завершується дисципліна – іспитом в 4 семестрі.
Рекомендована та необхідна література
1. Нікітченко М.С., Шкільняк О.С., Шкільняк С.С. Теорія алгоритмів. – K., 2015. 2. Нікітченко М.С., Шкільняк С.С. Математична логіка та теорія алгоритмів. – К., 2008. 3. Шкільняк С.С. Tеорія алгоритмів. Приклади й задачі. – К., 2012. 4. Cutland N. Computability. An Introduction to Recursive Function Theory. – Cambridge University Press, 1980. 5. Лісовик Л.П., Шкільняк С.С. Теорія алгоритмів. – К., 2003. 6. Шкільняк С.С. Математична логіка. Приклади й задачі. – К., 2022. 7. Aho A., Hopcroft J., Ullman J. The Design and Analysis of Computer Algorithms. – Addison-Wesley Publishing company, 1976. 8. Gross, M. et Lentin, A. Notions sur les grammaires formelles. – Gauthier-Villars, Paris, 1967. 9. Kleene S.C. Mathematical Logic. – Dower Publications, 2013. 10. Rogers H. Theory of Recursive Functions and Effective Computability. – McGraw-Hill Book Company, 1967. 11. Shoenfield J. Mathematical Logic.– Addison-Wesley Publishing company, 1967.
Заплановані освітні заходи та методи викладання
Лекція, практичні заняття, самостійна робота.
Методи та критерії оцінювання
Семестрове оцінювання (максимальна кількість балів): 1. Контрольна робота 1: РН 1.1, РН 2.1 – 8 балів 2. Контрольна робота 2: РН 1.2, РН 2.2 – 15 балів 3. Контрольна робота 3: РН 1.3, РН 2.3 – 13 балів 4. Домашнє контрольне завдання 1: РН 1.1, РН 2.1 – 7 балів 5. Домашнє контрольне завдання 2: РН 1.2, РН 2.2 – 8 балів 4. Домашнє контрольне завдання 1: РН 1.3, РН 2.3 – 5 балів 5. Pобота студентів на заняттях: РН 3.1 – 4 бали Підсумкове оцінювання (у формі іспиту): – максимальна кількість балів які можуть бути отримані студентом: 40 балів; – результати навчання які будуть оцінюватись: PH 1.1, PH 1.2, PH 1.3, PH 2.1, PH 2.2, PH 2.3; – форма проведення і види завдань: письмова форма.
Мова викладання
Українська

Кафедри

Наступні кафедри задіяні у викладанні наведеної дисципліни

Теорії та технології програмування
Факультет комп'ютерних наук та кібернетики