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í

  • 4. termín z TINu proběhne v pondělí 21.2. od 10:00 v učebně A218. Počítám, že se dostaví studenti, kteří se přihlásili v dotazníku na moodle a studenti, kteří se se mnou osobně domluvili. Pokud má ještě někdo právo na 4. termín a chtěl by dorazit, prosím napište mi - učebna má omezenou kapacitu.
  • Hromadná konzultace k hodnocení 3. termínu proběhne v pondělí (14.2.) od 10:00 v místnosti A218.
  • Hromadná konzultace k hodnocení 2. termínu proběhne v středu (26.1.) od 13:00 v místnosti A218.
  • 2. termín žávěrečné zkoušky se koná 19.1. od 13:00 v místnosti D105.
    Na řešení budete mít k dispozici 2:30 čistého času.
    S sebou si přineste psací potřeby, průkaz s fotografií a eventuelně láhev s pitím. Papíry dostanete od nás v dostatečném množství. Při použití jakýchkoliv nepovolených pomůcek bude zkouška hodnocena 0 body a budou zváženy další kroky.
    Pokud Vám nebude dobře, prosím zůstaňte doma a omluvte se oficielní cestou. Váš výkon u zkoušky by navíc neodpovídal vaším možnostem.
  • Hromadná konzultace k hodnocení 1. termínu proběhne v pondělí (17.1.) od 12:00 v místnosti A218
  • Konzultace k hodnocení Vašich testů proběhne v úterý (14.12.) po ukončení hromadné konzultace k TINu. Předpokládaný start je kolem 15:30 v místnosti D105. Pokud se někdo z vážných důvodů (např. kolize s výukou či nemoc) nemůže dostavit a chtěl by hodnocení konzultovat, ozvěte se emailem (ceskam@fit.vutbr.cz).
  • Záznam democvičení z 22.10. bohužel není kompletní. Místo toho můžete využít záznam z minulého roku (democvičení z 16.10. 2010), kde se dělají z velké části stejné příklady (ignorujte začátek na regulární jazyky).
  • Na základě Vaších žádostí a současné epidemiologické situace opět zprovozníme youtube stream z přednášek TINu. Stream bude dostupný na odkazu https://youtube.com/playlist?list=PL_eb8wrKJwYskX8EJeqE2n6qJgqNbT-z3.
  • 1. průběžný test se koná dne 22.10. od 14:00 do 16:00. Rozdělení studentů do učeben bude následující:
    • D105: A. - M.
    • E112: N. - Šťa.
    • G108: Ště. - Ž.
    Na řešení budete mít k dispozici 2 hodinu čistého času. S sebou si přineste psací potřeby, průkaz s fotografií a eventuelně láhev s pitím. Papíry dostanete od nás v dostatečném množství. Při použití jakýchkoliv nepovolených pomůcek bude zkouška hodnocena 0 body.
  • Po skončení 1. průběžného testu bude následovat democvičení TIN v místnosti D105 (začátek cca 16:10).
  • V uterý 19.10 začne přednáška v 14:30 a bude probíhat v učebně D0206.
  • Hromadná konzultace k 1. testu proběhem v pondělí 18.10 od 11.00 v místnosti D0206. Jelikož nelze zajistit dostatečnou kapacitu učeben, konzultace bude streamována na odkazu https://youtube.com/playlist?list=PL_eb8wrKJwYskX8EJeqE2n6qJgqNbT-z3 (záznam bude dostupný ihned na youtube).
  • Vzhledem ke schůzce studentů a pedagogů ke kvalitě výuky na FIT, která je plánována na úterý 19.10 od 14:00, jsem se (zatím předběžně) domluvil s panem proděkanem, že TIN začne o 30 minut později (tj. v 14:30). Toto dovolí jak mně, tak i Vám se schůzky aspoň částečně zúčastnit. V prvních zhruba 15-20 minutách budu odpovídat studentům na dotazy ohledně TIN a MSP. Pak budete mít možnost se krátce zapojit do diskuze. V 14:30 se přesuneme na přednášku TIN. Z kapacitních důvodů možná dojde k prohození učeben (tj. TIN by byl v D0206). Prosím sledujte stránky předmětu TIN, kde bude upřesněno, jak a kde bude výuka v úterý 19.10 probíhat.
  • Na základě Vašich žádostí dojde k prohození dema a prvního testu. Tudíž test se bude psát v pátek 22.10. od 14:00 (rozdělení studentů do učeben zveřejníme příští týden na stránkách předmětu). Test bude na 2 až 2.5 hodiny. Poté bude krátká přestávka a budeme pokračovat v demu v místnosti D105.
  • 1. test bude na regulární jazyky a bude obsahovat jak otázky na teorii, tak příklady, které budou testovat pochopení probírané látky. U testu nebudou povoleny žádné studijní materiály. Další organizační pokyny budou zveřejněný příští týden na stránkách předmětu.
  • Záznamy z 3. týdne výuky (2. přednáška a 2. demo na téma pokročilé aspekty regulárních jazyků) budou zveřejněny nejpozději do konce tohoto týdne. Pokud máte k organizaci příštího týdne jakékoliv dotazy, napište mi email či využijte diskuzní fórum předmětu na platformě moodle.vut. Rovněž prosím sledujte aktuální informace na stránkách předmětu, kde budeme průběžně informace doplňovat.

Plán pro zimní semestr 2021


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 20.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 27.9. Státní svátek Konstrukce a transformace pro regulární jazyky
3. týden od 4.10. Regulární jazyky 2 Pumping lemma, Myhill-Nerodova věta a uzávěrové vlastnosti
4. týden od 11.10. Bezkontextové jazyky 1 Pumping lemma, Myhill-Nerodova věta a uzávěrové vlastnosti
5. týden od 18.10. Bezkontextové jazyky 2 Konstrukce a Pumping lemma pro bezkontextové jazyky 22.10. od 14:00 -- První vnitrosemestrální test (Regulární jazyky)
6. týden od 25.10. Turingovy stroje 1 Konstrukce a transformace pro bezkontextové jazyky
7. týden od 1.11. Turingovy stroje 2 Pumping lemma uzávěrové vlastnosti a algoritmy pro bezkontextové jazyky
8. týden od 8.11. Nerozhodnutelnost 1 Turingovy stroje a rozhodnutelnost
9. týden od 15.11. Nerozhodnutelnost 2 Opakování před testem
10. týden od 22.11. Vyčíslitelné funkce a Gödelova nerozhodnutelnost Nerozhodnutelnost 26.11. od 14:00 -- Druhý vnitrosemestrální test (Bezkontextové jazyky + Turingovy stroje)
11. týden od 29.11. Složitost 1 Nerozhodnutelnost
12. týden od 6.12. Složitost 2 Složitost
13. týden od 13.12. Hromadná konzultace Složitost

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

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 6. a 11. týdnu semestru a v 1. týdnu zkouškového období.

Úlohy na procvičení

  • Sbírka příkladů s řešením typových úloh je k dispozici zde (verze z 23.12. 2021). Pokud v řešení naleznete chybu, napište email na ceskam@fit.vutbr.cz -- můžete získat prémiové body.
  • Zadání domácích úloh z minulých let jsou k dispozici zde, nebo v dokumentovém skladu ve Wisu.

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: