..:: Martin Kot ::..
Úvod do teoretické informatiky - šk. rok 2008/9
Obecné Aktuálně Ke stažení Projekty
 
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: 
  • 2x10b - písemné práce v průběhu semestru, jedna z oblasti teorie jazyků a automatů a druhá z vyčíslitelnosti a složitosti
  • 15b - písemně vypracované řešení zadaného příkladu formou odborného textu a odprezentování cvičícímu (podrobnější informace na této stránce)
  • Bonusových 15b - písemné vypracování a ústní odreferování jednoho z vybraných obtížnějších příkladů. Za každý příklad má možnost získat body jen první úspěšný řešitel v ročníku.
  • Podmínkou na zápočet je získání alespoň 20 bodů v součtu referátu a zápočtových 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
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ímonday            
J360
Moravec P.
J360
Moravec P.
J360
Křižka F.
J360
Křižka F.
úterýtuesday    
J360
Menšík M.
J360
Menšík M.
   
J317
Dráždilová P.
J317
Dráždilová P.
   
středawednesday  
J360
Číhalová M.
J360
Číhalová M.
   
J360
Číhalová M.
     
J401
Sawa Z.
 
J358
Dráždilová P.
J358
Moravec P.
NA1
Sawa Z., Kot M.
     
J401
Sawa Z.
   
čtvrtekthursday                
J358
Walder J.
J358
Walder J.
   
   
J358
Kuchař Š.
J358
Kuchař Š.
   
J357
Kuchař Š.
       
pátekfriday                            
 
Přednášky
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.
Matematická logika
  • Základy výrokové a predikátové logiky.
  • Analýza vět přirozeného jazyka v jazyce predikátové nebo výrokové logiky.
  • Odvozování důsledků. Množinové / sémantické důkazy.
  • Základy rezoluční metody.
 
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.