Předmět Teoretická informatika (TI)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu TI - Teoretická informatika, Vysoká škola báňská - Technická univerzita Ostrava (VŠB-TU).

Materiál	Typ	Datum	Počet stažení

Cíl

Student po úspěšném absolvování předmětu:- umí vyhodnotit vhodnost a rozsah možného nasazení metod konečných automatů, bezkontextových gramatik apod. při řešení konkrétních problémů praxe a umí příslušná řešení vytvářet, analyzovat a porovnávat- je schopen analyzovat výpočtovou složitost problémů vyskytujících se v inženýrské praxi a navrhovat vhodné algoritmy pro jejich řešení- rozumí pojmům jako aproximační algoritmy, pravděpodobnostní algoritmy apod. a umí vyhodnotit možnosti jejich použití v konkrétních praktických kontextech

Osnova

Přednášky:1. Přehled kursu.Připomenutí základních množinových pojmů, relace ekvivalence,uspořádání, grafů, formalismu výrokové a predikátové logiky, důkazůindukcí a sporem. (Všechny tyto pojmy a metody budou průběžně používány v průběhukursu. Speciální důraz bude kladen na správné užívání formalismulogiky a pravidel usuzování.)2. Formální jazyky, operace na jazycích, regulární výrazy jako reprezentace jazyků,algoritmus vyhledávání vzorku v textu prezentovaný jako(deterministický) konečnýautomat. Modulární návrh konečných automatů (KA), s využitímcharakterizace jazyka logickými formulemi.3. Deterministické a nedeterministické konečné automaty, operace s konečnými automaty,převod nedeterministického KA na deterministický,sestrojení KA k regulárnímu výrazu (RV).4. Minimalizace DKA, kanonický tvar, izomorfismus automatů.KA a RV definují stejnou třídu, tzv. regulární jazyky.Charakterizace regulárních jazyků umožňujícídůkazy neregularity; využití logického důkazu sporem.5. Bezkontextové gramatiky, jejich (ne)jednoznačnost, užití přispecifikaci (fragmentů) programovacích jazyků a logických formalismů.(Nedeterministické) zásobníkové automaty (ZA). Syntaktická analýza (rekurzivním sestupem).6. Bezkontextové jazyky a jejich podtřída analyzovatelná deterministickými ZA. Základy jednoduchého překladače (konstruujícího kon. automat k danému reg. výrazu).7. Nebezkontextové jazyky, Chomského hierarchie. Formální jazyk jako výpočetní problém.Pojem algoritmu, modely výpočtu (Turingův stroj, RAM, zmínka o rekurzivních a lambda-vyčíslitelnýchfunkcích).8. Church-Turingova teze. Univerzální stroj.(Algoritmická) nerozhodnutelnost, problém zastavení, převeditelnost (redukce) mezi problémy. Riceova věta (každá netriviální vstupně/výstupnívlastnost programů je nerozhodnutelná).Algoritmická nerozhodnutelnost logických teorií (speciálně standardníaritmetiky).9. Výpočetní složitost algoritmů, obecné metody návrhupolynomiálních algoritmů: chytré prohledávání, metoda rozděl a panuj, hltavé (greedy) postupyu optimalizačních algoritmů, dynamické programování.10. Výpočetní složitost problémů, třídy složitosti,polynomiální převeditelnost mezi problémy.Problém SAT (splnitelnost booleovských formulí) a nedeterministicképolynomiální algoritmy. Třída NPTIME. NP-úplnost.11. Třída PSPACE=NPSPACE, PSPACE-úplné problémy, vyšší třídysložitosti. Rozhodnutelnost Presburgerovy aritmetiky.12. Aproximační algoritmy, tj. polynomiální algoritmy aproximujícíoptimální řešení optimalizačních problémů. (Ne)aproximovatelnostkonkrétních problémů.13. Randomizované algoritmy, např. pro prvočíselnost, která jezákladem pro kryptografické algoritmy.14. Příklady paralelních algoritmůa neparalelizovatelných (vnitřně sekvenčních) problémů.Cvičení (na tabulové učebně):1. Procvičení základních množinových pojmů, relace ekvivalence,uspořádání, grafů, formalismu výrokové a predikátové logiky, důkazůindukcí a sporem. (Toto bude také průběžně procvičováno na konkrétních příkladech vdalších cvičeních.)2. Procvičení základních jazykových operací; speciálně pak operacekvocientu. Návrh konečných automatů pro jednoduché jazyky a konstrukcesložitějších automatů z jednodušších.3. Návrh nedeterministických konečných automatů, převod nadeterministické. Procvičení regulárních výrazů jako prostředku popisu regulárních jazyků.4. Procvičení algoritmů pro převod do normovaného tvaru a zjišťováníizomorfismu automatů. Procvičení algoritmu minimalizace. Důkazyneregularity konkrétních jazyků.5. Návrh konkrétních bezkontextových gramatik.Převod konkrétních (nejednoznačných) gramatik na jednoznačné.Procvičení algoritmů redukce a odstranění epsilon-pravidel.Konstrukce zásobníkových automatů, ekvivalentních bezkontextovýmgramatikám.6. Sestrojení překladače konstruujícího kon. automat k danému reg. výrazu.7. Důkazy nebezkontextovosti jazyků pomocípumping lemmatu. Konstrukce jednoduchého Turingova stroje a programuRAM.8. Procvičení důkazu nerozhodnutelnosti konkrétních problémů.Procvičení aplikace Riceovy věty. 9. Procvičení několika obecných metod návrhu polynomiálních algoritmůna konkrétních příkladech.10. Návrh nedeterministických polynomiálních algoritmů.Prokázání polynomiální převeditelnosti mezi konkrétními problémy.11. Prokazování příslušnosti jednotlivých problémů k PTIME, NPTIME, PSPACE,NPSPACE a prokazování NP- a PSPACE-obtížnosti.12. Konstrukce a analýza aproximačních algoritmů pro vybranéoptimalizační problémy.13. Analýza vybraných randomizovaných algoritmů.14. Návrh paralelního algoritmu. Připomenutí témat písemné zkoušky.

Literatura

- Petr Jančar: Teoretická informatika, VŠB-TU, Ostrava, 2007(dostupná z web-stránky předmětu)

Požadavky

Žádné

Garant

prof. RNDr. Petr Jančar, CSc.

Vyučující

prof. RNDr. Petr Jančar, CSc.Ing. Martin Kot, Ph.D.Ing. Ondřej MecaIng. Martin Šurkovský