INFORMACE O KURSU IB005

FORMÁLNÍ  JAZYKY  A  AUTOMATY 

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


Syllabus prednasky

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

Predpokladem pro zapis prednasky IB005 je znalost pojmu v rozsahu prednasky IB000 Uvod do informatiky a dále MB005 Zaklady matematiky nebo ekvivaletnich prednasek (zejmena sekce Matematika Prirodovedecke fakulty)

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.


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 B408, Botanická 68a

Cvičení

Skupina 'A', kterou vede RNDr. Jan Strejček, PhD, je tzv. vyberove cviceni: je urceno pro zajemce, kteri maji predmet zapsan poprve, zvladli Uvod do informatiky a Zaklady matematiky na A, resp. B a kteri zvladaji (by zvladali) probiranou latku na normalnich cvicenich bez problemu ci samostudiem. Obsah vyberovych cviceni nebude mit vzdy zcela tesnou navaznost na prednasky (a to, co bude procviceno navic oproti standardnim cvicenim se nebude zkouset).

RNDr. Jiří Barnat, PhD
Katedra teorie programovani FI MU
xbarnat@fi.muni.cz
místnost B421, Botanická 68a
RNDr. Jan Strejček, PhD
Katedra teorie programovani FI MU
xstrejc@fi.muni.cz
místnost B421, 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í: zacatek dubna. Na tuto pisemku bude nutno se prihlasit via IS.
Nove: vnitrosemestralni pisemka se kona 7.4., 14:00, D1. Dalsi info byly zaslany via e-mail
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: budou oznameny pozdeji 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.


Nebodované dobrovolné úlohy

Zadání dobrovolných nebodovaných domácích úloh: zadani_all.pdf.

Smyslem těchto domácích úloh je dát studentům šanci vypracovat si řešení netriviálních příkladů a nechat si toto řešení vzorově opravit stejným způsobem a stylem, jako jsou opravovány vnitrosemestrální a závěrečné písemky. Studenti tak mohou získat představu o svých schopnostech dobře napsat písemky dříve, než na písemkách samotných.

Princip odevzdávání nebodovaných domácích úloh je následující:

Domaci ukoly k procviceni


Pro Vasi info: minule pisemky z I005


Last modified: Tuesday, 18-Sep-2012 11:06:43 CEST