|
Lecturer(s)
|
-
Bělohlávek Radim, prof. RNDr. Ph.D., DSc.
-
Osička Petr, Mgr. Ph.D.
-
Masopust Tomáš, doc. RNDr. Ph.D., DSc.
|
|
Course content
|
<ol> <li>Formal languages and automata: Basic notions, Chomsky hierarchy.</li> <li>Regular languages: Deterministic and non-deterministic finite automata and their relationship, regular expressions, relationship of finite automata and regular expressions to regular languages.</li> <li>Computability: Turing machine (TM), language recognized by TM, language decided by TM, computable and partially computable problems, Halting problem.</li> <li>Complexity: Complexity classes, class P, class NP, their relationship, NP-complete problems, applications of hard problems.</li> </ol>
|
|
Learning activities and teaching methods
|
|
Lecture, Dialogic Lecture (Discussion, Dialog, Brainstorming)
|
|
Learning outcomes
|
This course introduces basics of Formal languages and automata, Computability, and Complexity.
1. Knowledge Identify unsolvable problems and solvable problems and their computational complexity.
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
Oral exam
Exam: oral exam
|
|
Recommended literature
|
-
Hopcroft J. E., Motwani R., Ullman J. D. (2006). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Boston.
-
LAWSON. (2003). Finite Automata. Chapman & Hall/CRC.
-
Linz, P. (2016). An Introduction to Formal Languages and Automata. Jones and Bartlett Publishers, Inc.
-
Melichar, B. (2003). Jazyky a překlady. Skriptum, přepracované 2. vydání. Vydavatelství ČVUT, Praha.
-
Simovici D. A., Tenney R. L. (1999). Theory of Formal Languages with Applications. World Scientific, Singapore.
-
Sipser M. (1997). Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA.
|