Інфопакет

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

ОК.15

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

Перший

2022/2023

4 Семестр

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; – форма проведення і види завдань: письмова форма.

Українська