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

==========================  10.10.2006  ==============================

Příklady algoritmicky nerozhodnutelných úloh, dokazatelně složitých úloh
a úloh pravděpodobně složitých.
Typy úloh a jejich formalizace: výpočet funkce, rozhodovací úloha,
vyhledávací úloha, optimalizační úloha.
Výpočetní modely a měření složitosti: vícepáskový TS, časová a prostorová
složitost jako funkce vstupu, složitost v nejhorším případě jako funkce
délky vstupu.
Značení O, \Omega, \Theta.

==========================  17.10.2006  ==============================

Přednáška se nekonala.

==========================  24.10.2006  ==============================

RAM, míry složitosti.
Booleovské obvody, rozdíl proti formulím.
Transformace obvodu v obecné bázi do de Morganovy báze.
Třídy složitosti DTIME, DSPACE
Diskuse adekvátnosti popsaného modelu pro studium složitosti:
 - složitost se uvažuje jen asymptoticky, což umožňuje
   matematické zkoumání, ale někdy se tím model vzdaluje
   od prakticky důležitých výpočtů, které se týkají
   vstupů omezené velikosti,
 - je potřeba pracovat s efektivním kódováním,
 - vztah složitosti rozhodovacích a obecných úloh
   (je třeba ještě spočítat složitost).

==========================  31.10.2006  ==============================

Dokončení převodu výpočtu obecné funkce na rozhodovací úlohu.
Programovací jazyk pro TS.
Simulace k-TS na 1-TS a 2-TS.
Simulace 1-TS na RAM.

==========================  7.11.2006  ==============================

Odhad složitosti simulace TS na RAM (čas O(t), O(t logt)).
Simulace RAM na TS (čas O(b^2), O(k^2 log k)).

Třída NP, zavedení přes existenční kvantifikaci.
Porovnávání složitosti úloh pomocí p-převoditelnosti.
Tranzitivita p-převoditelnosti.

==========================  14.11.2006  ==============================

p-převoditelnost SAT na problém kliky.
NP-úplné úlohy.
SAT je NP-uplný (převodem přes splnitelnost obvodů).
3-SAT je NP-úplný (s využitím (\le 3)-SAT).
SAT je p-převoditelný na 3-SAT.
Formulace problému batohu a přesného 3-pokrytí.

==========================  21.11.2006  ==============================

NP-úplnost problémů: přesné 3-pokrytí, problém batohu, problém rozdělení,
problém vrcholového pokrytí, Hamiltonovská kružnice.

==========================  28.11.2006  ==============================

Celková struktura důkazu NP-úplnosti Hamiltonovské kružnice.
Problém batohu s malými čísly (poly algoritmus od velikosti
  vstupních čísel).
Úplnost rezoluce, (\le 2)-SAT je v P.
Aproximace problému vrcholového pokrytí.

==========================  5.12.2006  ==============================

Obecná, metrická a Eukleidovská verze problému obchodního cestujícího.
Metrická verze je NP-úplná.
Aproximační algoritmus pro metrickou verzi s faktorem 3/2.
Aproximační algoritmus pro problém množinového pokrytí (analýza hladového algoritmu).

==========================  12.12.2006  ==============================

Důkaz NP-úplnosti následujících problémů
 - MAX-2-SAT (z 3-SAT nebo z problému kliky)
 - NAE-SAT (ze splnitelnosti obvodů)
 - MAX-CUT (z NAE-SAT)

==========================  19.12.2006  ==============================

Pravděpodobnostní aproximační algoritmus pro MAX-CUT.
Deterministická verze pomocí metody postupného upřesňování.
Dvě verze výpočtu: kombinatorická a přes multilineární polynom.