Název:

Seminář teoretické informatiky

Zkratka:STI
Ak.rok:2010/2011
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
IT-MGR-2MBI1.volitelný
IT-MGR-2MBS1.volitelný
IT-MGR-2MGM1.volitelný
IT-MGR-2MGM.1.volitelný
IT-MGR-2MIN1.volitelný
IT-MGR-2MIN.1.volitelný
IT-MGR-2MIS1.volitelný
IT-MGR-2MIS.1.volitelný
IT-MGR-2MMI1.volitelný
IT-MGR-2MMM1.volitelný
IT-MGR-2MPS1.volitelný
IT-MGR-2MPV1.volitelný
IT-MGR-2MSK1.volitelný
Vyučovací jazyk:čeština
Kredity:2 kredity
Ukončení:zápočet
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:026000
 zkouškatestycvičenílaboratořeostatní
Body:00000
Garant:Vojnar Tomáš, prof. Ing., Ph.D., UITS
Přednášející:Vojnar Tomáš, prof. Ing., Ph.D., UITS
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav inteligentních systémů FIT VUT v Brně
 
Cíle předmětu:
Rozšíření schopností aplikovat poznatky pokročilé teorie formálních jazyků a teorie vyčíslitelnosti a výpočetní složitosti a schopnosti řešit konkrétní teoretické a praktické problémy.
Anotace:
Výuka probíhá formou demonstračních cvičení s aktivním podílem studentů na řešení konkrétních problémů a příkladů z oblastí teoretické informatiky včetně teorie vyčíslitelnosti a složitosti. Řešené problémy a příklady spadají do témat pokročilé teorie a aplikací regulárních jazyků, bezkontextových jazyky a kontextových jazyků, Turingových strojů, rozhodnutelnosti, redukce rozhodovacích problémů, vyčíslitelných funkcí a základů složitosti. Aplikačními oblastmi jsou modelování systémů, formální analýza a verifikace systémů, překladače, umělá inteligence, lingvistika ap.
Požadované prerekvizitní znalosti a dovednosti:
Základní znalosti z teorie algeber, teorie grafů a regulárních a bezkontextových jazyků.
Získané dovednosti, znalosti a kompetence z předmětu:
Hlubší pochopení principů a schopnost aplikace poznatků z teorie formálních jazyků a teorie vyčíslitelnosti a složitosti. Student je schopen aplikovat získané znalosti při řešení teoretických i praktických problémů modelování, programování, formální specifikace, automatizace návrhu, verifikace a umělé inteligence.
Dovednosti, znalosti a kompetence obecné:
Rozšíření a zkvalitnění schopností samostatně formalizovat a řešit informatické i aplikační problémy, vytvářet algoritmy i konstruovat důkazy. Student mj. získává hlubší kompetence k výzkumné práci v různých oblastech informatiky.
Osnova seminářů:
  1. Množiny a relace. Řetězce, jazyky, operace nad nimi. Gramatiky, Chomského hierarchie jazyků a gramatik.
  2. Regulární jazyky a konečné automaty, determinizace a minimalizace automatů, převod regulárních výrazů na konečné automaty.
  3. Kleeneho algebra. Pumping lemma, důkaz neregularity jazyků.
  4. Bezkontextové jazyky a gramatiky. Transformace bezkontextových gramatik.
  5. Operace nad bezkontextovými jazyky a uzavřenost vůči nim. Pumping lemma bezkontextových jazyků.
  6. Zásobníkové automaty, (nedeterministická) syntaktická analýza shora dolů a zdola nahoru. Deterministické zásobníkové jazyky.
  7. Turingovy stroje.
  8. Jazyky rekurzívní a rekurzívně vyčíslitelné a jejich vlastnosti.
  9. Rozhodnutelnost, částečná rozhodnutelnost a nerozhodnutelnost problémů, redukce problémů.
  10. Vyčíslitelné funkce. Další Turingovsky úplné výpočetní mechanismy (automaty s více zásobníky, automaty s čítači).
  11. Třídy složitosti. Vlastnosti prostorových a časových tříd složitosti.
  12. NP problémy. Polynomiální redukce.
  13. Aplikace poznatků z teoretické informatiky v překladačích, automatizované verifikaci, lingvistice, ... Přehled různých oblastí rozšiřujících probranou látku (automatizované učení jazyků ze vzorků, stromové jazyky s využitím ve verifikaci nebo např. při manipulaci XML, automaty s omezeními, hierarchie nerozhodnutelných problémů, ...).
Literatura referenční:
  1. Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0
  2. Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2. vydání, 2000. ISBN 0-201-44124-1
  3. Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3. vydání, 2002. ISBN 0-072-32200-4
  4. Brookshear, J.G.: Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California, 1989. ISBN 0-805-30143-7
  5. Aho, A.V., Ullmann, J.D.: The Theory of Parsing,Translation and Compiling, Prentice-Hall, 1972. ISBN 0-139-14564-8
Literatura studijní:
  1. Češka, M. a kol.: Vyčíslitelnost a složitost, Nakl. VUT Brno, 1993. ISBN 80-214-0441-8
  2. Češka, M., Rábová, Z.: Gramatiky a jazyky, Nakl. VUT Brno, 1992. ISBN 80-214-0449-3
  3. Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0
  4. Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2. vydání, 2000. ISBN 0-201-44124-1
  5. Černá, I., Křetínský, M., Kučera, A.: Automaty a formální jazyky I, učební text FI MU, Brno, 1999.
  6. Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997. ISBN 1-85032-243-0
Kontrolovaná výuka:
Kontrola účasti, maximálně dvě neomluvené absence.
Podmínky zápočtu:
Maximálně dvě neomluvené absence.