..:: Martin Kot ::..
Úvod do teoretické informatiky - šk. rok 2012/13
Obecné Aktuálně Ke stažení Kombinované studium
Obecné údaje
Garant:  Ing. Zdeněk Sawa, Ph.D.
Počet kreditů:  6
Rozsah:  2/2/0/2
Ukončení:  Zkouška
Oficiální stránka:  http://www.cs.vsb.cz/sawa/uti/
Přednášející: 
Cvičící:  , , ,
, , ,
, , ,
 
Rozdělení bodů
Zápočet: 
  • 22b - písemná práce v průběhu semestru, rozdělena na dvě části - jedna z oblasti logiky a druhá z teorie jazyků a automatů
  • Podmínkou na zápočet je získání alespoň 7 bodů ze zápočtové písemky
Zkouška: 
  • 78b - písemná zkouška rozdělená na 3 části po 26 bodech (logika, jazyky a automaty, vyčíslitelnost a složitost).
  • Z každé části je nutno získat alespoň 10 bodů pro úspěšné absolvování zkoušky.
  • 0b - nepovinná ústní zkouška - možnost upravit body v obou směrech na základě konzultací nad písemkou
 
Anotace
Cílem je naučit posluchače zacházet se základními pojmy teoretické informatiky a používat je v běžné programátorské praxi. Zároveň jsou předmětem podány teoretické základy nutné pro další studium informatiky na vyšším stupni.
 
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í                            
úterý    
D213
Šurkovský M.
D210
Takács O.
   
K308
Robenek D.
K309
Robenek D.
   
K309
Šurkovský M.
K308
Takács O.
D213
Dráždilová P.
               
středa    
C3
Sawa Z.
   
C3
Sawa Z.
           
   
JD358
Menšík M.
                   
K309
Dráždilová P.
K309
Dráždilová P.
K309
Menšík M.
               
čtvrtek    
D209
Meca O.
K309
Meca O.
JD358
Macek J.
JD358
Macek J.
D210
Vích L.
D213
Vích L.
K309
Ciprich N.
D210
Ciprich N.
   
JA401
Sawa Z.
JA401
Sawa Z.
       
pátek                            
sobota                            
 
Přednášky
Matematická logika
  • Logika. Důkazy. Logické spojky.
  • Další logické spojky. Syntaxe a sémantika v logice.
  • Tabulková metoda. Ekvivalentní úpravy. Predikátová logika.
  • Kvantifikátory. Naivní teorie množin.
Jazyky a Automaty
  • Formální jazyky. Konečné automaty.
  • Konstrukce konečných automatů. Nedeterministické konečné automaty.
  • Převod nedeterministických konečných automatů na deterministické. Regulární výrazy.
  • Bezkontextové gramatiky jazyky.
Vyčíslitelnost a složitost
  • Algoritmické problémy. Modely výpočtu.
  • Asymptotická notace. Složitost algoritmů.
  • Složitost problémů. Třídy složitosti. Převody mezi problémy. Třída NPTIME.
  • Algoritmicky nerozhodnutelné problémy.
 
Studijní literatura
Základní
Další
  • M. Chytil: Automaty a gramatiky, SNTL Praha, 1984.
  • 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.
  • Ding-Zhu Du, Ker-I Ko: Problem Solving in Automata, Languages, and Complexity, Wiley, 2001.
Literatura není povinná, pouze doporučená, na přednáškách a cvičeních se dozvíte vše potřebné. (Toto není recitační kroužek, takže se nemusíte učit nazpaměť pasáže z knih. Lépe řečeno, nazpaměť se ani učit nesmíte, látce je třeba porozumět.)
Pokud máte k dispozici jiné úvodní knihy či skripta pro daný předmět, klidně je můžete používat. Jedna věc však platí pro všechny -- některé věci na přednášce se mohou líšit od literatury (například odchylky v definicích pojmů, které nejsou jednoznačně ustálené) a u zkoušky pak platí to, co bylo na přednášce.