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).
• Opravené úkoly dostanete nejpozději další týden po odevzdání 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

21. 11. 2008 ve 12:00 se bude na několika různých lokalitách (D1+D2 na FI MU, C423+D185 na FAST VUT Veveří 95, Z240 na FAST VUT Žižkova 17, P31 na FSS MU) psát vnitrosemestrální písemka. Maximální počet bodů, které lze získat za tuto písemku je 80. 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. Datum zahájení přihlašování je 1. 11. 2008. 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ě 220 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

[Zde došlo letos ke změně.] 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: