Název:

Teoretická informatika (v angličtině)

Zkratka:TINe
Ak.rok:2018/2019
Semestr:letní
Studijní plán:
ProgramObor/
specializace
RočníkPovinnost
IT-MGR-2MGMe1.povinný
Vyučovací jazyk:angličtina
Aktuální informace:
* This course is prepared for incoming Erasmus+ students only, and it is instructed in English.
* This course will be open if a certain/sure minimum of enrolled students is at least five students.

Kredity:5 kreditů
Ukončení:zápočet+zkouška (kombinovaná)
Výuka:
hod./sempřednáškasem./cvič.lab. cvič.poč. cvič.jiná
Rozsah:3900013
 zkouškatestycvičenílaboratořeostatní
Body:60200020
Garant:Češka Milan, prof. RNDr., CSc. (UITS)
Zástupce garanta:Češka Milan, RNDr., Ph.D. (UITS)
Přednášející:Češka Milan, RNDr., Ph.D. (UITS)
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav inteligentních systémů FIT VUT v Brně
Rozvrh:
DenVýukaTýdenMístnostOdDoPSKSkupiny
Pozkouška - 2nd term2019-05-27E105 14:0016:501EIT 2EIT INTE
Pozkouška - 3rd term2019-06-03A113 14:0016:501EIT 2EIT INTE
zkouška - 1st term2019-05-17E104 13:0015:501EIT 2EIT INTE
 
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.
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, aplikace teorie formálních jazyků, modelovací a rozhodovací síla formálního modelu, operace nad jazyky.
  2. Regulární jazyky a jejich vlastnosti, Kleenova věta, Nerodova věta, věta o vkládání (Pumping theorem).
  3. Minimalizace konečného automatu, relace nerozlišitelnosti stavů, konstrukce redukovaného konečného automatu.
  4. Uzávěrové vlastnosti regulárních jazyků, regulární jazyky jako množinová Booleova algebra, rozhodnutelné problémy regulárních jazyků.
  5. Bezkontextové jazyky a jejich vlastnosti. Normální tvary bezkontextových gramatik, jednoznačné a deterministické bezkontextové jazyky, věta o vkládání pro bezkontextové jazyky.
  6. Uzávěrové vlastnosti bezkontextových jazyků, uzavřenost vzhledem k substituci, důsledky, rozhodnutelné problémy bezkontextových jazyků.
  7. 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.
  8. 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 čitači.
  9. TS a jazyky typu 0, diagonalizace, vlastnosti rekurzivních a rekurzivně vyčíslitelných jazyků, lineárně ohraničené automaty a jazyky typu 1.
  10. Vyčíslitelné funkce, počáteční funkce, primitivně rekurzivní funkce, mí-rekurzivní funkce, vztah vyčíslitelných funkcí a Turingových strojů.
  11. Church-Turingova téze, univerzální TS, nerozhodnutelnost, problém zastavení TS, redukce, Postův korespondenční problém.
  12. Nerozhodnutelné problémy teorie formálních jazyků.
  13. Úvod do výpočetní složitosti, Turingovská složitost, třída P a NP problémů.
Osnova ostatní - projekty, práce:
 
  • Řešení problému z oblasti regulárních jazyků a konečných automatů.
  • Řešení problému z oblasti bezkontextových jazyků.
  • Řešení problému z oblasti Turingových strojů.
  • Řešení problému z oblasti vyčíslitelných funkcí.
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
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
Kontrolovaná výuka:
  Písemná půlsemestrální zkouška, průběžná kontrola a hodnocení projektů.
Průběžná kontrola studia:
  Bodové hodnocení výsledků půlsemestrální zkoušky (max 20 bodů) a vypracovaných projektů (max. 20 bodů).
Podmínky zápočtu:
  Celkový zisk minimálně 15 bodů z prvních třech úkolů a z půlsemestrální zkoušky (tj. celkem z 35 bodů).
 

Vaše IPv4 adresa: 34.204.0.181
Přepnout na https