..:: Martin Kot ::..
Teoretická informatika - šk. rok 2011/12
Obecné Aktuálně Ke stažení Referáty Kombinované studium
Obecné údaje
Garant:  Prof. RNDr. Petr Jančar, CSc.
Počet kreditů:  8
Rozsah:  4/2/0/0
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ísemka (2 části 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í referátu (uznané cvičí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
 
Anotace
Kurs prohlubuje a rozšiřuje teoretické základy v oblasti formálních jazyků, automatů, gramatik, výpočtových problémů a algoritmů, které student měl v základní formě nabýt v bakalářském studiu.
 
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í    
J360
Šaloun P.
C3
Jančar P.
     
D209
Šaloun P.
   
úterý                            
středa
D210
Šaloun P.
D210
Šaloun P.
J358
Kot M.
       
B5 (lichý týden)
Jančar P.
   
D209
Kot M.
                       
čtvrtek            
J360
Sawa Z.
J360
Sawa Z.
       
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.
Vyčíslitelnost a složitost
  • 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.