Teoretická informatika 1 - informace



Na této stránce budete nalézat aktuální informace k předmětu TI1, 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/TI1/.


Vyučující



Aktuální upozornění

  • Termíny zkoušek:
    • Půlsemestrální zkouška: pátek 12.11.2004 ve 13:00-14:00.
    • Řádný termín: pondělí 17.1.2005, 15:30-17:30.
    • 1. opravný termín: pátek 28.1.2005, 12:00-14:00.
    • 2. opravný termín: pátek 4.2.2005, 12:00-14:00.




Orientační program cvičení


cvičení program
1
  • opakování pojmů z algebry (množina, relace, zobrazení, tranzitivní a reflexivní uzávěr)
  • operace nad řetězci, formální jazyky a operace nad nimi
  • obecná gramatika, derivace v gramatice
  • Chomského hierarchie jazyků
2
  • NKA a DKA
  • determinizace NKA
  • vztah regulárních gramatik a KA
3
  • minimalizace DKA
  • regulární výrazy
  • rovnice nad RV
  • převody RV a KA
4
  • Pumping lemma
  • vlastnosti regulárních jazyků
  • algoritmy pro práci s KA
5
  • bezkontextové gramatiky, levá a pravá derivace, derivační strom, fráze
  • transformace bezkontextových gramatik
6
  • zásobníkové automaty, syntaktická analýza
  • Chomského a Greibachové normální formy
  • Pumping lemma pro bezkontextové jazyky
  • uzávěrové vlastnosti bezkontextových jazyků



Studijní literatura



Domácí úkoly


Součástí bodového hodnocení předmětu je i 6 domácíh úloh. Zadány budou s předstihem jednoho týdne před demo-cvičením a odevzdávat se budou v týdnu po demo-cvičení: V prvním týdnu výuky bude zadán první úkol, bude ho možno konzultovat v týdnu druhém na cvičení, v týdnu třetím bude odevzdán první úkol a zadán druhý atd.

Vypracované úkoly odevzdávejte na sekretariát ústavů FIT do přihrádky Tomáše Vojnara nebo Vladimíra Marka podle toho, kdo daný úkol bude opravovat (viz níže). Seznam domácích úloh:
  • Úkol 1 (30 bodů): pdf -- opravuje T. Vojnar
  • Úkol 2 (30 bodů): ps pdf -- opravuje V. Marek
  • Úkol 3 (30 bodů): pdf -- opravuje T. Vojnar
  • Úkol 4 (30 bodů): ps pdf -- opravuje V. Marek
  • Úkol 5 (40 bodů): pdf -- opravuje T. Vojnar
  • Úkol 6 (40 bodů): ps pdf -- opravuje V. Marek, odevzdání do 6.1.2005


PESIM

Stáhnout lze zde: tar.gz zip