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 a dosažené výsledky. Obecné informace o předmětu naleznete na adrese http://www.fit.vut.cz/study/course/TIN/.

Aktuální upozornění

  • Zadána 1. domácí úloha. Termín odevzdání je stanoven na 30.10.
  • Informace o organizaci výuky během uzavření fakulty pro prezenční výuku budou průběžně zveřejňovány ve WISu ve fóru předmětu: TIN: organizace předmětu v období zrušené prezenční výuky

Plán pro zimní semestr 2020


Data Téma přednášky Democvičení (pátek od 13:00) Cvičení (ve skupinách dle rozvrhu) Další aktivity
1. týden od 21.9. Úvod do jazyků a gramatik + regulární jazyky 1 Formální jazyky,operace nad nimi a konstrukce obecných gramatik
2. týden od 28.9. Regulární jazyky 2 Konstrukce pro RJ a Pumping lemma
3. týden od 5.10. Bezkontextové jazyky 1 Konstrukce pro RJ a Pumping lemma
4. týden od 12.10. Bezkontextové jazyky 2 Konstrukce pro bezkontextové jazyky 15.10. od 18:00 -- První vnitrosemestrální test (Regulární jazyky)
5. týden od 19.10. Turingovy stroje 1 Transformace bezkontextových gramatik a jenodznačnost
6. týden od 26.10. Turingovy stroje 2 Pumping lemma a pokročilé konstrukce pro bezkontextové jazyky
7. týden od 2.11. Nerozhodnutelnost 1 Turingovy stroje 1
8. týden od 9.11. Nerozhodnutelnost 2 Opakování před testem
9. týden od 16.11. Nerozhodnutelnost 19.11. od 18:00 -- Druhý vnitrosemestrální test (Bezkontextové jazyky + Turingovy stroje)
10. týden od 23.11. Vyčíslitelné funkce a Gödelova nerozhodnutelnost Nerozhodnutelnost
11. týden od 30.11. Složitost 1 Složitost 1
12. týden od 7.12. Složitost 2 Složitost 2
13. týden od 14.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 13: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. Jejich zadání se postupně bude objevovat v této části stránek předmětu. Úlohy se budou odevzdávat ve 6. a 11. týdnu semestru a v 1. týdnu zkouškového období.

Pozor na opisování! Při opravování úkolů více než dříve kontrolujeme opisování. Opsané nebo i jen částečně opsané úkoly jsou hodnoceny 0 body, a to pro autora opsaného i pro autora zdrojového textu. Vážně, doopravdy, kontrolujeme to a rozdáváme nuly. Můžete řešení úkolu probrat s kolegy, ale nepřežeňte to, a určitě si neukazujte vypracovaná řešení. Tak jen velmi těžko vytvoříte řešení, kde se na stejných řádcích vyskytuje skoro stejný text... Buďte opatrní na to, komu svůj úkol dáváte ke čtení nebo kam jej posíláte. Řada případů opisování se děje bez autorova vědomí. Dále upozorňujeme, že některá internetová fóra jsou otevřená a nejsou anonymní. Často obsahují chyby, podle kterých se potom zvlášť dobře identifikují podobná vypracování úkolů.

Vypracování a odevzdávání úloh:

Úlohu můžete napsat rukou, na počítači, nebo libovolně kombinovat tyto možnosti (např. napsat text na počítači a doplnit obrazky rukou). Ručně napsané části pak naskenujte, nebo nafoťte a celou úlohu převeďte do jednoho souboru ve formátu PDF. Odevzdávat se bude prostřednictvím https://moodle.vutbr.cz

Seznam domácích úloh:

  • Úkol 1 (5 bodů): pdf - opravuje A. Rogalewicz, termín odevzdání: pátek 30.10. do 23:59. Soubor PDF odevzdejte prostřednictvím https://moodle.vutbr.cz
  • Úkol 2 (5 bodů): pdf - opravuje O. Lengál, termín odevzdání: pátek 4.12. do 23:59. Soubor PDF odevzdejte prostřednictvím https://moodle.vutbr.cz
  • Úkol 3 (5 bodů): pdf - opravuje L. Holík, termín odevzdání: úterý 5.1. do 23:59. Soubor PDF odevzdejte prostřednictvím https://moodle.vutbr.cz

Úlohy na procvičení

Zde se budou postupně (koncem každého týdne) přidávat úlohy na procviční aktuálně probírané látky Doporučujeme si tyto úlohy projít, zkusit vyřešit a v případě nejasnosti se zeptat (domluvit si konzultaci), a to pokud možno ještě před zkouškou... V případě zájmu/potřeby je možno najít také jistě řadu dalších zadání na webu -- najdete-li něco zajímavého i pro ostatní, pošlete odkaz do fóra předmětu.

Příklady označené * jsou náročnější a patří do kategorie příkladů do domácích úloh. Proto se nebojte, že by se příklady této náročnosti mohly objevit na testech případě na zkoušce.

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: