IB110 Introduction to Informatics

Faculty of Informatics
Spring 2025
Extent and Intensity
2/2/0. 3 credit(s) (plus extra credits for completion). Type of Completion: zk (examination).
In-person direct teaching
Teacher(s)
doc. RNDr. Petr Novotný, Ph.D. (lecturer)
Mgr. Jakub Balabán (seminar tutor)
RNDr. Mgr. Jana Dražanová, Ph.D. (seminar tutor)
Bc. Tereza Kinská (seminar tutor)
Vojtěch Skyba (seminar tutor)
Bc. Adéla Štěpková (seminar tutor)
Bc. Dávid Šutor (seminar tutor)
Bc. Matěj Pavlík (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
Prerequisites
! IB005 Formal languages and Automata || ! IB107 Computability and Complexity
This course is designed for students of the associated programs. Students in the Informatics program enroll in the full courses, IB005 and IB107. Graduates of both full courses may have IB110 recognized.
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 12 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
    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 (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/jaro2023/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 2021, Spring 2022, Spring 2023, Spring 2024.
  • Enrolment Statistics (recent)
  • Permalink: https://is.muni.cz/course/fi/spring2025/IB110