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í

  • Hromadná konzultace k hodnocení 2. testu proběhne v pondělí 27.11. po přednášce z TINu (tj. zhruba od 13.15) v místnosti D105. Pro účely zpětné vazby jsme zveřejnili zadání 2. testu: varianta A a varianta B.
  • Příští pondělí (tj. 13.11.) od 8:00 proběhne 2. test z TINu. Test bude zaměřen na bezkontextové jazyky a Turingovy stroje včetně důkazů (částečné) rozhodnutelnosti (další informace viz hromadný email). Zde najdete ukázku 2. testu z minulého roku.
  • V čtvrtek 9.11. od 14:00 se v místnosti M104+M105 bude konat náhradní termín za 1.test, kterého se mohou zúčastnit studenti, kteří byli řádně omluveni (nemoc, jiná omluvenka) z řádného termínu. Abychom připravili správný počet zadaní, prosím požádejte do 7.11. 23:59 o náhradní termín pomocí skupiny založené v e-learningu.
  • Hromadná konzultace k hodnocení 1. testu proběhne v pondělí 23.10. po přednášce z TINu (tj. zhruba od 13.00 – přednáška bude zkrácena) v místnosti D105.
  • Pro účely zpětné vazby jsme zveřejnili zadání 1. testu: varianta A, varianta B a komentář k řešení a nejčastější chyby.
  • 1. test z TINu se uskuteční tento pátek (to je 13.10.). Na základě Vašich žádostí dojde k prohození dema a testu. Tudíž test se bude psát od 14:00 v učebně D105. Poté se uskuteční democvičení ve stejné učebně.

    Plán pro zimní semestr 2023


    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 18.9. Úvod a motivace do studia formálních jazyků + regulární jazyky 1 Opakování diskrétní matematiky + formální jazyky
    2. týden od 25.9. Regulární jazyky 2 Regulární jazyky
    3. týden od 2.10. Bezkontextové jazyky 1 Regulární jazyky
    4. týden od 9.10. Bezkontextové jazyky 2 Bezkontextové jazyky pátek 13.10. od 17:00 -- První vnitrosemestrální test (Regulární jazyky)
    5. týden od 16.10. Turingovy stroje 1 Bezkontextové jazyky 1
    6. týden od 23.10. Turingovy stroje 2 + vztah TS k vyčíslitelným funkcím Bezkontextové jazyky 2 Odevzdávání 1. úkolu
    7. týden od 30.10. Nerozhodnutelnost Turingovy stroje a rozhodnutelnost
    8. týden od 6.11. Logika 1 (axiomatizace) Nerozhodnutelnost
    9. týden od 13.11. Logika 2 (Gödelova nerozhodnutelnost) Nerozhodnutelnost pátek 17.11. svátek pondělí 13.11. od 8:00 -- Druhý vnitrosemestrální test (Bezkontextové jazyky + Turingovy stroje a rozhodnutelnost)
    10. týden od 20.11. Složitost 1 Logika 1 Odevzdávání 2. úkolu
    11. týden od 27.11. Složitost 2 Logika 2
    12. týden od 4.12. Složitost 3 Složitost
    13. týden od 11.12. Hromadná konzultace Složitost Odevzdávání 3. úkolu

    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


    Úlohy na procvičení

    • Sbírka příkladů s řešením typových úloh je k dispozici zde (verze z 8.12.2023). 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: