..:: Martin Kot ::..
Introduction to theoretical computer science
Aktuální informace
06.06.2007 V sekci ke stažení je nový výukový text. K přípravě na zkoušku je možno použít podle vlastního výběru buď nový nebo starý text. Příklady by měly obsahovat téměř shodné, ale v novém textu jsme se pokoušeli o srozumitelnější výklad teorie.
21.05.2007 Mezi odkazy na výukové texty v sekci ke stažení přibyl odkaz na stránku s animacemi. Jsou tam přehledně shrnuté animace používané ve výuce v Teoretické informatice, animace používané v přednáškách z UTI apod. Seznam ještě není úplný, bude se ještě rozrůstat.
21.05.2007 Již je možné se přihlašovat na zkoušky. Termíny jsou ve třech dnech, každý den bude tolik termínů, aby mohli jít na zkoušku všichni (tedy mohou se ještě podle zájmu přidat termíny v jiném čase). Nebudou již žádné další termíny v jiných dnech.
11.05.2007 V sekci ke stažení je nová ukázková zkoušková písemka, která vyhovuje letošním podmínkám (příklady 1-4 jsou z oblasti jazyků a automatů a součet bodů mají 35, příklady 5-8 jsou z oblasti vyčíslitelnosti a složitosti a součet bodů mají 30).
02.05.2007 Náhradní termín zápočtové písemky pro studenty, kteří se ze závažných důvodů omluvili z řádného termínu, bude 4.5. ve 13 hodin na C3. Tedy zůstal platný termín, který jim byl sdělen v odpovědi na omluvu.
27.04.2007 Protože se na předtermín hlásí i studenti, kteří předmět neopakují, tak bych chtěl upozornit, že zkoušková písemka bude normálně zahrnovat učivo celého předmětu a ne jen již probranou část. A jak bylo oznámeno na přednášce, bude nutné získat alespoň 10 z 35 bodů v části věnované jazykům a automatům a alespoň 10 z 30 bodů v části věnované vyčíslitelnosti a složitosti (která právě zatím celá probraná a procvičená nebyla).
24.04.2007 Studenti, kteří UTI opakují a chtějí letos v červnu dělat státnice, mohou jít na předtermín zkoušky 7.5.2007 ve 13 hodin na B6. Je nutné normálně se přihlásit na zkoušku v KatISu.
19.04.2007 Z důvodu akademického uvedení Windows Vista konaného ve středu 25.4.2007 v nové aule NA1 se bude přednáška ten den opět konat v sále nad novou menzou (stejně jako to bylo 14.3.).
19.04.2007 Výsledky opravených semestrálních písemek již jsou zapsány v KatISu. Opravené písemky donesou k nahlédnutí cvičící na cvičení podle toho, kam kdo patří podle KatISu.
14.04.2007 V sekci ke stažení jsou první dvě kapitoly (Formální jazyky, Konečné automaty) nově vznikajícího definitivního výukového textu. Jiný popis stejného tématu může být dobrý pro dokonalejší pochopení před blížicí se písemkou.
27.03.2007 Zápočtová písemka by se měla psát 18.4.2007 v 11:30 v NA1 (místo přednášky). Upozorňujeme, že účast na písemce je jednou z podmínek pro získání zápočtu.
07.03.2007 Z důvodů konání akce Symbióza 2007 v prostorách budovy nové auly se bude přednáška dne 14.3.2007 konat v sále ve druhém patře menzy (v běžném čase od 11:30).
01.03.2007 Množí se dotazy na dílčí uznávání výsledků z loňského roku. Taková možnost neexistuje. Všichni studenti opakující tento předmět by v KatISu měli mít uznaný zápočet z loňského roku. Pokud mají zájem si body vylepšit, musí si tento uznaný zápočet nechat zrušit a potom absolvovat písemku i referát znovu!
27.02.2007 V sekci ke stažení najdete příklady na cvičení i zadání projektů (referátů). Slajdy z přednášek jsou zatím loňské - postupně se budou objevovat opravené letošní, ale změny by neměly být nijak výrazné. Letos nový výukový text se bude v průběhu semestru měnit více, ale i aktuálně zveřejněná verze by měla být pro studium užitečná a obsahovat vše podstatné bez zásadních chyb.
 
Průběh přednášek
28.2.2007
  • Seznámení s podmínkami předmětu
  • Formální jazyky a operace s nimi
  • Motivační příklady pro zavedení konečných automatů
7.3.2007
  • Vyhledávání řetězce v textu
  • Formální definice deterministického konečného automatu
  • Uzávěrové vlastnosti regulárních jazyků - konstrukce automatu pro sjednocení a průnik jazyků, doplněk jazyka
  • Definice nedeterministického konečného automatu (zatím ne zobecněného)
  • Převod nedeterministických automatů na deterministické (nedokončeno)
14.3.2007
  • Převod nedeterministických automatů na deterministické
  • Zobecněné nedeterministické automaty
  • Regulární výrazy
  • Ekvivalence regulárních výrazů a konečných automatů
  • Uzavřenost třídy regulárních jazyků vůči různým operacím
21.3.2006
  • Normovaný tvar automatu
  • Minimalizace konečného automatu
  • Ekvivalence konečných automatů
  • Motivace k pumping lemma a jeho znění zatím bez využití k důkazům neregularity jazyka
28.3.2006
  • Pumping lemma, důkazy neregularity jazyků
  • Bezkontextové gramatiky - definice, příklady
  • Derivace, levá a pravá derivace, derivační strom
  • Bezkontextové jazyky, uzavřenost třídy bezkontextových jazyků vůči jazykovým operacím
4.4.2006
  • Redukce gramatiky
  • Zásobníkové automaty
  • Ekvivalence zásobníkových automatů a bezkontextových gramatik - podrobněji jen převod BG na ZA
  • Turingovy stroje - ještě budou dokončeny na příští přednášce
11.4.2006
  • Turingovy stroje
  • Generativní gramatika a Chomského hierarchie
  • Pojmy algoritmus a problém, kódování vstupu a výstupu
  • Algoritmicky neřešitelné problémy, nerozhodnutelné problémy (Halting problem)
18.4.2006
  • Zápočtová písemka
25.4.2006
  • Vybrané nerozhodnutelné problémy
  • Časová složitost algoritmu (v nejhorším, průměrném i nejlepším případě)
  • Asymptotická notace pro porovnávání funkcí
2.5.2006
  • Rekurentní vztahy
  • Třídy složitosti a vztahy mezi nimi
  • Horní a dolní odhady složitosti
9.5.2006
  • Dolní odhad pro problém třídění
  • Nedeterministický Turigův stroj a nedeterministiký RAM
  • Pojem nedeterminismu
  • Nedeterministické třídy složitosti (NPTIME, NPSPACE)
  • Polynomiální převoditelnost
  • NP-obtížnost, NP-úplnost
  • Cookova věta (SAT je NP-úplný) (začátek)
23.5.2006
  • Cookova věta (SAT je NP-úplný) (dokončení)
  • Problém 3-SAT, převod SAT na 3-SAT
  • Problém barvení grafu 3 barvami (3-COL) a převod 3-SAT na 3-COL
  • Problém nezávislé množiny (IS) a převod 3-COL na IS
  • Problém vrcholového pokrytí (VC) a převod IS na VC
  • Problémy Hamiltonovský cyklus (HC) a Hamiltonovská kružnice (HK) a převod HC na HK
  • Problém obchodního cestujícího (TSP) a převod HK na TSP
  • Problém loupežníka (PART) a převod 3-SAT na PART