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í