Náplň přednášek:
1. Úvod. Čím se zabývá teoretická informatika (algoritmy, algoritmické problémy, formální jazyky, ...).
2. Formální jazyky - základní pojmy (abeceda, slovo, jazyk). Operace na jazycích. Regulární výrazy.
3. Deterministické konečné automaty (DKA). Konstrukce konečných automatů. Některé jazykové operace na DKA.
4. Nedeterministické konečné automaty (NKA). Převod NKA na DKA. Jazykové operace na NKA. Vztah mezi regulárními výrazy a konečnými automaty.
5. Bezkontextové gramatiky a jazyky.
6. Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám. Chomského hierarchie.
7. Algoritmické problémy. Modely výpočtu (Turingovy stroje a stroje RAM). Churchova-Turingova teze.
8. Korektnost algoritmů. Dokazování korektnosti algoritmů.
9. Výpočetní složitost algoritmů. Asymptotická notace. Analýza výpočetní složitosti konkrétních algoritmů (iterativních i rekurzivních).
10. Různé obecné techniky návrhu algoritmů - řešení hrubou silou, rozděl a panuj, prohledávání s návratem, greedy algoritmy, dynamické programování.
11. Složitost problémů. Třídy složitosti (především třídy P a NP). Převody mezi problémy. NP-úplné problémy.
12. Konkrétní příklady NP-úplných problémů a převodů mezi problémy.
13. Algoritmicky nerozhodnutelné problémy (např. halting problem).
Náplň cvičení:
(Pozn.: Témata cvičení odpovídají tématům přednášek.)
1. Zopakování základů logiky, teorie množin, relací, funkcí a teorie grafů.
2. Operace na jazycích. Regulární výrazy.
3. Konstrukce deterministických konečných automatů (DKA). Operace na těchto automatech.
4. Konstrukce nedeterministických konečných automatů (NKA). Převod NKA na DKA. Převody mezi regulárními výrazy a konečnými automaty.
5. Konstrukce bezkontextových gramatik. Různé operace na těchto gramatikách.
6. Zásobníkové automaty.
7. Algoritmické problémy. Turingovy stroje a stroje RAM.
8. Dokazování korektnosti algoritmů.
9. Asymptotická notace. Analýza výpočetní složitosti algoritmů.
10. Techniky návrhů algoritmů.
11. Složitost problémů. Třídy složitosti. Převody mezi problémy.
12. Dokazování NP-úplnosti problémů.
13. Dokazování algoritmické nerozhodnutelnosti problémů.
1. Úvod. Čím se zabývá teoretická informatika (algoritmy, algoritmické problémy, formální jazyky, ...).
2. Formální jazyky - základní pojmy (abeceda, slovo, jazyk). Operace na jazycích. Regulární výrazy.
3. Deterministické konečné automaty (DKA). Konstrukce konečných automatů. Některé jazykové operace na DKA.
4. Nedeterministické konečné automaty (NKA). Převod NKA na DKA. Jazykové operace na NKA. Vztah mezi regulárními výrazy a konečnými automaty.
5. Bezkontextové gramatiky a jazyky.
6. Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám. Chomského hierarchie.
7. Algoritmické problémy. Modely výpočtu (Turingovy stroje a stroje RAM). Churchova-Turingova teze.
8. Korektnost algoritmů. Dokazování korektnosti algoritmů.
9. Výpočetní složitost algoritmů. Asymptotická notace. Analýza výpočetní složitosti konkrétních algoritmů (iterativních i rekurzivních).
10. Různé obecné techniky návrhu algoritmů - řešení hrubou silou, rozděl a panuj, prohledávání s návratem, greedy algoritmy, dynamické programování.
11. Složitost problémů. Třídy složitosti (především třídy P a NP). Převody mezi problémy. NP-úplné problémy.
12. Konkrétní příklady NP-úplných problémů a převodů mezi problémy.
13. Algoritmicky nerozhodnutelné problémy (např. halting problem).
Náplň cvičení:
(Pozn.: Témata cvičení odpovídají tématům přednášek.)
1. Zopakování základů logiky, teorie množin, relací, funkcí a teorie grafů.
2. Operace na jazycích. Regulární výrazy.
3. Konstrukce deterministických konečných automatů (DKA). Operace na těchto automatech.
4. Konstrukce nedeterministických konečných automatů (NKA). Převod NKA na DKA. Převody mezi regulárními výrazy a konečnými automaty.
5. Konstrukce bezkontextových gramatik. Různé operace na těchto gramatikách.
6. Zásobníkové automaty.
7. Algoritmické problémy. Turingovy stroje a stroje RAM.
8. Dokazování korektnosti algoritmů.
9. Asymptotická notace. Analýza výpočetní složitosti algoritmů.
10. Techniky návrhů algoritmů.
11. Složitost problémů. Třídy složitosti. Převody mezi problémy.
12. Dokazování NP-úplnosti problémů.
13. Dokazování algoritmické nerozhodnutelnosti problémů.