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
10 Laboratory exercises
0 Project laboratory

Grading System

Excellent
Very Good
Good
Acceptable