<eng>Theory of Computability</eng> | Faculty of Technical Sciences

Subject: Theory of Computability (17.0M537)

Type of studies	Title
Master Academic Studies	Information Engineering (Year: 1, Semester: Summer)
Master Academic Studies	Mathematics in Engineering (Year: 1, Semester: Summer)
Master Academic Studies	Information and Analytics Engineering (Year: 1, Semester: Summer)

General information:

Category	Scientific-professional
Scientific or art field	Teorijska i primenjena matematika
ECTS	5

The basic objective of the course is to acquire basic knowledge in theory algorithms, including the concept of algorithm, recursive functions, Turing machine and time complexity. Students will be familiar with these fundamental concepts, but also with their application in various branches of computer science (e.g. on the development of programming languages and models of concurrency). During the course, students sill study formal methods and techniques through theory, examples and discussion. The main goal is that students develop skills to analyze preformance and behaviour of algorithms.

As an outcome of the course, the student will have basic knowledge in the theory of algorithms and their complexity. In addition, students will master skills of analyzing the complexity of algorithms, using known methods.

Notion of algorithms and computability. Recursive functions. Turing machines. Church-Turing thesis. Decidability. Time complexity.

The presentation of the theoretical part during the lectures is followed by the characteristic examples which contribute to better understanding of the subject matter. The students are expected to individually study the additional literature which they discuss with the . subject teacher at the consultation classes.

Authors	Title	Year	Publisher	Language
Sipser, M.	Introduction to the Theory of Computation	2006	Thomson Course Technology, Boston	English
Pippinger, N.	Theories of computability	1997	Cambridge University Press, Cambridge	English
Epstein, R.L., Carnielli, W.A.	Computability. Computable Functions, Logic, and the Foundations of Mathematics	1989	Wadsworth & Brooks, Pacific Grove	English

Course activity	Pre-examination	Obligations	Number of points
Test	Yes	Yes	10.00
Lecture attendance	Yes	Yes	5.00
Exercise attendance	Yes	Yes	5.00
Written part of the exam - tasks and theory	No	Yes	40.00
Theoretical part of the exam	No	Yes	30.00
Test	Yes	Yes	10.00