Vaje iz alternativnih modelov računanja Sergio Cabello 9. november 2010 naslov: Vaje iz alternativnih modelov računanja avtorske pravice: Sergio Cabello izdaja: prva izdaja založnik: samozaložba avtor: Sergio Cabello leto izida: 2010 (v Ljubljani) natis: elektronsko gradivo http://www.fmf.uni- lj.si/~cabello/gradiva/vajeamr.pdf CIP - Kataložni zapis o publikaciji Narodna in univerzitetna knjiznica, Ljubljana 510.5(075.8)(076.1) CABELLO, Sergio Vaje iz alternativnih modelov računanja [Elektronski vir] / Sergio Cabello. - 1. izd. -El. knjiga. - V Ljubljani : samozal., 2010 Način dostopa (URL): http://www.fmf.uni-lj.si/~cabello/gradiva/vajeamr.pdf ISBN 978-961-276-042-7 253228544 Kazalo 1 Naključni algoritmi 4 2 Aproksimacijski algoritmi in #P 14 3 Vzporedni algoritmi 23 Priporočam naslednje monografije, ki pokrijejo vsaka svoj del predmeta: • J. JaJa. Introduction to parallel algorithms. Addison-Wesley, 1992. • R. Motwani in P. Raghavan. Randomized Algorithms. Cambridge University Press, 2001. • M. Mitzenmacher in E. Upfal. Probability and Computing. Cambridge University Press, 2005. • J. Kleinberg in E. Tardos. Algorithm Design. Addison-Wesley, 2005. • V.V. Vazirani. Approximation Algorithms. Springer-Verlag, 2001. Vse skupaj obravnavajo seveda precej več tem, kot jih obravnavamo pri predmetu. Na spletni strani Permute-With-Allso na voljo tudi skripta in prosojnice, ki so bolj neformalne in zato vcasih laZje razumljive. Poiscite! V najslabsem primeru lahko najdete druge zanimive stvari. Zahvala. Zahvaljujem se Gasperju Fijavzu za stevilne popravke. Seveda pa je avtor odgovoren za vse preostale napake. 1 Naključni algoritmi 1.1. Podprogram NepoštenKovanec(-) vrne '1' s verjetnostjo p in '0' z verjetnostjo 1 — p. Vrednost p £ (0,1) ni znana. Opisi naključni algoritem PoštenKovanec(-), ki enakomerno vrača '1' oziroma '0' in kot naključen podprogram uporablja samo Nepošten-Kovanec. Naj bo N slučajna spremenljvka, ki pove, kolikokrat pokliče PoštenKovanec podprogram NepoštenKovanec. Kaksno je matematično upanje E[N]? 1.2. Delamo naslednji poskus. Imamo n kosar B^B2, ... , Bn. Na vsakem koraku dodamo novo Zogo v naključno izbrano kosaro izmed Bi, B2,..., Bn. Naj bo X stevilo korakov do dogodka 'vsaka kosara vsebuje vsaj eno zogo'. Kaksno je matematično upanje slučajne spremenljevke X? (Namig: opazuj slučajno spremenljvko Xj, ki pove, koliko zog porabimo, da gremo od dogodka 'i praznih kosar' do dogodka '(i — 1) praznih kosar'.) 1.3. Denimo, da je rojstni dan naključnega človeka enakomerno porazdeljen po dneh v letu (prestopna leta zanemari). Rečimo, da je v isti sobi k naključno izbranih ljudi. Naj bo X stevilo parov ljudi v sobi, ki imajo isti rojstni dan. Za katere k je pričakovana vrednost spremenljevke X najmanj 1? Kaj se dogaja na planetu Kriptonu, kjer ima vsako leto n dni? 1.4. Problem Max-Cut je naslednja optimizačijska naloga: v grafu G isčemo prerez, ki ima največjo moč. Problem Max-Cut je NP-tez ak. Opi s i naključni algoritem, ki vrne prerez s pričakovano močjo najmanj |E(G)|/2. Ali to pomeni, da vedno obstaja prerez s močjo najmanj |E(G)|/2? 1.5. Delamo naslednji poskus. Na začetku imamo kos aro, ki vsebuje natanko 1 belo zogo in 1 črno zogo. Nato n krat ponovimo naslednji korak: izberemo naključno zogo iz kosare in jo damo nazaj v kos aro z dodatno zogo iste barve. V kos ari je na konču n + 1 zog. Pokazi, da je stevilo belih z og enakomerno porazdeljeno na {1,..., n}. 1.6. k-mediana mnoziče stevil S je element m iz S, ki zadosča k = |{a £ S | a < m}|. Opazujemo naslednji algoritem, ki vrne k-mediano: Algorithm Find(S; k) Input: mnoziča S z n različnimi stevili; stevilo k med 1 in n Output: k-mediana mnoziče S 1. Enakomerno izberemo naključen element y iz S; 2. Si = {x £ S | x < y}; 3. S2 = {x £ S | x > y}; 4. if |Si| > k 5. then return Find(S1; k); 6. if |Si| = k — 1 7. then return y; 8. if |Si| 0) and (A[i] > key) 6. do A[i + 1] ^ A[i]; 7. i ^ i — 1; 8. A [i + 1] ^ key; Naj bo X sluCajna spremenljvka, ki pove, kolikokrat delamo primerjavo (A[i] > key) v vrstici 5 algoritma. Kaksna je priCakovana vrednost spremenljvke X? Analiza mora biti natanCna in brez O-notacije. (Privzames lahko, da v vrstici 5 algoritem ne dela primerjave (A[i] > key), ko je (i < 0).) 1.9. Opazujemo naslednji algoritem: Algorithm BrezImena Input: Naravno stevilo n > 1 1. korak ^ 0; 2. K ^ kosara, ki vsebuje natanko eno belo in eno Crno zogo; 3. while K vsebuje < n belih z og 4. do Z ^ zoga izbrana nakljuCno enakomerno iz ko s are K; 5. if Z je zoga barve X; 6. then damo Z nazaj v ko saro K in damo se eno novo belo zogo v kosaro K; 7. else damo Z nazaj v kos aro K; 8. korak ^ korak + 1; (a) Koliko je priCakovana vrednost sluCajne spremenljke korak na koncu izvajanja algoritma, Ce je X bela barva. (b) Koliko je pricakovana vrednost slucajne spremenljke korak na koncu izvajanja algoritma, ce je X crna barva. 1.10. Oznaka [n] naj pomeni {1, ...n}. Naj bo a : [n] ^ [n] permutacija enakomerno izbrana iz mnozice permutacij. (a) Naj bo X stevilo negibnih tock permutacije, X = |{i G [n] | a (i) = i}|. Kaksno je matematicno upanje spremenljivke X in spremenljivke X2? (b) Koliko je E E |a(i) - i| i€[nj 1.11. Opazujemo naslednji algoritem: Algorithm BrezImena2 Input: Naravno stevilo n > 1 1. korak 4 0; 2. 1korak 4 n; 3. while i korak = 1 4. do ikorak+1 4 element izbran nakljucno enakomerno med {1,..., ikorak}; 5. korak 4 korak + 1; Pokazi, da je pricakovana vrednost spremenljvke korak na koncu algoritma O (log n). 1.12. Poiskati zelimo algoritem, ki vrne enakomerno nakljucno permutacijo elementov tabele A[1... n]. Imamo podprogram RANDOM(a, b), ki izbere enakomerno nakljucno celo stevilo na intervalu [a,b]. Opazujemo naslednji algoritem: Algorithm Permute-With-All(A) 1. for i = 1 to n 2. do swap A[i] 4—> A[Random(1,n)]; (a) Dokazi, da Permute-With-All ne izbere nakljucne permutacije enakomerno. (b) Opisi algoritem, ki pravilno vrne enakomerno nakljucno permutacijo v linearnem casu. Dokazi pravilnost. 1.13. Imamo podprogram RandomBit(), ki enakomerno vrne nakljucen bit. Torej velja Pr[RANDOMBlT() = 0] = Pr[RANDOMBlT() = 1] = 2. Z uporabo psevdokode opi s i algoritem RANDOM(a, b), ki vrne enakomerno izbran naklju cni element iz Z n [a, b], kjer sta a in b naravni stevili. Znotraj algoritma Random lahko dobimo nakljucne podatke le z uporabo RandomBit(). Kaksna je pricakovana casovna zahtevnost algoritma? 1.14. Naj bodo a1,... ,an nakljucna realna stevila, ki so izbrana enakomerno na intervalu [0,1]. Opi s i algoritem, ki uredi a1,...,an v pri c akovanem linearnem c asu. Algoritem lahko uporablja funkcijo floor. (Namig: poglej kvadrat stevila elementov na intervalu [i/n, (i + 1)/n].) 1.15. Na predavanjih smo spoznali nakljucni algoritem Min-Cut za problem iskanja minimalnega prereza. Ta algoritem spremenimo na naslednji nacin: na vsakem koraku namesto izbora nakljucne povezave za skrcitev (contraction) izberemo dve nakljucni tocki grafa in ju identificiramo. Pokazi, da obstajajo grafi, za katere je verjetnost, da tako popravljeni algoritem vrne minimalni prerez, eksponentno majhna. (Namig: (^/2) je priblizno 2n/y/n.) 1.16. Na predavanjih smo spoznali nakljucni algoritem Min-Cut za problem iskanja minimalnega prereza. Videli smo, da vrne Min-Cut minimalni prerez s verjetnostjo najmanj 2/(n(n — 1)), kjer je n stevilo tock grafa. Kaksno je stevilo skrcitev in verjetnost napake za naslednje variante. (a) Min-Cut ponovimo t krat in vrnemo najboljsi prerez, ki ga smo nasli. (Namig: spomni se, da je 1 — x < e-x.) (b) Povezave skrcimo po algoritmu Min-Cut, dokler ne dobimo grafa s k tockami, kjer je k < n. Potem naredimo t kopij tega grafa, ki ima k tock, in na vsaki kopiji posebej uporabimo algoritem Min-Cut ter vrnemo najboljsi najden prerez. 1.17. Opazujemo naslednji enostavni primer hazardne igre. Na zacetku imamo dohodek nic. Igramo n krogov. V vsakem krogu se dohodek poveca za 1 s verjetnostjo 1/3 ali se zmanjsa za 1 s verjetnostjo 2/3. Pokazi, da obstaja absolutna zgornja meja (neodvisna od n) za pricakovano stevilo krogov, v katerih imamo pozitiven dohodek. 1.18. Naj bo T drevo s korenom. Vsi listi drevesa so na nivoju h in vsako notranje vozlisce drevesa T ima natanko 3 sinove. Torej ima drevo T natanko 3h listov. Pisimo n = 3h. Vsak list drevesa ima podano vrednost 0 ali 1. Situacija je predstavljena na levi strani slike 1.1. Vrednost notranjega vozlisca je definirana rekurzivno po vecinskem pravilu: ima vrednost 0, ce imata dva ali trije sinovi vrednost 0, sicer ima vrednost 1. Zanima nas vrednost korena. Poglej desno stran slike 1.1. Opisi nakljucni algoritem, ki izracuna vrednost korena in pogleda pri cakovano pod-linearno s tevilo listov. Pric akovano s tevilo listov, pri katerih algoritem pogleda vrednost, naj bo O(nc), pri cemer je konstanta c < 1. Namig: ko vemo, da imata 2 sinova vrednost 1, vrednost tretjega sina ni pomembna. Slika 1.1: Slika za vajo 1.18. 1.19. Pokazi, daje ZPP=RPn co-RP. 1.20. Pokaz i, daje BPP=co-BPP. 1.21. Podana je tabela A[1 ■ ■ ■ n] stevil. Opi s i podlinearni algoritem tipa Monte Carlo, ki zadosCa naslednji zahtevi: Ce je najmanj n/2 elementov iz A negativnih, potem algoritem vrne 'VeC kot ena polovica je negativnih.'; Ce je najveC n/4 elementov iz A negativnih, potem algoritem vrne 'Manj kot ena Cetrtina je negativnih'; sicer algoritem vrne karkoli, lahko tudi napaCen odgovor. Verjetnost napake algoritma naj bo najveC 5, kjer je 5 < 1 vhodni parameter. 1.22. Zanima nas naslednji odloCitveni problem: ali sta dve podani multimnoz ici stevil enaki. DoloCi polinom za vsako multimnozico na tak naCin, da sta polinoma enaka natanko tedaj, ko sta multimnoz ici enaki. Nato opi s i algoritem tipa Monte Carlo, ki doloC i, ali sta dve podani multimnozici stevil enaki. 1.23. Opazujemo ne nujno po s ten kovanec. Ko ga meCemo, grb pade z verjetnostjo p G (0,1), kjer p ni znan. Radi bi ocenili vrednost p. Kovanec vrzemo m krat in uporabljamo cenilko (estimator) p = h/m, kjer je h stevilo grbov. Kaksen mora biti m, da velja Pr[|p — p| < ep] > 1 — 5? (Vrednost m bo odvisna od 5, e,p.) Kaj se dogaja, ko gre p ^ 0? 1.24. Delamo naslednji poskus. Imamo n kosar B1;B2, ... , Bn. Naslednji korak ponovimo k krat: novo zogo damo v kosaro, ki jo izberemo enakomerno nakljuCno. Naj bo Xi stevilo zog v kosari Bi na koncu. Naj bo Xmin = min{Xi,... , Xn}. DoloCi vrednost k = k(n), za katero velja 2 Pr[Xmin < 2 ln n] < -. n Ali pri tako izbranem k = k(n) velja E[Xmin] = Q(logn)? 1.25. Naj bo S0 = {1,..., n}, kjer je n = 2k za neko naravno stevilo k. Za vsak i G N definiramo mnoz ico Si takole: zaC nemo z Si = 0 in potem vsak element iz Si-1 neodvisno kopiramo v Si z verjetnostjo 1/2. Naj bo Z = £ |Si|. i=0 (a) Pokazi, da je za dovolj velik n verjetnost Pr[Z > 10n] < 1/100. (b) Naj bo t = min ({i G N | Si = 0} U {n3}). Ali velja E[t] = O(logn)? 1.26. Posteno igralno kocko s stevilkami {1,2,..., 6} vrzemo n krat. Naj bo X vsota stevil, ki smo jih dobili na kocki. Vemo, da je E[X] = 7n/2. Z uporabo meje Cernova pokaz i naslednjo trditev: za vsako konstanto 5 > 0 obstaja konstanta c = c(5) > 0, ki zadosCa Pr X G [2n — cvn, 2n + cvn > 1 5. 1.27. Naj bodo X1,X2,...,Xn neodvisne sluCajne spremenljvke z zalogo {—1,1}. Ni nujno, da so enakomerne. Naj bo X = Y^n=i Xi. Denimo, da velja E[X] = 0. Pokaz i mejo tipa Cernova za Pr[|X| > t], ki velja za poljuben t G (0,n). 1.28. Naj bo A matrika velikosti n x n s koefičienti iz {0,1}. Zanima nas vrednost 0(A) = min{||Ab|U | b £ {—1,1}n}, kjer je ||c||^ največja absolutna vrednost koefičientov vektorja c: ||(ci C2 ••• Cn)T |U = max |ci |. i=1—n Pokazi, da velja 0(A) = O(\/n log n). Namig: izberi naključni vektor b £ {—1,1}n in uporabi mejo Cernova iz vaje 1.27. 1.29. Opazujemo naslednji algoritem: Algorithm BrezImena3 Input: Naravno stevilo k 1. x = 0; 2. for i = 1 to k 3. do vrz emo po s teno igralno kočko 4. if dobimo 1 5. then izberemo točko (a, b) £ [0, 2] x [0, 2] enakomerno naključno; 6. if a2 < b 7. then x = x + 1 8. return rez = x/k (a) Določi E[rez]. (b) Izračunaj vrednost parametra k, za katerega velja Pr {|rez — E[rez]| < 10-5} > 0.99. (č) Kaj bi spremenili v algoritmu, če zelimo E[rez] = ln2? Namig: J Xdx = ln x. 1.30. Oznaka [n] naj pomeni {1, ...n}. Predpostavimo, da podprogram RANDOM(k) vrne naključno čelo stevilo med 1 in k enakomerno. Opazujemo naslednji algoritem, ki vrne injektivno funkčijo f : [n] ^ [k] pri nekem k > n. Algorithm Vaja1 Input: n, k, pri čemer je n < k 1. for i = 1, 2,..., n 2. do f (i) :=RANDOM(k); 3. while f (i) £ {f (j) | j < i}; 4. do f (i) :=RANDOM(k); Naj bo X sluč ajna spremenljvka, ki pove, kolikokrat smo kličali RANDOM(k). (a) Ce je k = n, koliko je E[X]? (b) Kako je E[X] odvisno od parametra k? (č) Pokaz i, da je v primeru k = 2n, verjetnost Pr[X > 2 ■ E[X]] zelo zelo majhna. 1.31. Imamo n nalog, ki jih moramo razdeliti med m strojev, pri cemer m deli n. Posamezen stroj opravi posamezno nalogo v eni uri z verjetnostjo p oziroma v k urah z verjetnostjo 1 — p. Vsak stroj dobi nakljucno podmnoz ico n/m nalog. Naj C oznacuje c as potreben za dokoncanje vseh nalog. Z uporabo meje Cernova poka zi zgornjo in spodnjo mejo vrednosti slucajne spremenljevke C (z veliko verjetnostjo). 1.32. Graf G z n tockami konstruiramo nakljucno na naslednji nacin: za vsak par tock u, v grafa dodamo povezavo uv s verjetnostjo p = p(n). Za katere vrednosti p je stevilo pricakovanih 5-klik enako 1? Ali je, pri tako izbranem p, stevilo povezav nakljucnega grafa G skoncentrirano (concentrated) okoli matematicna upanja? 1.33. Imamo 10 ko s ar in n zog. Kot obicajno vrzemo z ogo v nakljucno kosaro, pri cemer ima vsaka kosara isto verjetnost. Naj bo X stevilo zog v kosari, ki ima najvecje stevilo zog. Naj bo Y stevilo zog v kos ari, ki ima najmanj sje stevilo z og. Pokaz i, da za vsak e > 0 obstaja vrednost c = c(e) > 0, ki zadosca Pr [X — Y > c^n ] < e. (Namig: opazuj vsak par ko s ar posebej.) 1.34. Podana je ogromna multimnozica S, ki vsebuje n s tevil. Poiskati z elimo pribli z ek mediane S. Pravimo, da je stevilo x e-aproksimacija mediane za multimnoz ico S, ce imata {s G S | s < x} in {s G S | s > x} moc najmanj (1/2 — e)n. Denimo, da je e pozitiven in dovolj majhen. Opazujemo naslednji algoritem. Podmnozico R C S konstruiramo takole: k krat izberemo nakljucen element mnoz ice S in ga dodamo v R. (R je multimnoz ica in lahko posamezen element vsebuje veckrat.) Nato izracunamo mediano m multimnozice R in vrnemo m. Stevilo k moramo izbrati tako, da pravilno najdemo e-aproksimacijo mediane. (a) Naj bo x£ element iz S, ki je v polozaju (1/2 — e)n, ko je S urejena od najmanjsega do najvecjega elementa (increasingly). Naj bo X stevilo elementov mnoz ice R, ki so manjsi kot Pokazi, da velja Pr[X > k/2] < 1/200 za k = 6(e-2). (b) Doloc i natancno vrednost parametra k, za katerega algoritem vrne (0.05)-aproksi-macijo mediane za S z verjetnostjo najmanj 0.99. (c) Za podane parametre 5 G (0,1) in e izracunaj vrednost k = k(e, 5) za to, da vrne algoritem e-aproksimacijo mediane za S z verjetnostjo najmanj 1 — 5. 1.35. Podana je ogromna mnoz ica S, ki vsebuje n razli c nih elementov. Zanima nas konstrukcija nakljucne podmnozice R C S, ki vsebuje natancno ^/n elementov. Privzames lahko, da je y/n celo stevilo. Eksperimentiramo s naslednjim algoritmom, ki ima dva dela. Prvi del poteka takole: za cnemo s prazno mno zico R in nato vsak element s G S neodvisno dodamo v R s verjetnostjo n-1/2 + cn-3/4, kjer je c ustrezno izbrana konstanta. V drugem delu vrne algoritem 'Napako', ce ima R manj kot y/n elementov. Drugace pa algoritem odstrani |R| — ^/n naklju c nih elementov iz R in vrne rezultat. (a) Kaks na je pricakovana moc mnoz ice R na koncu prvega dela? (b) Doloci konstanto c, za katero je verjetnost napake v algoritmu manjsa kot 1/100. (c) Predpostavimo, da algoritem ne vrne 'Napake'. Pokazi, da je stevilo elementov, ki jih algoritem na drugem koraku odstrani, z veliko verjetnostjo O(nl/i^Jlog n). (d) Predpostavimo, da algoritem ne vrne 'Napake'. Pokaz i, da je pri c akovano stevilo elementov, ki jih algoritem na drugem koraku odstrani, 1.36. Na trgu je nova zbirka n razlic nih znamk. Novo znamko dobimo, ko kupimo kuverto. Vsaka kuverta vsebuje znamko, ki je izbrana enakomerno nakljucno med znamkami v kompletu. V vaji 1.2 smo videli, daje pri c akovano s tevilo kupljenih kuvert do dokonc anja kompleta 0(n log n). Pri cakujemo, da bo v prihodnosti vsak komplet znamk zelo dragocen. Torej se odlocimo, da bomo kupili dovolj kuvert, da dobimo veliko kompletov znamk. Poka zi, da z veliko verjetnostjo lahko dobimo 100 log n kompletov, ce kupimo 105n log n kuvert. 1.37. Imamo Markovsko verigo s stanji {1,2,3,4} in prehodno matriko 0 3/10 1/10 3/5 1/10 1/10 7/10 1/10 1/10 7/10 1/10 1/10 9/10 1/10 0 0 • Izracunaj stacionarno porazdelitev. • Izracunaj verjetnost, da imamo stanje 4 po 32 korakih, ce smo zaceli v stanju 1. • Izracunaj verjetnost, da imamo stanje 4 po 128 korakih, ce je stanje na zacetku izbrano nakljucno enakomerno. 1.38. k-barvanje grafa G je preslikava b : V (G) ^ {1,..., k}. Graf G je k-obarvljiv, ce obstaja taksno k-barvanje, da nobena povezava ni enobarvna. Graf G je (A, k)-obarvljiv, ce obstaja taksno k-barvanje, da noben trikotnik (3-klika) ni enobarven. Naj bo G 3-obarvljiv graf. (a) Pokaz i, da je graf G (A, 2)-obarvljiv. (b) Opazuj naslednji algoritem, ki vrne 2-barvanje grafa G, ki zadosca, da noben trikotnik (3-klika) ni enobarven: dokler obstaja enobarven trikotnik v G, algoritem izbere enobarven trikotnik in spremeni barvo nakljucne tocke takega trikotnika. Doloci zgornjo mejo za pricakovano stevilo korakov algoritma. 1.39. Matrika P je dvojno stohasticna matrika (doubly stochastic), ce je vsota koeficientov vsake vrstice in vsakega stolpca enaka 1. Imamo Markovsko verigo, pri cemer je prehodna matrika dvojno stohasti cna. Poka zi, da je enakomerna porazdelitev staciona-narna. 1.40. Imamo Markovsko verigo z n stanji, stacionarno porazdelitvjo n = (n1;... , nn) in prehodno matriko P. Recimo, da zacnemo verigo v casu 0 in naredimo m korakov. Naj bo X0,X1 , X2,...,Xm zaporedje stanj, ki ga dobimo. Zanima nas obrnjeno zaporedje stanj Xm, Xm_i,..., Xo. • Za podano stanje Xk+1 pokazi, da je stanje Xk neodvisno od Xk+2, Xk+3,..., Xm. • Pokazi, da zadosča prehodna matrika obrnjenega zaporedja Q enakosti Qi,j = nj Pj,i/ni. 1.41. Imamo Markovsko verigo na stanjih {1,..., n}. Za prehodno matriko P za i < n velja Pi,i+1 = 1/2 in Pi,1 = 1/2, pa tudi Pn,n = 1/2 in Pn,1 = 1/2. Izračunaj stačionarno porazdelitev. 1.42. Imamo 2 kosari (L in D) in n zog, ki so porazdeljene med L in D. Na vsakem časovnem koraku izberemo enakomerno naključno zogo in jo damo v drugo kos aro. To je, če je izbrana zoga v L, potem jo damo v D, in obratno. Naj bo Xt stevilo zog v kos ari L na časovnem koraku t. X1, X2,... je Markovska veriga. (a) Opisi prehodno matriko verige. (b) Poisči stačionarno porazdelitev verige. (Namig: če razumes postopek, lahko odgovor n uganis in dokaz es njegovo pravilnost. V re sitvi nastopajo binomski koefičienti Vj 1.43. Imamo ko s aro, ki vsebuje n z og. Nekatere izmed z og so bele, druge so č rne. Na posameznem koraku naredimo naslednje: izberemo naključno zogo iz kosare in jo zamenjamo z novo belo zogo z verjetnostjo 2/3 in s črno zogo z verjetnostjo 1/3. Kosara ima vedno n zog. Naj bo Xt stevilo belih zog v kos ari na konču koraka t. Zaporedje Xo, X1, X2,... je Markovska veriga, kjer je Xo s tevilo belih z og na začetku. (a) Napisi prehodno matriko Markovske verige. (b) Pokazi, daje ni = (n) Jn stačionarna porazdelitev verige. (Namig: koliko je (1+2)n?) (č) Zakaj lahko porazdelitev opisano v točki (b) kar uganemo? (d) Predpostavimo, da je n = 3 in da so v začetku vse zoge črne. Določi zgornjo mejo za pričakovano vrednost slučajne spremenljvke min{t | Xt = 3}. 1.44. Imamo 3 kos are K0,K1,K2. V kosari K0 sta 2 zogi. Kosari K1 in K2 sta prazni. Na vsakem koraku izberemo eno naključno zogo. Ce jo izberemo iz kos are Ki, jo damo v kosaro Ki+1 mod3. Stanje na konču koraka t opisemo s trojko Xt = (a0,a1,a2) £ {0,1, 2}3, ki zadosča a0 + a1 + a2 = 2. Začetno stanje je X0 = (2,0,0). Zaporedje X0, X1, X2,... je Markovska veriga. (a) Napisi prehodno matriko Markovske verige. (b) Izračunaj stačionarno porazdelitev verige. (č) Naj bo Y s tevilo z og v kos ari K0 na konču koraka t, in naj bo Zt = j=0 Y. Izrač unaj vrednost (Zt/t). 1.45. V povezanem grafu G naredimo naključen obhod. (a) Pokazi, da je stačionarna porazdelitev enaka deg(v) nv = n—TTrH za vsako toč ko v £ V (G). 2|E (G)| (b) Pokazi, da za vsako tocko v G V (G) velja hvv = 2|E(G)| v'v deg(v) ' (c) Pokazi, da za vsako povezavo uv G E(G) velja hv,u < 2|E(G)|. (Namig: izracunaj hv,v z uporabo sosedov tocke v.) (c) Pokazi, da je cas pokritja (cover time) (pricakovani cas do obiska vseh tock) najvec 4|V(G)| ■ |E(G)|. (Namig: uporabi vpeto drevo.) 1.46. Naj bo Gn naslednji graf: • V (Gn) = {v1,v2, ...,v2n-1}, • tocke v1, . . . , vn inducirajo poln podgraf (so vse paroma sosede), (V^--(V^-(v5-(V^-(V7) • tocke vnvn+1vn+2 ...v2n-1 inducirajo pot, drugih povezav ni. Na sliki je graf G4. Opazujemo nakljucni obhod v grafu Gn, kjer se na vsakem koraku premaknemo v enakomerno izbranega nakljucnega soseda. (a) Kak sna je stacionarna porazdelitev? (b) Naj bo Z stevilo korakov potrebnih za obisk vseh tock, ce zacnemo obhod v tocki v2n-1. Pokaz i, da je E[Z] = O(n2). (c) Naj bo Yt slucajna spremenljvka, ki pove indeks tocke na koraku t. Na primer, ce je na desetem koraku obhod v tocki v4, potem je Y10 = 4. Naj bo Zt = Yt. Izrac unaj vrednost (Zt/t). 1.47. Muca in miska neodvisno in nakljucno hodita v grafu G, ki je povezan in ni dvodelen (bipartite). Obhoda zac neta v istem c asu v razli c nih toc kah in naredita en korak v vsakem casovnem koraku. Kot si predstavljate, muca poje misko, ce se v istem casovnem trenutku srecata v isti tocki. Dokaz i zgornjo mejo O(|E(G)|2-| V(G)|) za pric akovano stevilo korakov do trenutka, ko poje muca misko. (Namig: poglej Markovsko verigo na stanjih (a, b), kjer je a polozaj muce in b polozaj miske, in uporabi vajo 1.45.) 2 Aproksimacijski algoritmi in #P 2.1. Zanima nas problem TSP v ravnini z evklidsko razdaljo: vhod je mnoz ica toCk P, cena povezave uv pa je enaka evklidski razdalji med toCkama u in v. Opazujemo naslednji algoritem: Ce so p1 ,p2,... ,pn toCke vhoda urejene po ^-koordinatah (predpostavimo da so vse x-koordinate razliCne), algoritem vrne obhod pi ^ p2 ^ p3 ^----► pn ^ pi. Pokaz i, da tak algoritem ni k-aproksimacijski algoritem za nobeno konstanto k. 2.2. Barvanje grafa G je preslikava b : V (G) ^ N, ki zadosCa b(u) = b(v) za vsako povezavo uv G E(G). Graf z elimo obarvati z najmanj s im moz nim stevilom barv, to je, minimizirati moC mnozice b(V(G)). Uporabljamo naslednji pozresni algoritem. Naj bodo v1; v2,..., vn toC ke grafa G. Za vsak i = 1,..., n naj bo Gi podgraf grafa G induciran na toCkah v1; v2,..., vi. Za vsak i = 1,..., n iterativno definiramo barvo toC ke vi kot b(vi) = min{n G N | b(-) je barvanje grafa Gi}. Pokazi, da tak algoritem ni k-aproksimacijski algoritem za nobeno konstanto k. 2.3. Za vsak k G N definiramo naslednji optimizacijski problem: k-LARGEsTCovER Vhod: konCna mnozica S in druzina podmnozic F C 2S, kjer je vsaka podmno-z ica X G F moC i k. Naloga: maksimiziraj |G| pri pogojih: G C F in podmnozice poddruzine G so paroma disjunktne. (a) Kaksen problem je 2-LargestCover? (b) Opisi k-aproksimacijski algoritem za problem k-LARGEsTCovER. 2.4. Zanima nas naslednji optimizacijski problem: BinPaoking Vhod: Seznam naravnih stevil a1,..., an G N in vrednost B G N . Za vsak i naj velja ai < B. Naloga: minimiziraj vrednost k pri pogojih: /1; I2,..., Ik C [n], [n] je disjunk-tna unija /1;..., Ik in za vsak j = 1,..., k naj velja ^ie/ ai < B. Elemente velikosti a1,..., an razdelimo elementov na ko s are velikosti B in pri tem z elimo minimizirati stevilo ko sar, ki jih rabimo. (a) Predpostavimo, da P=NP. Pokaz i, da za ta problem ne obstaja a-aproksimacijski algoritem za nobeno konstanto a G (1, 3/2). (b) Uporabljamo algoritem s strategijo first-fit: na koraku i (i = 1,... k) dodamo indeks i v prvo skupino Ij, ki ima dovolj prostora za ai. To je, indeks i je dodan v mnozico Ij, Ce trenutno velja j = min{j' | ^ a < B — ai}. Pokazi, da je tak algoritem 2-aproksimacijski. 2.5. Zanima nas naslednji optimizačijski problem: SeveralValuableBins Vhod: n elementov vrednosti a1,a2,...,an £ N in stevilo B £ N. Velja Ei a > B. Naloga: naredi čim večje stevilo skupin elementov, kjer je vsota vrednosti vsake skupine najmanj B. (a) Prevedi problem SeveralValuableBins na ILP. (b) Opi s i 2-aproksimačijski algoritem za problem SeveralValuableBins. (č) Pokazi: če obstaja (5/3)-aproksimačijski algoritem za SeveralValuableBins, potem je P=NP. 2.6. V dvodelnem grafu G = (U, V, E) naj E označuje njegovo mnoz ičo povezav, U in V pa naj bosta oba barvna razreda njegovih točk. Za k £ N definiramo naslednji optimizačijski problem: k-COMpATIBLEMATOHING Vhod: Dvodelni grafi Gi = (U, V, Ei), G2 = (U, V, E2), ..., Gfc = (U, V, Ek) z istimi točkami. Naloga: maksimiziraj |F| pri pogojih: F C E1 U ■ ■ ■ U Ek in pri čemer je za vsak i = 1,... k mnoz iča povezav F n Ei prirejanje. (a) Opi s i k-aproksimačijski algoritem za problem k-COMpATIBLEMATOHING. (b) Opisi (3/2)-aproksimačijski algoritem za problem 2-CompatibleMatohing. 2.7. V dvodelnem grafu G = (U, V, E) naj E označuje njegovo mnoz ičo povezav, U in V pa naj bosta oba barvna razreda njegovih točk. Za k £ N definiramo naslednji optimizačijski problem: k-COMPATIBLEMAXDEGREE2 Vhod: Dvodelni grafi Gi = (U, V, Ei), G2 = (U, V, E2), ..., Gk = (U, V, Ek) z istimi točkami. Naloga: maksimiziraj |F| pri pogojih: F C E1 U ■ ■ ■ U Ek pri čemer ima za vsak i = 1,... k graf (U, V, Ei n F) maksimalno stopnjo največ 2. (a) Prevedi problem k-CoMPATiBLEMAxDEGREE2 na ILP. (b) Opisi (2k)-aproksimačijski algoritem za problem k-CoMPATiBLEMAxDEGREE2. 2.8. Zanima nas problem (+1)-TSP. Vhod problema (+1)-TSP je vhod navadnega problema TSP, kjer imajo čene/razdalje naslednje lastnosti: dij = dji za vsak i, j (simetrija), dij < 1 + dik + dkj za vsak i, j,k (priblizna trikotniska neenakost), in dij £ N za vsak i, j (čene so naravna stevila). Isčemo aproksimačijski algoritem za problem (+1)-TSP. Uporabljamo 2-aproksimačijski algoritem za metrični TSP (ali A-TSP), ki ga smo spoznali na predavanjih. Ni jasno in mogoče ni res, da je tak algoritem 2-aproksimačijski za (+1)-TSP. Ali je tak algoritem k-aproksimačijski za kaksno konstanto k? 2.9. Zanima nas metrični TSP (A-TSP), kjer je dij čena/razdalja med točko i in točko j. Naslednji algoritem je znan kot Christofidesov postopek: • poiscemo minimalno vpeto drevo T v polnem grafu Kn z cenami dj; • z Odd oznac imo mnoz ico tock, ki imajo v drevesu T liho stopnjo; • konstruiramo podgraf H grafa Kn induciran na mnozici Odd, z istimi cenami na povezavah dj; • v H poiscemo popolno prirejanje M z minimalno vsoto cen; • konstruiramo Eulerjev obhod W = v1v2v3 ■ ■ ■ v2n v grafu T + M; • v obhodu W = v1v2v3 ■ ■ ■ v2n odstranimo vse veckratne ponovitve tock. Naj bo Q obhod, ki ga dobimo. (Na primer, iz obhoda W = v1v2v3v2v1v4v2v1 pridelamo obhod Q = v1v2v3v4v1.) • vrnemo Q. Vsak korak algoritma porabi polinomski cas. Ali je res, da vrne algoritem dopustno resitev? Zakaj? Dokazi, da je Christofidesov algoritem (3/2)-aproksimacijski. (Namig: kaj lahko recemo o dolz ini prirejanja M?) 2.10. Na predavanjih smo spoznali 2-aproksimacijski algoritem za metric ni TSP (A-TSP). Pokaz i, da algoritem ni (2 — e)-aproksimacijski za nobeno konstanto e > 0. (Namig: poi s ci protiprimer s cenami 1 in 2.) 2.11. Zanima nas naslednji problem razporeda (scheduling). Imamo n nalog in m identic nih strojev M1;..., Mm. Vsak izmed strojev za nalogo j rabi c as tj > 0. Strojem zelimo dodeliti naloge na tak nacin, da minimiziramo cas koncanja zadnjega stroja. To je, ce je A(i) je mnoz ica nalog stroja Mj, potem stroj Mi konc a v casu Ti = E tj, je a (i) minimizirati pa zelimo vrednost max{T1; T2,..., Tm}. (a) Opazujmo naslednji pozresni algoritem: za vsak j = 1,...,n, nalogo j dodelimo stroju, ki bi trenutno dodelitev nalog 1, . . . , (j — 1) kon cal najhitreje. Poka zi, da je tak algoritem 2-aproksimacijski. (b) Pokazi, da je algoritem toc ke (a) (2 — 1/m)-approksimacijski. (c) Pokazi, da je aproksimacijski faktor (2 — 1/m) tesen za algoritem tocke (a). To je, doka zi, da obstaja vhod problema, za katero algoritem vrne dodelitev, ki porabi vsaj (2 — 1/m) krat vec c asa kot optimalna dodelitev. (Namig: poskusi n = (m(m —1) + 1 nalog.) (d) Recimo, da je strojev 10, za vsako nalogo naj velja 1 < ti < 50, vsota trajanja vseh nalog pa naj bo najmanj 3000. Pokazi, daje algoritem tocke (a) potem (7/6)-aproksimacijski. (e) Opazujmo alternativni algoritem, ki je znan kot ordered scheduling algorithm. Najprej uredimo naloge glede casa izvajanja od najdalj sega do najkraj sega. Nato uporabimo pozresni algoritem odstavke (a) s to urejenostjo. Pokazi, da je tak algoritem (3/2)-aproksimacijski. (V resnici je tak algoritem (4/3)-aproksimacijski, dokaz pa je precej tezji.) 2.12. Zanima nas problem 0/1-Nahrbtnik: 0/1-Nahrbtnik Vhod: elementi e1,e2,...en, kjer ima posamezen element ei ceno ci G N in velikost vi G N. Velikost nahrbtnika V. Naloga: maksimiziraj ^ ieI ci pri pogojih I C {1,... ,n} in ^ ieI vi < V. Predpostavimo, da je vi < V za vsak i in da je ^i vi > V. Predpostavimo, da so elementi urejeni po relativni ceni glede na velikost, naj za vsak i velja ci/vi > ci+1/vi+1. (a) Uporabljamo naslednji pozres ni algoritem: na koraku i damo element ei v nahrbtnik ce je prostora s e dovolj. Pokaz i, da tak algoritem ni a-aproksimacijski algoritem za nobeno konstanto a. (b) Uporabljamo naslednji algoritem. Poiscemo prvi indeks k, ki zadosca ^k=1 vi > V, in potem izberemo najbolj so res itev med /1 = {1,..., k — 1} in /2 = {k}. Pokaz i, da je tak algoritem 2-aproksimacijski. (Namig: Pokazi, da je vrednost optimalne re s itve najvec ^k=1 ci.) 2.13. Zanima nas problem k-MuLTiwAYCuT: k-MuLTiwAYCuT Vhod: graf G in toc ke s1, s2,..., sk G V (G). Naloga: minimiziraj |A| pri pogojih: A C E (G) in graf G — A nima nobenih poti med si in s j, za vsak i, j, i = j. Opazujemo naslednji algoritem. Za vsak si izracunamo mnozico povezav Bi, ki ima najmanj so moc in loci si od {s1,..., sk} \ si. To je, G — Bi nima poti med si in sj za noben s j = si. Vsak Bi lahko izracunamo v polinomskem c asu; za nalogo ni pomembno, kako to naredimo. Algoritem vrne Ui Bi. (a) Pokazi, da je tak algoritem 2-aproksimacijski. (b) Pokaz i, da tak algoritem ni 9/5-aproksimacijski. (c) Opisi (3/2)-aproksimacijski algoritem za problem 3-MultiwayCut. 2.14. Opis i 6-aproksimacijski algoritem za problem konstrukcije najvecje neodvisne mnoz ice v ravniskih grafih. (Mnozica tock U grafa G je neodvisna, ce za vsaki tocki u, v G U velja uv G E(G).) 2.15. Zanima nas problem VertexCover: dan je graf G, iscemo pa najmanjso mnozico toc k grafa, ki pokrijejo vsako povezavo grafa. Nekdo priporoc a naslednji algoritem: naj bo T vpeto drevo pregleda grafa G v globino. Vrnemo mnozico tock S, ki niso listi v T. Pokaz i, da je priporoceni algoritem 2-aproksimacijski algoritem za VertexCover. (Namig: najdi veliko prirejanje v grafu G.) 2.16. V tej nalogi imajo vsi kvadrati stranice vzporedne koordinatnima osema. Naj bo R mno zica kvadratov v ravnini, kjer ima vsak kvadrat plo s cino najve c 1. Predpostavimo, da je vsota ploscin kvadratov mnoz ice R vsaj 1. Pakiranje je tak s na podmnozica kvadratov S C R skupaj s poloz aji kvadratov iz S, da so vsi kvadrati znotraj kvadrata [0,1]2 in so notranjosti kvadratov paroma disjunktne. Zanima nas pakiranje, ki maksimizira pokrito plosCino. Opi s i 4-aproksimacijski algoritem za tak problem. (Namig: opisi algoritem, ki vrne pakiranje, ki pokrije plosCino najmanj 1/4.) 2.17. Zanima nas optimizacijski problem k-CovERiNG: k-CovERiNG Vhod: kon C na mnoz ica realnih stevil X = {x1, x2,... xn} C R. Naloga: maksimiziraj |(I1 U I2 U ... Ik) n X|, kjer so I1,12,..., Ik enotski intervali. Uporabljamo naslednji poz res ni algoritem: na koraku i (i = 1... k) izberemo enotski interval Ii, ki maksimizira |Ii n (X \ (I1 U ■ ■ ■ U Ii-1)|. (a) Pokazi, da tak algoritem ne resuje problema k-CovERiNG optimalno. (b) Pokaz i, da je tak algoritem (4/3)-aproksimacijski, ko je k = 2. (c) Pokazi, da je tak algoritem (27/19)-aproksimacijski, ko je k = 3. 2.18. Za vsako toCko x G R2 in vsako konCno mnozico toCk Q C R2 definiramo d(x, Q) = minq£Q d(x, q). Optimizacijski problem Center je definiran takole: Center Vhod: kon C na mnoz ica P C R2 in naravno s tevilo k. Naloga: izberi Q C P moC i k, ki minimizira maxpep d(p, Q). Naloga razumemo na naslednji naCin: minimizirati zelimo polmer k diskov, ki imajo sredi sCa v toC kah mnoz ice P in pokrijejo P. Problem Center je NP-tez ak. Opazujemo naslednji algoritem za center: Algorithm Greedy Input: P, k (denimo |P| < k) 1. izberemo poljubno toCko q1 iz P; 2. Q = {91}; 3. for i = 2 to k 4. do naj bo qi toC ka, ki maksimizira d(q, Q) med toCkami q G P; 5. Q = Q U{qi}; 6. return Q; (a) Pokazi, da je algoritem Greedy 2-aproksimacijski algoritem. (b) Pokazi, da algoritem Greedy ni (1.9)-aproksimacijski algoritem za k = 4. 2.19. Zanima nas problem LongestPath: podan je graf G, isCemo pa najdaljso pot v G, ki je seveda brez ponovljenih toCk. Predpostavimo, da P=NP. Pokaz i, da za problem LongestPath ne obstaja FPTAS. 2.20. Naj bo G = (V, E) poljuben graf. Za vsako celo stevilo £ > 1 definiramo graf G^ = (V na naslednji naCin: V W je mnozica £-teric toCk iz V, dve £-terici (v1, v2,..., v.) in (w1,w2,..., pa sta sosedi natanko tedaj, ko je za vsak i toCka vi bodisi soseda toCke wi ali pa sta vi in wi enaki. Preveri, da je G(1) = G. Zanima nas optimizacijski problem iskanja najveCje klike v podanem grafu, ki ga imenujemo Max-Klik. (a) Naj bo M^ moč največje klike v grafu . Pokaz i, da velja M^ = (M1)^. (b) Pokaz i naslednjo trditev: če obstaja k-aproksimačijski algoritem za problem Max-Klik za neko konstanto k, potem obstaja FPTAS za problem Max-Klik. (č) Predpostavimo, da P= NP. Pokazi, da ne obstaja k-aproksimačijski algoritem za problem Max-Klik za nobeno konstanto k. 2.21. Naj bo P mnoziča n točk v ravnini. Steinerjevo drevo T za P je drevo, ki zadosča V (T) c R2 in P C V (T). 'Dodatne' točke V (T) \ P imenujemo Steinerjeve toč ke. Dolz ina povezave uv je dolz ina daljiče uv, in dolzina drevesa je vsota dolzine povezav. Naj bo Tste(P) Steinerjevo drevo za P z minimalno dolzino. Problem iskanja Tste(P) je NP-te zak. Točke na ravnine definirajo 'navadno' vpeto drevo Tmin(P): opazujmo poln graf z mnoz ičo toč k P, kjer je čena povezave uv dolz ina daljiče uv, in naj bo Tmin(P) minimalno vpeto drevo tega grafa. (a) Pokazi, da je TSte(P) lahko strogo krajsi kot Tmin(P). (b) Pokazi, da je algoritem, ki izračuna Tmin(P) in ga vrne, 2-aproksimačiski algoritem za problem iskanja TSte(P). 2.22. Naj bo P mnoziča n točk v ravnini. Diameter A(P) mnoziče P je definiran kot A(P) = max |pq|, p,q€P,p=q kjer je |pq| dolzina daljiče Diameter A(P) lahko izračunamo v času O(n2). Zanima nas FPTAS, ki porabi linearni čas za vsako konstanto e. • Opisi linearni 2-aproksimačijski algoritem. • Opisi (1 + e)-aproksimačijski algoritem, ki porabi linearni čas za vsako konstanto e > 0. Lahko predpostavi s , da imas na voljo funkčijo čeli del (|_-_|). (Namig: uporabi prvo točko in mrezo z velikostjo odvisno od e.) 2.23. Opisi 2-aproksimačijski algoritem za naslednji problem: LinearOrdering Vhod: usmerjen graf G = (V, A). Naloga: poisči bijektivno preslikavo n : V u {1, ■ ■ ■ , |V|}, ki maksimizira moč mnoziče {■uvv £ A | n(u) < n(v)}. 2.24. Problem pod drobnogledom je barvanje grafov na n točkah. (a) Pokazi, da je vsak graf z maksimalno stopnjo A tudi (A + 1)-obarvljiv. Opisi algoritem, ki v polinomskem času vrne (A + 1)-barvanje. (b) Opisi algoritem, ki resi naslednjo nalogo v polinomskem času: vhod je graf G, ki je 3-obarvljiv. Poiskati zelimo O(y/n)-barvanje grafa G. (Namig: Ce je nek graf 2-obarvljiv, ga lahko 2-pobarvamo v polinomskem času.) 2.25. Zanima nas naslednji problem razporeda (scheduling). Opraviti moramo n nalog, na voljo pa imamo 2 identicna stroja M1; M2. Naloga j porabi cas tj > 0, kjer je tj celo stevilo. Strojema zelimo dodeliti naloge na tak nacin, da minimiziramo cas dokoncanja zadnjega stroja. To je, ce je A(i) je mnozica nalog stroja Mi, potem konca stroj Mi v casu Ti = E tj, jeA(i) minimizirati pa zelimo vrednost max{T1;T2}. (a) Opi si algoritem, ki uporablja dinami cno programiranje in najde optimalno re sitev v casu O(n(T*)2), kjer je T * cas optimalne resitve. (b) Opisi FPTAS za problem. 2.26. Zanima nas naslednji problem razporeda (scheduling). Opraviti moramo n nalog, na voljo imamo tri identi c ne stroje M1;M2,M3. Naloga j porabi cas tj > 0, kjer je tj celo stevilo. Ce je A(i) je mnoz ica nalog stroja Mi, potem konca stroj Mi v casu Ti = E tj. jeA(i) Zelimo minimizirati vrednost Tj2 + T22 + T|. (a) Opisi algoritem, ki uporablja dinami cno programiranje in najde optimalno resitev v psevdopolinomskem casu. (b) Opi s i FPTAS za problem. (c) Opisi PTAS, ki uporablja strukturiranje izhoda. 2.27. Gledamo problem 0/1-KnapsaokWithTaxes, ki je definiran takole. Imamo mnoz ico X z n elementi. Vsak element x G X ima velikost v(x) in ceno c(x). Velikosti in cene so cela stevila. Tudi imamo nahrbtnik s prostornino W. Nekatere elemente X pospravimo v nahrbtnik in gremo na pot v drugo drz avo. Na z alost carina na meji ne dela kot bi morala, in bo zaplenila element iz nahrbtnika, ki ima najvecjo ceno. Maksimizirati zelimo vsoto vrednosti elementov, ki bodo ostali v nahrbnitku. Bolj formalno: max J2xčy c(x) — maxxeY c(x) p.p. Y C X £xgy v(x) < W Opisi FPTAS za problem 0/1-KnapsackWithTaxes. 2.28. Naj bo Gn multigraf na tockah {1,2,..., n}, ki ima dve povezavi ei; ei med toc kama i in i + 1 za vsak i = 1,2,..., n — 1. Oznacimo s = 1 in t = n. Vsaka povezava e grafa Gn ima dolz ino t(e) G N in ceno c(e) G N. Opazujemo naslednji optimizacijski problem: podana je vrednost L > 0, zelimo pa minimizirati ceno poti od tocke s do tocke t pri pogoju, da ima pot dolz ino najvec L. Naj bo C * cena optimalne res itve. (a) Opisi algoritem, ki optimalno resuje ta problem v casu O(n2C*). (b) Opisi algoritem, ki optimalno resuje ta problem v Casu O(n2L). (c) Recimo, da poznamo vrednost C0, ki zado s C a C0 < C * < n ■ C0. Opi s i PTAS za problem. (PTAS lahko dobi C0 pri vhodu.) (d) Opisi PTAS za tak problem. 2.29. Naj bo S mnozica n enotskih kvadratov v ravnini, ki imajo robove vzporedne koordinatnima osema. Predpostavimo, da so kvadrati v splos nem poloz aju: x-koordinate in y-koordinate robov kvadratov iz S so same razliCne. Kvadrati se torej ne dotikajo, lahko pa se sekajo. Mnoz ica S definira naslednji graf GS: vsak kvadrat s G S definira vozli s Ce grafa GS, kvadrata s in s' pa sta soseda natanko tedaj, ko se sekata. Zanima nas najveCja neodvisna mnozica grafa GS. To geometrijsko pomeni, da isCemo najveCjo podmnoz ico R C S, kjer se nobena dva kvadrata iz R ne sekata. Ta problem je NP-tez ak. IsCemo PTAS. Naj bo k naravno stevilo veCje kot 2; k doloC imo kasneje. Za vsak a = 0,1,2,..., k — 1 definiramo naslednjo mnoz ico navpiCnih premic Va = {{x = i ■ k + a} | i G Z}. Naj bo H mnoz ica vodoravnih premic, ki jo dobimo iz Vb z rotacijo n/2 v smeri urnega kazalca. Naj bo S (a, b) podmnoz ica kvadratov s S, ki ne sekajo niti Va niti Hb. (a) Preveri, da razumes definicije Vb in S(a, b). (b) Pokazi naslednjo trditev: Ce je S znotraj kvadrata velikosti k x k, potem lahko izraC unamo optimalno resitev v Casu O(n2+k ). (c) Pokazi, da lahko izraCunamo optimalno resitev za kvadrate S (a, b) v Casu O(n2+k2). (d) Naj bo Sol(a, b) optimalna resitev za kvadrate S(a, b). Naj bo R najbolj s a res itev med Sol(a, b), kjer je a, b G {0,1,..., k — 1}. Naj bo R* optimalna re sitev za S. Pokazi, daje |R*| — |R| < (4/k)|R*|. (Namig: Dirichletov princip) (d) Opi s i PTAS. (Namig: Ce je pretezko, naprej razmisli o podobnem algoritmu za eno dimenzijo.) 2.30. Recimo, da imamo orakelj, ki za vsak podan graf v polinomskem C asu pre steje stevilo njegovih 4-barvanj. Opisi algoritem, ki zna z uporabo zgornjega oraklja v polinomskem Casu presteti, koliko 3-barvanj ima vhodni graf. Ali je prevedba varCna (parsi-monious)? 2.31. Naj bodo S1, S2,..., Sm podmozice konCne mnoz ice U. Za vsak 1 < i < m poznamo moC |Si|. Zelimo (e, č)-aproksimacijo velikosti mnoz ice S = Ui Si. Predpostavimo, da imamo algoritem, ki pri vhodu i vrne element izbran nakljuCno enakomerno iz Si. Ravno tako imamo algoritem, ki pri vhodu x G U vrne c(x) = |{i | x G Si}|. Naslednji poskus ponovimo t krat: v koraku j izberemo nakljuCno podmnozico Sj, kjer je verjetnost, da je Si izbrana, enaka |Si| Ek |Sk |, in potem iz tako izbrane mnoz ice S j izberemo se njen nakljucni element xj. Ce uporabljamo cenilko t Š Jli>| za |S|, kako veliko mora biti t, da je cenilka (e, 5)-aproksimacija za |S|. 3 Vzporedni algoritmi 3.1. Podana je tabela A[1.. .n], ki vsebuje n celih stevil. Konstruiraj tabelo S[1.. .n], kjer je S [i] vsota prvih i elementov tabele A[]. Torej, S [i] = A[1] + A[2] + ■ ■ ■ + A[i]. Opi s i vzporedni algoritem v modelu EREW, ki resuje ta problem v casu O(log n) in potrebuje O(n/ log n) procesorjev. 3.2. Podana je tabela A[1.. .n], ki vsebuje n elementov. Podana je tudi tabela L[1.. .n], kjer je L [i] G {1,2,..., k} oznaka elementa A[i]. Predpostavimo, da je k vnaprej izbrana konstanta, denimo k = 196. Konstruiraj tabelo B[1... n], ki vsebuje elemente iz A[1... n] urejene po oznakah: elementi z oznako '1' na zacetku, nato elementi z oznako '2', vse do elementov z oznako 'k'. Opi s i vzporedni algoritem v modelu EREW, ki re s uje ta problem v casu O(log n) in potrebuje O(n/ log n) procesorjev. 3.3. Podana je tabela A[1... n], ki vsebuje n elementov, in urejena tabela J[0... s], ki zadosca J [i] < J [i + 1] za vsak i. Naj velja tudi J [0] = 1 in J [s] = n. Konstruiraj tabelo B[1.. .n], ki za vsak i in i, ki ustrezata J [i — 1] < i < J [i] in 2 < i < n, zadosc a B[i] = A[J[i]]. Na primer, ce je vhod A = [1,2,3,4, 5,6, 7,8] in J = [1,3, 5,8], potem mora biti izhod B = [3, 3, 3, 5, 5, 8, 8, 8]. Opi s i vzporedni algoritem v modelu EREW, ki re s uje ta problem v c asu O(log n) in potrebuje O(n/ log n) procesorjev. 3.4. Podana je tabela A[1.. .n], ki vsebuje n celih stevil, in tabela B[1.. .n], pri cemer je vsak B[i] G {T, ±}. Naj velja tudi B[1] = T. Konstruiraj tabelo a[1 ... n], pri cemer je a[i] vsota elementov A[] na levo od polozaja i do vkljucno prvega polozaja j, ki zadosca B[j] = T. Kot primer, ce je A = [1, 2, 3, 4, 5, 6, 7] in B = [T, T, T, T], potem mora biti izhod a = [1,3,3,4,9,15, 7]. Opisi vzporedni algoritem v modelu EREW, ki re s uje ta problem v c asu O(log n) in potrebuje O(n/ log n) procesorjev. 3.5. Podana je tabela A[1.. .n], ki vsebuje n razlicnih tock v ravnini. Stirikotnik S je podan kot tabela oglisc S[1...4]. Konstruiraj tabelo B[1 ...n], ki na zacetku vsebuje toc ke iz A, ki so znotraj stirikotnika S. Opis i vzporedni algoritem, ki res uje ta problem v casu O(logn) in potrebuje O(n) operacij. Kaksen PRAM model racunanja uporabljas? 3.6. Dano je celo stevilo x. Konstruiraj tabelo potenc celega stevila x, B[1.. .n], B[i] = xi. Opisi vzporedni algoritem, ki res uje ta problem v casu O(logn) in potrebuje O(n) operacij. Kaksen PRAM model racunanja uporablja s ? 3.7. Imamo cikel C na vozlisc ih v0, v1,..., vn-1 s povezavami vi-1vi mod n za vsak i. Dana je tudi tabela E [1... s], kjer je vsak E [j] dodatna povezava. Pri tem velja, da je vsaka tocka vi kraji sce najvec ene dodatne povezave iz E[]. Cikel C nari semo v ravnini brez preseci s c. Zanima nas, ali lahko narisemo tudi vse povezave iz E[ ] znotraj C brez presec i s c. Opi si vzporedni algoritem, ki re suje tak problem v c asu O(log n) in potrebuje O(n) operacij. Kaksen PRAM model racunanja uporabljas? 3.8. Podana je tabela A[1 ...n] celih stevil in tabela Z[1 ...n] pozitivnih celih stevil, pri cemer velja Z [i] < i. Izracunaj tabelo M [1.. .n], kjer je M [i] maksimalno stevilo v podtabeli A[Z [i]... i], M [i] = maxj=Zjij A[j ]. (Crka Z pomeni 'zacetek'.) Opi s i algoritem, ki resuje ta problem v O(log n) casu in potrebuje O(n) procesorjev. 3.9. Opi s i algoritem, ki v c asu O(logn) izracuna produkt AB, kjer sta A in B n x n matriki. Kaksen PRAM model racunanja uporabljas? 3.10. Podana je tabela A[1... n], pri čemer je A[i] £ {0,1} za vsak i. Opi s i algoritem v modelu CRCW, ki v času O(1) najde prvi indeks k, ki zadosča A[k] = 1. Stevilo operačij algoritma naj bo linearno. Namig: deli in vladaj na ^[n podproblemov. 3.11. Podana je tabela A[1 ...n] čelih stevil. Zanima nas vrednost maxiA[i]. Opi s i algoritem, ki ta problem resuje v času O(1) z uporabo n1'01 pročesorjev. Kaksen PRAM model računanja uporabljas ? 3.12. Podana je tabela A[1.. .n] čelih stevil. Opi s i algoritem, ki v času O(1) odloči, ali je maksimalni element ponovljen. 3.13. Podana je tabela A[1 ...n]. Opisi algoritem v modelu CRCW, ki z uporabo polinomskega stevila pročesorjev v konstantem času odloči, ali je vsak element iz tabele A v njej zapisan natanko dvakrat. Na primer, za vhod A[c, a, b, c, b, a] mora biti odgovor 'DA', za vhoda A[a, a, a, a, b, b] ali A[a, b, c, a, b] mora biti odgovor 'NE'. 3.14. Podana je tabela A[1... n] čelih stevil. (a) Opi s i algoritem v modelu EREW, ki z uporabo polinomskega stevila pročesorjev v času O(log n) odloči, ali so vsi elementi iz tabele A enaki. (b) Opi s i algoritem v modelu EREW, ki z uporabo polinomskega stevila pročesorjev v času O(log n) odloči, ali ima vsak element iz tabele A isto stevilo ponovitev v A. Na primer, za vhoda A[3,1, 2,3,2,1] ali A[1,1,1,2,2,3,3,2,3] mora biti odgovor 'DA' in za vhoda A[1,1,1,1, 2,2] ali A[1,2, 3,1, 2] mora biti odgovor 'NE'. 3.15. Podani sta urejeni tabeli A[1 ...n] in B[1 ...n] različnih čelih stevil: A[1] < A[2] < ••• < A[n] in B[1] < B[2] < ••• < B[n]. Zanima nas konstrukčija urejene tabele C[1... 2n], ki vsebuje vse elemente iz A in B. (a) Opisi algoritem v modelu CRCW, ki ta problem resi v času O(1). (b) Opi s i algoritem v modelu CREW, ki ta problem re s i v č asu O(logn). (č) Opisi algoritem v modelu EREW, ki ta problem resi v času O(log2n). (d) Pokaz i, da je problem urejanja različnih čelih stevil v razredu NC. (e) Ce imata A in B lahko ponovljene elemente, kaj moramo spremeniti algoritmu, ki resi nalogo (a)? 3.16. Podana je urejena tabela A[1.. .n] različnih čelih stevil, A[1] < A[2] < ■ ■ ■ < A[n]. Podano je tudi čelo stevilo x, ki zadosča x < A[n]. Zanima nas rank(x : A) = max{i £ {1,... ,n} | A[i] < x}. Opis i algoritem v modelu CRCW, ki re s uje tak problem v času O(log n/ log p), kjer je p stevilo pročerjev. 3.17. Uporabimo model CRCW. Vhod je tabela A[1 ...n] različnih čelih stevil. Konstruiraj tabelo B[1... n], kjer je B[i] maksimalni indeks elementa iz A[1... i], ki je večje kot A[i]. Ce A[i] je največji element v A[1.. .i], potem naj bo B[i] = 0. Na primer, za vhod A = [3, 7, 5,2, 4, 8,1] mora biti izhod B = [0,0,2,3,3,0,6]. (a) Zapi s i psevdokodo algoritma, ki res uje ta problem v konstantem času in potrebuje polinomsko stevilo pročesorjev. (b) Opisi algoritem, ki resuje ta problem v c asu O(log n) in potrebuje linearno stevilo procesorjev. 3.18. Drevo s korenom opisemo s tabelo P[1...n]. Pri tem za koren r velja P[r] = r, sicer pa P [i] oznacuje oceta elementa i. Opisi algoritem, ki izracuna 2-barvanje drevesa v casu O (log n). 3.19. Drevo s korenom opisemo s tabelo P [1.. .n]. Pri tem za koren r velja P [r] = r, sicer pa P [i] oznac uje oceta elementa i. Opi s i algoritem, ki izracuna v casu O (log n) stevilo listov drevesa. (Ali je lahko koren drevesa list?) 3.20. Podana je tabela A[1... n], ki vsebuje cela stevila med 1 in k, pri cemer je k vnaprej znana vrednost. Konstruiraj tabelo B [1 ...n] na tak nacin, da je B[1], B[2],... B[n] permutacija stevil {1,2,... n} in je A[B[i]] < A[B[i + 1]] za vsak i = 1, 2,..., n — 1. Na primer, ce je vhod k = 4 in A = [1, 2, 3, 4,1,1, 3, 3], potem je ustrezen izhod B = [1, 5, 6, 2, 3, 7, 8, 4]. (a) Opisi algoritem v modelu CRCW, ki vrne v c asu O(k log n) tabelo B[]. (b) Opi s i algoritem v modelu CRCW, ki vrne v casu O(log k log n) tabelo B[]. Naj bo T drevo s korenom r in n voz lisci. Drevo s korenom opi semo s tabelo P[1... n]. Pri tem za koren r velja P [r] = r, sicer pa P [i] oznacuje oceta elementa i. Poisci permutacijo a[1 ... n] elementov {1,2,... n}, ki zadosc a: a[1] = r poleg tega pa velja i < j, ce je a(i) oce vozlisca a(j). Na primer, ce je n = 6 in P = [4,1,4,4,1,3], potem je mozna re s itev a = [4,1, 3, 5, 2, 6]. (c) Opisi algoritem v modelu CRCW, ki v casu O(log2 n) vrne taksno permutacijo a. 3.21. Vozlisca drevesa s korenom T oznacimo s 1,2,... ,n. Drevo je podano s tabelo P [1.. .n], kjer je P [i] oce vozlisca i. Za koren r pa velja P [r] =NULL. Izracunati zelimo tabelo B[1.. .n][1.. .n], ki zadosca 1 ce je j na poti od i do korena; B[i][j] = n . 0 sicer. (a) Opisi algoritem s psevdokodo, ki resuje ta problem v casu O(log n) in potrebuje polinomsko stevilo procesorjev. (Namig: skakanje kazalcev za neko operacijo, ki jo lahko izracunamo v O(1) casu z uporabo polinomskega stevila procesorjev.) (b) Denimo, da je drevo T seznam. Opisi algoritem v modelu EREW, ki resuje ta problem v casu O(log n) z uporabo O(n2/ log n) procesorjev. 3.22. Vozli sca drevesa s korenom T oznacimo s 1, 2, . . . , n. Drevo je podano s tabelo P [1 ...n], kjer je P [i] oce vozlisc a i. Za koren r pa velja P [r] =NULL. Drevo T je posebnega tipa: vsako vozli sce, ki ni koren, ima najvec enega sina. Koren lahko ima vec sinov. Podana je tudi tabela w[1... n], kjer je w[i] tez a vozli sca i. (a) Opisi algoritem v modelu CRCW, ki v casu O(log n) izracuna stevilo sinov korena. (b) Opisi algoritem v modelu CRCW, ki v Casu O (log n) izraCuna za vsako vozlisCe i vrednost ^(i) = Y1 w(u). u G V (T) ni na nobeni poti od i do korena 3.23. Naj bosta A[1... n] in B[1... n] tabeli bitov, ki hranita n-bitov stevil a in b. (a) Opisi algoritem v modelu EREW, ki v C asu O(log n) odloCi, ali je a < b, a = b ali a > b. (b) Opisi algoritem v modelu CRCW, ki v Casu O(1) odloCi, ali je a < b, a = b ali a > b.