Teoretická informatika (TIN) - informace pro studenty

Plán pro zimní semestr 2023

Semináře a cvičení

V rámci TIN se budou nepravidelně střídat demonstrační cvika (demo) a cvičení ve skupinách po cca 45 studentech (numerická cvičení). Demonstrační cvičení budou probíhat v pátek od 14:00 v D105. Numerická cvičení pak v termínech vypsaných v rozvrhu a ve STUDISUu.

V rámci každého týdne výuky budou vždy buď pouze democvičení, nebo pouze numerická cvičení.

Z demonstračních cvičení a z přednášek (od 2. týdne) bude k dispozici stream přes YouTube i záznam. I tak ale prosím pokud možno přijďte osobně.

Vyučující

• garant/přednášky/numerická cvičení/testy během semestru: doc. RNDr. Milan Češka, Ph.D. (konzultace v předem neomezených termínech na základě vzájemné dohody se zájemci e-mailem)
• zástupce garanta/democvičení/numerická cvičení: Prof. Ing. Tomáš Vojnar, Ph.D. (konzultace v předem neomezených termínech na základě vzájemné dohody se zájemci e-mailem)
• numerická cvičení/úkoly: doc. Mgr. Adam Rogalewicz, Ph.D. (konzultace v předem neomezených termínech na základě vzájemné dohody se zájemci e-mailem)
• numerická cvičení/úkoly: doc. Mgr. Lukáš Holík, Ph.D.(konzultace v předem neomezených termínech na základě vzájemné dohody se zájemci e-mailem)
• numerická cvičení/úkoly: Ing. Ondřej Lengál, Ph.D. (konzultace v předem neomezených termínech na základě vzájemné dohody se zájemci e-mailem)

Studijní materiály

• Prezentace z přednášek budou průběžně doplňovány (starší prezentace dostupné zde):
• Úvod a motivace do studia formálních jazyků a úvod do regulárních jazyků
• Pokročilé aspekty regulárních jazyků
• Úvod do bezkontextových jazyků a zásobníkových automatů
• Pokročilé aspekty bezkontextových jazyků
• Turingovy stroje
• Meze rozhodnutelnosti
• Formální systém výrokové a predikátové logiky
• Neúplnost formálních systémů
• Úvod do složitosti
• Vlastnoti složitostních tříd
• Regex Matching: od regulárních výrazů přes automaty a algoritmy ke složitosti a bezpečnosti (dodatečná přednáška)


• Studijní text (opora): pdf.


• Materiály k demo cvičením a numerickým cvičením budou průběžně doplňovány:
  • Demo 1: opakování z diskrétní matematiky, jazyky a gramatiky
  • Demo 2: KA, Pumping lemma pro regulární jazyky
  • Cvičení 1: Pumping lemma pro regulární jazyky, Myhill-Nerodova věta
  • Demo 3: ZA, konstrukce algoritmů, Pumping lemma pro bezkontextové jazyky, uzávěrové vlastnosti
  • Cvičení 2: transformace bezkontextových gramatik, jednoznačnost, DZA, syntaktická analýza
  • Cvičení 3: Pumping lemma pro bezkontextové jazyky, konstrukce algoritmů
  • Cvičení 4: Turingovy stroje, rozhodnutelnost
  • Demo 4: nerozhodnutelnost
  • Cvičení 5: nerozhodnutelnost (redukce, diagonalizace)
  • Cvičení 6: logika (normální formy výrokové logiky; jazyk, teorie, modely, bezespornost, úplnost, rozhodnutelnost predikátové logiky)
  • Demo 5: logika + poznámky
  • Demo 6: složitost (demo z 8.12. + část přednášky 11.12.)
  • Cvičení 7: složitost
  
  

  ---

  Referenční literatura

  Zejména na těchto textech je předmět vystavěn. U knih v angličtině (zejména knihy D.C. Kozen a Hopcroft, J.E. et al) doporučujeme možnost do těchto knih nahlédnout (příp. si je vypůjčit) v knihovně FIT -- jedná se o velmi kvalitní texty používané na řadě univerzit ve světě.
  • Češka, M.: Teoretická informatika, učební text FIT VUT v Brně, 2002. Viz výše uvedená elektronická verze.
  • Kozen, D.C.: Automata and Computability, Springer-Verlag, New York, Inc, 1997. ISBN 0-387-94907-0
  • Černá, I., Křetínský, M., Kučera, A.: Automaty a formální jazyky I, učební text FI MU, Brno, 1999.
  • Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2. vydání, 2000. ISBN 0-201-44124-1
  • Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997. ISBN 1-85032-243-0
  • Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall Europe, Pearson Education Limited, 1994. ISBN 0-13-915380-2
  • Meduna, A.: Formal Languages and Computation, CRC Press, 2014, ISBN 978-1-46651345-7 (k dispozici v knihovně FIT)
  
  

  ---

  Domácí úkoly

  Součástí bodového hodnocení předmětu jsou 3 domácí úlohy. Zadání úloh a pokyny pro vypracování budou postupně zveřejněny na e-learningu VUT.
  
  Úlohy se budou odevzdávat ve 6. a 10. a 13. týdnu semestru.

Úlohy na procvičení

• Sbírka příkladů s řešením typových úloh je k dispozici zde (verze z 3.1.2024). Pokud v řešení naleznete chybu, napište email na ceskam@fit.vutbr.cz -- můžete získat prémiové body.
• Řešení (téměř) všech příkladů se sbírky, které vypracoval a poskytl Tomáš Kocourek najdete zde (verze z 31.12 2022). Jde o neoficiální studijní materiál, který neprošel korekturou ze strany vyučujích předmětu TIN. Silně doporučujeme ho využít pouze jako kontrolu vlastních řešení.
• Zadání domácích úloh z minulých let jsou k dispozici zde.

Odkazy na WWW

• Skripta Teoretická informatika, pokrývající část přednášené látky: pdf.
  
  
• Javier Esparza: Automata theory, an algorithmic approach. Konečné automaty nad konečnými a nekonečnými slovy, konečné převodníky, aplikace automatů, vazba na logiku.
  
  
• Warshalův algoritmus pro výpočet tranzitivního uzávěru relace. Slidy zde
  
  
• Důkaz ekvivalence kontextových a nezkracujících gramatik: pdf.
  
  
• Řecká abeceda: pdf.
  
  
• Encyklopedie -- můžete je s výhodu využít pro vyhledání významu neznámých pojmů z matematiky, příp. i teoretické informatiky:
  • PlanetMath
  • Eric Weisstein's World of Mathematics
  
  
• Knihovny pro práci s konečnými automaty a jejich (často netradiční a zajímavé využití nejen v oblasti překladačů):
  • FSA. Knihovna napsaná v Prologu, snadno použitelná, poměrně výkonná, linkovatelná z jiných jazyků. Zahrnuje převodníky a vážené automaty. Využití mj. ve formální verifikaci či v lingvistice. Dá se snadno použít také pro experimenty s různými jazykovými operacemi.
  • Mona. Knihovna pro práci s logikami WS1S a WS2S založená na velmi optimalizované implementaci konečných automatů nad slovy a také nad stromy (ty lze použít i samostatně). Celá řada aplikací v oblasti formální verifikace, symbolických výpočtů apod. Obecně řeší některé problémy o neelementární složitosti, tj. složitosti vyjádřené věží exponenciál, jejíž výška není konstantní, ale závisí na vstupní instanci (zkuste se mimochodem zamyslet, udělat si pár výpočtů, jak rychle taková složitost roste).
  • Timbuk. Knihovna pro práci se stromovými automaty v jazyce Ocaml. Aplikace ve verifikaci, analýze kryptografických protokolů apod.
  • LASH. Nástroj pro symbolickou analýzu systémů popsaných pomocí soustav lineárních rovnic nad celočíselnými či reálnými čísly. Nekonečné množiny celočíselných/reálných vektorů jsou reprezentovány konečnými automaty nad konečnými či nekonečnými slovy (Büchiho automaty -- nepřijímají pochopitelně zastavením v koncovém stavu, ale namísto toho nekonečným cyklením přes přijímající stav).
  • VATA. Knihovna pro práci s konečnými a konečnými stromovými automaty. Je založená na efektivních algoritmech, které umožňují práci přímo s nedeterministickými automaty bez nutnosti determinizace.
  
  
• Kleeneho algebry: D. Kozen. A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events. Information and Computation, 1994.
  
  
• Známé otevřené problémy matematiky (The Millenium Prize Problems) včetně otázky, zda P = NP: pro zájemce je možno doporučit mj. zajímavou knihu Keith Devlin: Problémy pro třetí tisíciletí, Nakladatelství Dokořán a Argo, 2005. (Z anglického originálu The Millennium Problems: The Seven Greatest Unsolved Mathematical Puzzles of Our Time, Basic Books, 2002.) Za vyřešení každého z těchto problémů je vypsána odměna 1.000.000 USD.
  
  
• Složitost:
  • Summary of big-O Algebra
  • The Complexity Zoo
  
  
  
• First-Order Logic Glossary -- některé pojmy z oblasti logiky, teorie množin, rekurzívních funkcí.
  
  
• Pro zájemce o skutečně zásadní poznatky -- Gödelovy teorémy a z nich plynoucí meze formálního usuzování. Mimochodem Kurt Gödel je rodák z Brna (podle něj je pojmenována posluchárna E112).
  • Krátký důkaz Goedelovy věty pro programátory
  
  
  
• Zajímavosti:
  • Automat s frontou na wikipedii.
  • Nástroj pro vizualizaci výpočtu Turingova stroje.
  • Teaching Teaching & Understanding Understanding