IB110 Introduction to Informatics

Faculty of Informatics
Spring 2021
Extent and Intensity
2/2/0. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Petr Novotný, Ph.D. (lecturer)
Mgr. Jiří Zárevúcky (seminar tutor)
Bc. Ondřej Darmovzal (assistant)
Mgr. Ondřej Svoboda (assistant)
Mgr. Anh Minh Tran (assistant)
Guaranteed by
doc. RNDr. Petr Novotný, Ph.D.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics
Timetable
Thu 10:00–11:50 Virtuální místnost
  • Timetable of Seminar Groups:
IB110/01: Tue 10:00–11:50 Virtuální místnost, P. Novotný
IB110/02: Wed 12:00–13:50 Virtuální místnost, P. Novotný
IB110/03: Mon 16:00–17:50 Virtuální místnost, P. Novotný
IB110/04: Wed 18:00–19:50 Virtuální místnost, J. Zárevúcky
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
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
    recommended 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
    not specified
  • HROMKOVIČ, Juraj. Sedem divov informatiky. Ružomberok: Verbum, 2012, xi, 336. ISBN 9788080849580. info
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
Study Materials
The course is taught annually.
Teacher's information
https://is.muni.cz/auth/el/1433/podzim2021/IB110/index.qwarp
The course is also listed under the following terms Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2014, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Spring 2020, Spring 2022, Spring 2023, Spring 2024, Spring 2025.
  • Enrolment Statistics (Spring 2021, recent)
  • Permalink: https://is.muni.cz/course/fi/spring2021/IB110