Courses – Fakultet tehničkih nauka u Novom Sadu

Subject: Theory of Computability (17.0M537)

Native organizations units: No data

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

General information:

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

Educational goal:

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.

Educational outcome:

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.

Course content:

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

Teaching methods:

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.

Literature:

Authors	Title	Year	Publisher	Language
Janičić, P.	Matematička logika u računarstvu	2009	Matematički fakultet, Beograd	Serbian language
R.Tošić, S.Crvenković	Zbirka zadataka iz teorije algoritama	1980	Institut za matematiku, Novi Sad	Serbian language
Sipser, M.	Introduction to the Theory of Computation	2006	Thomson Course Technology, Boston	English
Epstein, R.L., Carnielli, W.A.	Computability. Computable Functions, Logic, and the Foundations of Mathematics	1989	Wadsworth & Brooks, Pacific Grove	English
Pippinger, N.	Theories of computability	1997	Cambridge University Press, Cambridge	English
Igor Dolinka	Kratak uvod u analizu algoritama	2008	Futura, Novi Sad	Serbian language

Knowledge evaluation:

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