Introduction to Theoretical Computer Science
Data is displayed for academic year: 2023./2024.
Associate Lecturers
Laboratory exercises
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
- 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
Lectures
Lecturer-driven classroom presentations of theoretical concepts with examples and problem solving
LaboratorySoftware 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
- 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
Literature
Siniša Srbljić (2010.), Uvod u teoriju računarstva, Element
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