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.vutbr.cz/study/courses/TIN/.

Aktuální upozornění

  • Zveřejněna 2. domácí úloha. Termín odevzdání: úterý 20.11. v 17:00.
  • Půlsemestrální zkouška se bude konat v pondělí 5.11. ve 13:00. Rozsah zkoušené látky: odpřednášená do 29.10., tj. po varianty zásobníkového automatu včetně (podle slidů z přednášek).
  • 1. termín z TIN se bude konat ve čtvrtek 3.1. od 14:00. Rozdělení studentů do učeben bude následující:
    • D105: A. - O.
    • E112: P. - Ž.
    • Na řešení budete mít k dispozici 2 hodiny čistého času. S sebou si přineste psací potřeby, průkaz s fotografií a eventuelně lahev 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.

Další upozornění

  • Upozornění: V tomto akademickém roce nebudou studentům k dispozici záznamy přednášek ani jejich streaming.

  • Odevzdané domácí úkoly vám nebudou po ohodnocení vráceny. Bude pouze možnost do opravených úkolů nahlédnout v rámci specielně vyhlášených konzultačních hodin. Pokud si chcete svoje řešení ponechat, vytvořte si jeho kopii jestě před odevzdáním.

  • Pro získání bodů ze závěrečné semestrální zkoušky je nutné tuto zkoušku složit tak, aby byla hodnocena nejméně 25 body. V opačném případě bude zkouška hodnocena 0 body.

  • Diskusní fóra k předmětu: V IS FIT jsou pro předmět TIN zřízeny diskusní fóra. Využívejte je prosím k diskusi problémů, nejasností apod., na které při studiu probírané látky narazíte. Budeme Vaši diskusi sledovat a v případě potřeby do ní vstoupíme -- nebude zde tedy nebezpečí zavádějících informací, které se zhusta vyskytují na různých utajených fórech (a poté pronikají ve značném počtu kopií do zkoušek či řešení úkolů). Dáme ovšem nejprve prostor Vám, abyste si problémy, na které narazíte, zkusili vyřešit sami: tím že se pokusíte pomoci Vašim kolegům se také dost naučíte.

  • POZOR!!! Při opravování úkolů budou ohodnoceny opsané úkoly 0 body! Můžete možné řešení úkolu probrat s kolegy, ale pak ho již na papír přeneste samostatně. Při takovém postupu jen velmi těžko obdržíte řešení, kde se na stejných řádcích vyskytuje přesně stejný text...


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

Domácí úkoly

Součástí bodového hodnocení předmětu jsou 4 domácí úlohy. Jejich zadání se postupně bude objevovat v této části stránek předmětu.

Vypracované úkoly (stačí je napsat rukou, ale prosím čitelně) odevzdávejte na dozornu ve výpočetním středisku. Pro odevzdávání úkolů platí následující pravidla:
  • Úlohy se odevzdávají navrch krabice v pořadí, ve kterém studenti na dozornu přijdou. Požadavek umístění vašeho řešení hlouběji do krabice může služba zaznamenat na první stranu řešení. Takto označená řešení budou automaticky hodnocena srážkou 3 bodů.
  • Odevzdané úlohy se zásadně nevracejí zpět na dopracování.
  • Služba může požadovat předložení průkazu identity. Pokud odevzdávající odmítne průkaz předložit, služba toto zaznamená na první stranu řešení. Takto označená řešení budou automaticky hodnocena 0 body.
  • Úlohy mohou být odevzdány v zastoupení. V případě kontroly průkazu identity služba může napsat na první stranu řešení odevzdáno v zastoupení panem X.Y.
  • Student, který odevzdá více než jedno řešení domácí úlohy (původní, opravené, znovu opravené, ...) získá body podle následujícího vzorce: X - (Y-1), kde X je dosažený bodový zisk z nejlepšího řešení a Y je počet odevzdaných řešení.
  • Odevzdání po termínu může být hodnoceno srážkou až 5 bodů. Služba má právo tento fakt na první stranu odevzdaného řešení zaznamenat. Všechny úlohy odevzdané po takto označené úloze jsou brány taktéž jako odevzdané po termínu a hodnocené minimálně stejnou bodovou srážkou (i když na nich není napsána poznámka o pozdním odevzdání).
  • Služba není povinna odpovídat na jakékoliv dotazy studentů týkajících se předmětu TIN a domácích úloh. Dotazy směřujte přímo na vyučující TIN.


Seznam domácích úloh:
  • Úkol 1 (5 bodů): pdf - opravuje A. Rogalewicz, termín odevzdání: úterý 23.10. do 17:00. Krabice bude na dozornu umístěna během čtvrtka 18.10.

  • Úkol 2 (5 bodů): pdf - opravuje L. Holík, termín odevzdání: úterý 20.11. do 17:00.

  • Úkol 3 (5 bodů): pdf - opravuje A. Rogalewicz, termín odevzdání: pátek 14.12. do 12:00.

  • Úkol 4 (5 bodů): pdf - opravuje L. Holík, termín odevzdání: čtvrtek 3.1. na zkoušce.


Úlohy na procvičení

Doporučujeme si následující ú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.
  • domácí úlohy z předchozích let: jazyky a gramatiky obecně, regulární jazyky (KA, G3, RV), bezkontextové jazyky (ZA, G2).
  • Další zadání jsou k dispozici v dokumentovém skladu ve WISu.

Odkazy na WWW

Jsou průběžně doplňovány...
  • 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.
    • AT&T FSM Library. Dlouhá řada aplikací skutečně z nejrůznějších oblastí (multimédia, sítě, ...).
    • 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).

  • Kleeneho algebry: D. Kozen. A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events. Technical Report TR 90-1123, Dept. of Comp. Sci., Cornell University, Ithaca, NY, USA, 1990.

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

  • Třídy složitosti:
  • 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).

  • What is computation?

  • Zajímavosti: