INFORMACE O KURSU IB005

FORMÁLNÍ  JAZYKY  A  AUTOMATY 

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

Syllabus prednasky

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

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

• prof. RNDr. Mojmír Křetínský, CSc.: pátek, 12:30 - 14:30
  
• RNDr. Jiří Barnat, Ph.D. : bude oznámeno na cvičeních
  
• RNDr. Jan Strejček, Ph.D. : bude oznámeno na cvičeních
  

Studijni materialy

• I.Černá, M.Křetínský a A.Kučera: Automaty a formální jazyky I
  materiál ke kursu I005 (I005 je dřívější označení nynějšího IB005)
  hard copy v knihkupectví "U Marečka", FI MU 2002. Elektronicka verze je zde jako ps nebo jako pdf
• stručný dodatek o LL(1) gramatikách je zde (ps) ; kopie též v knihkupectví "U Marečka"
• P. Jančar: Teoretická informatika, VŠB-TU Ostrava 2007
  materiál určený pro samostudium, ke stažení zde
• J.Gruska: Foundations of Computing. Thomson International Computer Press, 1997
• M.A.Harrison: Introduction to Formal Language Theory
  Addison-Wesley Publ.Comp., 1978
• J.E.Hopccroft, J.D.Ullman: Introduction to Automata Theory, Languages and Computation
  Addison-Wesley Publ.Comp.,1979
• J.E.Hopccroft, R.Motwani, J.D.Ullman: Introduction to Automata Theory, Languages and Computation, 2nd ed.
  Addison-Wesley Publ.Comp.,2001
• M.Chytil; Automaty a gramatiky
  SNTL Praha, 1984
• D.Kozen: Automata and computability
  Springer, 1997
• A.P.Parkes: A concise introduction to languages and machines (Undergraduate topics in computer science), Springer, 2008
• ZKUSTO
• Kurs na VSB v Ostravě
• Kurs na MFF v Praze
• K dispozici jsou též příklady k procvičení:
  sbírka "Příklady k cvičením" a
  další (níže uvedené) ukoly k procviceni, vcetne jejich vzorovych reseni. Dobrá rada: úkoly zkoušejte řešit samostatně a až následně konzultujte Vaše řešení s řešením vzorovým!

Pozadavky na absolvovani predmetu

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

• student vypracuje čitelná řešení přesně identifikovaných příkladů
• řešení přinese na cvičení, kde je předá cvičícímu
• cvičící do následujícího cvičení opraví řešení nejvýše 2 příkladů každému studentovi
• v rámci příštího cvičení se cvičící veřejně avšak anonymně vyjádří k chybám v odevzdaných a opravených řešeních

Domaci ukoly k procviceni

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

Pro Vasi info: minule pisemky z I005

• 1.pisemka v LS'98
• 2.pisemka v LS'98
• 2.pisemka v LS'97
• nahradni 2.pisemka v LS'97 (pro nemocne v radnem terminu)
• 1.vnitrosemestralni pisemka v LS'99
• 1.vnitrosemestralni pisemka v LS'99
• 2.vnitrosemestralni pisemka v LS'99
• 2.vnitrosemestralni pisemka v LS'99
• Durazne upozornuji, ze typy prikladu mohou byt jine nez ty, ktere byly v minulých letech.