# Computing

## Introduction to Theoretical Computer Science

- Class 60
- Practice 0
- Independent work 90

### Course title

Introduction to Theoretical Computer Science

### Lecture type

Obligatory

### Course code

183412

### Semester

4

### ECTS

5

### Lecturers and associates

- Associate Professor PhD Goran Delač
- Assistant Professor PhD Ante Đerek
- Associate Professor PhD Zoran Kalafatić
- Full Professor PhD Siniša Srbljić
- Associate Professor PhD Dejan Škvorc
- Assistant Professor PhD Klemo Vladimir

### Course objectives

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.

### Prerequisites for:

- Software Design
- Software Design Project
- Programming Language Translation

### Required reading

(.), 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 and Bartlett Publishers; 2000; ISBN: 978-0763714222,

(.), Automata and Computability; D. C. Kozen; Springer; 1997; ISBN: 978-0387949079,

#### Online education during epidemiological measures

- Study program duration
- 6 semesters (3 years)
- Semester duration
- 15 weeks of active teaching + 5 examination weeks
- Total number of ECTS points
- 180
- Title
- Bacc.ing.comp (Bachelor of Science in Computing)

**Academic calendar**

#### Minimal 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