#
FI:IB110 Introduction to Informatics - Course Information

## IB110 Introduction to Informatics

**Faculty of Informatics**

Spring 2022

**Extent and Intensity**- 2/2/0. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).

Taught online. **Teacher(s)**- RNDr. Petr Novotný, Ph.D. (lecturer)

Mgr. Jiří Zárevúcky (seminar tutor) **Guaranteed by**- RNDr. Petr Novotný, Ph.D.

Department of Computer Science - Faculty of Informatics

Supplier department: Department of Computer Science - Faculty of Informatics **Prerequisites**- !
**IB102**Automata and Grammars && !**IB005**Formal languages and Automata

none **Course Enrolment Limitations**- The course is only offered to the students of the study fields the course is directly associated with.

**fields of study / plans the course is directly associated with**- there are 16 fields of study the course is directly associated with, display
**Course objectives**- The main objective of the course is to acquaint the students with basic abstract computational models and their use in analysis of algorithms and computational problems. At the end of the course, the students will understand fundamental concepts in the theory of finite automata, computability and complexity theory. They will be able to leverage the knowledge of these concepts for deeper understanding of concepts appearing in a practice of programming.
**Learning outcomes**- Successful course graduates will be able to:

- explain the notion of a finite automaton and construct finite automata for simple regular languages

- explain the notion of a regular expression and construct REs for simple regular languages

- explain the concept of non-determinism and use non-determinism to simplify the construction of finite automata

- use the basic algorithms for handling of finite automata (determinisation etc.)

- understand the notion of decidability and explain the existence of undecidable problems

- explain the concept of a Turing machine and construct TMs for simple problems

- understand the concept of reduction between computational problems

- understand the concept of computational complexity, the basic complexity classes and relationships between them **Syllabus**- Finite automata and regular languages. Construction of finite automata.
- Non-deterministic automata, the use of non-determinism, determinisation, minimalisation.
- Regular expressions and regular grammars. Examples of non-regular languages.
- Computational problems and algorithms. Turing machines. Decidable and undecidable problems, diagonalisation.
- Reductions between computational problems.
- Time and space complexity of algorithms and problems. Classes P and NP. NP-complete problems. Examples of complexity classes and relationships between them.

**Literature**- JANČAR, Petr.
*Teoretická informatika*. 2010. URL info - HOPCROFT, John E., Rajeev MOTWANI and Jeffrey D. ULLMAN.
*Introduction to automata theory, languages, and computation*. 3rd ed. Boston: Pearson/Addison Wesley, 2007. xvii, 535. ISBN 0321455363. info - ČERNÁ, Ivana, Mojmír KŘETÍNSKÝ and Antonín KUČERA.
*Formální jazyky a automaty I (Formal Languages and Automata I)*. Brno: Masarykova univerzita, 2006. 159 pp. Elportal. ISSN 1802-128X. URL info

*recommended literature*- HROMKOVIČ, Juraj.
*Sedem divov informatiky*. xi, 336. ISBN 9788080849580. info

*not specified*- JANČAR, Petr.
**Teaching methods**- lectures and seminars
**Assessment methods**- The overall grade will depend on the outcome of the mid-term and final exams. To sign up for an exam term, the student will have to fulfill active participation criteria (seminar participation and homework assignments).
**Language of instruction**- Czech
**Further Comments**- The course is taught annually.

The course is taught: every week. **Teacher's information**- https://is.muni.cz/auth/el/1433/podzim2021/IB110/index.qwarp

- Enrolment Statistics (Spring 2022, recent)
- Permalink: https://is.muni.cz/course/fi/spring2022/IB110