460-4005/01 – Teoretická informatika (TI)
Garantující katedra | Katedra informatiky | Kredity | 8 |
Garant předmětu | prof. RNDr. Petr Jančar, CSc. | Garant verze předmětu | prof. RNDr. Petr Jančar, CSc. |
Úroveň studia | pregraduální nebo graduální | Povinnost | povinně volitelný |
Ročník | 1 | Semestr | letní |
| | Jazyk výuky | čeština |
Rok zavedení | 2010/2011 | Rok zrušení | 2014/2015 |
Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
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ě)
Projekt
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
algoritmů, které student měl v základní formě nabýt v bakalářském
studiu.
Povinná literatura:
Petr Jančar: Teoretická informatika, VŠB-TU, Ostrava, 2007
(dostupná z web-stránky předmětu)
Doporučená literatura:
Petr Jančar: Teoretická informatika, VŠB-TU, Ostrava, 2007
(dostupná z web-stránky předmětu)
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 studenta nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
Úvod ke kursu: celkový přehled. Základní pojmy z oblasti formálních
jazyků. Konečné automaty a jazyky jimi rozpoznávané. Modulární návrh
konečných automatů.
Dosažitelné stavy u konečných automatů, normovaný tvar. Minimální
automaty a algoritmus minimalizace. Regulární a neregulární jazyky;
Charakterizace regulárních jazyků umožňující důkazy neregularity.
Nedeterministické konečné automaty; jejich uplatnění
v návrhu deterministických konečných automatů.
Regulární operace.
Regulární výrazy jako prostředek popisu regulárních jazyků.
Ekvivalence konečných automatů, regulárních výrazů a regulárních
gramatik.
Uzávěrové vlastnosti třídy regulárních jazyků.
Další varianty konečně
stavových modelů (dvoucestné konečné automaty, konečně stavové
převodníky, ...).
Bezkontextové gramatiky a jazyky.
Ilustrace významu bezkontextových gramatik pro (syntaxí řízený)
překlad, speciálně na gramatice generující regulární výrazy.
Jednoznačné gramatiky.
Redukované a nevypouštějící bezkontextové gramatiky.
Zásobníkové automaty. Vztah mezi zásobníkovými automaty a
bezkontextovými gramatikami.
Deterministické zásobníkové automaty.
Uzávěrové vlastnosti třídy bezkontextových jazyků.
Chomského normální forma bezkontextových gramatik.
Pumping lemma pro bezkontextové jazyky a jeho použití.
Obecné generativní gramatiky. Turingovy stroje. Chomského hierarchie.
Složitost algoritmu. Model RAM. Asymptotické odhady růstu funkcí, značení.
Obecné metody návrhu (efektivní prohledávání, hltavé algoritmy, ...)
a analýza složitosti vybraných (polynomiálních) algoritmů.
Další metody návrhu polynomiálních algoritmů (rozděl a panuj,
dynamické programování, ...).
Problémy, třídy složitosti problémů, horní a dolní odhady složitosti problémů.
Vzájemná polynomiální simulace rozumných výpočetních modelů.
Třída PTIME, její robustnost, význam.
Nedeterministické Turingovy stroje.
Třída NPTIME. Otázka `P=NP~?'. Polynomiální převeditelnost mezi problémy. NP-úplnost
a konkrétní NP-úplné problémy.
Další třídy časové i prostorové složitosti a jejich vzájemné vztahy.
Dokazatelně nezvládnutelné problémy.
Church-Turingova teze. Rozhodnutelnost a částečná rozhodnutelnost problémů.
Univerzální Turingův stroj. Metoda diagonalizace,
nerozhodnutelnost problému zastavení.
Algoritmická převeditelnost, další nerozhodnutelné problémy. Riceova věta.
Nástin problematiky aproximačních, pravděpodobnostních,
paralelních a distribuovaných algoritmů.
Cvičení:
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.
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ů.
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ů.
Převody mezi konečnými automaty, regulárními výrazy a regulárními
gramatikami. Procvičení
uzávěrových vlastností třídy regulárních jazyků.
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ů.
Převody mezi bezkontextovými gramatikami a zásobníkovými automaty.
Návrhy
deterministických zásobníkových automatů.
Procvičení uzávěrových vlastností třídy bezkontextových jazyků.
Převod gramatik do Chomského normální formy.
Důkazy nebezkontextovosti jazyků pomocí
pumping lemmatu.
Konstrukce Turingových strojů.
Procvičení porovnání asymptotického růstu konkrétních funkcí.
Návrh a analýza složitosti konkrétních
(polynomiálních) algoritmů.
Procvičení několika
obecných metod návrhu polynomiálních algoritmů.
Návrh vzájemné simulace mezi konkrétními výpočetními modely.
Návrh nedeterministických polynomiálních algoritmů.
Prokázání polynomiální převeditelnosti mezi konkrétními problémy.
Prokazování příslušnosti jednotlivých problémů k PTIME, NPTIME, PSPACE,
NPSPACE a prokazování NP- a PSPACE-obtížnosti.
Konstrukce částí univerzálního Turingova stroje.
Důkazy nerozhodnutelnosti problémů. Aplikace Riceovy věty.
Procvičení vybraných témat z aproximačních a pravděpodobnostních
algoritmů.
Projekty:
Každému studentu bude na začátku semestru přiděleno vybrané téma
související s náplní kurzu. Student téma nastuduje z určených a/nebo samostatně
vyhledaných zdrojů, samostatně zpracuje a výsledek zpracování odevzdá
v elektronické a písemné formě cvičícímu; musí přitom dodržet
stanovený termín a minimální rozsah vytvořeného materiálu.
Porozumění zpracovanému tématu bude prověřeno
u studentů denního studia jejich referátem na
určeném cvičení a u studentů kombinovaného studia diskusí
se zkoušejícím v dohodnutém termínu.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky