Sylabus přednášky

• Motivace - problém specifikace (nekonečných, regulárních) jazyků; základní operace nad jazyky.
• Konečné automaty a regulární gramatiky; Pumping lemma, minimalizace. Nedeterministické konečné automaty, vztah k regulárním gramatikám.
• Vlastnosti regulárních jazyků; uzávěrové vlastnosti, regulární výrazy, Kleeneho věta, konečnost.
• Bezkontextové gramatiky a jazyky; transformace bezkontextových gramatik, vybrané normální formy, pumping lemma, uzávěrové vlastnosti.
• Zásobníkové automaty a jejich vztah k bezkontextovým gramatikám; nedeterministická syntaktická analýza shora dolů a zdola nahoru.
• Deterministické zásobníkové automaty a deterministická analýza.
• Turingovy stroje, rozhodnutelnost problémů, časová a prostorová složitost.
• Redukce problémů, složitostní třídy a vztahy mezi nimi. NP-úplné problémy.

Výuka

Konzultace k výuce probíhají (nejlépe po předchozí emailové domluvě) v kanceláři C414.  

• Přednášky

  Přednáška se koná v D3, v D1 je přenos. Přednášky se zaznamenávají, záznamy budou studentům k dispozici. Vždy v pátek nebo v průběhu víkendu budou zveřejněny slajdy k pondělní přednášce. Slajdy můžete před přednáškou vytisknout a použít k dopisování poznámek v průběhu přednášky. V žádném případě nelze slajdy doporučit jako samostatný studijní materiál - k tomu slouží především skripta Automaty a formální jazyky I a kniha Introduction to the Theory of Computation (obojí je uvedeno v čele seznamu doporučené literatury).

• Cvičení

  Účast na cvičeních se neeviduje. Přesto silně doporučujeme cvičení nevynechávat. Kromě své skupiny můžete navštěvovat i další skupinu či skupiny, je-li v nich dostatek místa. Na cvičení choďte připravení, tj. se znalostí základních definic, vět a algoritmů. Na cvičeních se budou řešit vybrané příklady ze sbírky příkladů k cvičením z IB005 a IB102. Sbírku si prosím noste na cvičení (nejlépe vytištěnou). Během semestru dojde k úpravám sbírky, část věnovaná příkladům a řešením je však vcelku stabilní.

Domácí úkoly

• Domácí úkoly jsou nepovinné, ale silně doporučené. Jejich řešením si utvrdíte znalosti získané na přednášce a můžete získat i body do hodnocení (viz níže).
• Každý týden v pondělí bude zveřejněna jedna sada obsahující obvykle dva příklady, každý za 2 body.
• Každý příklad vypracujte na samostatný list (opravují je různí lidé), na který napíšete svoje jméno, UČO, číslo příkladu a číslo seminární skupiny, kterou navštěvujete.
• Vypracovaný úkol můžete odevzdat buď do příslušné skříňky naproti hlavnímu vchodu do D1 do příštího pondělí 9:00 nebo do stejné doby vložit elektronicky do vyhrazené složky v Odevzdávárně v ISu (použijte výhradně formát pdf, vypracujte každý příklad do samostatného souboru a nepoužívejte barvy - bude se tisknout černobíle, uveďte také svoje jméno, UČO, číslo příkladu a číslo seminární skupiny, kterou navštěvujete).
• Budete-li chtít využít možnosti editovat domácí úlohy ve formátu TeX, stáhněte si kromě zadání rovněž soubor ib102.cls a umístěte jej do složky, v které probíhá překlad TeXem (typicky do stejné složky jako soubor s řešením).
• Při řešení úkolů je možné vzájemně spolupracovat. Vlastní řešení však musí každý student zformulovat zcela samostatně (vlastními slovy), nikoliv jako kopii (či drobnou obměnu) cizího řešení. Porušením tohoto pravidla se vystavujete naprosto reálnému riziku disciplinárního řízení a odpovídající sankce.
• Bude-li řešení nějakého příkladu zveřejněno před termínem odevzdání (např. na diskusním fóru), bude tento příklad anulován.
• Opravené úkoly dostanete zpět na cvičení.

Hodnocení předmětu

Do výsledného hodnocení předmětu se započítávají body ze tří zdrojů :

• Vnitrosemestrální písemka

Vnitrosemestrální písemka se bude psát ve čtvrtek 30. října od 18:00 v učebnách D1, D2 a D3 na FI a v učebně P31 na FSS. Maximální počet bodů, které lze získat za tuto písemku, je 50. Písemka je tematicky zaměřena na regulární jazyky a učivo z první přednášky, trvá 90 minut a píše se bez použití poznámek a literatury. Na písemku je nutné se přihlásit v ISu, agenda přihlašování na zkoušky. Pro ty, kteří budou v termínu písemky nemocní (a doloží tento fakt potvrzením o pracovní neschopnosti na studijním oddělení), bude konán během prosince jeden náhradní termín. K této písemce neexistuje žádný opravný termín.

Zadání vnitrosemestrální písemky z roku 2006 můžete stáhnout zde.

• Závěrečná zkouška

Během zkouškového období budou 4 zkouškové termíny:

Zkouška je písemná a lze za ni získat maximálně 150 bodů. Písemka pokrývá učivo z celého semestru, trvá 120 minut a píše se bez použití poznámek a literatury. Na písemku je také nutné přihlásit se v ISu, agenda přihlašování na zkoušky. Jestliže jako řádný termín využijete až ten předposlední, máte pak možnost jenom jednoho opravného termínu.

Zadání závěrečné písemky z roku 2013 můžete stáhnout zde.

• Domácí úkoly

Body z domácích úkolů se rozdělí na tzv. tvrdé body a měkké body tak, že první získaný bod z každé odevzdané sady úkolů je tvrdý a ostatní jsou měkké. Celkem bude možné získat asi 10-11 tvrdých bodů.  

• Hodnocení

Pro absolvování předmětu je rozhodující součet bodů z vnitrosemestrální a závěrečné písemky (max. 200) a tvrdých bodů z domácích úkolů. Pokud tento součet nedosáhne 111 bodů, získáváte F. Pokud získáte alespoň 111 bodů, připočtou se i měkké body z domácích úkolů a hodnocení se určí dle následující tabulky: