|
Lecturer(s)
|
-
Houda Michal, Mgr. Ph.D.
-
Beránek Ladislav, prof. Ing. CSc., MBA
|
|
Course content
|
Lecture topics: 1) Theory of information, characteristics of information, entropy, information transfer 2) Data compression and coding, source coding theorem, Kraft's inequality, non-uniform codes 3) Coding, self-correcting codes 4) Finite automata, the equivalence of automata, reduction, and normalization of finite automata, non-deterministic finite automata 5) Regular expressions, Kleen's theorem, converting a regular expression to an automaton, converting an automaton to a regular expression 6) Chomsky's hierarchy of grammars, context-free grammars, stack automata 7) Context grammars, Turing machines, different types of Turing machines, algorithm definition 8) Decision problems, Turing machine halting problem, Post's assignment problem and its applications 9) Complexity theory, time and space complexity, algorithm analysis, and complexity measurement 10) Definition of classes P and NP, polynomial transferability of problems, the notion of NP-completeness, examples of NP-complete problems
|
|
Learning activities and teaching methods
|
Monologic (reading, lecture, briefing)
- Class attendance
- 56 hours per semester
- Preparation for classes
- 54 hours per semester
- Preparation for credit
- 20 hours per semester
- Preparation for exam
- 30 hours per semester
|
|
Learning outcomes
|
The subject aims to become familiar with the principles and applications of information theory. It is divided into three parts. In the first part, students will learn how information is measured, coding, and the principles of data compression and coding. In the second part, they will deal with the area of automata and formal grammar, and the third part with the theory of computability and complexity. In addition to theoretical knowledge and an emphasis on mastering the formal apparatus of theoretical informatics, the exercises for this subject will be focused on the practical effects and possibilities of using the acquired theoretical knowledge.
Students will gain an overview of the basic principles and applications of information theory, especially the measurement and coding of information, formal grammar, and the theory of complexity and computability.
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
Combined exam
Credit - Active participation in exercises Exam - combined exam
|
|
Recommended literature
|
-
ČERNÁ, I., KŘETÍNSKÝ M., KUČERA, A. Formální jazyky a automaty I. Elportál. Masarykova univerzita, Brno, 2006.
-
LEWIS, Harry R. a Rachel ZAX. Essentialdiscrete mathematics for computer science. Princeton, New Jersey: Princeton University Press, 2019. ISBN 978-0-691-17929-2.
-
Linz, Peter. An introduction to formal languages and automata. Burlington, MA: Jones & Bartlett Learning, 2017. ISBN 978-1284077247.
-
MAREŠ, Martin a Tomáš VALLA. Průvodce labyrintem algoritmů. Praha, CZ.NIC, z.s.p.o, 2017. ISBN 978-80-88168-19-5.
-
MAREŠ, Milan. Základy teorie informace: zdroje informace a její měření. České Budějovice: Jihočeská univerzita, 2011. ISBN 978-80-7394-291-5.
-
VANÍČEK, Jiří. Teoretické základy informatiky. Praha: Kernberg, 2007. ISBN 978-80-903962-4-1.
|