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, Myhill-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, 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

Konzultační hodiny jsou každé pondělí 13:30-14:30 v kanceláři B415.

• 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 (zmíněná 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 se letos bude aktualizovat - doporučujeme si na cvičení vytisknout vždy jen aktuální část sbírky.

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í 10: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ěž soubr ib102.cls  (https://is.muni.cz/auth/el/1433/podzim2013/IB102/um/du/ib102.cls), umístěte jej do stejné složky v níž překládáte TeX.
• 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

V pátek 8. listopadu od 17:00 se bude psát vnitrosemestrální písemka. 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, 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 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-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: