Infopaket

Theory of Computation

ОК.15

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

First

2022/2023

4 Semester

5

LO 1. Apply the knowledge about basic forms and laws of abstract logical thinking, foundations of scientific cognition methodology, forms and methods of extracting, analyzing, processing and synthesizing information in computer science. LO 5. Design, develop and analyze algorithms for solving computational and logical problems. Evaluate algorithms efficiency and complexity on the basis of formal models of algorithms and computable functions.

Distance form

Know: basic concepts of discrete mathematics (basics of set theory, relations theory, Boolean function theory, theory of automata), basics of mathematical logic. Be able to: establish basic set-theoretic relations, use the apparatus of propositional logic and predicate logic to describe subject areas, and construct logical deductions.

The goal of the discipline is to acquire basic knowledge in the fundamentals of algorithm theory, including the study of formal models of algorithms and algorithmically computable functions, issues of computability, solvability, and the undecidability of mass problems. The educational discipline "Theory of Computation" is a component of the educational professional program "Informatics" of the first (bachelor) level of higher education in the field of knowledge 12 "Information Technologies" from the specialty 122 "Computer Science". This discipline is a compulsory course in the "Informatics" program. It is taught in the 4rd semester of the 2nd course in the amount of 150 hours (5 ECTS credits), in particular: lectures – 38 hours, practical classes – 34 hours, consultations – 2 hours, independent work – 76 hours. The course includes 3 Midterm Exams. The discipline ends with an exam in the 4rd semester.

1. Nikitchenko M.S., Shkilniak O.S., Shkilniak S.S. Teoriia alhorytmiv. – K., 2015. 2. Nikitchenko M.S., Shkilniak S.S. Matematychna lohika ta teoriia alhorytmiv. – К., 2008. 3. Shkilniak S.S. Teoriia alhorytmiv: pryklady i zadachi. – К., 2012. 4. Cutland N. Computability. An Introduction to Recursive Function Theory. – Cambridge University Press, 1980. 5. Lisovyk L.P., Shkilniak S.S. Teoriia alhorytmiv. – К., 2003. 6. Shkilniak S.S. Matematychna lohika: pryklady i zadachi. – К., 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.

Lectures, practical classes, independent work.

Semester Assessment (by levels): 1. Midterm Exam 1: LO 1.1, LO 2.1 – 8 points 2. Midterm Exam 2: LO 1.2, LO 2.2 – 15 points 3. Midterm Exam 3: LO 1.3, LO 2.3 – 13 points 4. Homework Assignments 1: LO 1.1, LO 2.1 – 7 points 5. Homework Assignments 2: LO 1.2, LO 2.2 – 8 points 6. Homework Assignments 3: LO 1.3, LO 2.3 – 5 points 7. Students' work in classes (current evaluation): LO 3.1 – 4 points. Final Assessment (in the form of an exam): – maximum number of points that can be obtained by the student: 40 points; – earning outcomes to be evaluated: LO 1.1, LO 1.2, LO 1.3, LO 2.1, LO 2.2, LO 2.3; – form of examination and types of tasks: written exam.

Ukrainian