Teoretická informatika (TIN) - informace pro studenty


Tato stránka obsahuje aktuální informace k předmětu TIN, studijní materiály, termíny zkoušek, domácí úkoly atd.

Domácí úlohy a diskuzní fóra jsou k dispozici na e-learningu VUT.

Aktuální upozornění

  • 1.termín zkoušky se koná v úterý 3.1. od 13:00. Rozdělení studentů do místností je následující:
    • D105: A.-Ml.
    • D0206: Mo.-Ž.
    S sebou psací potřeby, průkaz s fotografií a eventuálně lahev s pitím. Na vypracování budete mít 150 minut.

Plán pro zimní semestr 2022


Data Téma přednášky Democvičení (pátek od 14:00) Cvičení (ve skupinách dle rozvrhu) Další aktivity
1. týden od 19.9. Úvod do jazyků a gramatik + regulární jazyky 1 Formální jazyky,operace nad nimi a konstrukce pro regulární jazyky
2. týden od 26.9. Regulární jazyky 2 Pumping lemma, Myhill-Nerodova věta a uzávěrové vlastnosti
3. týden od 3.10. Bezkontextové jazyky 1 Regulární jazyky
4. týden od 10.10. Bezkontextové jazyky 2 Konstrukce a Pumping lemma pro bezkontextové jazyky 14.10. od 12:00 -- První vnitrosemestrální test (Regulární jazyky)
5. týden od 17.10. Turingovy stroje 1 Konstrukce a transformace pro bezkontextové jazyky
6. týden od 24.10. Turingovy stroje 2, vztah TS k vyčíslitelným funkcím * svátek 28.10.
Pumping lemma uzávěrové vlastnosti a algoritmy pro bezkontextové jazyky
7. týden od 31.10. Nerozhodnutelnost 1 Turingovy stroje a rozhodnutelnost
8. týden od 7.11. Nerozhodnutelnost 2 Opakování před testem
9. týden od 14.11. Gödelova nerozhodnutelnost Nerozhodnutelnost 18.11. od 12:00 -- Druhý vnitrosemestrální test (Bezkontextové jazyky + Turingovy stroje)
10. týden od 21.11. Složitost 1 Nerozhodnutelnost
11. týden od 28.11. Složitost 2 Složitost
12. týden od 5.12. Složitost 3 Gödelova nerozhodnutelnost a složitost
13. týden od 12.12. Hromadná konzultace Složitost Změna, tento týden proběhne democvičení.

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í.


Vyučující


Studijní materiály


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 4. a 8. 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 18.11. 2022). 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

Jsou průběžně doplňovány...
  • 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:
  • 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:

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

  • Zajímavosti: