..:: Martin Kot ::..

Introduction to theoretical computer science

English version of this subpage is under construction

Study text

16.02.2006

Výukový text k předmětu od doc. Hliněného

Assignments of projects

11.04.2006	Všechna zadání povinných zápočtových příkladů v pdf souboru
24.04.2006	Všechna zadání bonusových příkladů

Exercises

25.05.2006	Ukázkové zadání zkouškové písemky
16.02.2006	Příklady na cvičení v prvním týdnu - opakování množin, relací, grafů apod.
27.02.2006	Příklady k 1. přednášce - jazyky a operace s nimi. Doplněny chybějící obrázky k příkladům 5. a 6.
16.02.2006	Příklady k 2. přednášce - konečné automaty a operace s nimi
13.03.2006	Příklady k 3. přednášce - vyhledávání řetězců, regulární výrazy
16.02.2006	Příklady k 4. přednášce - minimalizace konečných automatů, regularita jazyků
25.03.2006	Příklady k 5. přednášce - bezkontextové gramatatiky a jazyky
05.04.2006	Příklady k 6. přednášce - zásobníkové automaty, Turingovy stroje
17.04.2006	Příklady k 7. přednášce - převody mezi výpočetními modely
29.03.2006	Příklady k 8. přednášce - časová složitost, asymptotické odhady složitosti
17.04.2006	Příklady k 9. přednášce - analýza složitosti rekurentních algoritmů
29.03.2006	Příklady k 10. přednášce - převody mezi problémy, příslušnost do třídy NP
29.03.2006	Příklady k 11. přednášce - NP-úplné problémy

Lectures - slides

04.04.2006	Soubor se všemi slidy (přednášky 1. - 12.), cca 8.8MB velké pdf
01.03.2006	Slidy k 1. přednášce (úvod s požadavky, motivace)
09.03.2006	Slidy k 2. přednášce (deterministické a nedeterministické konečné automaty)
09.03.2006	Slidy k 3. přednášce (nedeterministické konečné automaty - opakování a rozšíření na zobecněné, regularní výrazy, ekvivalence regulárních výrazů a konečných automatů)
25.03.2006	Slidy k 4. přednášce (minimalizace KA, normovaný tvar KA, ekvivalence KA, neregulární jazyky - pumping lemma a věta Myhilla-Neroda)
25.03.2006	Slidy k 5. přednášce (bezkontextové gramatiky - definice, redukované, nevypouštějící, Greibachové a Chomského normální formy)
30.03.2006	Slidy k 6. přednášce (zásobníkové automaty, ekvivalence zásobníkových automatů a bezkontextových gramatik, Turingovy stroje, generativní gramatiky, Chomského hierarchie)
04.04.2006	Slidy k 7. přednášce (algoritmy, modely výpočtu, rozhodnutelné a nerozhodnutelné problémy)
19.04.2006	Slidy k 8. přednášce (pojem složitosti algoritmu a problému, asymptotická notace složitosti, třída PTIME)
03.05.2006	Slidy k 9. přednášce (rekurentní vztahy, třídy složitosti, dolní a horní odhady složitosti)
10.05.2006	Slidy k 10. přednášce (nedeterminismus, třída NPTIME, NP-úplnost, Cookova věta)
18.05.2006	Slidy k 11. přednášce (důkazy NP-úplnosti)
25.05.2006	Slidy k 12. přednášce (randomizované algoritmy, aproximační algoritmy)