Introduction to Theoretical Computer Science
- model the behavior of a computer system and communication protocol using formal language
- model the behavior of a computer system, communication protocol or other kinds of technical systems using formal language
- design a computing process using a formal model
- apply formal models to verify the corectness of a computer system
- categorize a problem with respect to Chomsky hierarchy of formal languages
- select the optimal formal model for description, design, and implementation of a computer system
- estimate time and space complexity of a computing process
- evaluate the efficiency of a computer system and communication protocol
- assess the problem complexity class
Forms of Teaching
Week by Week Schedule
- String derivation and parsing; Deterministic finite automata (DFA).
- Minimization of DFA; Nondeterministic finite automata (NFA and NFA with eps-transitions).
- Equivalence of DFA, NFA, and NFA with eps-transitions.
- Regular languages; Regular expressions; Operations on automata; Properties of regular, context-free, recursive and recursively-enumerable languages, pumping lemma.
- Context-free languages; Properties of regular, context-free, recursive and recursively-enumerable languages, pumping lemma.
- Context-free grammar.
- Pushdown automata.
- Midterm exam.
- Recursively-enumerable languages; Turing machine; Unrestricted grammar; Properties of regular, context-free, recursive and recursively-enumerable languages, pumping lemma; Pumping lemma (proving languages non-regular and non-context-free).
- Chomsky hierarchy of formal languages, grammars, and automata; Context-sensitive languages, context-sensitive grammar, and linear bounded automata.
- Definitions of space and time complexity; The halting problem; (Non)deterministic computation; Tractability; Computability with examples of uncomputable functions; Decidability with examples of undecidable functions.
- Introduction to P and NP classes, NP-complete and NP-hard problems; Introduction to the NP-complete class and exemplary NP-complete problems (e.g., SAT, Knapsack).
- Review of the classes P and NP; Introduce P-space and EXP; Polynomial hierarchy; NP-completeness (Cook-Levin theorem); Classic NP-complete problems.
- Reduction Techniques; Complexity classes; Polynomial complexity classes (P and NP classes); Definition of complete and hard problems; P-complete (hard) and NP-complete (hard) problems.
- Final exam.
Computing (study)(4. semester)
(.), Uvod u teoriju računarstva; S. Srbljić; Element Zagreb; 2007; ISBN: 978-953-197-624-4,
(.), Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography; J. Hromkovic; Springer; 2003; ISBN: 978-3540140153,
(.), Introduction to Automata Theory, Languages, and Computation; J. E. Hopcroft, R. Motwani, J. D. Ullman; Addison-Wesley; 2000; ISBN: 978-0201441246,
(.), An Introduction to Formal Languages and Automata; P. Linz; Jones & Bartlett Publishers; 2000; ISBN: 978-0763714222,
(.), Automata and Computability; D. C. Kozen; Springer; 1997; ISBN: 978-0387949079,
L1 English Level
10 Laboratory exercises
0 Project laboratory