456-0330/01 – Teoretická informatika (TI)

Garantující katedraKatedra informatikyKredity8
Garant předmětuprof. RNDr. Petr Jančar, CSc.Garant verze předmětuprof. RNDr. Petr Jančar, CSc.
Úroveň studiapregraduální nebo graduálníPovinnostpovinně volitelný
Ročník1Semestrletní
Jazyk výukyčeština
Rok zavedení2003/2004Rok zrušení2009/2010
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
BOH126 Ing. Stanislav Böhm, Ph.D.
JAN59 prof. RNDr. Petr Jančar, CSc.
KOT06 Ing. Martin Kot, Ph.D.
SAW75 doc. Ing. Zdeněk Sawa, Ph.D.
SKN002 Ing. Petra Schreiberová, Ph.D.
TAK003 Ing. Ondřej Takács
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 4+2
kombinovaná Zápočet a zkouška 10+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ě)
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:

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

E-learning

Další požadavky na studenta

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

Kombinovaná forma (platnost od: 2008/2009 letní semestr, platnost do: 2010/2011 letní 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 35 (35) 9
                1. zápočtová písemka Písemka 12  0
                2. zápočtová písemka Písemka 12  0
                Referát Projekt 11  1
        Zkouška Zkouška 65  25
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2009/2010 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinně volitelný stu. plán
2009/2010 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 1 povinně volitelný stu. plán
2009/2010 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinně volitelný stu. plán
2009/2010 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 1 povinně volitelný stu. plán
2009/2010 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2009/2010 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinně volitelný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinně volitelný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 1 povinně volitelný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 1 povinně volitelný stu. plán
2008/2009 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2007/2008 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2007/2008 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinně volitelný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinně volitelný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 1 povinně volitelný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 1 povinně volitelný stu. plán
2006/2007 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2006/2007 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 1 povinně volitelný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 1 povinně volitelný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie P čeština Ostrava 1 povinně volitelný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (2612T059) Mobilní technologie K čeština Ostrava 1 povinně volitelný stu. plán
2005/2006 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2005/2006 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 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