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

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 nejpozději v pátek 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 (odkaz naleznete 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 noste na cvičení. Během semestru může dojít k drobným úpravám sbírky, část věnovaná příkladům je však vcelku stabilní.

 

Domácí úkoly

• Domácí úkoly jsou nepovinné, ale silně doporučené – ani ne tak kvůli bodovému zisku (viz níže), ale abyste si probíraná témata pořádně procvičili a dostali nějakou zpětnou vazbu na to, jak si vedete – jejich řešením si utvrdíte znalosti získané na přednášce.
• Vždy v pondělí bude v interaktivní osnově zveřejněna jedna sada úkolů obsahující obvykle dva příklady, každý za 2 body. Většinu týdnů se bude jednat o otevřené úlohy očekávající textovou odpověď (s možností odevzdávat elektronicky), některé týdnu budou však část či všechny úlohy zadány formou odpovědníků v ISu.
• Při řešení úkolů je možné vzájemně spolupracovat. Ze společné porady si však odneste pouze myšlenku. Vlastní řešení 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.
• Textové úkoly se odevzdávají na skenovatelných listech, díky čemuž se po opravení dají naskenovat a svůj opravený úkol i s případnými poznámkami opravujících můžete najít v ISu. Aby to mohlo fungovat, je nutné dodržet následující pravidla:
  • úkoly smíte odevzdávat pouze na skenovatelném listu, a to buď elektronicky nebo musí být list vytištěn v dostatečné kvalitě a nepoškozený;
  • speciálně tedy nesmíte například přehýbat papír, sešívat více listů k sobě, používat papír jiného formátu než A4, či odevzdávat do odevzdávárny nekvalitně naskenované nebo dokonce mobilem nafocené papíry;
  • hlavička papíru musí být čitelně vyplněná, a to jak strojově čitelné UČO, tak rukou psané údaje (kromě počtu bodů, který doplní opravující), hlavička musí být vyplněná i v elektronické verzi, protože úkoly se budou tisknout;
    
  • musíte zachovat kompletní hlavičku a patičku se strojově čitelnými údaji (čtverečky a strojově čitelné údaje), do patičky nic nevpisujte;
  • pokud potřebujete více prostoru, můžete použít druhou stranu listu nebo další list (lze získat z TeX verze zadání, například pomocí overleaf (viz níže), nepotřebujete tedy instalovat LaTeX na svůj počítač ani jej umět, stačí vložit do řešení příkazy \newpage\  tolikrát, kolik chcete nových stránek (za \newpage musí být zpětné lomítko a mezera, jinak se stránka nevloží));
  • doporučený postup je použít TeX šablonu, není to náročné a návod je níže: nejjednodušší způsob, jak dodržet všechna pravidla práce se skenovatelnými listy je používat sázecí systém LaTeX a odevzdávat PDF elektronicky;
  • pokud nebude možné váš úkol naskenovat, riskujete stržení až poloviny bodů z domácího úkolu (zaokrouhlováno dolů).
• 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). Dávejte si pozor, aby vaše řešení bylo dobře čitelné. V týdnu po odevzdání bude zveřejněno vzorové řešení úloh.
• Pokud si po odevzdání uvědomíte, že jste udělali chybu a chcete odevzdat znovu, tak:
  • elektronicky odevzdané soubory lze přepisovat, přepište tedy původní odevzdání,
  • u papírových řešení uveďte na nové řešení jasně, že se jedná o nové odevzdání a původní rušíte,
  • nezávisle na druhu odevzdání, pokud odevzdáte dvě různá řešení bez označení, které je finální, dostanete minimum z bodového zisku obou řešení.
• Bude-li řešení nějakého příkladu zveřejněno před termínem odevzdání (např. na diskusním fóru, facebooku a podobně), bude tento příklad anulován.
• Body z úkolů budou k nalezení v poznámkových blocích, opravené úkoly budou naskenované v ISu (vždy pouze ta strana listu, na které je skenovací hlavička) a v případě potřeby vidět druhou stranu budou k nahlédnutí v laboratoři ParaDiSe (kontaktujte Vladimíra Štilla e-mailem s kódem předmětu v hlavičce a domluvte se na termínu návštěvy).
• Dotazy na domácí úkoly směřujte do diskusního fóra, nebo, v případě, že váš dotaz může prozrazovat část řešení nebo se týká pouze vaší osoby (např. "Domácí úkol jsem odevzdal, ale nedostal jsem žádné
  body."), kontaktujte Vladimíra Štilla e-mailem s kódem předmětu v hlavičce.

Jak na LaTeX

Sázecí systém LaTeX vám umožní snadné vyplňování naší šablony a tvorbu bezproblémově čitelných a skenovatelných řešení. Proto také poskytujeme návod na jeho použití v kontextu našeho předmětu, ten naleznete na odkazu níže. K sazbě budete potřebovat také styl pro IB102, který rovněž naleznete níže. Použití LaTeXu není náročné, navíc nepotřebujete ani instalaci na svém počítači, plně postačí použít webový editor na https://www.overleaf.com/.

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 7. 11. 2019 od 18:00 se bude v učebnách D1, D2, D3, A217 a A318 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 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 včas dodají příslušné potvrzení na Studijní 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 2011 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
8. 1. 2020	10:00	D1 + D3
17. 1. 2020	9:00	D1 + D3 + A217
27. 1. 2020	13:00	D1 + D3 + A217
6. 2. 2020	11:00	D1 + D3

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 jen jednoho opravného termínu.

Zadání závěrečné písemky z roku 2011 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 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:

počet bodů	hodnocení
179 a více	A
alespoň 162 a méně než 179	B
alespoň 145 a méně než 162	C
alespoň 128 a méně než 145	D
alespoň 111 a méně než 128	E
méně než 111	F