Teoretická informatika (TIN) - informace pro studenty

Aktuální upozornění

• 2.test se koná v pátek 8.11. od 16:00 do 18:00.. Test bude pokrývat bezkontextové jazyky, Turingovy stroje a úvodní části složitosti včetně analýzy složitosti algoritmů mimo Turingovy stroje (amortizovaná složitost v 2. testu nebude). Ukázka testu z minulého roku -- pozor neobsahuje složitost, která bude letos v 2. testu nově (příklady na procvičení složitosti najdete ve sbírce příkladů). Rozdělení studentů do místností je následující:
  • D105: A. - O.
  • D0206: P. - Ž.
  S sebou psací potřeby, průkaz s fotografií a eventuálně lahev s pitím.
• Zadání 1. testu a krátký komentář k hodnocení
• 1.test se koná v pátek 11.10. od 16:00 do 18:00. Rozdělení studentů do místností je následující:
  • D105: A. - O.
  • D0206: P. - Ž.
  S sebou psací potřeby, průkaz s fotografií a eventuálně lahev s pitím. Ukázka testu z minulého roku.
• Přednášky i democvičení se streamují na této adrese.

Plán pro zimní semestr 2024

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 ve čtvrtek od 16:00 v E112 (+ E104 + E105) . 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 bude pořízen záznam. I tak ale prosím pokud možno přijďte osobně.

Vyučující

• garant/přednášky/democvičení/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)
• democvičení/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)
• přednášky/democvičení/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)
• přednášky: 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)
• democvičení/numerická cvičení: Ing. Tomáš Kocourek

Studijní materiály

• Prezentace z přednášek budou průběžně doplňovány.
  • Úvod a motivace do studia formálních jazyků a úvod do regulárních jazyků
  • Pokročilé aspekty regulárních jazyků
  • Bezkontextové jazyky a zásobníkové automaty
  • Turingovy stroje
  • Úvod do složitosti
  • Analýza složitosti a amortizovaná složitost
  • Vlastnoti složitostních tříd a polynomiální redukce
  
  
• Prezentace z loňského roku jsou dostupné zde.


• Studijní text (opora): pdf.


• Materiály k demo cvičením budou průběžně doplňovány:
  • Demo 1: Pojmy diskrétní matematiky, úvod do jazyků a gramatik
  • Demo 2: Regulární jazyky
  • Demo 3: Bezkontextové jazyk + Turingovy stroje a rozhodnutelnost
• Materiály k numerickým cvičením budou průběžně doplňovány:
  • Cvičení 1: Regulární jazyky
  • Cvičení 2: Bezkontextové jazyky
  • Cvičení 3: Turingovy stroje
  • Cvičení 4: Složitost

Referenční literatura

• Č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

Ú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