..:: Martin Kot ::..
Úvod do teoretické informatiky - šk. rok 2006/7
Obecné Aktuálně Ke stažení Projekty
 
Základní studijní materiály
21.02.2007 Výukový text k předmětu (Jedná se o první verzi, která se bude v průběhu semestru měnit. Proto nedoporučujeme si tisknout celý text v současné podobě, ale spíše vždy aktuální učivo studovat z aktuální verze textu. Toto je referenční kopie zveřejněná na začátku semestru pro porovnání změn s aktuálními kopiemi.)
23.03.2007 Výukový text k předmětu - aktuální, ale stále ne definitivní, verze.
Seznam změn (proti referenční kopii z 21.2.2007):
  • 26.2.2007 - Úpravy v první kapitole a několik typografických úprav
  • 12.3.2007 - V obrázku 3.3 změněn stav q3 na nepřijímající a opraveny další obrázky, kde se špatně zarovnaly stavy vůči přechodům.
  • 23.3.2007 - Opravena chyba v řešení Řešeného příkladu 4.4. a v zobrazení Řešeného příkladu 4.3.
  • 10.4.2007 - Vyřazena Cvičení 8.26 a 8.27, protože obsahovaly příklady k učivu neprobíránému v této verzi textu.
06.06.2007 Nový výukový text - zcela přepsaný výukový text, který je možné použít k přípravě na zkoušku. K absolvování předmětu stačí informace z jednoho z textů (původního nebo nového), v novém se snažíme o srozumitelnější výklad.
21.05.2007 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é.
 
Rozšiřující studijní materiály
21.02.2007 Rozšířená verze výukového textu (pro studenty s hlubším zájmem o danou problematiku). Referenční kopie zveřejněná na začátku semestru (pro porovnání změn s aktuálními kopiemi.)
23.03.2007 Rozšířená verze výukového textu - aktuální, ale stále ne definitivní, verze.
Seznam změn (proti referenční kopii z 21.2.2007):
  • 26.2.2007 - Úpravy v první kapitole a několik typografických úprav
  • 12.3.2007 - V obrázku 3.3 změněn stav q3 na nepřijímající a opraveny další obrázky, kde se špatně zarovnaly stavy vůči přechodům.
  • 23.3.2007 - Opravena chyba v řešení Řešeného příkladu 4.4. a v zobrazení Řešeného příkladu 4.3.
  • 10.4.2007 - Opravena chyba v řešení Cvičení 8.26. To bylo navíc přesunuto do kapitoly zabývající se redukcí gramatik (nové číslo tohoto cvičení je 8.28). Dále příklad 8.27 přesunut do sekce
06.06.2007 Rozšířená verze nového výukového textu - zcela přepsaný výukový text ve verzi hlavně pro předmět Teoretická informatika a pro studenty UTI s hlubším zájmem o problematiku.
 
Zadání projektů
04.04.2007 Všechna zadání povinných zápočtových příkladů v pdf souboru
21.02.2007 Všechna zadání bonusových příkladů
 
Příklady na cvičení
21.02.2007 Loňské ukázkové zadání zkouškové písemky
11.05.2007 Letošní ukázkové zadání zkouškové písemky. Příklady 1-4 tvoří 1. část, 5-8 tvoří 2. část a z každé části je nutné získat alespoň 10 bodů. Samozřejmě ukázková písemka nezahrnuje všechny možné typy příkladů, které se na zkoušce mohou vyskytnout. Slouží jen pro představu, jak by mohla přibližně zkouška vypadat.
21.02.2007 Příklady na cvičení v prvním týdnu - opakování množin, relací, grafů apod.
21.02.2007 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.
21.02.2007 Příklady k 2. přednášce - konečné automaty a operace s nimi
21.02.2007 Příklady k 3. přednášce - vyhledávání řetězců, regulární výrazy
21.02.2007 Příklady k 4. přednášce - minimalizace konečných automatů, regularita jazyků
21.02.2007 Příklady k 5. přednášce - bezkontextové gramatatiky a jazyky
21.02.2007 Příklady k 6. přednášce - zásobníkové automaty, Turingovy stroje
21.02.2007 Příklady k 7. přednášce - převody mezi výpočetními modely
21.02.2007 Příklady k 8. přednášce - časová složitost, asymptotické odhady složitosti
21.02.2007 Příklady k 9. přednášce - analýza složitosti rekurentních algoritmů
21.02.2007 Příklady k 10. přednášce - převody mezi problémy, příslušnost do třídy NP
21.02.2007 Příklady k 11. přednášce - NP-úplné problémy
 
Přednášky - slidy
30.05.2007 Soubor se všemi slidy (převzané z loňského roku a drobně modifikované), cca 8.5MB velké pdf
06.03.2007 Organizační informace, požadavky apod.
06.03.2007 Motivační příklady, formální jazyky
14.03.2007 Deterministické a nedeterministické konečné automaty
14.03.2007 Regularní výrazy, ekvivalence regulárních výrazů a konečných automatů
28.03.2007 Minimalizace KA, normovaný tvar KA, ekvivalence KA, neregulární jazyky - pumping lemma
28.03.2007 Bezkontextové gramatiky - definice, redukované, nevypouštějící, Greibachové a Chomského normální forma
03.04.2007 Zásobníkové automaty, ekvivalence zásobníkových automatů a bezkontextových gramatik, Turingovy stroje, generativní gramatiky, Chomského hierarchie
24.04.2007 Algoritmy, modely výpočtu, rozhodnutelné a nerozhodnutelné problémy
24.04.2007 Pojem složitosti algoritmu a problému, asymptotická notace složitosti, třída PTIME
23.05.2007 Rekurentní vztahy, třídy složitosti, dolní a horní odhady složitosti
23.05.2007 Pojem nedeterminismu, třída NPTIME, NP-úplnost, Cookova věta
30.05.2007 Důkazy NP-úplnosti vybraných problémů
30.05.2007 Randomizované algoritmy, aproximační algoritmy