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

==========================  20.2.2008  ==============================

Přednáška se nekonala.

==========================  27.2.2008  ==============================

Zopakování:
 - NP-úplnost problému vrcholového pokrytí
 - optimalizační úloha
 - definice aproximačního faktoru pro aproximační algoritmus
NP-úplnost problému Hamiltonovské kružnice převodem
z problému vrcholového pokrytí
(Dokázáno, že z existence vrcholového pokrytí v původní
instanci plyne existence Hamiltonovské kružnice 
v odvozené instanci).

==========================  5.3.2008  ==============================

Přednáška se nekonala.

==========================  12.3.2008  ==============================

Dokončení NP-úplnosti Hamiltonovské kružnice.
Problém obchodního cestujícího, varianty: obecná, metrická, Euklidovská.
NP-úplnost metrické varianty s celočíselnými vzdálenostmi.
Eulerovský graf, minimální kostra grafu, minimální párování.
Aproximační algoritmus pro problém obchodního cestujícího s faktorem 3/2.

==========================  19.3.2008  ==============================

NP-úplnost problému MAX-2-SAT převodem z problému kliky
nebo z problému 3-SAT.
NP-úplnost problému NAE-SAT. Naznačeno, jak se použije
pro důkaz NP-úplnosti MAX-CUT.

==========================  26.3.2008  ==============================

Dokončení důkazu NP-úplnosti MAX-CUT.
Aproximační algoritmy pro MAX-CUT a MAX-SAT s faktorem 1/2.
Vyjádření úlohy MAX-SAT pomocí celočíselného lineárního programování.

==========================  2.4.2008  ==============================

Přednáška se nekonala.

==========================  9.4.2008  ==============================

Odhad střední hodnoty počtu splněných klausulí při pravděpodobnostech
proměnných vypočtených pomocí relaxace úlohy celočíselného programovaání.
Důkaz faktoru 3/4 pro zkombinovaný algoritmus.
Formulována věta o neaproximovatelnosti MAX-3-SAT.
Důsledek pro neaproximovatelnost problému kliky.

==========================  16.4.2008  ==============================

Neaproximovatelnost kliky s libovolným kladným faktorem.
Třída PCP, PCP věta, důsledek pro neaproximovatelnost MAX-SAT.
PSPACE, NP \subseteq PSPACE.
\Sigma_k, \Pi_k, PSPACE není právě sjednocení \Sigma_k, pokud
je hierarchie nekonečná.

==========================  23.4.2008  ==============================

KBF, PSPACE-úplnost KBF
hra na grafech, PSPACE-úplnost hry na grafech

==========================  30.4.2008  ==============================

Eukleidův algoritmus, složitost nejhoršího případu,
vyjádření (a,b) = xa + yb.
Okruh Z_m, řešení rovnic ax=1 (m) při (a,m)=1.
Grupa Z_m^*, Eulerova funkce a Eulerova věta.
Čínská věta o zbytcích.
Zbývá dokázat vyjádření Eulerovy funkce.

==========================  7.5.2008  ==============================

Výpočet Eulerovy funkce.
Kryptografický systém s veřejným klíčem RSA, Diffie-Hellman protokol pro
distribuci tajného klíče.
Popis základních Booleovských modelů kromě read-once rozhodovacích diagramů.