Informace o předmětu (sylabus, systém hodnocení,...)
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 D1, v D3 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 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 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
Ve čtvrtek 18. 11. 2010 v 19:00 se bude 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. 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:
datum |
čas | místnost |
7. 1. 2011 | 9:00 | D1+D3 (dle potřeby i D2) |
13. 1. 2011 | 9:00 | D1+D3 (dle potřeby i D2) |
25. 1. 2011 | 12:00 | D1+D3 (dle potřeby i D2) |
4. 2. 2011 | 9:00 | D1+D3 |
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:
počet bodů | hodnocení |
270 a více | A |
245 až 269 | B |
220 až 244 | C |
195 až 219 | D |
170 až 194 | E |
méně než 170 | F |