1. cvičení •
Substituční metodou dokažte linearitu algoritmu pro hledání mediánu a stanovte konstantu linearity. T(n)=c*n/5+T(n/5)+(n-1)+T(7/10*n) Hadam theta(n) MI: Je to O? n=10 T(10)<=c*2+k*2+9+k*7=c*2+k*9. Chceme k*10>=c*2+k*9 a tedy k>=2*c OK At to plati pro n*7/10 (>1/5*n) T(n)<=c*n/5+k*n/5+ (n-1)+k*n*7/10=c*n/5+n-1+k*n*9/10=n*(c/5+1)-1+k*9/10*n< n*(c/5+1)+k*9/10*n n*(c/5+1)+k*9/10*n
=n*(c/5+1)-1+k2*9/10*n k2*n<=n*(c/5+1)-1+k2*9/10*n 1/10*k2<=(c/5+1)-1/n zrejme plati (c/5+1)-1/n --> c/5+1 pro velka n Takze pro k2<=10*(c5+1)-10 je to jiste OK, ale pro n-->infinity staci k2--> 10*(c/5+1)=2*c+10 T(n)=O(n) && T(n)=Omega(n) => T(n)=theta(n) konstanta linearity je 10*(c/5+1)
•
Najděte asymptotická řešení následujících rekurentních rovnic (předpokládejte, že T(n) je konstanta pro všechna n<3) :
a)
T(n) = 2T(n/2) + n3 log_2(2)=1<3 => theta(n^3) b) T(n) = T(9n/10) + n log_{10/9}(1)=0<1 => theta(n) c) T(n) = 16T(n/4) + n2 log_4(16)=2 == 2 => theta(n^2*log_4(n)) d) T(n) = 7T(n/3) + n2 log_3(7)<2 => theta(n^2) e) T(n) = 7T(n/2) + n2 log_2(7)>2 => theta(n^log_2(7)) f) T(n) = 2T(n/4) + n log_4(2)= ½ == ½ => theta(n^ ½*log_4(n)) g) T(n) = T(n-1) + n T(n)=T(n-1)+n=T(n-2)+n-1+n=C+3+...+(n-1)+n=(n-1)/2*n-1-2+C=(n^2-n)/2-3+C Odhad je theta(n^2) z vlastnosti limity podilu. Overeni: O+Omega. Pro n=4 je pro O T(4)=C+4 a k1*4^2>=C+4 --> k1>=(C+4)/16 (analogicky v Omega k2<= (C+4)/16 Je to O? T(n)=k1*(n-1)^2+n<=k1*n^2...k1*(n^2-(n^2-2n+1))>=n --> k1>=n/(2n-1) k1>=lim n/(2n-1)=1/2 Analogicky Omega: k2<=1/2 Slozitost je theta(n^2)
h) T(n) = T( n ) + 1 T(n)=T(n^(1/2))+1=T(n^(1/4))+1+1=...=log_2(log_2(n))... stromek velikostí úloh má na každé vrstvě (n^(1/2^k)) podúloh velikosti (n^(1/2^k)) ulohy vyšší úrovně.
1 k 2
1 k 2
n ∗n =n
1 k−1 2
výška stromu je tedy log_2(log_2(n)) theta(log_2(log_2(n))). Jen jsem sesečetl počet 1. Overeni: n=9....T(9)=T(3)+1=c+1 Pro O: k1*log_2(log_2(9))>=c+1 resp. Pro Omega: k2*log_2(log_2(9))<=c+1 Je to O?
T n=T n1=k 1∗log 2 log 2 n1≤k 1∗log 2 log 2 n 1 1 log 2 log 2 n=log 2 ∗log 2 n=log 2 log 2 nlog 2 =log 2 log 2 n−1 2 2 −k 11≤0 k 1≥1
Omega analogicky ale k_2<=1 Slozitost je theta(log_2(log_2(n))) Alternativne: 2^m=n, m=log_2(n) T(n)=T(2^m)=T(2^{m/2})+1 S(m)=S(m/2)+1=theta(log_2(m)) T(n)=theta(log_2(log_2(n)))
i)
T(n) = 2T( n ) + log n Výška stromu řešení/rekurze je log_2(log_2(n)).
22 T nlog nlog n=...=2 ∗C log n∗log 2 log 2 n= =C∗log 2 nlog n∗log 2 log 2 n log 2 log 2 n
log je rostouci, pokud je základ >1 (jinak by s velikosti ulhy klesala slozitost!) pro tákové základy tedy odhadneme theta(log(n)*log_2(log_2(n))) Prvni test: T(4)=2*C+log(4). k_2*log(4)log_2(log_2(n))<=T(4)<=k_1*log(4)log_2(log_2(n)) 1) je to O?
2∗k 1∗log n∗log 2 log 2 nlog n≤k 1∗log n∗log 2 log 2 n 1 log 2 log 2 n=log 2 log 2 n=log 2 log 2 n−1 2 1 2∗k 1∗ log n∗log 2 log 2 n−1log n≤k 1∗log n∗log 2 log 2 n 2 −k 1∗log nlog n≤0 1≤k 1
Je to O. 2) Analogicky Omega. K_2>=1 Je to Omega. Slozitost je theta(log(n)*log_2(log_2(n))) Alternativne: 2^m=n, m=log_2(n) T(n)=T(2^m)=2*T(2^{m/2})+m*log(2) S(m)=2*S(m/2)+m/2*log(2)=theta(m*log_2(m)) T(n)=theta(log_2(n)*log_2(log_2(n)))
j)
T(n) = 3T(n/2) + n log n
n n n n T n=3∗T n∗log n=3∗3∗T ∗log n∗log n=...= 2 4 2 2 log n k k 3 1 log n =3 ∗C ∑ ∗n∗log n∗ 2 k =0 2 log 3− Magický odhad : n∗log n≤n ,0 ale dost malé
2
2
2
log 2 n
∑
k =0
3 2
k
=n
=n
k =0
1 ≤∑ 3 ⋅ 2 k =0
k
log 2 n
log 2 3−
k
k
∗n
=
log 2 3− k
=
k
2 ⋅∑ 3 ⋅ = 3 k =0
log 2 3−
k
log 2 n1
1−2 log 3− log 3 ⋅ =n ⋅2⋅n −1∗E≤F∗n 1−2 log n k k 3 1 log 3 Sláva : ∑ ∗n∗log n∗ =O n 2 k =0 2
⋅∑ 2⋅k =n
log 2 3−
log 2 n
log 2 n
1 ⋅∑ 3 ⋅ 2 k =0
log 2 3−
=n log 2 n
k
1 ∗n∗log n∗ 2
log 2 3−
2
2
T n=n
log 2 3
2
O n
log 2 3
=n
2
log 2 3
Slozitost je theta(n^log_2(3)). Alternativne: S(n)=3*S(n/2)+n <= T(n) = 3T(n/2) + n log n <= U(n)=3*U(n/2)+n^epsilon, forall epsilon>1 S(n)=U(n)=n^log_2(3), pro vhodne epsilon
k) T(n) = T(n-1) + 1/n T(n)=..=C+1/3+1/4+..+1/(n-1)+1/n=C+S(k=3..n){1/k} Pozorovani: int(1/x)=ln(x) n−1
∫ 0
n
n
1 1 1 dx≤∑ ≤∫ dx1 x1 1 k 1 x
Zrejme tedy bude theta(ln(n)) overeni: T(4)=C+1/4<=k1*ln(4) OK pro O, podobne Omega.
T n=k 1∗ln n−11/ n≤k 1∗ln n k 1∗ln n−11/ n≤k 1∗ln n 1 1/ n∗ ≤k 1 n ln n−1 1 n lim =1 x ∞ n ln n−1
k_1>1 OK O i Omega (k_2<1) Slozitost je theta(ln(n)).
l)
T(n) = T(n-1) + log n T(n)=...=C+log(3)+...+log(n)=C+log(n!)-log(2) theta(log(n!)) protoze log(2) je konstanta a C take. Log je pro zaklad > 1 rostouci. Navic log(2)>0 Test: k_2*log(4!)<=T(4)=C+log(4)<=k_1*log(4!)
k 1∗log n−1!log n≤k 1∗log n ! log n≤k 1∗log n 1≤k 1 Je to O. Analogicky Omega k_2<=1 Slozitost je theta(log(n!)). m) T(n) = 2T(n/5) + T(n/2) + n 2*(1/5)^x+(1/2)^x pro x=1 je 2/5+1/2<1 OK theta(n) n) T(n) = 3T(n/2) + 4T(n/4) + n2 3*(1/2)^x+4*(1/4)^x pro x=2 je 3/4+1/4=1 theta(n^2*log_2(n)) o) T(n) = 2T(2n/3) + T(n/3) + n n
2∗2/3x 1/3x pro x=3/2 je 2∗ 23 /33 1/33 =4/3∗ 2/31/3∗ 1/31 zlé Řešíme : 2 ⋅2/3x 1/3x =1 1 1 2 ⋅2 x⋅ x x =1 3 3 1 ⋅2 x11=1 x 3 1 x=2 ∗81=1 9 Slozitost theta(n^2).
•
Jak rychle lze vynásobit obdélníkové matice velikosti (kn x n) a (n x kn) pokud použijeme Strassenův algoritmus pro násobení matic velikosti (n x n) jako podprocedůru? Zkuste obě možná pořadí násobení a odvoďte asymptotickou složitost takových násobení (jako funkci k a n). A=(k*n x n); A'=(k*n x k*n) kde sloupce a'_j, j>n jsou 0 analogicky B, B' ale s radky. A'*B' ma T(k*n)=theta((k*n)^log_2(7)) (k*n)^log_2(7)=k^log_2(7)*n^log_2(7) a zrejme k^log_2(7)=konst (pro konst. k) Doplneni sloupcu/radku lze jiste provest v case linearne umernem poctu doplnenych elementu. Pokud mame metodu na matice n x n a nechceme doplnovat, je to jako k nasobeni n x n a jejich secteni. Bez ohledu na poradi. i) Radkova A={A1,A2..Ak}, sloupcova B={B1##B2##..##Bk} A*B=Sum{m=1..k}A_m*B_m nasobeni umime v theta(n^log_2(7)) a provedeme jej k krat. Dále secteni 2 matic n x n lze udelat v (n^2) scitani. Takze k matic v (k-1)*n^2 scitani. Celkem cas theta((k-1)*n^2+k*n^log_2(7)) coz je zrejme theta(k*n^log_2(7)). Protože log_2(7)>2. theta(k*n^log_2(7)) coz je lepsi, nez rozsirovani na matice k*n x k*n s vysl. theta(k^log_2(7)*n^log_2(7)) *
=
ii) (k*n x n)(n x k*n)=(k*n x k*n) zde potrebuji k*k matic (vynasobenych) a ty slozene daji vysledek. theta(k^2*n^log_2(7)) coz je stale lepsi, nez rozsirovani na matice k*n x k*n s vysl. theta(k^log_2(7)*n^log_2(7)) *
=
2. cvičení Je dána množina úkolů S={1,2, ... ,n} a pro každý úkol i čas jeho zahájení s(i) a jeho ukončení f(i). Úkoly i a j jsou kompatibilní pokud mají polouzavřené intervaly [s(i),f(i)) a [s(j),f(j)) prázdný průnik. Najděte co největší množinu (po dvou) kompatibilních úkolů. a) Na přednášce byl předveden hladový algoritmus řešící tento problém. Úkolem zde je dokázat, že ne každý hladový algoritmus povede k nalezení optima. Zkonstruujte protipříklady na následující hladové volby: i. algoritmus v každém kroku vybere nejkratší úkol z těch, které jsou kompatibilní se všemi již vybranými Mam rozvrzene ulohy do [?,1] [4,6] [1, 5][5, 9] Pak: [1,5],[4,6],[5,9] vybere [4,6] ale lepsi by bylo [1,5][5,9] ii. Bere nejmenší s(i) [1, 4] [2,3][3,5] vezme [1,4] místo [2,3][3,5] iii. algoritmus v každém kroku vybere takový úkol, který je kompatibilní se všemi již vybranými, a který se překrývá s nejmenším počtem úkolů z těch, které jsou kompatibilní se všemi již vybranými [2,4] [6,8] [2,4] [6,8] [2,4][4,6][6,8] [1,3][3,5][5,7][7,9] volba [4,6] determinuje rozpad na 2 segmenty, kterých jde rozvrhnout vždy jen jednu ulohu. GREEDY=>3 ulohy max lze 4 ulohy [1,3][3,5][5,7][7,9] b) Problém má stejná vstupní data jako dříve, ale tentokrát chceme rozvrhnout všechny úkoly za použití co nejmenšího počtu „zdrojů“ (např. poslucháren pokud úkoly = přednášky), tj. chceme rozdělit úkoly do co nejmenšího počtu kompatibilních podmnožin. Rozmyslete, zda lze pro řešení tohoto problému použít „iteraci“ algoritmu z přednášky (tj. nalezneme největší kompatibilní podmnožinu, ve zbytku opět nalezneme největší kompatibilní podmnožinu, atd. dokud zbývají nezařazené úkoly). Zkuste zkonstruovat jiný hladový algoritmus pro tento problém a dokažte jeho korektnost. Nelze iterovat GREEDY_SELECT: [3, 6] [1, 4] [1,2][2,3] [4,5][5,6] Rozvrhne do 3 zdroju. Male 4 do jednoho. A pak velke každý do jedoho. Optimum je zrejme: velky+2 male do jednoho a 2 male+velky do druheho. Navrh GREEDY_OPTRES: Beru ulohu s nejmensim s(i) z nerozvrzenych uloh a rozvrhnu ji do prvního mozneho zdroje, kde neblokuje. Dk: Co když to není optimalni? Pak to jde lepe. Pokud ale GREEDY_OPTRES rozvrhl ulohy do (k-1) zdroju a další chce rozvrhnout do k-teho zdroje, tak to znamena, ze existuje k vzajemne se blokujicich uloh. A ty nelze rozvrhnout do méně nez k zdroju. A to lepe nejde. V následujících příkladech dokažte, že daná struktura je matroid: a) Nechť S je konečná neprázdná množina o n prvcích a k je přirozené číslo menší než n. Nechť I je množina všech podmnožin množiny S o velikosti nejvýše k. Dokažte, že (S,I) je matroid.
1) S je neprázdná, konečná. 2) dědičná vlastnost B∈ I , A⊂B ⇒ A∈ I ∅∈I ∣∅∣=0≤k A⊂B ⇒∣A∣≤∣B∣≤k ⇒ A∈I 3) výměnná vlastnost A , B∈ I ,∣A∣∣B∣∨ pak ∃ x∈B ∖ A: A∪{x}∈ I ∣A∣∣B∣, ∃ x∈B ∖ A , ∣A∪{x}∣=∣A∣1≤∣B∣≤k ⇒ A∪{x}∈ I
b) Nechť S je konečná neprázdná množina a nechť S1, S2, ..., Sn je rozdělení množiny S na po dvou disjunktní podmnožiny. Nechť I = {A | ∀i |A∩ Si| ≤ 1}. Dokažte, že (S,I) je matroid.
1) S je neprázdná, konečná. 2) dědičná vlastnost B∈ I , A⊂B ⇒ A∈ I ∅∈ I ∀ A:∣A∩∅∣=0≤1 A⊂B pokud ∃ S i , ze∣A∩S i∣1 pak A doplnim na B a prunik se nezmensi. Spor takze A∈ I 3) Vyměnná vl. A , B∈ I ,∣A∣∣B∣ pak ∃ x∈B ∖ A: A∪{x}∈ I B ∖ A=C ≠∅ , C obsahuje vsechny kandidaty na doplneni A. Navic urcite C ∈ I , protoze lze C doplnit na B a prunik s S i by se nezmensil. Pozorovani 1: ∀ y ∈C ∃ prave jedna S i , y∈S i S i po dvou disj. At R={S i ;∣C ∩S i∣0, S i jsou ta nase deleni S } Pozorovani∧S i jsou deleni ⇒∣C∣=∣R∣ i) Pokud ∃T ∈R , A∩T =∅ pak lze zrejme jako x na doplneni A vzit x∈C ∩T protoze T odpovida nejake S i kde∣A∩S i∣=0 a ∣ A∪{x}∩S i∣=1. Ostatni pruniky se nezmeni S i po dvou disj.. ii) Pokud ¬∃T ∈R vyhovujici v (i) A⊈B jinak lze doplnit A do B. At D= A∖ B. E= A∩B Pozorovani 2 : ∀ T ∈R ,∣E∩T∣=0 jinak zrejme B∉ I mohutnost pruniku B s nejakou S i je alespon 2 Pozorovani 3: ∀ T ∈R ,∣D∩T∣0, jinak by toto T vyhovovalo v (i) Pozorovani 4 :∣D∣=∣R∣ Prvek D jednoznacne urcuje T , jinak D resp. A∉ I. A neni (i) ∣A∣∣B∣ ∣A∣= ∣E∣∣D∣=∣E∣∣R∣=∣E∣∣C∣ =∣B∣ SPOR c)
Nechť (S,I) je matroid a nechť J = {A | S-A obsahuje nějakou maximální množinu z I} Dokažte, že (S,J) je matroid. 1) S je neprazdna, konečná protoze (S,I) je matroid. 2) Dedicnost.
∅∈ J , urcite. S ∖∅=S a jsou v J vsechny max mnoz. B⊂ A , pak S ∖ A⊂S ∖ Btakze max mnozina co byla v J pro B tam pro A je jiste tez
3) Vymenna vl.
A ' , B ' ∈ J ,∣A '∣∣B '∣ pak ∃ x ∈ B ' , {x }∪ A' ∈ B '
A'
A
Y
Z
W
B'
B
A' ∈J s max. mnoz. A∈ I. B ' ∈ J s max. mnoz. B∈ I.
X
V
X = A∩B ' , Y =B∩ A' , Z =B ' ∖ A∪ A' V = A∖ X , W =B ∖Y
1) Pokud Z ≠∅ , lze doplnit A' o x∈Z. A nadale bude zrejme A∈S ∖ A' ∪{x} 2) Z =∅ Pozorovani 1:∣A'∣∣B '∣, Z =∅⇒∣Y∣∣X ∣ Pozorovani 2 :∣A∣=∣B∣,∣Y∣∣X ∣⇒∣V∣∣W∣ S , I je matroid. Doplnime vymenna vl.V alespon jednim prvkem z W a pak prvky z X , abychom ziskali V max takovou , ze je maximalni v I a zaroven patri do S ∖ A' . Pokud je W ≠∅ tak B ' ∖ A∪V max ≠∅ a lze pouzit bod (1) Pozorovani 3:∣V∣∣W∣⇒∣W∣≠∅
3. cvičení 1.
Nechť je orientovaný graf G=(V,E), kde |V| = n, zadán maticí sousednosti. Navrhněte algoritmus, který zjistí zda G obsahuje stok, tj. vrchol x takový, že vstupní stupeň x je n-1 a výstupní stupeň x je 0, přičemž algoritmus smí použít (přečíst) pouze O(n) prvků matice (předpokládejme, že před zahájením algoritmu je již celá matice načtena do paměti).
Alg 1.:
První běh
Další běh
Směry: Plná šedá-diagonála Přerušovaná šedá-čtené hodnoty Plná červná-již dříve zrušený řádek/sloupec Přerušovaná červená-nevyhovující řádek/sloupec
Pozice: Již známé: černá-0, bílá-1 Čtené v tomto kroku: zelená-0, červená-1
Práce v n-tém kroku: O(2(n-1)) Zabiji v každém kroku alespoň ½ úlohy (rekurzivně). Nemohou být dva „kříže“ vedle sebe. Jedu po diagonále [x,x], jen přes ještě živé „kříže,“ a kontroluji v k-tém kroku hranice „křížů“ ([x-k,x],[x+k,x], [x,x-k],[x,x+k]). Pokud narazím na OK „kříž“ nemusím souseda (ve směru průchodu vůbec testovat, je KO) a vyřadím ho ze seznamu (i když vlastně je testován jako sjednocení tesstů jeho sousedů). Až projedu diagonálu, můžu ji jako pro k+1 krok projed opačným směrem atd. Oblasti mimo matci mne nezajímají. Zkončím, pokud není co testovat. SUCCESS: zbyde „kříž“ FAIL: jinak T(n)=T(n/2)+θ(2(n-1))=θ(n) Alg 2.:
První část čtení Směr: Plná modrá-skok na první řádek s nešedým prvkem sloupec další potom, kde se četla 1 v původním. Přerušovaná červená-potřeba ověřit 0 hodnoty Přerušovaná zelená-potřeba ověřit 1 hodnoty
Konec čtení Pozice: aJiž známé: šedá-vstupní stupeň vrcholu méně než (n-1), černá-0. Čtené v tomto kroku: zelená-1, červená-0
Čtu z 1. řadku sekvenčně zleva doprava prvky. Dokud čtu 0 OK, ale jakmile na razím na 1 (sloupec p), skočím na p-tý řádek na sloupec p+1 (první za diagonálou) a pokračuji ve čtení (jako předtím) od této pozice na tomto řádku. Celé to běží, dkoud nepřečtu n prvků 0, nebo prvek 1 na posledním řádku. 0 čtená na sloupci [r,s] znamená vstupní stupeň vrcholu deg(s)<=n-2. Takový vrchol automaticky nevyhovuje. Pokud dojdu na pravý kraj matice a čtu 0, stačí ověřit zda zbytek řádku je plný 0 a sloupec (krom průsečíku) plný 1 SUCCESS. Když není, nebo je posledním prvkem řádku 1, tak FAIL. Jsem totiž ve stavu, kdy n-1 vrcholů má deg_in(v)<=n-2.
A krom sloupce posledního skoku (musí se křížit na diagonále, symetrie vstup/výstup) nevyhoví protento řádek jistě žádný (v místě křížení musí být 0). čtu „n“ 0...v n krocích (nebo selže na konci řádku). Dále ověření sloupce a zbytku řádky v max. (n-2)+(n-1)., v nejhorším skočím z prvního řádku na poslední. T(n)=θ(n+(n-2)+(n-1))=θ(n) Alg. 3.: 0
Začátek
1
Po n-1 krocích
Šipka značí posun nadalší pozici po přečtení 0 resp. 1. Bílá značí posledního možného kadidáta Šedý kříž již je zřejmě nevyhovující Začnu z pravého horního rohu. Pokud čtu 0, posunu se o jedno pole doleva, pokud 1, posunu se o jedno pole dolů. A to opakuji n-1 krát. Kde jsem? Každý krok vlevo znamená, že zkončím o řádek výš a víc vlevo. Naopak krok dolů znamená o řádek níž a méně vlevo.Udělám D kroků dolů a L doleva. Budu na [D,(n-1)-L]. Po n-1 (D+L=n-1) krocích na [(n-1)-L,(n-1)-L], což je diagonála. Změnu směru dělám vlastně pokud zjistím, že nalezená hodnota neodpovídá zvolenému směru (samé 0 vodorovně a svisle samé 1). Proto při posunu lze vždy zahodit jednu možnost. Nakonec jsem na diagonále a možnost zbývá jedna. Tu ověřím a hotovo. T(n)=θ((n-1)+(n-2)+(n-1))=θ(n)
2.
Navrhněte algoritmus založený na BFS (modifikaci BFS), který rozhodne,zda je daný neorientovaný graf bipartitní, a pokud ano, tak identifikuje obě partity (vytvoří příslušný rozklad množiny vrcholů). BFS objevuje v kroku k vždy všechny vrcholy, do kterých ze „startovního“ vrcholu vede cesta délky k (tzn.nemůže se mi stát, že bych chtěl vrchol zařadit do dvou různých hladin). Graf je bipartitní, právě když neobsahuje lichou kružnici (délky alespoň 3). Což je ekvivalentní s tím, že BFS v kroku k nenajde 2 vrcholy (do kterých ze „startovního“ vrcholu vede cesta délky k) spojené hranou. Zřejmě 2k+1 je liché. Obarvim tedy vrholy barva[k mod 2] a podle barvy i rozradim do partit.
3.
Z přednášky víme: Algoritmus DFS(G) nalezne topologické očíslování vrcholů orientovaného grafu G (podle klesajících časů opuštění vrcholu), pokud je G acyklický. Dokažte nebo vyvraťte : pro libovolný graf G (cyklický i acyklický) výše uvedené očíslování minimalizuje (v množině všech očíslování vrcholů) počet inkonzistentních hran, tj. hran, které vedou od vrcholu s větším číslem do vrcholu s menším číslem. Problematické jsou právě všechny zpětné hrany. A jedna hrna může být na více cyklech.
Pustím-li DFS shora, najde 3 zpětné hrany. Pustím-li DFS zespoda, najde 2 zpětné nebo 2 zpětné a jednu dopřednou. Prosté DFS tedy nelze použít.
4.
Orientovaný graf G se nazývá polosouvislý, pokud pro každé dva vrcholy x,y existuje v G orientovaná cesta z x do y nebo orientovaná cesta z y do x (nebo obě). Navrhněte algoritmus na testování polosouvislosti grafů s co nejlepší asymptotickou složitostí. Zjistíme si v O(n+m) SSK. Máme komponenty S_1,...,S_n. Pozorování 1.: Žádné S_i neleží na kružnici. Jinak tyto S_i s touto kružnicí jsou SSK a to ostře větší, než každá z těchto S_i. (Z S_i se dostanu do S_j z S_j do S_i).
> DFS mi SSK vyda topologicky "predtridene". > Staci jen spustit hledani cesty (v G^T protismerna chuze) ze SSK_1. A > navic v DFS(G^T) lze rovnou kontrolovat, zda pricna hrana vede "do" > tvorene SSK_i, hledam cestu pres vsechny SSK, takze nutne potrbuji "z" > posledni jiz vyresene SSK_{i-1} (orientace hran je opacna). A > nepotrebuji tudiz ani stavet multigraf. Spravne? Presne tak. Algo na SSK staci "obohatit" o to, ze pri staveni i-teho stromu na grafu G^T (coz je topologicky i-ta SSK grafu G) vede z nejakeho vrcholu teto SSK hrana do nejakeho vrcholu v predchozi SSK. Tim padem vede hrana v grafu G z (i-1)-ni SSK do i-te, a G je polosouvisly tehdy a jen tehdy kdyz tohle plati pro kazde i.
4. cvičení 1.
Spočtěte výšku binomiálního stromu řádu k. MI: i) Výška B_0 je 0. ii) ať B_{k-1} je k-1. B_k jsou 2 B_{k-1} kde „ta druhá“ je pověšena pod kořen té první. Výška obou B_{k-1} je k-1. Výška B_k je tedy k.
2.
Dokažte dolní a horní odhad pro výšku libovolného stromu řádu k, který se může vyskytovat ve Fibonacciho haldě. Dolní: řád k-tého syna je alespoň k-2 (v pořadí jakém byli sliti). To platí na všech ůrovních. Nutně tedy výška stromu řádu k, který se může vyskytovat ve Fibonacciho haldě je alespoň k/2. Horní: Je to n-1 (n je počet prvků v haldě). Pro m=1, jeden prvek OK. Výška je 0. Ať to platí pro m=n-1. 1)Vložím 3x INSERT nové minimum //tři nejmenší prvky v haldě. 2) EXTRACT_MIN //odebere jedno min. z bodu 1) a reorganizuje. Každý řád max jednou 3) DECREASE_KEY na 2. nejmenší prvek. Aby byl nejmenší. 4) EXTRACT_MIN
Výška stromu je n. Obrazek ilustruje kroky 2, 3 a 4.
3.
Zkonstruujte příklad grafu se zápornými váhami na hranách, na kterém selže Dijkstrův algoritmus (chceme graf takový, že nejkratší cesty jsou definovány, t.j. neexistuje záporný cyklus).
Ať uvažuji že upravuji v DECREASE_KEY „hotové“ vrcholy nebo ne. Cesta z modrého do zeleného. V prvním případě ještě alg. Upraví délku cesty pro červený na 2+(-2)=0. V druhém případě ne. Ani v jednom z případů však již nemění hodnotu pro zelený vrchol. 4.
Nechť 0 ≤ w(u,v) ≤ 1 reprezentuje „spolehlivost“ hrany (u,v) v komunikační síti, t.j. pravděpodobnost, že komunikační kanál (u,v) neselže. Nechť jsou navíc tyto pravděpodobnosti nezávislé. Navrhněte algoritmus, který nalezne nejspolehlivější komunikační cestu mezi danými dvěma vrcholy v síti. w(u,v)=0 mohu rovnou vyradit. Úprava vah hran w'=-ln(w(u,v)) >=0 což je ln(1/w(u,v)) Hledám Dijkstrou. MIN SUM -ln w(x,y)=MIN -ln(PI w(x,y))=-MAX ln(PI w(x,y))=-MAX ln(S(c)). ln je rostoucí.
5.
Nechť je dán vážený orientovaný graf G = (V,E), kde |V| = n, |E| = m a váhy na hranách jsou zadány funkcí w : E → {1,2, ... ,k}. Dále předpokládejme, že k ≤ n. Implementujte Dijkstrův algoritmus tak, aby běžel v O (nk +m). Pole n*k, čtujen jedním směrem. EXTRACT_MIN.......O(k) projití cast pole bez vracení. Držím akt. minimum. Pro každý vrchol. Prvky nejsou vlastně nikdy na větším prostoru než k+1. DECREASE_KEY....O(1) jen přesunu prvek v poli. Pro každouhranu. Ale nikdy nejdu níž než je pozice min. Nejvzdálenější může být jedině Pole[MIN_POS+k].
6.
Změňte implementaci předchozího problému tak, aby algoritmus běžel v O((n +m) log k). halda k+1, modulo používám, ale klíče nemodulo. Pole[k+1] organizované jako bin. halda. EXTRACT_MIN...O(log k)...pro každý vrchol právě jednou DECREASE_KEY...O(log k)...pro každou hranu právě jednou Potřebuji i pole vrcholu k přímé adresaci do haldy. Je potřeba zdůvonit, proč ex. max. k+1 neprázdných tříd vrcholů. Odpověď: přičítám max. k k min.
5. cvičení 1.
Nechť máme k dispozici „černou skřínku“, která umí řešit SAT (rozhodovací problém splnitelnosti CNF formulí) v polynomiálním čase. Zkonstruujte algoritmus, které pro danou CNF najde v polynomiálním čase splňující ohodnocení proměnných, pokud takové ohodnocení existuje. Zkusím SAT success: iteruji dosadit za x_i; SAT: success, i++; fail, do x_i dosadím opak a i++.
2.
Definujme problém TAUT následovně: Instance: Boolovská formule F sestávající z n proměnných a operací negace, disjunkce a konjunkce Otázka: Je F tautologie? a) Je TAUT ve třídě NP? Neví se. b) Je TAUT ve třídě co-NP? Ano. Certifikát nesplňující ohodnocení. c)
Jaká je složitost TAUT pokud je F CNF? Snadné.
d) Jaká je složitost TAUT pokud je F DNF? coNP-C? Pokud toto umím, umím SAT. Probém coTAUT: Instance: Fle F v DNF Otázka: Existije ohodnocení x fle F, aby F[x]=0?
SAT ∝coTAUT Problem SAT: Instance: Fle F v DNF Otázka: Existije ohodnocení x fle F, aby F[x]=1? Pozorování:
F [ x ]=1 ⇔¬ F [ x ]=0 ∃ohodnocení x formule F , F [ x ]=1 ⇔∃ohodnocení y formule F ,¬ F [ y ]=0 De Morgan :¬CNF [ x i ]⇔ DNF [¬ x i ]: ¬ x 1,1∨ x 1,2∨..∧ x 2,1∨x 2,2∨..∧..=¬ x 1,1∧¬ x 1,2∧..∨¬ x 2,1∧¬ x 2,2∧..∨..
F...CNF, ¬F...DNF coTAUT(¬F)=ANO <=> SAT(F)=ANO coTAUT je NP-C. TAUT je tedy coNP-C.
6. cvičení 1.
Definujme problém LOUP (loupežníci) následovně: Instance: Přirozená čísla a1, ... , an Otázka: Existuje podmnožina T množiny indexů S = {1, ... ,n} taková, že Dokažte, že LOUP je NP-úplný problém.
∑i∈T ai = ∑i∈S-T ai
Certifikat: Mnoziny. Pomocí SP. Řešit SP pro b nebo A-b je ekvivalentni. b>=1/2A...b'=b b<1/2A.....b'=(A-b) a_{n+1}=b'-(A-b')=2b'-A SP: K={a_1, ..a_n}, b Umím půlit. LOUP({a_1, ..a_n}+{a_{n+1}}) =>) SP má řešení. SUM(S \subset K)a_i=b' SUM(S)a_i+a_{n+1}=b'+SUM(K-S)a_i+a_{n+1} SUM(K-S)a_i+a_{n+1}=A-b'+2b'-A=b' <=) LOUP({a_1, ..a_n}+{a_{n+1}}) má řešení SUM(O)a_i=SUM(O)a_j SUM(O)a_i=(A+2b'-A)/2=b'=SUM(O)a_j Ať a_{n+1} je v O. Pak P je řešením SP. 2.
Nejkratší cestu mezi dvěma vrcholy v neorientovaném váženém grafu lze nalézt pomocí Dijkstrova algoritmu, pokud jsou zadané váhy na hranách nezáporné. Jak se změní složitost této úlohy, pokud povolíme, aby byly váhy záporné? NP-C. Hamiltonovska cesta je NP-C (pomocí HK). A toto lze pomocí Hamiltonovska cesty (váhy volím -1) Nejkratsi cesta kde vahy cela cisla, problem OptPath. 1) Hamiltonovska cestka (HC) je NP-C. HKe(x',y), e...hrana. Hledam HC(x,x'). Pokud ex. HC, tak v poslednim kroku misto do x' prejdu do x a mam HK. Pokud ex. HK, tak v poslednim kroku misto do x prejdu do x' a mam HC. 2) HC umim rozhodnou, zda ex. delky nejvys k. => jen porovnam delku cesty s _k_ <= snizovanim _k_ se doberu k minimu. pulim intrval _k_=(max vaha(v))*(n-1), pak pripadne _k_/2 a dal bud _k_/2+_k_/4 nebo _k_/4 atd. A po log2(k) krocich mam min, je to tak? To ale zavisi na _k_ nemelo by se to spis delat jinak? Omezit to pomoci polynomu s n. Co kdyz je treba _k_=2^(2^n)? Rozhod. problem ma certifikat danou cesta. Je to OK duvod pro nalezeni OptPath do NP?
Mam G graf a chci HC. At umim OptPath. Graf G ohodnotim na vsech hranach -1. Nutne tedy nejkratsi (nejlevnejsi) cesta<=> nejdelsi (nejvic hran). Navic pouzit lze max (n-1) hran. Pokud tedy pouziji (n-1) hran, mam nejlepsi mozne minimum -(n-1), ale zaroven i HC. 3.
Definujme problém 0-1 CP (celočíselné programování) následovně: Instance: Celočíselná matice A řádu m krát n a celočíselný vektor b délky m Otázka: Existuje vektor x délky n obsahující pouze čísla 0 a 1 takový, že Ax ≤ b ? Dokažte, že 0-1 CP je NP-úplný problém. Dík SP je NP-C.
a 1 ... a n ∗x≤ b −b −a 1 ... −a n a∗x ≤b∧−a∗x ≤−b a∗x ≤b∧a∗x ≥b a∗x =b
4.
Definujme problém IP (izomorfismus podgrafů) následovně: Instance: Neorientované grafy G a H Otázka: Je graf G izomorfní s nějakým podgrafem grafu H? (varianta 1) Otázka: Je graf G izomorfní s nějakým indukovaným podgrafem grafu H? (varianta 2) Dokažte, že obě varianty IP jsou NP-úplné problémy. Hleám kliku. Graf G a graf H: 1) G isom. s neinduk podg H 2) G isom. s induk podg H, induk=max podgraf na mnozine vrcholu Certif: seznam dvojic vrcholu, co se maji zobrazit na sebe at 1 nebo 2: volim G=K_n, H=graf kde kliku hledam 1) hledam primo kliku 2) max podgraf na n vrcholech. pokud ex. klika musim najit ji (je max). Případně lze hledat HK (neinduk. varianta)
