460-4065/02 – Teoretická informatika (TI)
| Garantující katedra | Katedra informatiky | Kredity | 6 |
| Garant předmětu | doc. Ing. Zdeněk Sawa, Ph.D. | Garant verze předmětu | doc. Ing. Zdeněk Sawa, Ph.D. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | volitelný odborný |
| Ročník | 1 | Semestr | zimní |
| | Jazyk výuky | angličtina |
| Rok zavedení | 2015/2016 | Rok zrušení | 2022/2023 |
| Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Student po úspěšném absolvování předmětu:
- umí vyhodnotit vhodnost a rozsah možného nasazení metod konečných automatů,
bezkontextových gramatik apod. při řešení konkrétních problémů praxe
a umí příslušná řešení vytvářet, analyzovat a porovnávat
- je schopen analyzovat výpočtovou složitost problémů vyskytujících se
v inženýrské praxi a navrhovat vhodné algoritmy pro jejich řešení
- rozumí pojmům jako aproximační algoritmy, pravděpodobnostní
algoritmy apod. a umí vyhodnotit možnosti jejich použití v
konkrétních praktických kontextech
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Kurs prohlubuje a rozšiřuje teoretické základy v oblasti
formálních jazyků, automatů, gramatik, výpočtových problémů a
hlavně algoritmů a jejich složitosti, které student měl v základní formě nabýt v bakalářském studiu. Je také kladen speciální důraz na správné používání formalismu matematické logiky a důkazových technik.
Povinná literatura:
[1] Petr Jančar: Teoretická informatika, VŠB-TU, Ostrava, 2007 (dostupná z web-stránky předmětu).
Doporučená literatura:
[2] Sipser, M.: Introduction to the Theory of Computation, PWS Publishing Company, 1997.
[3] Kozen, D.: Automata and Computability, Undergraduate Text in Computer Science, Springer-Verlag, 1997.
[4] Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009.
[5] Papadimitriou, C.: Computational Complexity, Addison Wesley, 1993.
[6] Kozen, D.: Theory of computation, Springer 2006.
[7] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
[8] Hromkovič, J.: Theoretical Computer Science: Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, Springer, 2003.
[9] Hopcroft, J.E., Motwani, R., Ullman, J, D.: Introduction to Automata Theory, Languages, and Computation, (3rd edition), Addison Wesley, 2006.
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
E-learning
Další požadavky na studenta
Další požadavky na studenty nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
1. Přehled kursu.
Připomenutí základních množinových pojmů, relace ekvivalence,
uspořádání, grafů, formalismu výrokové a predikátové logiky, důkazů
indukcí a sporem.
(Všechny tyto pojmy a metody budou průběžně používány v průběhu
kursu. Speciální důraz bude kladen na správné užívání formalismu
logiky a pravidel usuzování.)
2. Formální jazyky, operace na jazycích,
regulární výrazy jako reprezentace jazyků,
algoritmus vyhledávání vzorku v textu prezentovaný jako
(deterministický) konečný
automat. Modulární návrh konečných automatů (KA), s využitím
charakterizace jazyka logickými formulemi.
3. Deterministické a nedeterministické
konečné automaty, operace s konečnými automaty,
převod nedeterministického KA na deterministický,
sestrojení KA k regulárnímu výrazu (RV).
4. Minimalizace DKA, kanonický tvar, izomorfismus automatů.
KA a RV definují stejnou třídu, tzv. regulární jazyky.
Charakterizace regulárních jazyků umožňující
důkazy neregularity; využití logického důkazu sporem.
5. Bezkontextové gramatiky, jejich (ne)jednoznačnost, užití při
specifikaci (fragmentů) programovacích jazyků a logických formalismů.
(Nedeterministické) zásobníkové automaty (ZA).
Syntaktická analýza (rekurzivním sestupem).
6. Bezkontextové jazyky a jejich podtřída analyzovatelná
deterministickými ZA. Základy jednoduchého překladače
(konstruujícího kon. automat k danému reg. výrazu).
7. Nebezkontextové jazyky, Chomského hierarchie.
Formální jazyk jako výpočetní problém.
Pojem algoritmu, modely výpočtu
(Turingův stroj, RAM, zmínka o rekurzivních a lambda-vyčíslitelných
funkcích).
8. Church-Turingova teze. Univerzální stroj.
(Algoritmická) nerozhodnutelnost,
problém zastavení, převeditelnost (redukce)
mezi problémy. Riceova věta (každá netriviální vstupně/výstupní
vlastnost programů je nerozhodnutelná).
Algoritmická nerozhodnutelnost logických teorií (speciálně standardní
aritmetiky).
9. Výpočetní složitost algoritmů, obecné metody návrhu
polynomiálních algoritmů: chytré prohledávání,
metoda rozděl a panuj, hltavé (greedy) postupy
u optimalizačních algoritmů, dynamické programování.
10. Výpočetní složitost problémů, třídy složitosti,
polynomiální převeditelnost mezi problémy.
Problém SAT (splnitelnost booleovských formulí) a nedeterministické
polynomiální algoritmy. Třída NPTIME. NP-úplnost.
11. Třída PSPACE=NPSPACE, PSPACE-úplné problémy, vyšší třídy
složitosti. Rozhodnutelnost Presburgerovy aritmetiky.
12. Aproximační algoritmy, tj. polynomiální algoritmy aproximující
optimální řešení optimalizačních problémů. (Ne)aproximovatelnost
konkrétních problémů.
13. Randomizované algoritmy, např. pro prvočíselnost, která je
základem pro kryptografické algoritmy.
14. Příklady paralelních algoritmů
a neparalelizovatelných (vnitřně sekvenčních) problémů.
Cvičení (na tabulové učebně):
1. Procvičení základních množinových pojmů, relace ekvivalence,
uspořádání, grafů, formalismu výrokové a predikátové logiky, důkazů
indukcí a sporem.
(Toto bude také průběžně procvičováno na konkrétních příkladech v
dalších cvičeních.)
2. Procvičení základních jazykových operací; speciálně pak operace
kvocientu. Návrh konečných automatů pro jednoduché jazyky a konstrukce
složitějších automatů z jednodušších.
3. Návrh nedeterministických konečných automatů, převod na
deterministické.
Procvičení regulárních výrazů jako prostředku popisu regulárních jazyků.
4. Procvičení algoritmů pro převod do normovaného tvaru a zjišťování
izomorfismu automatů. Procvičení algoritmu minimalizace. Důkazy
neregularity konkrétních jazyků.
5. Návrh konkrétních bezkontextových gramatik.
Převod konkrétních (nejednoznačných) gramatik na jednoznačné.
Procvičení algoritmů redukce a odstranění epsilon-pravidel.
Konstrukce zásobníkových automatů, ekvivalentních bezkontextovým
gramatikám.
6. Sestrojení překladače
konstruujícího kon. automat k danému reg. výrazu.
7. Důkazy nebezkontextovosti jazyků pomocí
pumping lemmatu. Konstrukce jednoduchého Turingova stroje a programu
RAM.
8. Procvičení důkazu nerozhodnutelnosti konkrétních problémů.
Procvičení aplikace Riceovy věty.
9. Procvičení několika obecných metod návrhu polynomiálních algoritmů
na konkrétních příkladech.
10. Návrh nedeterministických polynomiálních algoritmů.
Prokázání polynomiální převeditelnosti mezi konkrétními problémy.
11. Prokazování příslušnosti jednotlivých problémů k PTIME, NPTIME, PSPACE,
NPSPACE a prokazování NP- a PSPACE-obtížnosti.
12. Konstrukce a analýza aproximačních algoritmů pro vybrané
optimalizační problémy.
13. Analýza vybraných randomizovaných algoritmů.
14. Návrh paralelního algoritmu. Připomenutí témat písemné zkoušky.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky