Název:

Teoretická informatika

Zkratka:TIN
Ak.rok:2017/2018
Semestr:zimní
Studijní plán:
ProgramOborRočníkPovinnost
IT-MGR-2MBI1.povinný
IT-MGR-2MBS1.povinný
IT-MGR-2MGM1.povinný
IT-MGR-2MIN1.povinný
IT-MGR-2MIS1.povinný
IT-MGR-2MMI1.povinný
IT-MGR-2MMM1.povinný
IT-MGR-2MPV1.povinný
IT-MGR-2MSK1.povinný
Vyučovací jazyk:čeština
Aktuální informace:

Em., 2017-02-25: Souběžný zápis semináře STI umožňuje studentům prohloubení znalostí a praktických dovedností v řešení problémů teoretické informatiky.
Aktuální informace k předmětu jsou dostupné také na
http://www.fit.vutbr.cz/study/courses/TIN/public/
Informace veřejné:http://www.fit.vutbr.cz/study/courses/TIN/public/
Informace pro zapsané:http://www.fit.vutbr.cz/study/courses/TIN/private/
Kredity:5 kreditů
Ukončení:zápočet+zkouška (kombinovaná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:3900013
 zkouškatestycvičenílaboratořeostatní
Body:60250015
Garant:Češka Milan, prof. RNDr., CSc., UITS
Přednášející:Češka Milan, prof. RNDr., CSc., UITS
Cvičící:Češka Milan, RNDr., Ph.D., UITS
Holík Lukáš, Mgr., Ph.D., UITS
Lengál Ondřej, Ing., Ph.D., UITS
Rogalewicz Adam, doc. Mgr., Ph.D., UITS
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav inteligentních systémů FIT VUT v Brně
Navazující:
Funkcionální a logické programování (FLP), UIFS
Paralelní a distribuované algoritmy (PRL), UITS
Petriho sítě (PES), UITS
Složitost (SLOa), UITS
Rozvrh:
DenVýukaTýdenMístnostOdDoPSKSk-odSk-do
Útcvičení - Hromadna konzultace2017-12-19D10510:0011:50
ÚtKonzultace k průběžné zkoušce.2017-10-17A21817:0017:50
ÚtKonzultace k průběžné zkoušce.2017-11-28A21817:0017:50
Stzkouška - řádná2018-01-03D10513:0015:501MIT
Stzkouška - řádná2018-01-03D10513:0015:502MIT
Stzkouška - řádná2018-01-03D020613:0015:501MIT
Stzkouška - řádná2018-01-03D020613:0015:502MIT
Stzkouška - řádná2018-01-03D020713:0015:501MIT
Stzkouška - řádná2018-01-03E11213:0015:501MIT
Stzkouška - řádná2018-01-03E10413:0015:501MIT
Stzkouška - řádná2018-01-03E10513:0015:501MIT
Stzkouška - řádná2018-01-03G20213:0015:501MIT
Čtzkouška - 1. oprava2018-01-18D10513:0015:501MIT
Čtzkouška - 1. oprava2018-01-18D10513:0015:502MIT
Čtzkouška - 1. oprava2018-01-18D020613:0015:501MIT
Čtzkouška - 1. oprava2018-01-18D020713:0015:502MIT
Čtzkouška - 2. oprava2018-02-01D10513:0015:501MIT
Čtzkouška - 2. oprava2018-02-01D10513:0015:502MIT
Čtzkouška - 2. oprava2018-02-01D020713:0015:501MIT
Čtzkouška - 2. oprava2018-02-01D020713:0015:502MIT
 
Cíle předmětu:
  Rozšíření znalostí teorie formálních jazyků a osvojení základů teorie vyčíslitelnosti a základních pojmů výpočetní složitosti.
Anotace:
  Aplikace teorie formálních jazyků v informatice a informačních technologiích (překladače, modelování a analýza systémů, lingvistika, biologie atd.), modelovací a rozhodovací síla formálního modelu, regulární jazyky a jejich vlastnosti, minimalizace konečného automatu, bezkontextové jazyky a jejich vlastnosti, Turingovy stroje, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, vyčíslitelné funkce, nerozhodnutelnost, nerozhodnutelné problémy teorie formálních jazyků, úvod do výpočetní složitosti a Petriho  sítí.
Požadované prerekvizitní znalosti a dovednosti:
  Základní znalosti z binárních relací, teorie grafů a formálních jazyků včetně konečných a zásobníkových automatů a pojmů algoritmické složitosti.
Získané dovednosti, znalosti a kompetence z předmětu:
  Znalosti základních a pokročilejších pojmů, přístupů a výsledků teorie automatů a teorie vyčíslitelnosti a základů teorie výpočetní složitosti, vedoucí k hlubšímu pochopení povahy popisu a realizace výpočetních procesů. 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é:
  Student získává základní kompetence k teoretické výzkumné práci.
Osnova přednášek:
 
  1. Úvod do teorie formálních jazyků, způsoby specifikace jazyků, regulární jazyky a gramatiky, konečné automaty, regulární výrazy.
  2. Bezkontextové jazyky a gramatiky, zásobníkové automaty.
  3. Regulární jazyky jako množinová Booleova algebra, Kleeneho algebra, Kleenova věta, minimalizace konečného automatu.
  4. Věta o vkládání (Pumping theorem), Nerodova věta, rozhodnutelné problémy regulárních jazyků. Transformace a normální tvary bezkontextových gramatik. 
  5. Pokročilé vlastnosti bezkontextových jazyků, věta o vkládání pro bezkontextové jazyky, rozhodnutelné problémy bezkontextových jazyků. Deterministické bezkontextové jazyky. 
  6. Turingovy stroje (TS), definice TS a jazyka přijímaného TS, rekurzivně vyčíslitelné a rekurzivní jazyky a problémy, TS a funkce, metody konstrukce TS. 
  7. Modifikace TS, TS s obousměrně nekonečnou páskou, s více páskami, nedeterministický TS, stroj se dvěma zásobníky, stroje s čítači. 
  8. TS a jazyky typu 0, diagonalizace, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, lineárně ohraničené automaty a jazyky typu 1. 
  9. Church-Turingova téze, univerzální TS, nerozhodnutelnost, problém zastavení TS, redukce, Postův korespondenční problém. Nerozhodnutelné problémy teorie formálních jazyků. 
  10. Vyčíslitelné funkce, počáteční funkce, primitivně rekurzivní funkce, mí-rekurzivní funkce, vztah vyčíslitelných funkcí a Turingových strojů. 
  11. Úvod do výpočetní složitosti, Turingovská složitost, asymptotická složitost.
  12. Třída P a NP problémů, problémy mimo třídu NP, polynomiální redukce, úplnost.
  13. Úvod do Petriho sití, motivace, definice P/T Petriho sítě, metody analýzy, třídy Petriho sítí.
[Úvodní dvě přednášky opakují a formalizují znalosti získané v předmětu IFJ, přednášky 3-5 prohlubují znalosti z oblasti regulárních a bezkontextových jazyků, přednášky 6-12 se věnují základním principům a konceptům z oblasti vyčíslitelnosti a složitosti formálních jazyků a problémů, poslední přednáška představuje základní principy v oblasti matematického popisu, modelování a analýzy paralelních a distribuovaných dynamických systémů s využitím Petriho sítí.]
Osnova ostatní - projekty, práce:
 
  1. Řešení problému z oblasti regulárních a bezkontextových jazyků. 
  2. Řešení problému z oblasti Turingových strojů a teorie nerozhodnutelnosti. 
  3. Řešení problému z oblasti vyčíslitelných funkcí, složitosti a Petriho sítí.
Literatura referenční:
 
  • Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0
  • 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
  • Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 3. vydání, 2002. ISBN 0-072-32200-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
  • Aho, A.V., Ullmann, J.D.: The Theory of Parsing,Translation and Compiling, Prentice-Hall, 1972. ISBN 0-139-14564-8
  • Reisig, W.: Petri Nets, An Introduction, Springer Verlag, 1985. ISBN: 0-387-13723-8
Literatura studijní:
 
  • Češka, M. a kol.: Vyčíslitelnost a složitost, Nakl. VUT Brno, 1993. ISBN 80-214-0441-8
  • Češka, M., Rábová, Z.: Gramatiky a jazyky, Nakl. VUT Brno, 1992. ISBN 80-214-0449-3
  • Kozen, D.C.: Automata and Computability, Springer-Verlag, New Yourk, Inc, 1997. ISBN 0-387-94907-0
  • Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2nd ed., 2000. ISBN 0-201-44124-1
  • Češka, M.: Petriho sítě, Akad.nakl. CERM, Brno, 1994. ISBN: 8-085-86735-4
Kontrolovaná výuka:
  Písemná zkouška ve 3. týdnu výuky zaměřená na základní znalosti z oblasti regulárních a bezkontextových jazyků, písemná zkouška v 9. týdnu výuky zaměřená na pokročilejší znalosti z oblasti regulárních a bezkontextových jazyků a na Turingovy stroje, průběžná kontrola a hodnocení projektů, závěrečná semestrální zkouška. Pro získání bodů ze závěrečné semestrální zkoušky je nutné tuto zkoušku složit tak, aby byla hodnocena nejméně 25 body. V opačném případě bude zkouška hodnocena 0 body.
Průběžná kontrola studia:
  Bodové hodnocení výsledků zkoušky ve 3. týdnu (max 10 bodů), zkoušky ve 9. týdnu (max 15 bodů), vypracovaných projektů (max. 3-krát 5 bodů) a závěrečné semestrální zkoušky (max 60 bodů).
Podmínky zápočtu:
  Celkový zisk minimálně 15 bodů z prvních dvou úkolů a ze zkoušek v 3. a 9. týdnu (tj. celkem z 35 bodů).