..:: Martin Kot ::..
Teoretická informatika - šk. rok 2006/7
Obecné Aktuálně Ke stažení Referáty
 
Obecné údaje
Garant:  Doc. RNDr. Petr Jančar, CSc.
Počet kreditů:  8
Rozsah:  4/4/0/0 (V praxi: 4/2/0/2)
Ukončení:  Zkouška
Web předmětu:  http://www.cs.vsb.cz/jancar/TEORET-INF/teoret-inf.htm
Přednášející:  ,
Cvičící:  ,
 
Rozdělení bodů
Zápočet: 
  • 24b - krátké písemky (4 po 6 bodech)
  • 11b - písemně vypracované a ústně předvedené řešení zadaného příkladu (podrobnější informace na této stránce)
  • Podmínkou na zápočet je předvedení řešení příkladu (uznáné cvičícím za dostatečné) a získané alespoň 4 body ze 6 z alespoň 2 písemek.
Zkouška: 
  • 65b - písemná zkouška
  • 0b - nepovinná ústní zkouška - možnost upravit body v obou směrech na základě konzultací nad písemkou
 
Anotace
Kurs rozšiřuje a prohlubuje teoretické základy informatiky nabyté v bakalářském studiu, speciálně v oblastech teorie jazyků a automatů a teorie vyčíslitelnosti a složitosti.
 
Rozvrh hodin
7:15
8:00
8:00
8:45
9:00
9:45
9:45
10:30
10:45
11:30
11:30
12:15
12:30
13:15
13:15
14:00
14:15
15:00
15:00
15:45
16:00
16:45
16:45
17:30
17:45
18:30
18:30
19:15
pondělí        
Všichni
C3
Jančar P.
           
úterý                            
středa
LN180
K309
Sawa Z.
           
LN177
D212
Sawa Z.
LN178
D210
Kot M.
   
LN181
K308
Kot M.
           
LN176
D210
Kot M.
LN179
D212
Sawa Z.
   
čtvrtek                            
pátek                            
 
Přednášky
Jazyky a Automaty
  • Úvod ke kursu: celkový přehled a motivace. Základní pojmy z oblasti formálních jazyků. Konečné automaty.
  • Nedeterministické konečné automaty a jejich vztah k deterministickým.
  • Regulární operace, regulární jazyky. Uzávěrové vlastnosti třídy regulárních jazyků.
  • Regulární výrazy, vztah ke konečným automatům.
  • Minimalizace konečných automatů.
  • Pumping lemma pro regulární jazyky a jeho použití.
  • Další varianty konečně stavových modelů (dvoucestné konečné automaty, konečně stavové převodníky, ...)
  • Bezkontextové gramatiky a jazyky. Redukované gramatiky, Chomského normální forma.
  • Zásobníkové automaty. Vztah mezi zásobníkovými automaty a bezkontextovými gramatikami.
  • Uzávěrové vlastnosti třídy bezkontextových jazyků. Deterministické zásobníkové automaty.
  • Pumping lemma pro bezkontextové jazyky.
  • Obecné generativní gramatiky. Chomského hierarchie. Turingovy stroje, rekurzivní a rekurzivně spočetné jazyky.
  • Složitost algoritmu. Model RAM. Asymptotické odhady, značení.
  • Analýza složitosti vybraných (polynomiálních) algoritmů. Nejhorší vs. průměrný případ.
  • Problémy, třídy složitosti problémů, horní a dolní odhady složitosti problémů. Vzájemná polynomiální simulace rozumných výpočetních modelů. Třída PTIME, její robustnost, význam.
  • Třída NPTIME. Otázka "P=NP?". Polynomiální převeditelnost mezi problémy. NP-úplnost. Další třídy časové i prostorové složitosti a jejich vzájemné vztahy.
  • Dokazatelně nezvládnutelné problémy. Church-Turingova teze. Rozhodnutelnost a částečná rozhodnutelnost problémů.
  • Rekurzivní a rekurzivně spočetné množiny (jazyky). Rekurzivní a částečně rekurzivní funkce. Univerzální Turingův stroj. Metoda diagonalizace, nerozhodnutelnost problému zastavení.
  • Algoritmická převeditelnost, další nerozhodnutelné problémy. Riceova věta.
  • Nástin problematiky aproximačních, pravděpodobnostních, paralelních a distribuovaných algoritmů.
 
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.