Introduction to Theoretical Computer Science

Data is displayed for academic year: 2023./2024.

Lecturers

Assoc. Prof.
Marin Šilić
Assoc. Prof.
Goran Delač
Prof.
Dejan Škvorc
Assoc. Prof.
Klemo Vladimir
Assoc. Prof.
Zoran Kalafatić
Asst. Prof.
Ante Đerek

Associate Lecturers

Asst. Prof.
Adrian Satja Kurdija

Laboratory exercises

Petar Paradžik
mag. inf. et math.
Stjepan Požgaj
mag. inf. et math.

Course Description

The course introduces formal models of automata and grammars used for description, definition, software and hardware implementation, as well as verification of the correctness of the execution of computer and communication processes, protocols, and systems. Basic properties of computing processes and systems, such as determinism, decidability, computability, complexity, and tractability, are explained. 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.

Study Programmes

University undergraduate
[FER3-EN] Computing - study
(4. semester)

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

Lecturer-driven classroom presentations of theoretical concepts with examples and problem solving

Laboratory

Software implementation of finite automata, finite automata minimization algorithms, pushdow automata, and recursive descent parsing. Students individually implement given assignment in a recommended programming language or tool, and submit their solutions to automatic online evaluation.

Grading Method

Continuous Assessment Exam
Type Threshold Percent of Grade Threshold Percent of Grade
Laboratory Exercises 50 % 30 % 50 % 0 %
Mid Term Exam: Written 50 % 35 % 0 %
Final Exam: Written 50 % 35 %
Exam: Written 50 % 100 %
Exam: Oral 100 %

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

Literature

Siniša Srbljić (2010.), Uvod u teoriju računarstva, Element
Juraj Hromkovič (2003.), Theoretical Computer Science, Springer Science & Business Media
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2007.), Introduction to Automata Theory, Languages, and Computation, Addison-Wesley
Peter Linz (2001.), An Introduction to Formal Languages and Automata, Jones & Bartlett Learning
Dexter C. Kozen (2007.), Automata and Computability, Springer Science & Business Media

For students

General

ID 209657
  Summer semester
5 ECTS
L3 English Level
L2 e-Learning
60 Lectures
0 Seminar
0 Exercises
10 Laboratory exercises
0 Project laboratory

Grading System

88 Excellent
75 Very Good
63 Good
50 Sufficient

Similar Courses