460-4065/01 – Teoretická informatika (TI)

Garantující katedraKatedra informatikyKredity6
Garant předmětudoc. Ing. Zdeněk Sawa, Ph.D.Garant verze předmětudoc. Ing. Zdeněk Sawa, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostvolitelný odborný
Ročník1Semestrzimní
Jazyk výukyčeština
Rok zavedení2015/2016Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
KOT06 Ing. Martin Kot, Ph.D.
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 3+3
kombinovaná Zápočet a zkouška 15+0

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

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

Vyučovací metody

Přednášky
Cvičení (v učebně)

Anotace

Kurs prohlubuje a rozšiřuje teoretické základy v oblasti formálních jazyků, automatů, gramatik, výpočtových problémů a hlavně algoritmů a jejich složitosti, které student měl v základní formě nabýt v bakalářském studiu. Je také kladen speciální důraz na správné používání formalismu matematické logiky a důkazových technik.

Povinná literatura:

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

Doporučená literatura:

- Michael Sipser: Introduction to the Theory of Computation, Thomson 2006 - T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms; The MIT Press, 1990

Forma způsobu ověření studijních výsledků a další požadavky na studenta

E-learning

Další požadavky na studenta

Další požadavky na studenty nejsou kladeny.

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

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ěhu kursu. Speciální důraz bude kladen na správné užívání formalismu logiky 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ím charakterizace 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ři specifikaci (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ých funkcí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ávrhu polynomiálních algoritmů: chytré prohledávání, metoda rozděl a panuj, hltavé (greedy) postupy u 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řídy složitosti. Rozhodnutelnost Presburgerovy aritmetiky. 12. Aproximační algoritmy, tj. polynomiální algoritmy aproximující optimální řešení optimalizačních problémů. (Ne)aproximovatelnost konkrétních problémů. 13. Randomizované algoritmy, např. pro prvočíselnost, která je zá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 v dalších cvičeních.) 2. Procvičení základních jazykových operací; speciálně pak operace kvocientu. Návrh konečných automatů pro jednoduché jazyky a konstrukce složitějších automatů z jednodušších. 3. Návrh nedeterministických konečných automatů, převod na deterministické. 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ůkazy neregularity 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ým gramatiká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 programu RAM. 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.

Podmínky absolvování předmětu

Prezenční forma (platnost od: 2015/2016 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 38 (38) 8
                referát Jiný typ úlohy 10  1
                záp. písemka Písemka 21  7
                aktivita na cvičení Jiný typ úlohy 7  0
        Zkouška Zkouška 62 (62) 25
                první část Písemka 31  11
                druhá část Písemka 31  11
Rozsah povinné účasti: 80% účast na cvičeních

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2020/2021 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 1 volitelný odborný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 1 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 1 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 1 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 1 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 1 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 1 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 1 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 1 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 1 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 1 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 1 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku