..:: Martin Kot ::..
Teoretická informatika - šk. rok 2012/13
Obecné údaje
Garant:  Prof. RNDr. Petr Jančar, CSc.
Počet kreditů:  8
Ukončení:  Zkouška
Web předmětu:  http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm
Tutor: 
 
Rozdělení bodů
Zápočet: 
  • 24b - krátká písemka (cca 45 minut), psát se bude na 5. tutoriálu
  • 11b - písemně vypracované a ústně předvedené řešení zadaného příkladu (podrobnější informace pod záložkou "Referáty")
  • Podmínkou na zápočet je předvedení referátu (uznané vyučujícím za dostatečné) a získaných alespoň 8 bodů z 24 z písemky.
Zkouška: 
  • 65b - písemná zkouška (minimálně je nutné získat 25b pro úspěšné absolvování předmětu)
  • 0b - nepovinná ústní zkouška - možnost upravit body v obou směrech na základě konzultací nad písemkou
 
Upozornění
  • Aktuální důležité informace se budou objevovat pod záložkou Aktuálně.
  • Zásady pro vypracování referátů najdete pod záložkou Referáty.
  • Různé užitečné materiály ke stažení najdete pod záložkou Ke stažení.
  • Sledujte i oficiální stránku předmětu, kde garant předmětu prof. Jančar zveřejňuje informace platné pro všechny studenty předmětu TI.
 
Průběh setkání
1. setkání (22.2.2013) 
  • Přehled náplně kursu, informace o požadavcích k zápočtu a o zkoušce, časový plán.
  • Formální jazyky a operace s nimi.
  • Konečné automaty.
2. setkání (8.3.2013) 
  • Redukce konečného automatu.
  • Regularita jazyků.
  • Zobecněné nedeterministické konečné automaty a jejich prevod na deterministické automaty.
3. setkání (22.3.2013) 
  • Regulární výrazy a jejich převod na ZNKA.
  • Bezkontextové gramatiky.
4. setkání (5.4.2013) 
  • Redukce gramatiky, jazykové operace na gramatikách.
  • Zásobníkové automaty.
  • Hierarchie jazyků.
  • Diskuse ukázkové zápočtové písemky.
5. setkání (19.4.2013) 
  • Zápočtová písemka.
  • Turingovy stroje.
  • Stroj RAM.
6. setkání (3.5.2013) 
  • Diskuse opravených písemek.
  • Převoditelnost problémů, třídy složitosti problémů.
  • Algoritmická nerozhodnutelnost problémů.
7. setkání (17.5.2013) 
  • Informace o zkoušce, diskuse ukázkové zkouškové písemky.
  • Prezentace referátů.
 
Studijní literatura
Základní
Další
  • T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms. The MIT Press, 1990.
  • John E. Hopcroft a Jeffrey D. Ullman: Formálne jazyky a automaty. Alfa Bratislava 1978.
  • J. Gruska: Foundation of Computing, International Thomson Computer Press 1997.
  • D. Kozen: Automata and Computability, Undergraduate Text in Computer Science, Springer Verlag 1997.
  • M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company 1997.