PRŮBĚH PŘEDNÁŠKY VÝPOČTOVÁ SLOŽITOST (ZIMNÍ SEMESTR 2004/2005)

==========================  12.10.2004  ==============================

Asymptotická složitost, složitost úlohy versus složitost algoritmu.
Příklady úloh algoritmicky neřešitelných, dokazatelně těžkých, pravděpodobně
těžkých a polynomiálně řešitelných.
Značení O, Omega, Theta.
Úlohy na výpočet funkce, rozhodovací, vyhledávací a optimalizační úlohy.
Ekvivalence rozhodovací a vyhledávací verze Hamiltonovské kr. a SAT,
Ekvivalence rozhodovací a optimalizační verze MAX-SAT.

==========================  19.10.2004  ==============================

Obecná kostrukce rozhodovací úlohy se složitostí odpovídající
výpočtu nějaké funkce.
Vícepáskový TS, jazyk pro zápis programu pro TS.
Simulace vícepáskového TS dvoupáskovým v čase t log t bez důkazu.
První část simulace vícepáskového stroje jednopáskovým v čase t^2.

==========================  26.10.2004  ==============================

Dokončení simulace vícepáskového stroje jednopáskovým.
Zavedení RAM, jednotková a logaritmická míra složitosti.
Simulace TS pomocí RAM v lineární jednotkové míře.
Simulace RAM pomocí TS v čase O(b^2) a O(k^2 log k).

==========================  2.11.2004  ==============================

Booleovské obvody, báze, úplná báze.
Obvod v libovolné bázi \Omega lze převést do báze {negace, disjunkce, konjunkce} 
jen s lineárním nárůstem velikosti.
Třída NP, p-převoditelnost,
L_1 p-přev. na L_2, L_2 \in P => L_1 \in P.
p-přev. je tranzitivní.
Zavedení NP-úplných úloh.
SAT je NP-úplný - zatím jen konstrukce posloupnosti obvodů,
které rozpoznávají R a jsou polynomiálně velké.

==========================  9.11.2004  ==============================

Dokončení důkazu, že splnitelnost obvodů je NP-úplná
a důkaz, že SAT a 3-SAT jsou NP-úplné.
Problém přesného 3-pokrytí je NP-úplný.
Problém přesného k-pokrytí (k \ge 3) je NP-úplný.

==========================  16.11.2004  ==============================

Problém batohu a problém dvou loupežníků jsou NP-úplné.
Popsán problém obchodního cestujícího, převod Ham. kr.
Algoritmus pro problém batohu v čase O(nb).
Úplnost rezoluční metody, polynomiální algoritmus pro 2-SAT.
Příprava pro 1.5 aproximační algoritmus, tj. Eulerovské
grafy, existence p-algoritmu pro minimální kostru
a párování.
Neříkal jsem aprox. vrcholového pokrytí.

==========================  23.11.2004  ==============================

Aproximační algoritmy pro
 - problém obchodního cestujícího s faktorem 1.5.
 - vrcholové pokrytí s faktorem 2.
 - množinové pokrytí s faktorem zhruba \log m.
 - problém maximálního řezu s faktorem 2.

==========================  30.11.2004  ==============================

PSPACE, PSPACE-úplnost.
KBF, PSPACE-úplnost problému KBF.

==========================  7.12.2004  ==============================

Převod formule f(w) z důkazu PSPACE úplnosti KBF do normální formy.
Jazyk všech Booleovských výrazů s hodnotou 1 je bezkontextový.
Náznak důkazu, že konečné hry mají vítěznou strategii pro jednoho
 z hráčů nebo remízní strategii pro oba hráče.
Zavedena hra na grafech a dokázána její PSPACE-úplnost.
Zavedeno co-NP.
Pravděpodobnostní důkaz neizomorfnosti grafů.
Polynomiální hierarchie, vztah k PSPACE.
Blumovy axiomy pro složitostní míry, věta o zrychlení bez důkazu.
Formulována věta o dírách.

==========================  14.12.2004  ==============================

Důkaz věty o dírách.
Zavedení konstruovatelnosti v čase a v prostoru.
Charakterizace pomocí vyčíslení v omezeném čase a prostoru.
Konstruovatelnost funkcí vyčíslitelných v binární
 soustavě v poly-čase a lineárním prostoru.
Numerický výpočet odmocniny a logaritmu.
Věta o prostorové hierarchii.

==========================  21.12.2004  ==============================

Věta o časové hierarchii.

==========================  4.1.2005  ==============================

NP-úplnost problému Hamiltonovské kružnice, MAX-2-SAT, NAE-SAT.

==========================  11.1.2005  ==============================

NP-úplnost problému MAX-CUT.
Ukázka nikoli ke zkoušce: pravděpodobnostní aproximační algoritmus pro MAX-CUT
(Goemans-Williamsonův) s faktorem alpha = 1.138217.

Rovnice odvozená v přednášce byla špatně. Správně má být
1/(pi*sqrt(1-t^2)) = acos(t)/(pi*(1-t)) = eps/2 = 1/(2*alpha)
a dává řešení t = -0.6891577, eps = 0.8785672, alpha = 1.138217.