..:: Martin Kot ::..
Teoretická informatika - šk. rok 2008/9
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 (2 po 12 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ých alespoň 8 bodů ze 24 z písemek.
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
 
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í        
C3
Jančar P.
               
úterý                
D212
Škňouřilová P.
       
středa                            
čtvrtek
D209
Kot M.
D209
Kot M.
       
C3
Jančar P.
       
D210
Sawa Z.
D210
Sawa Z.
D209
Škňouřilová P.
               
   
D212
Škňouřilová P.
   
D210
Kot M.
           
pátek                            
sobota                            
 
Přednášky
Jazyky a Automaty
  • Úvod ke kursu: celkový přehled. Základní pojmy z oblasti formálních jazyků. Konečné automaty a jazyky jimi rozpoznávané. Modulární návrh konečných automatů.
  • Dosažitelné stavy u konečných automatů, normovaný tvar. Minimální automaty a algoritmus minimalizace. Regulární a neregulární jazyky; Charakterizace regulárních jazyků umožňující důkazy neregularity.
  • Nedeterministické konečné automaty; jejich uplatnění v návrhu deterministických konečných automatů. Regulární operace. Regulární výrazy jako prostředek popisu regulárních jazyků.
  • Ekvivalence konečných automatů, regulárních výrazů a regulárních gramatik. Uzávěrové vlastnosti třídy regulárních jazyků. Další varianty konečně stavových modelů (dvoucestné konečné automaty, konečně stavové převodníky, ...).
  • Bezkontextové gramatiky a jazyky. Ilustrace významu bezkontextových gramatik pro (syntaxí řízený) překlad, speciálně na gramatice generující regulární výrazy. Jednoznačné gramatiky. Redukované a nevypouštějící bezkontextové gramatiky.
  • Zásobníkové automaty. Vztah mezi zásobníkovými automaty a bezkontextovými gramatikami. Deterministické zásobníkové automaty. Uzávěrové vlastnosti třídy bezkontextových jazyků.
  • Chomského normální forma bezkontextových gramatik. Pumping lemma pro bezkontextové jazyky a jeho použití. Obecné generativní gramatiky. Turingovy stroje. Chomského hierarchie.
  • Složitost algoritmu. Model RAM. Asymptotické odhady růstu funkcí, značení. Obecné metody návrhu (efektivní prohledávání, hltavé algoritmy, ...) a analýza složitosti vybraných (polynomiálních) algoritmů.
  • Další metody návrhu polynomiálních algoritmů (rozděl a panuj, dynamické programování, ...). 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.
  • Nedeterministické Turingovy stroje. Třída NPTIME. Otázka `P=NP~?'. Polynomiální převeditelnost mezi problémy. NP-úplnost a konkrétní NP-úplné problémy.
  • 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ů.
  • 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.