INFORMACE O KURSU IB005

FORMÁLNÍ  JAZYKY  A  AUTOMATY 

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


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
Mgr. David Klaška
FI MU
david.klaska@mail.muni.cz
po predchozi domluve via e-mail, místnost C408, 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.
Předběžný termín konání: cca polovina dubna.
Nove: vnitrosemestralni pisemka se kona 19.4., 10:00, D1.
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:
29.5., 13:00 radny; ostatni jsou radne i opravne:
8.6. (11:00), 18.6. (13:00) a 27.6. (13:00);
prihlaseni a dalsi info via IS.

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: 19. dubna.

    Pro Vasi info: minule pisemky z IB005


    Last modified: Saturday, 10-Mar-2018 21:24:02 CET