PRŮBĚH PŘEDNÁ©KY VÝPOČTOVÁ SLO®ITOST (LETNÍ SEMESTR 2003/2004)

=======================  19.2.2004  ===================================

Třída PSPACE, NP \subseteq PSPACE, definice PSPACE-úplné úlohy.
Kvantifikované Booleovské formule, normální tvar, úloha KBF.
KBF \in PSPACE.
d.cv. Zjistit, zda jazyk vąech konstantních Booleovských výrazů,
které mají hodnotu 1, je regulární, bezkontextový nebo jiného typu.

=======================  26.2.2004  ===================================

Problém KBF je PSPACE-úplný.

=======================   4.3.2004  ===================================

Problém konečná hra na grafech je PSPACE-úplný.
Existence vítězné strategie pro jednoho z hráčů nebo remízní
strategie pro oba hráče pro libovolnou konečnou hru.
Blumova axiomatizace sloľitostních měr.

=======================  11.3.2004  ===================================

Věta o exponenciálním zrychlení (bez důkazu).
Věta o dírách.
Zavedení funkcí konstruovatelných v čase a v prostoru.
Charakterizace pomocí vyčíslení funkce s omezenou sloľitostí.
Postačující podmínka pomocí výpočtu v binární soustavě, důkaz příątě.

=======================  25.3.2004  ===================================

Převod mezi jedničkovou a binární soustavou v logaritmickém
prostoru a lineárním čase.
Postačující podmínka na konstruktivnost funkce na základě
vyčíslitelnosti v binární soustavě
  (K otázce měření prostoru:
  při převodu z jedničkové do binární soustavy se nezapočítává prostor
  pro vstup, ale započítává prostor pro výstup,
  při převodu z binární zpět do jedničkové soustavy se započítává prostor
  pro vstup i výstup)
Algoritmus pro výpočet odmocniny a logaritmu.

=======================   8.4.2004  ===================================

Věty o prostorové a časové hierarchii (k časové hierarchii
napsán algoritmus, zbývá důkaz různosti jazyků).

=======================   15.4.2004  ===================================

Dokončen důkaz časové hierarchie.

Modely pro reprezentaci Booleovských funkcí, obvody, formule,
dnf, knf, rozhodovací diagramy, read-once r. diagramy, r. stromy.
Míry velikosti reprezentace.  Zavedení Poly(M) pro model M.
Vysvětleno, proč Poly(obvody) \supseteq P_{0,1}.
Znázorněn diagram inkluzí Poly(M) pro vybrané modely.
Simulace r. diagramu obvodem, tj. Poly(obvody) \supseteq Poly(r. diagramy).

=======================   22.4.2004  ===================================

Základní pojmy týkající se B.f. podle textu.
Přidáno tvrzení, ľe libovolná B.f. lze vyjádřit disjunkcí vąech
svých mintermů. Příklad neoptimálnosti takto vzniklé dnf.
Samoduální funkce, lineární funkce.

Úplná báze, třídy T_0, T_1, M, S, L.
Příklady úplných bází.
Formulována charakterizace úplných bází, důkaz příątě.
Lemma: Fce dvou proměnných je lineární právě kdyľ má sudý počet
jedniček v tabulce.

=======================   29.4.2004  ===================================

Klasifikace funkcí dvou proměnných.
Zopakování tříd T_0, T_1, M, S, L.
Charakterizace úplných bází (zbývá zkonstruovat konjunkci z nelineární spojky).

=======================    6.5.2004  ===================================

Dokončena charakterizace úplných bází.
Vyjádření parity.
Dolní odhady pro dnf pomocí délky mintermů.
Monotonní funkce má monotonní mintermy.