..:: Martin Kot ::..
Teoretická informatika - šk. rok 2014/15
Obecné Aktuálně Ke stažení Referáty Kombinované studium
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í (20.2.2015) 
  • Přehled náplně kursu, informace o požadavcích k zápočtu a o zkoušce, časový plán.
  • Oblast konečných automatů a regulárních jazyků.
2. setkání (6.3.2015) 
  • Bezkontextové jazyky a gramatiky.
  • Zásobníkové automaty.
3. setkání (20.3.2015) 
  • Turingovy stroje, model RAM.
  • Složitost algoritmů.
4. setkání (3.4.2015) 
  • Obecné metody návrhu algoritmů a analýza jejich složitosti.
  • Třídy složitosti problémů, speciálně PTIME, NPTIME, PSPACE.
  • Diskuse ukázkové zápočtové písemky.
5. setkání (17.4.2015) 
  • Zápočtová písemka.
  • Polynomiální převoditelnost problémů, NP-úplnost.
  • Algoritmická nerozhodnutelnost problémů.
6. setkání (15.5.2015) 
  • 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.