Introduction to Theoretical Computer Science

Learning Outcomes

  1. model the behavior of a computer system and communication protocol using formal language
  2. model the behavior of a computer system, communication protocol or other kinds of technical systems using formal language
  3. design a computing process using a formal model
  4. apply formal models to verify the corectness of a computer system
  5. categorize a problem with respect to Chomsky hierarchy of formal languages
  6. select the optimal formal model for description, design, and implementation of a computer system
  7. estimate time and space complexity of a computing process
  8. evaluate the efficiency of a computer system and communication protocol
  9. assess the problem complexity class

Forms of Teaching

Lectures

Partial e-learning

Laboratory

Week by Week Schedule

  1. String derivation and parsing, Deterministic finite automata (DFA)
  2. Minimization of DFA, Nondeterministic finite automata (NFA and NFA with eps-transitions)
  3. Equivalence of DFA, NFA, and NFA with eps-transitions
  4. Regular languages, Regular expressions, Operations on automata, Properties of regular, context-free, recursive and recursively-enumerable languages, pumping lemma
  5. Context-free languages, Properties of regular, context-free, recursive and recursively-enumerable languages, pumping lemma
  6. Context-free grammar
  7. Pushdown automata
  8. Midterm exam
  9. 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)
  10. Chomsky hierarchy of formal languages, grammars, and automata, Context-sensitive languages, context-sensitive grammar, and linear bounded automata
  11. 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
  12. 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)
  13. Review of the classes P and NP; Introduce P-space and EXP, Polynomial hierarchy, NP-completeness (Cook-Levin theorem), Classic NP-complete problems
  14. 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
  15. Final exam

Study Programmes

University undergraduate
Computing (study)
(4. semester)

Literature

(.), 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,

Associate Lecturers

General

ID 183412
  Summer semester
5 ECTS
L1 English Level
L1 e-Learning
60 Lectures
0 Exercises
0 Laboratory exercises
0 Project laboratory

Grading System

Excellent
Very Good
Good
Acceptable