Detail předmětu
Teoretická informatika
TIN Ak. rok 2024/2025 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 logiky a 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ů půlsemestrální test (písemná část)
- 15 bodů projekty
Zajišťuje ústav
Přednášející
Cvičící
Lengál Ondřej, Ing., Ph.D. (UITS)
Rogalewicz Adam, doc. Mgr., Ph.D. (UITS)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS)
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.
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. Pokročilé vlastnosti bezkontextových jazyků, věta o vkládání pro bezkontextové jazyky, rozhodnutelné problémy bezkontextových jazyků.
- 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.
- Úvod do výpočetní složitosti, Turingovská složitost a asymptotická složitost. Třídy složitosti.
- Amortizovaná složitost. Třída P a NP problémů
- Polynomiální redukce, úplnost a problémy mimo třídu NP.
- Analýza složitosti vybraných problémů.
- 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.
- Hromadná konzultace
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 2 projektů (max. 7 bodů a 8 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. Písemný test v 9. týdnu výuky je zaměřený na bezkontextové jazyky, rozhodnutelnost včetně konstrukce Turingových strojů a základy složitosti.
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.
Rozvrh
Den | Typ | Týdny | Místn. | Od | Do | Kapacita | PSK | Skup | Info |
---|---|---|---|---|---|---|---|---|---|
Po | přednáška | 1., 2., 3., 4., 5., 6., 10., 11., 12., 13. výuky | D105 | 11:00 | 13:50 | 316 | 1MIT 2MIT | NBIO - NSPE xx | Češka |
Po | přednáška | 8., 9. výuky | D105 | 11:00 | 13:50 | 316 | 1MIT 2MIT | NBIO - NSPE xx | Holík |
Út | cvičení | 3., 4., 6., 7., 9., 11., 12. výuky | A113 | 08:00 | 09:50 | 64 | 1MIT 2MIT | xx | |
Út | cvičení | 3., 4., 6., 7., 9., 11., 12. výuky | D0207 | 16:00 | 17:50 | 90 | 1MIT 2MIT | xx | |
St | cvičení | 3., 4., 6., 7., 9., 11., 12. výuky | G202 | 13:00 | 14:50 | 80 | 1MIT 2MIT | xx | |
Čt | cvičení | 3., 4., 6., 7., 9., 11., 12. výuky | E104 | 16:00 | 17:50 | 70 | 1MIT | xx | |
Čt | seminář | 1., 2. výuky | E104 E105 E112 | 16:00 | 18:50 | 294 | 1MIT 2MIT | NBIO - NSPE xx | Rogalewicz |
Čt | seminář | 5., 13. výuky | E104 E105 E112 | 16:00 | 18:50 | 294 | 1MIT 2MIT | NBIO - NSPE xx | |
Čt | seminář | 2024-11-07 | E104 E105 E112 | 16:00 | 18:50 | 294 | 1MIT 2MIT | NBIO - NSPE xx | Lengál |
Čt | seminář | 2024-11-21 | E104 E105 E112 | 16:00 | 18:50 | 294 | 1MIT 2MIT | NBIO - NSPE xx | Češka |
Pá | cvičení | 3., 4., 6., 7., 9., 11., 12. výuky | A112 | 10:00 | 11:50 | 64 | 1MIT 2MIT | xx | |
Pá | cvičení *) | výuky | A112 | 16:00 | 17:50 | 64 | 1MIT 2MIT | xx |
Zařazení předmětu ve studijních plánech