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.
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.