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.