INFORMACE O KURSU IB005

FORMÁLNÍ  JAZYKY  A  AUTOMATY 

Katedra teorie programování
Fakulta informatiky MU
semestr: jaro 2017


Syllabus prednasky

Pocet kreditu: 6 (4/2) plus funkce ukonceni

Predpokladem pro zapis prednasky IB005 je znalost pojmu v rozsahu prednasky IB000 Matematické základy informatiky

Pojem jazyka a problem jeho konecne specifikace.
Prepisovaci systemy, gramatiky. Chomskeho hierarchie.
Konecne automaty (deterministicke a nedeterministicke) a regularni jazyky. Vzajemne vztahy konecnych automatu a regularnich gramatik.
Vlastnosti regularnich jazyku.
Bezkontextove gramatiky a zasobnikove automaty a jejich vzajemne vztahy.
Vlastnosti bezkontextovych jazyku.
Deterministicke zasobnikove automaty a bezkontextove jazyky (detCFL) a jejich zakladni vlastnosti.
Turingovy stroje a jazyky typu 0 a jejich vzajemne vztahy. Vycislitelne jazyky a funkce.
Rozhodnutelne a nerozhodnutelne problemy, diagonalizace a redukce.
Postuv problem prirazeni, vybrane nerozhodnutelne problemy z oblasti jazyku a automatu/gramatik.


Cas a misto konani

rozvrh konání přednášek a cvičení (autorizovany pristup na IS)

Vyučující

Přednášky

prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování FI MU
mojmir@fi.muni.cz
místnost C419, Botanická 68a

Cvičení

doc. RNDr. Jan Strejček, Ph.D.
Katedra teorie programovani FI MU
xstrejc@fi.muni.cz
místnost C414, Botanická 68a
RNDr. Martin Jonáš
FI MU
martin.jonas@mail.muni.cz
místnost C415, Botanická 68a
Bc. Tomáš Lamser
FI MU
409855@mail.muni.cz
po predchozi domluve via e-mail, místnost C408, Botanická 68a

Konzultacni hodiny


kniha Studijni materialy

Na internetu lze nalézt spoustu dalších materiálů a příkladů k formálním jazykům, automatům a gramatikám. K prozkoumání doporučuji např. stránky kurzu Teorie jazyků a automatů z VŠB-TU Ostrava (najdete na nich např. hojně komentované výukové animace).

Pozadavky na absolvovani predmetu

Behem semestru se bude konat jedenkrat tzv. vnitrosemestralni pisemna prace (doba a misto bude oznameno 14 dnu predem na prednasce a prostrednictvim e-mail dopisu, a to dle kapacitnich/casovych moznosti ziskat velke poslucharny).
Pro ty, kteri budou nemocni v tuto dobu (a dolozi tento fakt neschopenkou na studijnim oddeleni), bude konan jeden nahradni termin.

Za vnitrosemestralni pisemku lze ziskat 20 bodu.
Nove: vnitrosemestralni pisemka se kona 16.4., 16:00, D3.
Na tuto pisemku bude nutno se prihlasit via IS. Dalsi info u prihlasky na ISu.
Body ziskane z teto prace se zapocitavaji do celkoveho hodnoceni predmetu (viz nize). Pouziti literatury a poznamek neni povoleno.

Zkouska: Závěrečná zkouska je pisemna a lze za ni ziskat maximalne 80 bodu. Pouziti literatury a poznamek neni povoleno.

Terminy zaverecne zkousky: jsou oznameny via IS.
Dle casovych moznosti, zajmu a vzajemne dohody muze byt jeden z radnych terminu nahrazen predterminem (posledni tyden vyuky v semestru).

Hodnoceni: maximalni mozny zapocitavany zisk z obou pisemnych praci je 100 b.
A(vyborne): alespon 87 b., B: alespon 79 b., C: alespon 71 b., D: alespon 63, E: alespon 55 b.
Ukonceni kolokviem neni mozne.
Ukonceni zapoctem: alespon 50 b.


Domaci ukoly k procviceni

  •     sbírka "Příklady k cvičením" (referencovaná již výše v seznamu studijních materiálů)

    Aktuality

        Pravdepodobny termin vnitrosemestralni pisemky: zacatkem dubna.

    Pro Vasi info: minule pisemky z IB005


    Last modified: Wednesday, 22-Feb-2017 08:57:56 CET