Detail předmětu
Teoretická informatika
TIN Ak. rok 2023/2024 zimní semestr 7 kreditů
Aplikace teorie formálních jazyků v informatice a informačních technologiích (překladače, modelování a analýza systémů, lingvistika, biologie atd.), modelovací a rozhodovací síla formálního modelu, regulární jazyky a jejich vlastnosti, minimalizace konečného automatu, bezkontextové jazyky a jejich vlastnosti, Turingovy stroje, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, vyčíslitelné funkce, nerozhodnutelnost, nerozhodnutelné problémy teorie formálních jazyků a úvod do výpočetní složitosti.
Garant předmětu
Koordinátor předmětu
Jazyk výuky
Zakončení
Rozsah
- 39 hod. přednášky
- 10 hod. seminář
- 16 hod. cvičení
- 13 hod. projekty
Bodové hodnocení
- 60 bodů závěrečná zkouška (písemná část)
- 25 bodů průběžné testy (písemná část)
- 15 bodů projekty
Zajišťuje ústav
Přednášející
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS)
Cvičící
Holík Lukáš, doc. Mgr., Ph.D. (UITS)
Lengál Ondřej, Ing., Ph.D. (UITS)
Rogalewicz Adam, doc. Mgr., Ph.D. (UITS)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS)
Stránky předmětu
Cíle předmětu
Rozšíření znalostí teorie formálních jazyků a osvojení základů teorie vyčíslitelnosti a základních pojmů výpočetní složitosti.
Znalosti základních a pokročilejších pojmů, přístupů a výsledků teorie automatů a teorie vyčíslitelnosti a základů teorie výpočetní složitosti, vedoucí k hlubšímu pochopení povahy popisu a realizace výpočetních procesů.
Student získává základní kompetence k teoretické výzkumné práci.
Proč je předmět vyučován
Předmět seznámí studenty se základními principy, na kterých informatika stojí, a umožní jim chápat, kde leží meze počítání, jaká je cena řešení různých problémů na počítačích a kde jsou tedy meze toho, co lze od řešení problémů na výpočetních zařízeních - minimálně v té podobě, v jaké jsou v současné době chápány - čekat. Předmět studenty dále seznámí, a to výrazně hlouběji než předměty na bakalářském stupni, s řadou konkrétních konceptů, jako jsou různé typy automatů a gramatik, a konkrétních algoritmů nad nimi, které se běžně používají v celé řadě aplikačních oblastí (např. překladače, zpracování textu, analýza síťového provozu, optimalizace hardware i software, modelování a návrh systémů, statická i dynamická analýza a verifikace, umělá inteligence apod.). Hlubší znalosti z této oblasti umožní studentům nejen aplikovat existující algoritmy, ale také je dále rozvíjet a dolaďovat na míru konkrétních řešených problémů, jak je v praxi často zapotřebí. V neposlední řadě pak předmět buduje ve studentech schopnost abstraktního a systematického myšlení, schopnost číst a chápat formální zápisy (a být pak schopen pochopit a v praxi aplikovat průběžně publikované nové výsledky vědy a výzkumu) a také schopnost přesného vyjadřování.
Požadované prerekvizitní znalosti a dovednosti
Základní znalosti z binárních relací, algebraických struktur, matematické logiky, teorie grafů a formálních jazyků včetně konečných a zásobníkových automatů a pojmů algoritmické složitosti.
Literatura studijní
- Češka, M. a kol.: Vyčíslitelnost a složitost, Nakl. VUT Brno, 1993. ISBN 80-214-0441-8
- Češka, M., Rábová, Z.: Gramatiky a jazyky, Nakl. VUT Brno, 1992. ISBN 80-214-0449-3
- Češka, M., Vojnar, T.: Studijní text k předmětu Teoretická informatika (http://www.fit.vutbr.cz/study/courses/TIN/public/Texty/TIN-studijni-text.pdf), 165 str. (in Czech)
- Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0
- Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd ed., 2000. ISBN 0-201-44124-1
- Meduna, A.: Formal Languages and Computation. New York, Taylor & Francis, 2014.
- Aho, A.V., Ullmann, J.D.: The Theory of Parsing,Translation and Compiling, Prentice-Hall, 1972. ISBN 0-139-14564-8
- Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3rd ed., 2002. ISBN 0-072-32200-4
- Brookshear, J.G. : Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California, 1989. ISBN 0-805-30143-7
Literatura referenční
- Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd ed., 2000. ISBN 0-201-44124-1
- Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0
- Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3rd ed., 2002. ISBN 0-072-32200-4
- Brookshear, J.G. : Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California, 1989. ISBN 0-805-30143-7
- Aho, A.V., Ullmann, J.D.: The Theory of Parsing,Translation and Compiling, Prentice-Hall, 1972. ISBN 0-139-14564-8
Osnova přednášek
- Úvod do teorie formálních jazyků, způsoby specifikace jazyků, regulární jazyky a gramatiky, konečné automaty, regulární výrazy.
- Minimalizace konečného automatu, věta o vkládání (Pumping theorem), Nerodova věta, rozhodnutelné problémy regulárních jazyků.
- Bezkontextové jazyky a gramatiky, zásobníkové automaty, transformace a normální tvary bezkontextových gramatik.
- Pokročilé vlastnosti bezkontextových jazyků, věta o vkládání pro bezkontextové jazyky, rozhodnutelné problémy bezkontextových jazyků, deterministické bezkontextové jazyky.
- Turingovy stroje (TS), rekurzivně vyčíslitelné a rekurzivní jazyky a problémy.
- TS a jazyky typu 0, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, lineárně ohraničené automaty a jazyky typu 1.
- Church-Turingova téze, nerozhodnutelnost, problém zastavení TS, redukce, Postův korespondenční problém, nerozhodnutelné problémy teorie formálních jazyků, diagonalizace.
- Predikátová logika a její axiomatizace.
- Gödelovy věty o neúplnosti.
- Úvod do výpočetní složitosti, Turingovská složitost, asymptotická složitost.
- Třída P a NP problémů, polynomiální redukce, úplnost.
- Amortizovaná složitost, problémy mimo třídu NP.
Osnova numerických cvičení
- Základy diskrétní matematiky, formální jazyky a operace nad nimi. Gramatiky, Chomského hierarchie jazyků a gramatik.
- Regulární jazyky a konečné automaty, determinizace automatů
- Převod regulárních výrazů na konečné automaty. Minimalizace automatů, Pumping lemma.
- Bezkontextové jazyky a gramatiky. Transformace bezkontextových gramatik.
- Operace nad bezkontextovými jazyky a uzavřenost vůči nim. Pumping lemma bezkontextových jazyků.
- Zásobníkové automaty, (nedeterministická) syntaktická analýza shora dolů a zdola nahoru. Deterministické zásobníkové jazyky.
- Turingovy stroje.
- Rozhodnutelnost, částečná rozhodnutelnost a nerozhodnutelnost problémů, redukce problémů I.
- Rozhodnutelnost, částečná rozhodnutelnost a nerozhodnutelnost problémů II.
- Predikátová logika I.
- Predikátová logika II.
- Třídy složitosti. Vlastnosti prostorových a časových tříd složitosti.
- P a NP problémy. Polynomiální redukce.
Osnova ostatní - projekty, práce
- Řešení problému z oblasti regulárních a bezkontextových jazyků.
- Řešení problému z oblasti bezkontextových jazyků, Turingových strojů a teorie nerozhodnutelnosti.
- Řešení problému z oblasti nerozhodnutelnosti a složitosti.
Průběžná kontrola studia
Bodové hodnocení předmětu se skládá z výsledků testu ve 4. týdnu (max 10 bodů), testu ve 9. týdnu (max 15 bodů), vypracovaných projektů (max. 3-krát 5 bodů) a závěrečné semestrální zkoušky (max 60 bodů).
Písemný test ve 4. týdnu výuky je zaměřen na regulární jazyky a základní znalosti v oblasti bezkontextových jazyků. Písemný test v 9. týdnu výuky je zaměřený na pokročilejší znalosti z bezkontextových jazyků a na oblast rozhodnutelnosti a nerozhodnutelnosti včetně konstrukce Turingových strojů.
Závěrečné semestrální zkouška má 4 části. Pro získání bodů ze závěrečné zkoušky je nutné mít z každé části alespoň 4 body a celkově získat alespoň 25 bodů. V opačném případě bude zkouška hodnocena 0 body.
Podmínky zápočtu
Celkový zisk minimálně 18 bodů z domácích úkolů a ze testů v 4. a 9. týdnu (tj. celkem z 40 bodů).
Zařazení předmětu ve studijních plánech