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

česky

Zakončení

zápočet+zkouška (kombinovaná)

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í

Cvičící

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

  1. Úvod do teorie formálních jazyků, způsoby specifikace jazyků, regulární jazyky a gramatiky, konečné automaty, regulární výrazy.
  2. Minimalizace konečného automatu, věta o vkládání (Pumping theorem), Nerodova věta, rozhodnutelné problémy regulárních jazyků. 
  3. Bezkontextové jazyky a gramatiky, zásobníkové automaty, transformace a normální tvary bezkontextových gramatik. 
  4. Pokročilé vlastnosti bezkontextových jazyků, věta o vkládání pro bezkontextové jazyky, rozhodnutelné problémy bezkontextových jazyků, deterministické bezkontextové jazyky. 
  5. Turingovy stroje (TS), rekurzivně vyčíslitelné a rekurzivní jazyky a problémy.
  6. TS a jazyky typu 0, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, lineárně ohraničené automaty a jazyky typu 1. 
  7. 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. 
  8. Predikátová logika a její axiomatizace.
  9. Gödelovy věty o neúplnosti.
  10. Úvod do výpočetní složitosti, Turingovská složitost, asymptotická složitost.
  11. Třída P a NP problémů, polynomiální redukce, úplnost.
  12. Amortizovaná složitost, problémy mimo třídu NP.

Osnova numerických cvičení

  1. Základy diskrétní matematiky, formální jazyky a operace nad nimi. Gramatiky, Chomského hierarchie jazyků a gramatik. 
  2. Regulární jazyky a konečné automaty, determinizace automatů
  3. Převod regulárních výrazů na konečné automaty. Minimalizace automatů, Pumping lemma.
  4. Bezkontextové jazyky a gramatiky. Transformace bezkontextových gramatik. 
  5. Operace nad bezkontextovými jazyky a uzavřenost vůči nim. Pumping lemma bezkontextových jazyků. 
  6. Zásobníkové automaty, (nedeterministická) syntaktická analýza shora dolů a zdola nahoru. Deterministické zásobníkové jazyky. 
  7. Turingovy stroje. 
  8. Rozhodnutelnost, částečná rozhodnutelnost a nerozhodnutelnost problémů, redukce problémů I.  
  9. Rozhodnutelnost, částečná rozhodnutelnost a nerozhodnutelnost problémů II.
  10. Predikátová logika I.
  11. Predikátová logika II.
  12. Třídy složitosti. Vlastnosti prostorových a časových tříd složitosti. 
  13. P a NP problémy. Polynomiální redukce. 

Osnova ostatní - projekty, práce

  1. Řešení problému z oblasti regulárních a bezkontextových jazyků. 
  2. Řešení problému z oblasti bezkontextových jazyků, Turingových strojů a teorie nerozhodnutelnosti. 
  3. Ř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ů.

Podmínky pro udělení zápočtu, který je podmínkou pro připuštění k závěrečné semestrální zkoušce: Celkový zisk minimálně 18 bodů z z projektů a z testů v 4. a 9. týdnu (tj. celkem z 40 bodů).

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ů).

Rozvrh

DenTypTýdnyMístn.OdDoKapacitaPSKSkupInfo
Po zkouška 2023-11-13 E104 E105 E112 08:0009:50 2. průběžný test
Po přednáška 1., 2., 3., 4., 5., 6., 7., 10., 11., 13. výuky D105 11:0013:50316 1MIT 2MIT NBIO - NSPE xx Češka
Po přednáška 8., 9. výuky D105 11:0013:50316 1MIT 2MIT NBIO - NSPE xx Holík
Po přednáška 2023-12-04 D105 11:0013:50316 1MIT 2MIT NBIO - NSPE xx Vojnar
Po zkouška 2024-01-29 D105 13:0016:50 3. termín
Po cvičení 3., 7., 10. výuky A113 18:0019:5043 1MIT 2MIT xx Lengál
Po cvičení 6., 9. výuky A113 18:0019:5043 1MIT 2MIT xx Češka
Po cvičení 2023-10-16 A113 18:0019:5043 1MIT 2MIT xx Holík
Po cvičení 2023-12-11 A113 18:0019:5043 1MIT 2MIT xx Rogalewicz
Út cvičení 3., 7., 10. výuky A113 08:0009:5043 1MIT 2MIT xx Lengál
Út cvičení 6., 9. výuky A113 08:0009:5043 1MIT 2MIT xx Češka
Út cvičení 2023-10-17 A113 08:0009:5043 1MIT 2MIT xx Holík
Út cvičení 2023-12-12 A113 08:0009:5043 1MIT 2MIT xx Rogalewicz
Út cvičení 3., 7., 10. výuky A113 18:0019:5043 1MIT 2MIT xx Lengál
Út cvičení 6., 9. výuky A113 18:0019:5043 1MIT 2MIT xx Češka
Út cvičení 2023-10-17 A113 18:0019:5043 1MIT 2MIT xx Holík
Út cvičení 2023-12-12 A113 18:0019:5043 1MIT 2MIT xx Rogalewicz
St zkouška 2024-01-17 D105 13:0016:50 2. termín
Čt ostatní 2023-12-28 A211 00:1000:15 hodnocení 2. domácí úlohy
Čt cvičení 3., 7., 10. výuky D0206 09:0010:5043 1MIT 2MIT xx Lengál
Čt cvičení 6., 9. výuky D0206 09:0010:5043 1MIT 2MIT xx Češka
Čt cvičení 2023-10-19 D0206 09:0010:5043 1MIT 2MIT xx Holík
Čt cvičení 2023-12-14 D0206 09:0010:5043 1MIT 2MIT xx Rogalewicz
zkouška 2023-10-13 D105 14:0015:50 1.test
zkouška 2024-01-05 D0206 D105 14:0017:50 1. termín
cvičení 3., 5., 6., 7., 10., 13. výuky D105 14:0015:5043 1MIT 2MIT xx Vojnar
seminář 1., 2., 4., 8. výuky D105 14:0016:50316 1MIT 2MIT NBIO - NSPE xx Vojnar
seminář 2023-12-01 D105 14:0016:50316 1MIT 2MIT NBIO - NSPE xx Holík
seminář 2023-12-08 D105 14:0016:50316 1MIT 2MIT NBIO - NSPE xx Češka
cvičení 3., 5., 6., 7., 10., 13. výuky A112 16:0017:5043 1MIT 2MIT xx Vojnar
seminář 2023-10-13 D105 16:0018:50316 1MIT FIT ost xx Vojnar Mimoradny posun democviceni kvuli zkousce

Zařazení předmětu ve studijních plánech

Nahoru