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, Nerodova věta, 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.

Výuka

Kompletní rozvrh předmětu je k nalezení zde. Konzultační hodiny jsou každou středu 16:00-17:50 v kanceláři B421.

• 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 sobotu ráno budou zveřejněny slajdy k pondělní přednášce. Slajdy je možné použít k dopisování poznámek v průběhu přednášek. V žádném případě se nedají použít jako samostatný studijní materiál - k tomu slouží především skripta (zmíněná v čele seznamu doporučené literatury).

• Cvičení

  Cvičení jsou nepovinná, ale silně doporučená. Kromě své skupiny můžete navštěvovat i další skupinu či skupiny, je-li v nich ještě 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 vytiskněte.

Domácí úkoly

• Domácí úkoly jsou nepovinné, ale silně doporučené. Utvrdíte si tím 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í dva příklady, každý zpravidla 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ď osobně příští pondělí před začátkem přednášky nebo do stejné doby vložit elektronicky do vyhrazené složky v Odevzdávárně v ISu (použijte formát pdf, vypracujte každý  příklad na samostatnou stránku a nepoužívejte barvy - bude se tisknout černobíle).
• Při řešení úkolů je možné vzájemně spolupracovat. Vlastní řešení však musí každý student sformulovat samostatně (vlastními slovy), nikoliv jako kopii (či drobnou obměnu) cizího řešení.
• Bude-li řešení nějakého příkladu zveřejněno na diskusním fóru před termínem odevzdání, 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

V pátek 20. listopadu od 17:00 se bude současně v D1, D2, D3, A107, B204 a v učebnách T-010 a T-020 v budově VUT na Technické 8 psát vnitrosemestrální písemka. Maximální počet bodů, které lze získat za tuto písemku, je 75. Písemka je tematicky zaměřena na regulární jazyky, 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. Přihlašování bude zahájeno 1. 11. 2009. Pro ty, kteří budou v termínu písemky nemocní (a doloží tento fakt potvrzením o pracovní neschopenosti 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 celkem 4 zkouškové termíny:

Zkouška je písemná a lze za ni získat maximálně 225 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. U zkouškové písemky můžete využít opravný termín (resp. dva opravné termíny). 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 2006 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-12 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. 300) a tvrdých bodů z domácích úkolů. Pokud tento součet nedosáhne 170 bodů, získáváte F. Pokud získáte alespoň 170 bodů, připočtou se i měkké body z domácích úkolů a hodnocení se určí dle následující tabulky: