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.