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

==========================  4.10.2005  ==============================

Asymptotická složitost (čas a prostor jako funkce velikosti vstupních dat).
Uniformní a neuniformní modely (jeden algoritmus nebo pro každou velikost dat jiný).
Složitost úlohy nelze definovat narozdíl od složitosti algoritmu (existují
   úlohy s neomezeným zrychlováním).
Převod problému splnitelnosti (SAT) na problém kliky.
Třída P a NP (zavedení pomocí existenční kvantifikace).
Vztah tříd P a NP a NP-úplné úlohy.
Zavedení RAM (instrukce a registry)
  jednotková složitost s polynomiálním omezením velikosti mezivýsledků
  logaritmická (bitová) složitost
Násobení matic, komplexních čísel, čísel v binárním zápisu (rozklad
   (a_1*10^k + a_2) * (b_1*10^k + b_2), nedodělána rekurze)
Zmínka o polynomiálnosti testu na prvočíslo.
Pravděpodobnostní důkaz neizomorfnosti grafů.

==========================  11.10.2005  ==============================

Rekurzvní algoritmus násobení binárně zapsaných přirozených čísel složitosti n^{log_2 3}.
Zopakován problém asymptotické složitosti v porovnání s prakticky důležitými úlohami.
Problém neexistence odhadů složitosti pro mnoho důležitých úloh (jen relativní výsledky).
Diagram tříd NP, NP-úplné, P.

Nerozhodnutelnost některých problémů pro bezk.gram.
Problém slov v obecné algebře a grupě.
Algoritmická neřešitelnost polynomiálních rovnic v celých číslech.

Zavedení typů úloh a jejich reprezentace pomocí slov a jazyků 
 - výpočet funkce,
 - rozhodovací úlohy,
 - vyhledávací úlohy,
 - optimalizační úlohy.
Příklady řešení vyhledávání pomocí rozhodování (Hamilt. kružnice, problém SAT).
Nedořešen problém hledání důkazu pomocí znalosti dokazatelnosti vět.

Značení O(f), \Omega(f), \Theta(f).

Věta o ekvivalenci složitosti f a L_f, pokud délka f(w) poly-omezená.
Problém efektivního kódování.

Problémy se složitostí porovnávání a přenosu úseků pásky na jednopáskovém TS.
Popis vícepáskového TS, zatím bez koncových stavů a výstupu.

==========================  18.10.2005  ==============================

Způsoby zastavení TS pomocí koncových stavů.
Ukončení výpočtu RAM s vydáním výstupu.
Rozdíl RAM a RASP.

Obvody. Složitost funkce (úlohy) v obvodech lze exaktně definovat (narozdíl od TS).
Rozdíl složitosti obvodů proti formulím na příkladu parity, konstrukce obvodu
pro libovolnou funkci n proměnných, který má složitost O(n2^n), O(2^n), zmíněna
též konstrukce složitosti O(2^n/n).

Myšlenka důkazu existence Booleovských funkcí n proměnných, jejichž složitost
v obvodech je alespoň eps * 2^n/n pro kladné eps.

Programovací jazyk pro TS. Proměnné s konečným oborem hodnot, read, write, testy,
zápis pomocí běžných programovacích konstrukcí bez rekurze nebo pomocí vývojových
diagramů.

Začátek simulace vícepáskového TS jednopáskovým.

==========================  25.10.2005  ==============================

Redukce problému doplnění částečného latinského čtverce na Sudoku.
Dokončení simulace k-TS na 1-TS.
Zmíněn princip simulace k-TS na 2-TS.
Simulace 1-TS a k-TS na RAM.
Ukázán způsob uložení registrů RAM na pásku TS.

==========================  1.11.2005  ==============================

Dokončena simulace RAM na TS.
Obvody velikosti O(t(n)*s(n)) pro jazyk rozpoznatelný TS v čase
  t(n) a prostoru s(n).
Zmínka, že "opačná" implikace platí, když má TS pomocnou pásku jen pro
  čtení s nekonečným obsahem.
Zavedení p-převoditelnosti, ukázka f pro převod SAT na Klika (musí se
  ošetřit i neformule), tranzitivita.

==========================  8.11.2005  ==============================

Pokud L_1 p-přev. na L_2, L_2 v P, pak L_1 v P.
Definice NP-úplné úlohy.
Důkaz NP-úplnosti postupně pro tyto úlohy
1. problém splnitelnosti obvodu.
2. problém SAT (splnitelnost formulí v KNF)
3. problém 3-SAT (splnitelnost formulí v KNF s právě třemi literály v klausuli)
Problém přesného 3-pokrytí je NP-úplný.

Připomínám celkovou strukturu důkazu:
množina X se dostane jako sjednocení X_1 + X_2 + X_3
množina M se dostane jako sjednocení M_1 + M_2 + M_3

X_1 je tvořena body a_{ij}, b_{ij}, u_{ij}, \bar u_{ij} 
M_1 je tvořena trojicemi z těchto bodů
X_2 je tvořena body r_j, s_j
M_2 je tvořena trojicemi z bodů r_j, s_j, u_{ij} a \bar u_{ij}, které
    odpovídají výskytům literálů v klausulích.
X_3 je tvořena body e_k, f_k pro k=1,...,m(n-1).
M_3 je tvořena všemi možnými trojicemi tvaru (u_{ij}, e_k, f_k) a (\bar u_{ij}, e_k, f_k).

V tvrzení o X_1 a M_1 jsme použili předpoklad, že M_2 a M_3 nepokrývá
   žádný z bodů a_{ij}, b_{ij}.
V tvrzení o X_2 a M_2 jsme použili předpoklad, že M_3 nepokrývá
   žádný z bodů r_j, s_j.
Tyto předpoklady umožnily dokázat potřebnou vlastnost M_1 nezávisle na definici M_2 a M_3
a vlastnost M_2 nezávisle na definici M_3.

==========================  15.11.2005  ==============================

Hodina odpadla.

==========================  22.11.2005  ==============================

Struktura důkazu NP-úplnosti problému přesného 3 pokrytí.
NP-úplnost problému batohu a problému dvou loupežníků.
Úplnost rezoluce pro výrokový počet.
2-SAT je v P.

==========================  29.11.2005  ==============================

NP-úplnost problému vrcholového pokrytí a Hamiltonovské kružnice.
Aproximační algoritmy.
Aproximační algoritmus pro vrcholové pokrytí s faktorem 2.
Aproximační algoritmus pro množinové pokrytí (nedokončeno).

==========================  6.12.2005  ==============================

Aproximační algoritmus pro množinové pokrytí.
Problém obchodního cestujícího, NP-úplnost, aproximační alg. s faktorem 3/2
(s použitím kostry bez párování se dostane aprox. alg. s faktorem 2).

==========================  13.12.2005  ==============================

MAX-2-SAT je NP-úplný (p-převoditelnost z problému kliky nebo 3-SAT).
Vážený MAX-CUT je NP-úplný. Důkaz pomocí NP-úplnosti NAE-SAT.

==========================  20.12.2005  ==============================

(3,3)-SAT má jen pozitivní instance. 
(3,4)-SAT je NP-uplný.
Aproximační algoritmus pro MAX-SAT s faktorem 2.
Sestavena soustava nerovnic pro výpočet pravděpodobností pro druhý krok
vylepšeného algoritmu.

==========================  3.1.2006  ==============================

Náhodné ohodnocení proměnných, které bylo získáno minule řešením
soustavy lineárních nerovnic, splní klausli c_j délky k_j s pravděpodobností
alespoň \beta_{k_j} \hat{z_j}, kde \beta_k = 1 - (1 - 1/k)^k.