..:: Martin Kot ::..
Úvod do teoretické informatiky - šk. rok 2005/6
Obecné Aktuálně Ke stažení Projekty
 
Studijní text
16.02.2006 Výukový text k předmětu od doc. Hliněného
 
Zadání projektů
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ů
 
Příklady na cvičení
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
 
Přednášky - slidy
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)