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.