|
|  |
| Introduction to Theoretical Computer Science |
| Abbreviation: | Load: 60(L)
+ 0(E)
+ 15(LE)
+ 0(CE)
|
| Lecturers in charge: | Prof. dr. sc. Siniša Srbljić
Prof. dr. sc. Dalibor Vrsalović
Prof. dr. sc. Zoran Kalafatić |
| Lecturers: | dr. sc. Ivan Benc
(
Lectures
)
dr. sc. Andro Milanović
(
Lectures
)
Prof. dr. sc. Joško Radej
(
Lectures
)
dr. sc. Daniel Skrobo
(
Lectures
)
mr. sc. Ivan Gavran
(
Laboratory exercises
)
Danko Ivošević dipl.ing.
(
Laboratory exercises
)
mr. sc. Miroslav Popović
(
Laboratory exercises
)
mr. sc. Dejan Škvorc
(
Laboratory exercises
)
Ivan Žužak dipl.ing.
(
Laboratory exercises
)
|
| Course description: The course introduces the formal models of finite automata and formal grammars used for description, definition, software and hardware implementation, as well as verification of correctness of execution of different computer and communication processes, protocols, and systems. The basic properties of computing processes and systems, such as determinism, decidability, computability, complexity, and tractability, are explained. The basics of automata theory, formal grammars and languages are given. Chomsky hierarchy of languages is presented: regular languages, context-free languages, context-sensitive languages, recursive languages, and recursively-enumerable languages. Complexity classes and hierarchy of complexity classes are defined: complete and hard problems, polynomial classes P and NP, and reduction method. |
| Compulsory literature: |
| 1. | JEZIČNI PROCESORI 1: Uvod u teoriju formalnih jezika, automata i gramatika S. Srbljić Element,Zagreb 2003 |
| Recommended literature: |
| 2. | Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Ran J. Hromkovic Springer-Verlag 2004 |
| 3. | Introduction to Automata Theory, Languages, and Computation J.E. Hopcroft, R. Motwani, J.D. Ullman Addison-Wesley Publishing, Company 2000 |
| 4. | An Introduction to Formal Languages and Automata P. Linz Jones & Bartlett Publishers 2000 |
| 5. | Automata and Computability D.C. Kozen Springer-Verlag New York 1997 |
| |
