..:: Martin Kot ::..
Introduction to theoretical computer science

English version of this subpage is under construction

Study text
09.02.2009 Výukový text k teorii jazyků a automatů a k vyčíslitelnosti a složitosti. Výukový text vznikl v letech, kdy předmět neobsahoval matematickou logiku. Ne vše z něj tedy bude skutečně probráno.
09.02.2009 Studijní materiály pro oblast logiky na stránce doc. Duží
09.02.2009 Animace - seznam animací k předmětům Teoretická informatika a Úvod do teoretické informatiky. Jde o animace vytvořené v rámci bakalářských a diplomových prací, animace, které byly součástí přednášek (trochu doplněné, aby dávaly smysl i samostatně bez výkladu), a některé zcela nové.
 
Study text
09.02.2009 Rozšířená verze výukového textu (pro studenty s hlubším zájmem o danou problematiku).
 
Assignments of projects
Všechna zadání povinných zápočtových příkladů v pdf souboru (odkaz bude doplněn)
 
Exercises
09.02.2009 Příklady na 1. cvičení - opakování množin, relací, grafů apod.
24.02.2009 Příklady na 2. cvičení
24.02.2009 Příklady na 3. cvičení
24.02.2009 Příklady na 4. cvičení
24.02.2009 Příklady na 5. cvičení
31.03.2009 Příklady na 6. cvičení
07.04.2009 Příklady na 7. cvičení
07.04.2009 Příklady na 8. cvičení
20.04.2009 Příklady na 9. cvičení
20.04.2009 Příklady na 10. cvičení
 
Lectures - slides
24.02.2009 Organizační informace, požadavky apod., opakování základních pojmů, jazyky a operace s nimi
24.02.2009 Konečné automaty, konstrukce automatů pro průnik, sjednocení a doplněk jazyků, nedeterministické konečné automaty
10.03.2009 Převod nedeterministického konečného automatu na deterministický, konstrukce pro zřetězení jazyků a iteraci jazyka, regulární výrazy, převod regulárního výrazu na konečný automat, normovaný tvar automatu
10.03.2009 Neregularita jazyků, bezkontextové gramatiky
24.03.2009 Zásobníkové automaty, Turingovy stroje
31.03.2009 Chomského hierarchie, problémy, algoritmy, modely výpočtů, Churchova-Turingova teze
07.04.2009 Výpočetní složitost algoritmů, asymptotická notace, rekurentní vztahy
20.04.2009 Výpočetní složitost problémů, třídy složitosti, nedeterministické algoritmy, převeditelnost mezi problémy, NP-úplné problémy, nerozhodnutelné problémy
20.04.2009 Úvod do logiky, o čem je logika, deduktivně platné usuzování