INFORMACE O KURSU IB005

FORMÁLNÍ  JAZYKY  A  AUTOMATY 

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

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
Mgr. David Klaška
FI MU
david.klaska@mail.muni.cz
po predchozi domluve via e-mail, místnost C408, Botanická 68a
Mgr. Juraj Major
FI MU
jmajor@mail.muni.cz
po predchozi domluve via e-mail, místnost B315, 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 15 bodu.
Předběžný termín konání: cca v prvni polovine dubna.
Na tuto pisemku je 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.

Dalsi body lze ziskat za reseni domacich ukolu: max. 5 tzv. "tvrdých" bodů a max. 7 tzv. "měkkých" bodů -- vizte nize.

Zkouska:
Zaverecna zkouska je pisemna a lze za ni ziskat maximalne 80 bodu. Pouziti literatury a poznamek neni povoleno.

Terminy zaverecne zkousky: budou oznameny via IS.

Hodnoceni: maximalni mozny zapocitavany zisk "tvrdých" bodů a bodů z obou pisemnych praci je 100 b.
Při dosažení alespoň 55 bodů (hodnocení E) se přičtou získané měkké body.
Stupnice známek: A(vyborne): alespon 91 b., B: alespon 82 b., C: alespon 73 b., D: alespon 64, E: alespon 55 b.
Ukonceni kolokviem neni mozne.
Ukonceni zapoctem: alespon 50 b. (bez měkkých bodů).

Domácí úlohy

Systém, pravidla a hodnocení domácích úkolů jsou detailně specifikovány v interaktivní osnově předmětu v ISu zde .

Dalsi ukoly k samostatnemu procviceni

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

    Aktuality

        Pravdepodobny termin vnitrosemestralni pisemky: 19. dubna.

    Pro Vasi info: minule pisemky z IB005

    Last modified: Thursday, 27-Feb-2020 22:27:04 CET