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, 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.
• 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

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 a kniha Introduction to the Theory of Computation (obojí je uvedeno 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 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é. 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).
• 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.
• Při řešení úkolů je možné vzájemně spolupracovat. Ze společného 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.
• Od letošního roku se úkoly odevzdávají na skenovatelných listech. Po opravení se naskenují a každý svůj úkol najde v ISu, takže už nemusíte čekat a jejich doručení do cvičení. Zároveň je však 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í)
  • 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í sharelatex (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 pro elektronické odevzdávání je použít TeX šablonu, není to náročné a návod je níže
  • 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í 9: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.
• 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).

Jak na LaTeX

Sázecí systém LaTeX je od letošního roku doporučený pro elektronicky vypracovávaná řešení, umožní vám totiž 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://cs.sharelatex.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 27. 10. 2016 od 17:00 se bude v učebnách D1, D2 a A318 na FI a v učebně P31 na FSS 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 2014 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
6. 1. 2017	9:00	D1+D3 (dle potřeby i A318)
17. 1. 2017	9:00	D1+D3 (dle potřeby i A318)
25. 1. 2017	15:00	D1+D3 (dle potřeby i A318)
8. 2. 2017	9:00	D1+D3 (dle potřeby i A318)

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 2013 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:

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