PRŮBĚH PŘEDNÁŠKY VÝPOČTOVÁ SLOŽITOST (ZIMNÍ SEMESTR 2009/2010)
========================== 30.9.2009 ==============================
algoritmicky neřešitelné úlohy
- řešitelnost polynomů více proměnných v celých číslech
- L(G) = \Sigma^*
- L(G_1) \cap L(G_2) \not = \emptyset
dokazatelně obtížné úlohy, ale řešitelné
problém zastavení TS v daném čase
dokazatelnost v Presburgerově aritmetice
dokazatelnost v Aritmetice reálných čísel
pravděpodobně exponenciálně těžké úlohy
úlohy TAUT, SAT
pro k-SAT složitost 2^((1-eps)n)
Strassenův algoritmus násobení matic
násobení přirozených čísel ve složitosti n^{log_2 3}
algoritmy pro násobení matic složitosti n^\alpha pro různá \alpha
zmínka o větě o zrychlení - existuje úloha, která nemá nejefektivnější algoritmus
typy úloh
- rozhodovací
- výpočet funkce
- vyhledávací úloha
problém kliky ve formulaci jako
- rozhodovací úloha (existuje klika velikosti alespoň b?)
- výpočet funkce (velikost maximální kliky)
- vyhledávací úloha (najít některou maximální kliku)
========================== 7.10.2009 ==============================
Problém batohu, problém půlení, Hamiltonovská kružnice.
Převod vyhledávacích úloh na rozhodovací pro SAT a Hamiltonovskou kružnici.
Převod SAT na problém kliky a naopak.
Kódování vstupu pomocí posloupností symbolů, požadavek efektivního kódování.
Vícepáskový TS, zavedení časové a prostorové složitosti.
========================== 14.10.2009 ==============================
Program vícepáskového stroje, způsoby ukončení.
Třídy DTIME(t), DSPACE(s), P, PSPACE.
Random access machine, struktura, typy adresace, míry složitosti.
Věty o vzájemné simulaci TS a RAM v polynomiálním čase (bez důkazu).
Důkaz ekvivalence polynomiální složitosti pro výpočet polynomiálně omezené funkce
a z ní odvozené rozhodovací úlohy.
Začátek zavedení Booleovských obvodů.
Konstrukce formule velikosti O(2^n) pro libovolnou funkci n proměnných.
Zmínka o konstrukci obvodu velikosti O(2^n/n) pro libovolnou funkci n proměnných (bez důkazu)
(plyne z Věty 6.1 v textu http://www.cs.cas.cz/~savicky/vyuka/rbf/rbf.pdf).
========================== 21.10.2009 ==============================
Simulace vícepáskového TS pomocí jednopáskového TS.
Kódování obecné abecedy pomocí kombinací fixovaného počtu bitů.
Reprezentace jazyka pomocí posloupnosti obvodů.
Posloupnosti obvodů polynomiální složitosti a polynomiálně konstruovatelné.
Jazyk v P lze reprezentovat polynomiálně konstruovatelnou posloupností obvodů.
Třída NP, zavedení pomocí existenční kvantifikace.
Třída co-NP.
Polynomiální převoditelnost, definice NP-úplné a NP-těžké úlohy.
Pro libovolnou NP-úplnou úlohu L platí L \in P právě tehdy, když NP = P.
========================== 4.11.2009 ==============================
Problém 3-SAT je NP-úplný (Cookova věta), důkaz v následujících krocích:
- převod libovolné NP-úlohy na splnitelnost obvodů,
- převod splnitelnosti obvodů na SAT,
- převod SAT na 3-SAT.
Problém přesného 3-pokrytí je NP-úplný, převodem z 3-SAT.
========================== 11.11.2009 ==============================
NP-úplnost problémů batohu, půlení a Hamiltonovské kružnice.
Problém TSP je NP-těžký, při omezení vah hran na čísla s polynomiálně
dlouhým zápisem je NP-úplný.
========================== 18.11.2009 ==============================
NP-úplnost problému MAX-2-SAT převodem z 3-SAT nebo z problému kliky.
Množina klausulí je nesplnitelná právě tehdy, když z ní lze odvodit spor
(prázdnou klausuli) pomocí rezoluce.
Popsána Quinova procedura. V popisu chyběl jeden případ. Opravená verze je následující:
Vstup: seznam klausulí F (popisující vstupní funkci f)
Postup:
Vytvoříme seznam klausulí P inicializovaný jako prázdný.
Dokud je F neprázdný, opakujeme následující.
Vezmeme některou klausuli c z F.
Přidáme c do P a vypustíme ji z F.
Všechny rezolventy c s ostatními klausulemi v P přidáme do F.
Zredukujeme seznamy F a P tím, že vypustíme všechny klausule, pro
které existuje v F nebo P klausule, která jej její vlastní podmnožinou.
Výstup: Seznam P obsahuje právě všechny primární implikáty funkce určené vstupním seznamem F.
(Výklad v přednášce nerozlišoval seznamy F a P, což není podstatný rozdíl. Také neuvažoval
odstranění klausule, která v seznamu byla dříve, pokud je nová klausule její podmnožinou.
Toto je podstatné. Postup z přednášky může vytvořit seznam klausulí, který neobsahuje jen
primární implikáty, ale i některé další.)
========================== 25.11.2009 ==============================
Dokončení polynomiálního algoritmu pro 2-SAT.
Quineova procedura získání všech primárních implikátů.
Algoritmus pro problém batohu, který je polynomiální ve velikosti
vstupních čísel.
Aproximační algoritmus pro problém vrcholového pokrytí s faktorem 2.
Eulerovský graf obsahuje uzavřený sled, existují polynomiální
algoritmy pro nalezení kostry a úplného párování s minimálním součtem
vah hran, které jsou v nich obsaženy.
========================== 2.12.2009 ==============================
Aproximační algoritmy pro TSP s faktorem 2 a 3/2.
Aproximační algoritmus pro problém množinového pokrytí s aproximačním
faktorem logaritmus velikosti základní množiny.
Střední hodnota součtu libovolných náhodných veličin je součet středních
hodnot těchto veličin. Střední hodnota součinu nezávislých náhodných
veličin je součin středních hodnot těchto veličin. Obojí zatím bez důkazu.
Příklad náhodné veličiny s konečným mediánem a nekonečnou střední hodnotou.
Pravděpodobnostně ověřitelný protokol pro demonstraci neizomorfnosti grafů.
========================== 9.12.2009 ==============================
Zmínka o Ramseyovských grafech.
Vysvětlení pojmu střední hodnota a vyjádření střední hodnoty
součtu libovolných a součinu nezávislých náhodných veličin.
Deterministický postup splnění alespoň jedné poloviny neprázdných
klausulí.
Vyjádření pravděpodobnosti splnění jedné klausule při nezávislém
ohodnocení proměnných s pravděpodobností jedničky 1/2.
========================== 6.1.2010 ==============================
Pravděpodobnostní algoritmus pro MAX-SAT s faktorem 3/4.
Převedení tohoto algoritmu na deterministický pomocí multilineárního polynomu.