Algoritmuselm´elet z´ arthelyi dolgozat 2002. ´aprilis 8. 1. Egy n m´eret˝ u hash t´ abl´ aba line´aris aval sz´ urjuk be az a1 , a2 , . . . , ak , ak+1 elemeket. Az els˝ o k elem (2 ≤ pr´ob´ k < n) besz´ ur´asa sor´ an ¨ osszesen k2 u ¨ tk¨ oz´es t¨ ort´ent. Legrosszabb esetben h´ any u ¨ tk¨ oz´es lesz ak+1 besz´ ur´asakor? 2. Az 1, 1, 2, 2, 4, 7, 5, 2 sorozat egy a ´es b karakterekb˝ol ´all´ o sz´o Lempel-Ziw-Welch k´odol´ asa. A sz´ot´ar kezdetben az a → 1 ´es b → 2 bejegyz´eseket tartalmazza. Mi volt az eredeti sz´o? 3. A k1 , k2 , . . . , kn eg´eszekb˝ol AVL-f´ at ´ep´ıt¨ unk a szok´ asos algoritmussal. (Mindig besz´ urjuk a sorban k¨ovetz˝ ot ´es sz¨ uks´eg eset´en forgatunk.) Bizony´ıtsuk be, hogy legal´ abb O(log2 n) elem besz´ ur´asakor nincs sz¨ uks´eg forgat´ asra! 4. Egy n × n-es sakkt´ abla n´eh´ any mez˝ oj´en az ellenf´el egy husz´ arja (lova) ´all. Ha mi olyan mez˝ ore l´ep¨ unk, ahol az ellenf´el le tud u ¨ tni, akkor le is u ¨ t, de egy´ebk´ent az ellenf´el nem l´ep. Valamelyik mez˝ on viszont a mi husz´ arunk a´ll. Adjunk O(n2 ) l´ep´essz´ am´ u algoritmust, ami meghat´ arozza, hogy mely m´asik mez˝ okre tudunk (l´ol´ep´esek sorozat´ aval) eljutni a n´elk¨ ul, hogy az ellenf´el le¨ utne! 5. Adottak c1 , c2 , . . . , cn k¨ ul¨onb¨ oz˝o eg´esz sz´ amok. Ezeket szeretn´enk nagys´ ag szerint rendezni n¨ ovekv˝o, vagy cs¨okken˝ o sorrendbe u ´ gy, hogy a szok´ asos ¨ osszehasonl´ıt´as helyett, most a k¨ovetkez˝o k´erd´eseket lehet feltenni: H´ arom kiv´ alasztott elem k¨ oz¨ ul melyik a k¨ oz´eps˝ o? Bizony´ıtsuk be, hogy a leghat´ekonyabb algoritmus Θ(n log2 n) o¨sszehasonl´ıt´ast haszn´al! 6. Az A0 , A1 , . . . , An j´ at´ekosok tollaslabda bajnoks´agon vesznek r´eszt, amely sor´ an minden j´at´ekos minden m´asik j´at´ekossal k-szor j´ atszik. Minden m´erk˝oz´esen a gy˝ oztes 1, a vesztes 0 pontot kap (d¨ ontetlen nincs). A bajnoks´ag gy˝ oztese, aki a v´eg´en a legt¨obb pontot gy˝ ujt¨ otte. Most ´eppen a bajnoks´ag k¨ozep´en j´arunk, j´o n´eh´ any meccset lej´atszottak m´ar (nem felt´etlen¨ ul eg´esz fordul´okat), ezek eredm´eny´et ismerj¨ uk, de m´eg sok m´erk˝oz´es h´ atra van. Adjunk olyan O(n6 ) l´ep´essz´ am´ u algoritmust, ami eld¨ onti, hogy A0 megnyerheti-e m´eg a bajnoks´ agot (nem holtversenyben, hanem egyed¨ ul)!
Algoritmuselm´elet vizsga z´ arthelyi dolgozat 2002. m´ajus 28. 1. Add meg Kruskal m´odszer´et minim´ alis ¨ osszs´ uly´ u fesz´ıt˝ofa keres´es´ere! Mennyi a fut´ asideje? (Bizony´ıtani nem kell a m´odszer helyess´eg´et.) 2. Bizony´ıtsuk be, hogy R = coR! (R a rekurz´ıv nyelvek oszt´alya, coR pedig ennek komplementer nyelvzt´ alya.) 3. K´esz´ıts AVL-f´ at a 6, 2, 3, 5, 7, 9, 4 sz´ amokb´ ol a tanult m´odszerrel. Minden besz´ ur´as ut´ an add meg a keletkez˝o AVL-f´ at! 4. Adj O(n4 ) fut´ asi idej˝ u algoritmust, amely egy adott n pont´ u ir´ any´ıtatlan, nemnegat´ıv ´els´ ulyokkal ell´ atott gr´afban megtal´alja a legr¨ ovidebb ¨ osszhossz´ us´ag´ u k¨ort (ami egy ponton nem mehet ´at k´etszer). 5. Adj O(nk−1 log n) ¨ osszehasonl´ıt´ ast haszn´al´ o algorimust, ami eld¨ onti, hogy az adott k¨ ul¨onb¨ oz˝o x1 , x2 , . . . , xn racion´ alis sz´amok k¨oz¨ ul kiv´ alaszthat´o-e pontosan k darab u ´ gy, hogy az ¨osszeg¨ uk ´eppen S legyen! 6. Bizony´ıtsd be, hogy az X4C nyelv NP-teljes! X4C (Pontos fed´es n´egyesekkel) defin´ıci´ oja: adott egy U v´eges halmaz, ´es U n´egyelem˝ u r´eszhalmazainak egy F = {X1 , X2 , . . . , Xk } csal´ adja. Eld¨ ontend˝ o, hogy az F-b˝ol kiv´ alaszthat´ok-e p´ aronk´ent diszjunkt halmazok, melyek egy¨ uttesen lefedik U -t. Jel¨ olje X4C azokat az (U, F) p´ arokat, melyekre az F-b˝ol kiv´ alaszthat´o U ilyen ´ertelemben vett pontos fed´ese.
Algoritmuselm´elet vizsga z´ arthelyi dolgozat 2002. j´ unius 11. 1. Ismertesd a kupac adatszerkezetet ´es a kupacba val´o besz´ ur´as algoritmus´at. Ut´obbinak mennyi a maxim´ alis l´ep´essz´ama? (Itt semmit nem kell bizony´ıtani.)
1
2. Bizony´ıtsd be, hogy ha L1 ≺ L2 ´es L2 ∈ P, akkor L1 ∈ P. 3. Egy bin´aris fa inorder bej´ ar´ asa: j, b, k, g, i, a, c, d, f, e, h preorder bej´ ar´asa: a, b, j, g, k, i, d, c, e, f, h. Rekonstru´ ald a f´ at! 4. Adott 2n k¨ ul¨onb¨ oz˝o racion´ alis sz´ am. Adj O(n log n) ¨osszehasonl´ıt´ast haszn´al´o algoritmust, ami (x1 , y1 ), (x2 , y2 ), . . . , (xn , yn ) p´ arokba sorolja a sz´ amokat u ´ gy, hogy max (xi + yi ) 1≤i≤n
a lehet˝o legkisebb legyen! 5. Adott egy n pont´ u e ´el˝ u egyszer˝ u, ¨ osszef¨ ugg˝o gr´af, valamint egy k ≥ 2 eg´esz sz´am. Olyan fesz´ıtett r´eszgr´ afot keres¨ unk G-ben, melyben minden pontj´ anak foka legal´ abb k. Adj O(n2 ) fut´ asidej˝ u algoritmust, ami megadja G-ben a legt¨obb pontot tartalmaz´ o ilyen fesz´ıtett r´eszgr´ afot, ha van ilyen, illetve, megmondja, hogy ha nincs ilyen. 6. Legyen az N E nyelv a k¨ovetkez˝o: N E = {(x, y) | x, y Turing g´epek k´odjai, L(Mx ) 6= L(My )} , ahol L(Mz ) az z sz´ oval le´ırt Turing g´ep ´ altal felismert nyelvet jel¨oli. Bizony´ıtsd be, hogy N E nem rekurz´ıve felsorolhat´ o nyelv.
Algoritmuselm´elet vizsga z´ arthelyi dolgozat 2002. j´ unius 25.
1. Defini´ald az AVL-fa fogalm´ at! Mennyi egy n elemet tartalmaz´ o AV L-f´ aban egy keres´es id˝oig´enye legrosszabb esetben? (Itt semmit nem kell bizony´ıtani.) 2. Bizony´ıtsd be, hogy az Lh meg´ all´ asi probl´ema nyelve nem rekurz´ıv! (Felhaszn´alhat´o, hogy az Lu univerz´ alis nyelv nem rekurz´ıv.) 3. Nyitott c´ımz´essel hashelt¨ unk egy 11 elem˝ u t´ abl´ aba a h(k) = k (mod 11) hash-f¨ uggv´eny ´es kvadratikus marad´ek pr´oba seg´ıts´eg´evel. A k¨ovetkez˝o kulcsok ´erkeztek (a megadott sorrendben): 6, 5, 7, 17, 16, 3, 2, 14. Add meg a t´ abla v´egs˝ o ´allapot´at! 4. Adott egy n pont´ u e ´el˝ u egyszer˝ u, ¨ osszef¨ ugg˝o, ir´ any´ıtatlan gr´af. Adj O(n + e) fut´ asidej˝ u algoritmust, ami megtal´al egy olyan pontot, ami nem artikul´ aci´ os pont! (Egy pont artikul´ aci´ os pont, ha elhagy´as´aval a gr´af t¨ obb komponensre esik sz´et.) 5. Adott egy n × n-es m´atrix. Adj O(n2 log n) ¨ osszehasonl´ıt´ast haszn´al´o algoritmust, amely eld¨ onti, van-e k´et olyan sor, amelyeknek az els˝ o oszlopbeli elemei k¨ ul¨onb¨ oznek, viszont az ¨osszes t¨ obbi oszlopban megegyeznek! 6. Defini´ aljuk a H2C probl´em´ at: Adott egy U v´eges halmaz, ´es U r´eszhalmazainak egy F = {X1 , X2 , . . . , Xk } csal´adja. Eld¨ ontend˝ o, hogy kisz´ınezhet˝ ok-e U pontjai 2 sz´ınnel u ´ gy, hogy minden Xi halmazban szerepeljen mindk´et sz´ın. (Minden pont csak egy sz´ınt kaphat.) Jel¨ olje H2C azokat az (U, F) p´ arokat, melyekre van ilyen sz´ınez´es. Bizony´ıtsd be, hogy H2C NP-teljes.
Algoritmusok elm´elet z´ arthelyi 2003. m´arcius 31.
2
1. Egy ir´ any´ıtott gr´ af cs´ ucshalmaza {a, b, c, d, e, f }, az ´elek ´es s´ ulyaik pedig az al´abbiak: s(a, b) = 5, s(a, e) = 6, s(b, c) = 4, s(b, d) = 6, s(c, a) = 3, s(c, d) = 1, s(d, e) = 2, s(e, c) = 2, s(e, f ) = 1, s(f, b) = 3, s(f, c) = 1, s(f, d) = 1. a) Dijkstra m´odszer´evel hat´ arozza meg a-b´ol az ¨osszes t¨ obbi cs´ ucsba vezet˝ o legr¨ovidebb u ´ t hossz´ at. (Indokolni ´ nem kell, de l´ atsz´odjon, l´ep´esenk´ent hogyan v´altozik a t´ avols´ agokat t´ arol´o D t¨ omb ´es a KESZ halmaz.) b) Egy ´el s´ uly´ at 1-gyel cs¨ okkentj¨ uk. Mely ´elek eset´eben nem v´altoznak meg ezzel az a-t´ol m´ert t´ avols´ agok? 2. Egy 2-3 f´aba egym´ as ut´ an 1000 u ´ j elemet illesztett¨ unk be. Mutassa meg, hogy ha ennek sor´ an egyszer sem kellett cs´ ucsot sz´etv´ agni, akkor a beilleszt´esek sorozata el˝ott m´ar legal´ abb 2000 elemet t´ aroltunk a f´aban. 3. Egy n cs´ ucs´ u ir´ any´ıtott gr´ af m´elys´egi bej´ ar´asa sor´ an azt tapasztaltuk, hogy minden cs´ ucsra a befejez´esi ´es a m´elys´egi sz´am k¨ ul¨onbs´ege kisebb mint n/4. Igazoljuk, hogy a gr´af er˝osen ¨osszef¨ ugg˝o komponenseinek sz´ama legal´ abb 4. 4. Tervezzen adatstrukt´ ur´at a k¨ovetkez˝o felt´etelekkel. Term´eszetes sz´amokat kell t´ arolni, egy sz´am t¨ obbsz¨or is szerepelhet. A sz¨ uks´eges m˝ uveletek: ´ BESZUR(i): i egy u ´ jabb p´eld´ any´at t´ aroljuk ¨ ¨ TOROL(i): i egy p´eld´ any´at t¨ or¨ olj¨ uk ¨ OL(i): ¨ MINDTOR i¨ osszes p´eld´ any´at t¨ or¨ olj¨ uk DARAB(i): visszaadja, hogy h´ any p´eld´ any van i-b˝ol ELEM(K): megmondja, a nagys´ ag szerinti rendez´esben a K-adik elem ´ert´ek´et. Az adatstrukt´ ura legyen olyan, hogy ha m-f´ele elemet t´ arolunk, akkor mindegyik m˝ uvelet l´ep´esig´enye O(log m). (P´eld´ aul ha a t´ arolt elemek 1,1,3,3,3,8, akkor DARAB(1)=2, ELEM(4)=3 ´es m =3.) 5. Egy n hossz´ u 0-1 sorozatot olyan, legal´ abb 4 hossz´ u darabokra kell sz´etv´ agni, hogy minden keletkezett r´eszben az els˝ o k´et bit megegyezzen az utols´ o k´et bittel. Adjon O(n2 ) l´ep´essz´am´ u algoritmust, amely eld¨ onti, hogy van-e ilyen sz´etv´ ag´as. 6. A G(V, E) ir´ any´ıtott gr´ af minden ´ele az 1, 2, . . . , k sz´amok valamelyik´evel van s´ ulyozva. Egy u ´ t ´ert´eke legyen az u ´ ton tal´ alhat´ o ´elek s´ ulyainak maximuma. Hat´ arozza meg, hogy ha adott k´et cs´ ucs x, y ∈ V , akkor mennyi a lehet˝o legkisebb ´ert´ek˝ u x-b˝ol y-ba vezet˝ ou ´ t ´ert´eke. Ha G ´ellist´ aval adott ´es e ´ele van, akkor a l´ep´essz´am legyen O(e log k).
Algoritmusok elm´elete vizsgaz´ arthelyi 2003. m´ajus 30. ¨ algoritmus´at ´es 1. Ismertesse a kupac adatszerkezetet (a hozz´ a tartoz´ o m˝ uveletekkel egy¨ utt). ´Irja le a MINTOR adja meg a l´ep´essz´ am´ at. (Bizony´ıtani nem kell.) 2. Defini´alja az Ld diagon´ alis nyelvet ´es mutassa meg, hogy Ld nem rekurz´ıve felsorolhat´ o. 3. Igazolja, hogy ha coNP 6= NP, akkor MAXKLIKK 6∈ P. ´ 4. Ellist´ aval adott egy G gr´ af, melynek n cs´ ucsa ´es e ´ele van. A gr´af minden cs´ ucs´ ahoz hozz´ a van rendelve egy 1 ´es k k¨oz¨otti eg´esz sz´ am (c´ımke). Tal´ aljunk (ha l´etezik) olyan tarka utat a gr´afban, amelyben minden 1 ≤ i ≤ k c´ımke pontosan egyszer fordul el˝ o. Az algoritmus l´ep´essz´ama legyen O(k! (e + n)). ´ szeretn´enk u 5. Van egy null´ akkal ´es egyesekkel kit¨olt¨ ott n sorb´ol ´es n oszlopb´ol ´all´ o m´atrixunk. At ´ gy rendezni, hogy a f˝oa´tl´ oban csupa egyes ´ alljon (a t¨ obbi helyre nincs megk¨ ot´es). Az ´atrendez´es k´etf´ele l´ep´est haszn´alhat: vagy k´et sort cser´el meg vagy k´et oszlopot. Adjon polinom idej˝ u algoritmust, ami eld¨ onti, hogy megval´os´ıthat´o-e a k´ıv´ ant ´atrendez´es. 6. Adott ¨osszesen 2n k¨ ul¨onb¨ oz˝o sz´ am k´et n elem˝ u halmazban, A = {a1 , . . . , an } ´es B = {b1 , . . . , bn }. Azt szeretn´enk eld¨ onteni minim´ alis sz´ am´ u¨ osszehasonl´ıt´ assal, hogy a 2n sz´am k¨oz¨ ul a legnagyobb az A vagy a B halmazban van-e. (Azaz nem kell felt´etlen¨ ul meghat´ arozni, melyik elem a legnagyobb, csak azt, hogy melyik halmazba tartozik.) Mutassa meg, hogy ehhez a feladathoz is legal´ abb annyi ¨osszehasonl´ıt´as kell, amennyi 2n elem k¨oz¨ ul a maxim´ alis meghat´ aroz´as´ ahoz sz¨ uks´eges.
3
Algoritmusok elm´elete vizsgaz´ arthelyi 2003. j´ unius.6. 1. Ismertesse Dijkstra legr¨ ovidebb utakat keres˝o algoritmus´at arra az esetre, amikor a gr´af a m´atrix´aval adott. Mennyi az algoritmus l´ep´essz´ ama? (Az algoritmus helyess´eg´et nem kell igazolni, de a l´ep´essz´amot r¨ oviden indokolja.) 2. ´Irja le a Karp-redukci´ o defin´ıci´ oj´ at ´es adja meg a 3SZ´IN ≺ MAXFTL Karp-redukci´ot (indokl´ as nem kell). 3. Igaz-e, hogy minden L1 rekurz´ıve felsorolhat´ o ´es minden L2 ∈ P nyelv eset´en teljes¨ ul, hogy (a) L1 ∩ L2 rekurz´ıve felsorolhat´ o? (b) L1 ∩ L2 rekurz´ıv? (c) L1 ∩ L2 ∈ P ? 4. A b0 ...bn alak´ u n + 1 hossz´ u bitsorozatokat akarjuk t´ arolni. Tudjuk, hogy a b0 parit´ asbit, ami a sorozatban az egyesek sz´am´ at p´ arosra eg´esz´ıti ki. Ha nyitott c´ımz´es˝ u hash-el´est haszn´alunk h(x) ≡ x (mod M ) hashf¨ uggv´ennyel ´es line´aris pr´ob´ aval, akkor M = 2n vagy M = 2n + 1 m´eret˝ u hash-t´ abla eset´en lesz kevesebb u ¨ tk¨ oz´es? 5. M´ atrix´aval adott egy G(V, E) ir´ any´ıtott gr´ af, melynek minden ´el´ehez egy pozit´ıv s´ uly tartozik. A gr´af minden cs´ ucsa vagy egy rakt´ arat vagy egy boltot jelk´epez, az ´els´ ulyok a megfelel˝ o t´ avols´ agokat jelentik. Olyan G′ r´eszgr´ afj´ at keress¨ uk G-nek, amely minden cs´ ucsot tartalmaz, ´es amelyben minden bolthoz van legal´ abb egy rakt´ ar, ahonnan oda tudunk sz´ all´ıtani (azaz van k¨ozt¨ uk u ´ t a gr´afban). Adjon O(n2 ) l´ep´essz´am´ u algoritmust egy a felt´eteleknek megfelel˝ o minim´ alis ¨ osszs´ uly´ u G′ r´eszgr´ af megkeres´es´ere. 6. A l´ adapakol´as feladatban tudjuk hogy az ´erkez˝o t´ argyak m´erete kisebb mint 1/k, ahol k ≥ 3 eg´esz sz´am. Adjon k OPT + 1 darab l´ ad´ at haszn´al, amikor a legjobb pakol´as OPT polinom idej˝ u algoritmust, ami legfeljebb k−1 darab l´ ad´ at ig´enyel.
Algoritmusok elm´elete vizsgaz´ arthelyi 2003. j´ unius 13. 1. Ismertesse az AVL-fa adatszerkezetet (a hozz´ atartoz´o m˝ uveletekkel egy¨ utt). Mekkora egy AVL-fa m´elys´ege, mennyi az egyes m˝ uveletek l´ep´essz´ ama? (Bizony´ıtani nem kell) 2. Defini´alja a rekurz´ıve felsorolhat´ o ´es a rekurz´ıv nyelvek oszt´aly´at. Adjon meg olyan nyelvet, ami (a) mindkett˝ obe beletartozik (b) csak az egyikbe tartozik (melyikbe?) (c) egyikbe sem tartozik. (Bizony´ıtani nem kell.) 3. Legyen L ⊆ I ∗ egy NP-teljes nyelv ´es jel¨ olje L = I ∗ − L az L nyelv komplementer´et. Mutassa meg, hogy minden ′ ′ L ∈ co N P nyelvhez l´etezik L ≺ L Karp-redukci´o. 4. Valaki a k¨ovetkez˝o elj´ ar´ ast javasolta minim´alis fesz´ıt˝ofa keres´es´ere. A G gr´af ´eleit tetsz˝ oleges sorrendben megsz´ amozzuk, legyen ez e1 , e2 , . . . , em . Kezdetben T = ∅. Az i. l´ep´esben (i = 1, 2, . . . , m) a T halmazhoz vegy¨ uk hozz´ a az ei ´elet. Ha T -ben van k¨or, akkor hagyjuk el T -b˝ol a k¨or egyik legnagyobb s´ uly´ u ´el´et. Igaz-e, hogy ha a G ¨ osszef¨ ugg˝ o gr´ af, akkor az m-edik l´ep´es ut´ an a T -ben lev˝o ´elek G egy minim´alis fesz´ıt˝of´ aj´ at alkotj´ak? 5. P-beli vagy NP-teljes az al´ abbi L nyelv? L = {G(V, E) egyszer˝ u gr´ af, G cs´ ucsai kisz´ınezhet˝ ok |V | − 4 sz´ınnel}. 6. A G ir´ any´ıtott gr´ af cs´ ucshalmaza legyen V = {1, 2, . . . , n}. A gr´af egy olyan ´ellist´ aval adott, amiben az egyes cs´ ucsokhoz tartoz´ o ´elek tetsz˝ oleges sorrendben lehetnek. Line´ aris id˝oben k´esz´ıts¨ uk el ebb˝ol azt az ´ellist´ aj´ at Gnek, amiben minden cs´ ucs list´ aja rendezett (teh´ at az adott cs´ ucsb´ ol ´ellel el´erhet˝o pontok n¨ ovekv˝o sorrendben k¨ovetik egym´ ast).
4
Algoritmusok elm´elete vizsgaz´ arthelyi 2003. j´ unius 20. 1. ´Irja le az ¨osszef´es¨ ul´es ´es az ¨ osszef´es¨ ul´eses rendez´es elj´ar´as´at. Mennyi az elj´ar´asokban haszn´alt ¨osszehasonl´ıt´asok sz´ama? (Indokolni is kell.) 2. Defini´alja az Lu univerz´ alis ´es az Lh meg´ all´ asi nyelvet ´es adja meg, hogy melyik milyen nyelvoszt´alyba tartozik (bizony´ıt´as nem kell). 3. Rekurz´ıv-e az L1 ∩ L2 nyelv, ha L1 ∈ T IM E(n) ´es L2 ∈ SP ACE(2n )?
¨ 4. Egy kupacban defini´ alhatjuk a FOGYASZT ´es NOVEL m˝ uveleteket, melyek k¨oz¨ ul az els˝ o az adott helyen lev˝o kulcsot kisebbre, a m´asodik pedig nagyobbra cser´eli ´es a v´altoztat´ as ut´ an mindkett˝ o helyre´all´ıtja a kupactulajdons´ agot. (a) Adjon O(log n) l´ep´essz´ am´ u algoritmust mindk´et m˝ uveletre. (A v´altoztatand´ o kulcs hely´et tudjuk, nem kell a kupacban keresni.) ¨ (b) M´ odos´ıtsa az elj´ ar´ asokat bin´ a√ ris kupacr´ ol d-kupacra. Jel¨ olje f (n) a FOGYASZT ´es g(n) a NOVEL l´ep´essz´am´ at n elem˝ u d-kupac eset´en, ha d = n. Igaz-e, hogy g(n) = O(f (n))? 5. P-beli vagy NP-teljes az al´ abbi L nyelv? L = {G gr´af : cs´ ucsai 3 sz´ınnel kisz´ınezhet˝ ok u ´ gy, hogy mindh´arom sz´ınoszt´ alyba ugyanannyi cs´ ucs tartozzon }. 6. Ny´ ari utaz´ asunkra valut´ at akarunk v´altani. A p´enzv´alt´ o n k¨ ul¨onb¨ oz˝o valut´ aval foglalkozik, a j. fajta 1 egys´eg´e´ert rij -t kell fizetni az i. p´enznemben. (Pl. ha a j. a doll´ar, az i. a forint, akkor most rij = 222 lehet.) Az rij t¨ omb felhaszn´al´as´aval adjon O(n3 ) l´ep´eses algoritmust, amely minden valutap´ arra meghat´ arozza, hogy mi az el´erhet˝o legjobb ´atv´ alt´ asi ar´ any, ha feltessz¨ uk, hogy az ´atv´ alt´ asok´ert nem sz´amolnak fel k¨ ul¨on k¨olts´eget. (Az i-r˝ ol a j-re val´o ´atv´ alt´ as t¨ ort´enhet t¨ obb l´epcs˝ oben is, ´erdemes lehet el˝obb i-r˝ ol k1 -re konvert´ alni, onnan k2 -re, stb ´es v´eg¨ ul j-re.)
Algoritmuselm´elet z´ arthelyi 2004. m´arcius 29. 1. Egy ir´ any´ıtott gr´ af cs´ ucshalmaza {a, b, c, d, e, f }, az ´elek ´es s´ ulyaik pedig a k¨ovetkez˝oek: s(a, b) = 6, s(a, c) = 5, s(a, e) = 8, s(b, a) = 5, s(b, e) = 1, s(b, f ) = 2, s(c, b) = 2, s(c, f ) = 4, s(e, b) = 6, s(e, d) = 3, s(f, d) = 1, s(f, e) = 1. a) Dijkstra-algoritmussal hat´ arozza meg a-b´ol az ¨osszes t¨ obbi pontba vezet˝ o legr¨ovidebb u ´ t hossz´ at. (Indokolni ´ nem kell, de l´ep´esenk´ent ´ırja fel a t´ avols´ agokat tartalmaz´ o D t¨ omb ´es a KESZ halmaz ´allapot´at.) b) Vegy¨ uk hozz´ a a gr´ afhoz az (b, d) ´elet. Milyen s(b, d) ≥ 0 s´ ulyok eset´en v´altozn´ anak meg ezzel a legr¨ovidebb utak hosszai? 2. Az A[1 . . . n] t¨ ombben eg´esz sz´ amokat t´ arolunk, ugyanaz a sz´am t¨ obbsz¨or is szerepelhet. Hat´ arozzuk meg O(n log n) l´ep´esben az ¨ osszes olyan sz´ amot, amelyik egyn´el t¨ obbsz¨or fordul el˝o a t¨ ombben. 3. Egy bin´aris keres˝ of´ aban csupa k¨ ul¨onb¨ oz˝o eg´esz sz´amot t´ arolunk. Lehets´eges-e, hogy egy KERES(x) h´ıv´ as sor´ an a keres´esi u ´ t ment´en a 20, 18, 3, 15, 5, 8, 9 kulcsokat l´ atjuk ebben a sorrendben? Ha nem lehets´eges, indokolja meg mi´ert nem, ha pedig lehets´eges, hat´ arozza meg az ¨osszes olyan x eg´esz sz´amot, amire ez megt¨ort´enhet. 4. Egy szigeten ny´ıl´ o pizzasz´ all´ıt´ o c´eg triatlont kedvel˝o f˝on¨ oke kik¨ oti, hogy minden h´ azhozsz´all´ıt´asn´ al az u ´ t els˝ o r´esz´et u ´ szva kell megtenni, a k¨ovetkez˝ot biciklivel, majd a v´eg´et futva. Azt az´ert megengedi, hogy egy vagy ak´ ar t¨ obb szakasz is kimaradjon (pl. u ´ sz´ as ut´ an r¨ ogt¨ on fut´ as k¨ovetkezzen, vagy az eg´esz u ´ t egyf´ele legyen, p´eld´ aul csak bicikliz´esb˝ ol ´alljon), de a k¨ozleked´esi m´odok sorrendj´et nem szabad felcser´elni. (A f˝on¨ ok arr´ ol gondoskodik, hogy ahol lehet biciklizni, ott legyen is mivel.) A v´arost egy G(V, E) ir´ any´ıtatlan gr´af ´ırja le, a gr´af p cs´ ucsa jel¨oli a pizz´ az´ot. A gr´af ´ellist´ aj´ aval van megadva, az ´ellist´ aban minden ´eln´el szerepel, hogy ott mely k¨ozleked´esi form´ak megengedettek, egyszerre ak´ ar t¨ obb is. Adjon O(|V | + |E|) l´ep´essz´am´ u algoritmust annak meghat´ aroz´as´ara, hogy a pizz´ az´ob´ ol a v´aros mely pontjaira tud a c´eg a szab´ alyok betart´ as´aval sz´all´ıtani. 5. Egy kezdetben u ¨ res 2-3-f´ aba az 1, 2, . . . , n sz´amokat sz´ urtuk be ebben a sorrendben. Bizony´ıtsa be, hogy a keletkezett f´aban a harmadfok´ u cs´ ucsok sz´ ama O(log n). 6. A m´atrix´aval adott ir´ any´ıtatlan G(V, E) gr´ af egy v´aros u ´ th´al´ozat´ at reprezent´ alja. A gr´af bizonyos cs´ ucsaiban parkol´o van, minden parkol´ ohoz adott az ottani parkol´as k¨olts´ege. Egy parkol´o a v´arosrendez´es szerint felesleges, ha a parkol´ot´ol legfeljebb k utc´ anyira (azaz legfeljebb k ´ellel el´erhet˝oen) van n´ ala olcs´obb parkol´o. Adjon O(k|V |2 ) idej˝ u algoritmust, ami eld¨ onti, hogy van-e felesleges parkol´o a v´arosban. 5
Algoritmusok elm´elete vizsgaz´ arthelyi 2004. m´ajus 27. 1. ´Irja le Prim algoritmus´at s magyar´ azza meg, hogy ez mi´ert speci´ alis esete a piros-k´ek algoritmusnak. Adja meg a Prim-algoritmus l´ep´essz´ am´ at ´ellist´ as, kupacos megval´os´ıt´as eset´en (bizony´ıtani nem kell). 2. (a) Defini´alja az Lu univerz´ alis nyelvet. (b) Bizony´ıtsa vagy c´ afolja, hogy Lu ∈ R. (c) Bizony´ıtsa vagy c´ afolja, hogy Lu ∈ RE. 3. Legyen L1 ∈ SPACE(n) ´es L2 ∈ TIME(n10 ). Igaz-e, hogy L1 ∪ L2 ∈ EXPTIME ? ¨ ˝ 4. AVL-f´ akban val´ os´ıtsa meg az al´ abbi KOVETKEZ O(x) elj´ar´ast. Az elj´ar´asnak a legkisebb olyan f´aban szerepl˝ o kulcsot kell megadnia, amely nagyobb mint x, felt´eve, hogy az x kulcs szerepel a f´aban. Ha az AVL-f´ anak n cs´ ucsa van, akkor az elj´ ar´ as l´ep´essz´ ama legyen O(log n). 5. Igazolja, hogy ha egy L nyelv NP-teljes ´es L ∈ NP ∩ co NP, akkor NP = co NP. 6. A m´atrix´aval adott G ir´ any´ıtott gr´ af ´elei k¨oz¨ott van egy negat´ıv s´ uly´ u ´el, a t¨ obbi ´el s´ ulya pozit´ıv. A gr´afban nincs negat´ıv s´ uly´ u k¨or. Adjon O(n2 ) l´ep´essz´am´ u algoritmust az s ∈ V (G) pontb´ ol az ¨osszes t¨ obbi pontba vezet˝ o legr¨ovidebb utak meghat´ aroz´as´ ara.
Algoritmusok elm´elete vizsgaz´ arthelyi 2004. j´ unius 3. 1. ´Irja le a nyitott c´ımz´es˝ u hashel´es m´odszer´et, a m˝ uveletek megval´os´ıt´as´at line´aris pr´oba ´es kvadratikus marad´ek pr´oba eset´en. (A j´ o hash-f¨ uggv´enyekre nem kell kit´erni.) 2. (a) Defini´alja a SPACE(f (n)) ´es TIME(g(n)) oszt´alyokat. (b) Igazolja vagy c´ afolja, hogy TIME(g(n)) = co TIME(g(n)) (c) Igazolja vagy c´ afolja, hogy SPACE(f (n)) = co SPACE(f (n)) 3. A 2k − 1 elem˝ u A t¨ omb elemei mind k¨ ul¨onb¨ oz˝oek ´es n¨ ovekv˝o sorrendben vannak. Minden elemet egy k hossz´ u bitsorozat ´ır le, teh´ at tekinthetj¨ uk u ´ gy, hogy a 0, 1, 2, . . . , 2k − 1 sz´amokat t´ aroljuk egy kiv´etel´evel. A feladat ennek a hi´anyz´ o sz´ amnak a megkeres´ese. Ehhez egy l´ep´esben valamelyik elem egy bitj´ere k´erdezhet¨ unk r´ a: a BIT(i, j) elj´ ar´ as az A[i] elem j-edik bitj´et mondja meg. Adjon olyan algoritmust, amely a BIT elj´ar´as O(k)-szori h´ıv´ as´ aval megtal´ alja a hi´anyz´ o sz´ amot (bitsorozatot). 4. P-beli vagy NP-teljes az al´ abbi nyelv: L = {(a1 , . . . , an ) : ai ∈ Z ´es a sz´amok h´ arom r´eszre oszthat´oak u ´ gy, hogy mindh´arom r´esz ¨ osszege ugyanannyi legyen } 5. Rekurz´ıv-e az al´ abbi L nyelv? L = {x#y : l´etezik az x k´od´ u Mx ´es az y k´od´ u My Turing-g´ep, L(Mx ) ∩ L(My ) = ∅} 6. Az ´ellist´ aval adott G egyszer˝ u ir´ any´ıtatlan gr´afr´ol el akarjuk d¨ onteni, hogy van-e olyan ´ele, amely G minden k¨or´eben benne van. Adjon olyan algoritmust, amely ezt O(n) l´ep´esben megoldja (ahol n a G gr´af cs´ ucsainak sz´am´ at jel¨oli).
Algoritmusok elm´elete vizsgaz´ arthelyi 2004. j´ unius 10. ´ MINTOR ¨ elj´ar´asok algoritmus´at. 1. Ismertesse a (bin´ aris) kupac adatszerkezetet ´es a BESZUR, Mennyi ezeknek az elj´ ar´ asoknak a l´ep´essz´ ama (bizony´ıtani nem kell)?
6
2. Defini´alja az Lh meg´ all´ asi nyelvet. Az EXPTIME, R, RE nyelvoszt´alyok k¨oz¨ ul az Lh nyelv melyikben van benne ´es melyikben nincs? Az egyes v´alaszokat indokolja is! 3. Legyen L = {x#n | C(x) ≤ n}, ahol x egy {0, 1} feletti sz´o, n egy bin´arisan ´abr´ azolt pozit´ıv eg´esz sz´am, C(x) pedig az x sz´o Kolmogorov-bonyolults´ag´at jel¨oli. Helyes-e a k¨ovetkez˝o ´ervel´es? ,, Mivel egy legfeljebb n hossz´ u y sz´ o tan´ us´ıtja, hogy C(x) ≤ n, ez´ert az L nyelv NP-ben van”. 4. Az n m´eret˝ u (nem felt´etlen¨ ul rendezett) A t¨ omb elemei k¨ ul¨onb¨ oz˝o pozit´ıv eg´esz sz´amok. Adjon algoritmust, amely meghat´ aroz egy 1 ≤ k ≤ n sz´ amot ´es kiv´ alaszt k k¨ ul¨onb¨ oz˝o elemet az A t¨ ombb˝ ol u ´ gy, hogy a kiv´ alasztott elemek ¨osszege nem t¨ obb mint k 3 . Ha nincs ilyen k, akkor az algoritmus jelezze ezt a t´enyt. Az algoritmus l´ep´essz´ama legyen O(n log n). (K´et sz´ am ¨ osszehasonl´ıt´asa, ¨osszead´asa vagy szorz´ asa egy l´ep´esnek sz´am´ıt.) ¨ pedig az olyan ir´ 5. Jel¨ olje H a Hamilton-k¨ orrel rendelkez˝o ir´ any´ıtatlan gr´afok nyelv´et, 2KOR any´ıtatlan gr´afok´et, melyeknek cs´ ucsai lefedhet˝ oek k´et darab, k¨oz¨os pontot nem tartalmaz´ o k¨orrel. Igazolja, hogy l´etezik ¨ Karp-redukci´ (a) H ≺ 2KOR o ¨ ≺ H Karp-redukci´ (b) 2KOR o. 6. A G(V, E) egyszer˝ u¨ osszef¨ ugg˝ o gr´ af minden f ´el´ehez egy s(f ) s´ ulyt rendelt¨ unk. Legyen F1 ´es F2 a G gr´af k´et k¨ ul¨onb¨ oz˝o, minim´ alis s´ uly´ u fesz´ıt˝ of´ aja. Jel¨ olje f1 az F1 fa egy tetsz˝ oleges ´el´et. Bizony´ıtsa be, hogy van az F2 f´anak olyan f2 ´ele, hogy s(f1 ) = s(f2 ).
Algoritmusok elm´elete vizsgaz´ arthelyi 2004. j´ unius 17. 1. ´Irja le a radix rendez´es algoritmus´at ´es igazolja az algoritmus helyess´eg´et. Mennyi az algoritmus l´ep´essz´ama? 2. (a) Defini´alja az R, co R, RE, co RE nyelvoszt´alyokat. (b) Igazolja, vagy c´ afolja, hogy R = RE ∩ co RE. 3. Igazolja, hogy ha az L1 ´es L2 nyelvekre fenn´all, hogy L1 ∈ NP ´es L2 ∈ NP, akkor L1 ∩ L2 ∈ NP. 4. P-beli vagy NP-teljes az olyan 4 sz´ınnel sz´ınezhet˝ o G gr´afokb´ol ´all´ o nyelv, hogy G cs´ ucsai kisz´ınezhet˝ oek a piros, k´ek, z¨ old, s´ arga sz´ınekkel u ´ gy is, hogy pontosan egy cs´ ucs legyen piros ´es pontosan k´et cs´ ucs k´ek? 5. A kezdetben u ¨ res kupacba egyenk´ent sz´ urunk be n elemet. Igazolja, hogy el˝ofordulhat, hogy a besz´ ur´asok sor´ an v´egzett ¨osszehasonl´ıt´ asok sz´ ama Ω(n log n). 6. Legyenek a1 , a2 , . . . , an tetsz˝ oleges eg´esz sz´ amok ´es m < n2 eg´esz. Adjon algoritmust, amely a bin´aris alakjukkal megadott a1 , a2 , . . . , an ´es m sz´ amokr´ol eld¨ onti polinom id˝oben, hogy az a1 , a2 , . . . , an sz´amok k¨oz¨ ul kiv´ alaszthat´o-e n´eh´ any u ´ gy, hogy az ¨ osszeg¨ uk m-mel osztva egyet adjon marad´ekul.
Algoritmuselm´elet z´ arthelyi 2005. ´aprilis 8. 1. Egy kezdetben u ¨ res AVL-f´ aba a tanult algoritmussal egyenk´ent sz´ urja be a 7,4,3,9,5,6,2,1,8 kulcsokat, majd t¨ or¨olje az 5-¨os kulcsot. (Minden l´ep´es eredm´eny´et rajzolja le!) 2. Egy m m´eret˝ u hash-t´ abl´ aban m´ar van n´eh´ any elem. Adjon O(m) l´ep´essz´am´ u algoritmust, amely meghat´ arozza, hogy egy u ´ jabb elem line´aris pr´ob´ aval t¨ ort´en˝ o besz´ ur´asakor maximum h´ any u ¨ tk¨ oz´es t¨ ort´enhet. 3. Az A[1 : n] t¨ ombben lev˝o elemekr˝ ol tudjuk, hogy A[1] 6= A[n]. Adjon O(log n) ¨osszehasonl´ıt´ast haszn´al´o algoritmust, amely tal´ al egy olyan i indexet, hogy A[i] 6= A[i + 1]. 4. Egy gy¨ okeres szintezett f´ an A ´es B a k¨ovetkez˝o j´at´ekot j´atssza: felv´altva mozgatnak egy b´ abut ami kezdetben az els˝ o szinten, a gy¨ ok´erben van. Minden l´ep´esben a soron k¨ovetkez˝o j´at´ekos az aktu´alis v cs´ ucsb´ ol v valamelyik fi´ aba mozgatja a b´ abut. A j´ at´eknak akkor van v´ege, ha a b´ abu a fa egyik level´ebe ker¨ ul. A levelek egy r´esze z¨ oldre van festve. A kezd˝ o A j´ at´ekos akkor nyer, ha a j´at´ek egy z¨ old lev´elben ´er v´eget. Adott a fa ´ellist´ aja, ´es egy t¨ omb, ami a fa minden pontj´ ara megmondja, hogy az z¨ old-e. Mutasson egy O(n) l´ep´essz´am´ u algoritmust, amely meghat´ arozza, hogy az A j´at´ekos hogyan j´atszon, hogy biztosan nyerjen (felt´eve, hogy van ilyen nyer˝ o strat´egi´ aja). 7
5. Cirkuszi akrobat´ ak egym´ as v´all´ ara ´ allva min´el nagyobb tornyot szeretn´enek l´etrehozni (a toronyban minden szinten csak egy akrobata lesz). Eszt´etikai ´es gyakorlati szempontok miatt egy ember v´all´ ara csak olyan ´allhat, aki n´ ala alacsonyabb ´es k¨onnyebb is. A cirkuszban n akrobata van, adott mindegyik¨ uk magass´ aga ´es s´ ulya. Adjon algoritmust, amely O(n2 ) l´ep´esben megadja a lehets´eges legt¨obb emberb˝ ol ´all´ o torony ¨ossze´ all´ıt´as´at. ¨ 6. Egy n pont´ u teljes gr´ af cs´ ucsait kell kisz´ınezn¨ unk csupa k¨ ul¨onb¨ oz˝o sz´ın˝ ure. Osszesen k ≥ n f´ele sz´ın ´all rendelkez´esre, de az egyes pontok sz´ıne nem teljesen tetsz˝ oleges. Minden v cs´ ucshoz adott sz´ıneknek egy S(v) list´ aja, a v cs´ ucsot csak az S(v)-ben szerepl˝ o sz´ınek valamelyik´ere sz´ınezhetj¨ uk. Adjon O(nk 2 ) l´ep´essz´am´ u algoritmust, amely az S(v) list´ ak alapj´ an eld¨ onti, hogy van-e a megk¨ ot´eseknek megfelel˝ o sz´ınez´es, ´es ha van ilyen, tal´ al is egyet.
Algoritmusok elm´elete vizsgaz´ arthelyi 2005. m´ajus 26.
1. Ismertesse az ¨osszef´es¨ ul´eses rendez´est (´es az ehhez sz¨ uks´eges ¨osszef´es¨ ul´es algoritmus´at). Adja meg hogy ez a ´ ıt´as´at bizony´ıtsa is be. rendez´es mennyi ¨ osszehasonl´ıt´ ast haszn´al (legrosszabb esteben). All´ 2. Defini´alja, hogy egy X nyelvoszt´alynak mi a coX komplementer nyelvoszt´alya. Igazolja, hogy ha X ⊆ Y , akkor coX ⊆ coY . 3. Bizony´ıtsa be, hogy van olyan k konstans, mellyel minden x ∈ {0, 1}∗ sz´ora teljes¨ ul, hogy |C(x) − C(xx)| < k. (Itt C(z) a z sz´ o Kolmogorov-bonyolults´ag´at jel¨oli.) 4. Mutassa meg, hogy az al´ abbi L nyelv P-ben van, vagy azt, hogy NP-teljes: L = {(G, a, b) : a, b > 0 eg´eszek, a G gr´ afnak van a Ka,b teljes p´ aros gr´affal izomorf fesz´ıtett r´eszgr´ afja} 5. A kezdetben u ¨ res M m´eret˝ u hash-t´ abl´ aba sorban beraktuk a k1 , k2 , . . . , kn kulcsokat a h(x) ≡ x(mod M ) hashf¨ uggv´ennyel, line´aris pr´ob´ aval. Jel¨ olje t1 a keletkezett t´ abl´ aban az egym´ as melletti foglalt mez˝ ok maxim´ alis sz´am´ at. Amikor ugyanezt a k1 , k2 , . . . , kn sorozatot ugyanabban a sorrendben egy u ¨ res 2M m´eret˝ u t´ abl´ aba rakjuk be a h(x) ≡ x(mod 2M ) hash-f¨ uggv´ennyel, line´aris pr´ob´ aval, akkor a kepott t´ abl´ aban legyen t2 az egym´ as melletti foglalt mez˝ ok maxim´ alis sz´ ama. (a) Igazolja, hogy t2 ≤ t1 (b) Igaz-e, hogy t1 ≤ 2t2 ? ´ 6. Ellist´ aval adott az n pont´ u G(V, E) gr´ af, melynek minden e ´ele egy c(e) > 0 ´els´ ullyal van ell´ atva. Egy adott s ∈ V cs´ ucsb´ ol akarunk egy adott t ∈ V cs´ ucsba eljutni a legolcs´ obb m´odon, de az u ´ t k¨olts´eg´et a szok´ asost´ ol elt´er˝oen sz´amoljuk: ha az e ´el az u ´ t s-t˝ ol sz´ am´ıtott k-adik ´ele, akkor k · c(e) k¨olts´eggel j´arul hozz´ a az u ´ t k¨olts´eg´ehez. Adjon algoritmust, ami az ilyen ´ertelemben vett legolcs´ obb u ´ t k¨olts´eg´et O((n(n + |E|) log n) l´ep´esben.
Algoritmusok elm´elete vizsgaz´ arthelyi 2005. j´ unius 9. 1. Ismertesse a bin´ aris keres˝ ofa adatszerkezetet. ´Irja le a keres´es, a besz´ ur´as ´es a t¨ orl´es algoritmus´at. Maxim´alisan mennyi lehet ezek l´ep´essz´ ama? V´ alasz´ at indokolja is meg. 2. ´Irja le a legr¨ovidebb utak keres´es´ere szolg´ al´ o Floyd-algoritmust. Adja meg az algotimus l´ep´essz´am´ at. 3. Igazolja, hogy ha L1 ∈ NP ´es L2 ∈ SP ACE(n2 ), akkor L1 ∪ L2 ∈ EXP T IM E. 4. Mutassa meg, hogy az al´ abbi L nyelv P-ben van, vagy azt, hogy NP-teljes: L = {G(V, E) : G egyszer˝ u gr´ af, |E| ≤ 2|V |, a G gr´af sz´ınezhet˝ o 3 sz´ınnel }. 5. Legyen G egy ¨osszef¨ ugg˝ o gr´ af, az ´elein pozit´ıv ´els´ ulyokkal. A G gr´afnak most csak az olyan fesz´ıt˝of´ ak ´erdekelnek minket, melyekben legfeljebb 3 darab nem els˝ ofok´ u pont van. Adjon polinom idej˝ u algoritmust, amely meghat´aroz az ilyen tulajdons´ ag´ u fesz´ıt˝ of´ ak k¨oz¨ ul egy minim´alis s´ uly´ ut.
8
6. Legyen I = {0, 1} ´es L ⊆ {x#y : x, y ∈ I ∗ } egy tetsz˝ oleges nyelv. Minden w ∈ I ∗ sz´ohoz defini´ aljuk az Lw = {x : x#w ∈ L} nyelvet. (Az Lw nyelv lehet u ¨ res is.) Igazolja, hogy (a) ha L rekurz´ıv, akkor mindegyik Lw nyelv rekurz´ıv; (b) van olyan nem rekurz´ıv L nyelv, hogy mindegyik Lw nyelv rekurz´ıv.
Algoritmusok elm´elete vizsgaz´ arthelyi 2005. j´ unius 16. ´ 1. ´Irja le az UNIO-HOLVAN adatszerkezetet ´es a f´akkal val´o implement´ aci´ oj´ at (´ ut¨ osszenyom´ as n´elk¨ ul) Mennyi a m˝ uveletek l´epessz´ ama? (Bizony´ıtani nem kell.) 2. (a) Defini´alja a TIME(f (n)) ´es SPACE(g(n)) nyelvoszt´alyokat. (b) Bizony´ıtsa be, hogy TIME(f (n)) = co TIME(f (n)) ⊆ SPACE(f (n)). 3. Igazolja, hogy a TP = {G : G p´ aros gr´ af, van benne teljes p´ aros´ıt´as} nyelv ´es a Hamilton-k¨ orrel rendelkez˝o gr´afok H nyelve k¨oz¨ott van TP ≺ H Karp-redukci´o. 4. Legyen I = {0, 1} ´es L ⊆ I ∗ egy nyelv. Legyen L(2) = {wxw : w ∈ L, x ∈ I ∗ }. Bizony´ıtsa be, hogy ha L ∈ RE akkor L(2) ∈ RE is teljes¨ ul. 5. Mutassa meg, hogy a r´eszhalmaz¨ osszeg nyelv al´abbi v´altozata P-beli P L = {(s1 , . . . , sn ; b) : si , b eg´eszek, 0 < si < n2 , 0 < b ´es ∃I ⊆ {1, . . . , n} hogy i∈I si = b}. 6. Legyen a1 , a2 , . . . , an az 1, 2, . . . , n sz´ amok egy permut´ aci´ oja. Igazolja, hogy nincs olyan ¨osszehasonl´ıt´as alap´ u rendez´es, mely a lehets´eges a1 , . . . , an sorozatok t¨ obb mint fel´en´el O(n) ¨osszehasonl´ıt´ast haszn´al.
Algoritmusok elm´elete vizsgaz´ arthelyi 2005. j´ unius 23. 1. ´Irja le a legr¨ovidebb utak keres´es´ere szolg´ al´ o Dijkstra-algoritmust. Mi az algoritmus alkalmaz´ as´anak felt´etele? Mennyi az algoritmus l´ep´essz´ ama, ha a gr´ af ´ellist´ aval van megadva ´es a megval´os´ıt´as´aban bin´aris kupacot haszn´alunk? (Az algoritmus helyess´eg´et ´es a l´ep´essz´amot nem kell indokolni.) 2. (a) Defini´alja a diagon´ alis nyelvet. ´ ıt´as´at bizony´ıtsa is be. (b) Beletartozik-e a diagon´ alis nyelv az R, illetve RE nyelvoszt´alyokba? All´ 3. Legyen M egy nemdeterminisztikus Turing-g´ep ´es ´alljon KM azokb´ ol a w szavakb´ ol, melyekhez van az M g´epnek olyan sz´am´ıt´asi ´ aga, ami ment´en M nem ´ all meg. Igazolja, hogy KM ∈ co RE. 4. Mutassa meg, hogy az al´ abbi L nyelv P-ben van, vagy azt, hogy NP-teljes: L = {(G, k) : a G gr´ afban minden pont foksz´ ama kisebb mint a pontok sz´am´ anak fele, ´es G-ben van k f¨ uggetlen pont}. 5. Ir´ any´ıtatlan gr´af t´ arol´ as´ ara adjon meg egy adatszerkezetet az al´abbi m˝ uveletekkel: ´ ´ UJCS UCS(v): a gr´ afhoz hozz´ aad egy u ´ j cs´ ucsot; ´ EL(u, ´ UJ v): a m´ar l´etez˝ o u ´es v cs´ ucsok k¨oz´e felvesz egy ´elet; ´ VANUT(u, v): igen ´ert´eket ad vissza, ha vezet az u ´es v cs´ ucsok k¨oz¨ott u ´ t, egy´ebk´ent pedig nem ´ert´eket. Ha a t´ arolt gr´afnak n cs´ ucsa van, akkor mindh´arom m˝ uvelet l´ep´essz´ama legyen O(log n). 6. Minden nap t¨ obb u ´ j megmunk´ aland´o munkadarab ´erkezik a m˝ uhelybe, de naponta csak eggyel v´egeznek. Tegy¨ uk fel, hogy M napon ´ at minden nap M u ´ jabb munkadarab ´erkezik. A munkadarabok meg vannak sz´amozva 1-t˝ ol M 2 -ig, de tetsz˝ oleges sorrendben ´erkezhetnek. A m˝ uhelyben minden nap egy darabot, a felgy¨ ulemlett munkadarabok k¨oz¨ ul a legkisebb sorsz´ am´ ut csin´alj´ak meg. Jel¨ olje Ai az i-edik nap ´erkez˝o munkadarabok halmaz´at, |Ai | = M ´es A1 ∪ . . . ∪ AM = {1, . . . , M 2 }. Adjon algoritmust, amely az Ai halmazokb´ ol O(M 2 ) l´ep´esben meghat´ arozza, hogy az M nap k¨oz¨ ul melyik nap melyik munkadarab fog elk´esz¨ ulni.
9
Algoritmuselm´elet z´ arthelyi 2006. ´aprilis 7.
1. El˝ofordulhat-e nyitott c´ımz´eses hash-el´es eset´en, hogy az n > 3 m´eret˝ u t´ abl´ aban csak 3 elem van, de a keres´es l´ep´essz´ama n ? 2. Adott n k¨ ul¨onb¨ oz˝o elem, ezek k¨oz¨ ul keress¨ uk a kicsiket. A besz´ ur´asos, az ¨osszef´es¨ ul´eses, illetve a kupacos rendez´est a szok´ asos m´odon futtatva nagys´ agrendileg h´ any ¨osszehasonl´ıt´ast v´egz¨ unk, am´ıg megtudjuk, hogy melyik az els˝ o k darab legkisebb elem? 3. Legyen G egy ir´ any´ıtatlan ¨ osszef¨ ugg˝ o gr´ af. Igaz-e, hogy (a) G minden f ´el´ehez van G-nek olyan m´elys´egi bej´ ar´asa, amelyben f egy fa´el? (b) G minden f ´el´ehez van G-nek olyan sz´eless´egi bej´ ar´asa, amelyben f egy fa´el? (c) G minden F fesz´ıt˝ of´ aj´ ahoz van G-nek olyan m´elys´egi bej´ ar´asa, amelyben F minden ´ele fa´el? (d) G minden F fesz´ıt˝ of´ aj´ ahoz van G-nek olyan sz´eless´egi bej´ ar´asa, amelyben F minden ´ele fa´el? 4. Adott egy kupac, mely n darab sz´ amot tartalmaz. Egy u ´ j kupacot szeretn´enk ´ep´ıteni az eredeti kupac elemeinek (−1)-szereseib˝ ol. (Ehhez, ha akarjuk, haszn´alhatjuk az eredeti kupacot.) Mutassa meg, hogy az u ´ j kupac elk´esz´ıt´es´ehez haszn´alt ¨ osszehasonl´ıt´ asok sz´ ama Θ(n). 5. Vid´eken aut´ozunk, ahol benzink´ ut csak bizonyos falvakban van. Az A falubeli benzink´ utt´ol indulunk ´es a B faluba akarunk el´erni (ahol szint´en van benzink´ ut). A falvak k¨oz¨otti utakat egy n cs´ ucs´ u e ´el˝ u, ¨osszef¨ ugg˝o, ir´ any´ıtatlan gr´af ´ırja le, melynek cs´ ucsai a falvak, az ´elek pedig a falvak k¨oz¨otti utakat jelentik, egy ´el s´ ulya a k´et falut ¨osszek¨ ot˝o u ´ tszakasz hossza. A gr´ af az ´ellist´ aj´ aval adott, ´es ezen k´ıv¨ ul adott m´eg az a k falu, amelyben van benzink´ ut. Adjon O(ke log n) l´ep´essz´ am´ u algoritmust, amely meghat´ arozza az A-b´ol B-be viv˝ o legr¨ovidebb olyan u ´ tvonalat, melynek sor´ an soha nem kell 600 kilom´etern´el t¨ obbet aut´oznunk k´et benzink´ ut k¨oz¨ott. 6. Egy n sz´ob´ ol ´all´ o sz¨ oveget kell sorokra t¨ ordelni. A sz¨oveg i-edik szava ℓi karakterb˝ol ´all, egy sor s karakter hossz´ u. Ha egy sor a sz¨ oveg i-edik szav´aval kezd˝odik ´es a j-edik sz´oval v´egz˝ odik, akkor az elv´alaszt´o sz´ok¨ oz¨oket is figyelembe v´eve t = s − (ℓi + ℓi+1 + · · · + ℓj + j − i) u ¨ res hely marad a sor v´eg´en. Egy ilyen sor hib´aja legyen t2 . A t¨ ordel´es hib´ aja a nem u ¨ res sorok hib´ ainak ¨osszege. Adjon O(n2 ) l´ep´eses algoritmust egy legkisebb hib´aj´ u t¨ ordel´es meghat´ aroz´as´ ara! (A szavak sorrendje r¨ ogz´ıtett.)
Algoritmuselm´elet vizsgaz´ arthelyi 2006. m´ajus 29. Megold´ asait mindig indokolja meg (kiv´etel ez al´ ol az 1. feladat (c) r´esze). A 3., 4., 5. ´es 6. feladatn´ al felhaszn´ alhat´ o b´ armely, az el˝ oad´ ason elhangzott a ´ll´ıt´ as. 1. (a) Adja meg a k¨ovetkez˝o fogalmak defin´ıci´ oj´ at: bin´ aris fa, bin´aris keres˝ofa, AVL-fa. (b) Adjon als´ o ´es fels˝ o becsl´est egy n cs´ ucs´ u bin´aris keres˝ofa szintsz´ am´ ara! Indokolja is v´alasz´ at. (c) Nagys´ agrendileg h´ any szintje van egy n cs´ ucs´ u AVL-f´ anak? (Itt indokl´as nem sz¨ uks´eges.) 2. Bizony´ıtsa be, hogy a Karp-redukci´ o tranzit´ıv: ha L1 ≺ L2 ´es L2 ≺ L3 , akkor L1 ≺ L3 . 3. Igaz-e, hogy a 2-SZ´IN nyelv (a 2 sz´ınnel sz´ınezhet˝ o gr´afok nyelve) benne van -ban?
4. Legyen k pozit´ıv eg´esz sz´ am, A[1 : n] pedig egy olyan t¨ omb, melyben 1 ´es M k¨oz¨otti k¨ ul¨onb¨ oz˝o eg´esz sz´amokat t´ arolunk, nem felt´etlen¨ ul rendezetten. Egy (j, i) sz´amp´ arra azt mondjuk, hogy k-as h´ezag az A t¨ ombben, ha A[i] − A[j] ≥ k ´es A[j] ´es A[i] k¨oz´e nem esik m´asik A-beli elem (azaz nincs olyan 1 ≤ ℓ ≤ n index, melyre A[j] < A[ℓ] < A[i] ´ allna). Adjon O(n + ⌊M/k⌋) l´ep´est haszn´al´o algoritmust, ami adott k ´es A eset´en tal´ al egy k-as h´ezagot A-ban vagy ha nincs ilyen, akkor azt jelzi. (P´eld´ aul, ha a 14 15 23 20 t¨ ombben keres¨ unk 5-¨os h´ezagot, akkor a v´alasz (2, 4).) 5. A k¨oz¨os I ´ab´ec´e feletti L1 , L2 , . . . , Lk nyelvekr˝ol (ahol k ≥ 1 eg´esz sz´am) tudjuk, hogy (a) p´ aronk´ent diszjunktak (azaz Li ∩ Lj = ∅, ha i 6= j), (b) uni´ojuk kiadja az ¨ osszes sz´ ot (azaz L1 ∪ L2 ∪ . . . ∪ Lk = I ∗ ) ´es (c) rekurz´ıvan felsorolhat´ oak (azaz Li ∈ RE ha 1 ≤ i ≤ k). Bizony´ıtsa be, hogy ekkor mindegyik Li nyelv rekurz´ıv. 10
´ 6. Ellist´ aj´ aval adott egy n cs´ ucs´ u, e ´el˝ u egyszer˝ u, ir´ any´ıtatlan G gr´af. Tudjuk, hogy G-ben van K > n/2 elemsz´ am´ u f¨ uggetlen ponthalmaz. Adjon algoritmust, ami O(n + e) l´ep´esben tal´ al egy 2K − n m´eret˝ u f¨ uggetlen ponthalmazt G-ben. (Seg´ıts´eg: haszn´aljunk fel egy tanult k¨ozel´ıt˝ o gr´afalgoritmust.)
Algoritmuselm´elet vizsgaz´ arthelyi 2006. j´ unius 12. Megold´ asait mindig indokolja is meg. A 3–6. feladatokn´ al felhaszn´ alhat´ o b´ armely, az el˝ oad´ ason elhangzott a ´ll´ıt´ as.
1. ´Irja le az ¨osszef´es¨ ul´es ´es az ¨ osszef´es¨ ul´eses rendez´es elj´ar´as´at. Mennyi a l´ep´essz´amuk? (V´alasz´ at bizony´ıtsa is be.) 2. Defini´alja a Karp-redukci´ ot ´es bizony´ıtsa be, hogy ha L1 ≺ L2 ´es L2 NP-ben van, akkor L1 is NP-ben van. 3. Az L nyelv ´alljon azokb´ ol az ir´ any´ıtott gr´ afokb´ol, melyekben nincs ir´ any´ıtott k¨or, de van ir´ any´ıtott Hamilton-´ ut. Vagy adjon az L nyelv felismer´es´ere egy polinomi´ alis l´ep´essz´am´ u algoritmust (a l´ep´essz´am nagys´ agrendj´enek meghat´ aroz´as´aval egy¨ utt) vagy bizony´ıtsa be, hogy az L nyelv NP-teljes. 4. Igazolja, hogy ha lenne olyan Turing-g´ep, amely minden bemenet eset´en meg´ all ´es a meg´ all´ asi nyelvet fogadja el, akkor RE=R is teljes¨ ulne. 5. Legyen G = (V, E) egy s´ ulyozott ir´ any´ıtatlan gr´af, amiben minden ´el s´ ulya pozit´ıv. Tegy¨ uk fel, hogy G o¨sszef¨ ugg˝o, de nem teljes gr´ af. A G gr´ afhoz egy 0 s´ uly´ u ´elt akarunk hozz´ aadni u ´ gy, hogy a keletkez˝o G′ gr´afban a minim´alis fesz´ıt˝ ofa s´ ulya a lehet˝ o legkisebb legyen. Adjon algoritmust ami a m´atrix´aval adott G gr´afra O(|V |3 ) l´ep´esben meghat´ arozza, hogy melyik k´et, a G-ben nem ¨osszek¨ ot¨ott pont k¨oz´e h´ uzzuk be az u ´ j ´elet. 6. Van n f´ajlunk, az i-edik f´ ajl hossz´ at jel¨ olje hi . Tegy¨ uk fel, hogy a f´ajlok a hosszuk szerint nem cs¨okken˝ o sorrendben k¨ovetik egym´ ast, azaz 0 < h1 ≤ h2 ≤ · · · ≤ hn . Ment´eskor k´et egyforma m´eret˝ u lemez ´all rendelkez´es¨ unkre. A ment´esnek sorban kell t¨ ort´ennie, el˝ obb az els˝ o f´ajlr´ ol kell megmondani, melyik lemezre ker¨ ulj¨on, azut´ an a m´asodikr´ ol, stb. (F´ ajlokat sz´etv´ agni nem szabad, minden f´ajl teljes eg´esz´eben ker¨ ul az egyik vagy a m´asik lemezre.) Amikor a soron k¨ovetkez˝o f´ ajl m´ar egyik lemezre se f´er r´ a, akkor abbahagyjuk az elj´ar´ast. Egy ilyen elj´ar´as optim´ alis, ha a lehet˝ o legt¨obb f´ ajlt lehet seg´ıts´eg´evel kimenteni. Mutassa meg, hogy az a moh´ o elj´ ar´ as, amikor a k¨ovetkez˝o f´ajlt oda tessz¨ uk, ahol t¨ obb hely van, nem felt´etlen¨ ul optim´ alis. Legfeljebb h´ any f´ ajllal fogunk kevesebbet kimenteni ezzel a moh´ o elj´ar´assal az optim´ alis (szint´en sorrendben ment˝ o) megold´ashoz k´epest?
Algoritmuselm´elet vizsgaz´ arthelyi 2006. j´ unius 19. Megold´ asait mindig indokolja is meg. A 3–6. feladatokn´ al felhaszn´ alhat´ o b´ armely, az el˝ oad´ ason elhangzott a ´ll´ıt´ as.
1. ´Irja le a piros-k´ek algoritmust (a piros ´es k´ek szab´ allyal egy¨ utt). Az algoritmus helyess´eg´et nem kell bizony´ıtani. 2. Defini´alja a 3SZ´IN ´es MAXFTL nyelveket ´es adjon meg egy 3SZ´IN ≺ MAXFTL Karp-redukci´ ot (a redukci´o j´os´ag´at nem kell igazolni). 3. Legyen L egy nyelv, amir˝ ol tudjuk, hogy 5n3 − 3n2 + 2 t´ arkorl´ attal felismerhet˝o. K¨ovetkezik-e ebb˝ol, hogy az L komplementere az EXPTIME oszt´alyba tartozik? ´ 4. Alljon az L nyelv az olyan w#s#x szavakb´ ol, ahol w egy Mw Turing-g´ep k´odja ´es Mw az s bemenettel ind´ıtva a sz´am´ıt´asa sor´ an eljut valamikor abba az ´ allapotba, aminek a k´odja x. Igazolja, hogy L ∈ RE ´es L 6∈ R.
11
5. Egy bajnoks´agban 2n csapat vesz r´eszt. Minden fordul´oban minden csapat pontosan egy m´erk˝oz´est j´atszik. Minden m´erk˝oz´est a k´et r´esztvev˝ o csapat valamelyik´enek a p´ aly´aj´ an j´atszanak. A k¨ovetkez˝o k fordul´o mindegyik´ere m´ar adott, hogy ki kivel fog j´ atszani ( a beoszt´ as tetsz˝ oleges lehet, pl. ugyanaz a k´et csapat t¨ obbsz¨or is j´atszhat egym´ as ellen). Az viszont m´eg nincs meghat´ arozva, hogy melyik m´erk˝oz´es kinek a p´ aly´aj´ an t¨ ort´enjen. Olyan p´ alyabeoszt´ ast szeretn´enk k´esz´ıteni az adott m´erk˝oz´esekhez, hogy minden csapat felv´altva j´atszon a saj´at p´ aly´aj´ an ´es idegenben (azaz, amelyik csapat az els˝ o fordul´oban otthon j´atszik, az legk¨ ozelebb idegenben, ut´ ana megint otthon, stb). Adjon O(kn) l´ep´essz´ am´ u algoritmust, ami elk´esz´ıt egy ilyen p´ alyabeoszt´ ast vagy jelzi, hogy ez nem lehets´eges. 6. A 4 elem˝ u I abc felett adott k´et sz´ o: x = x1 x2 · · · xn ´es y = y1 y2 · · · yk , ahol 1 ≤ k ≤ n ´es xi , yj ∈ I. Keress¨ uk az x sz´oban az olyan r´eszszavakat, amelyek anagramm´ai y-nak, azaz az olyan i indexeket, hogy az xi , xi+1 , . . . , xi+k−1 bet˝ uk megfelel˝ o sorrendbe rakva az y sz´ ot adj´ ak. Adjon algoritmust, ami x-ben az ¨osszes ilyen i helyet O(n) l´ep´esben meghat´ arozza.
Algoritmuselm´elet vizsgaz´ arthelyi 2006. j´ unius 26. Megold´ asait mindig indokolja is meg. A 3–6. feladatokn´ al felhaszn´ alhat´ o b´ armely, az el˝ oad´ ason elhangzott a ´ll´ıt´ as.
1. ´Irja le az ¨osszes pontp´ ar k¨oz¨otti legr¨ ovidebb u ´ thossz meghat´ aroz´as´ara szolg´ al´o Floyd-algoritmust. Mennyi az algoritmus l´ep´essz´ ama, ha a gr´ af a m´atrix´aval adott? V´ alasz´ at indokolja is. ´ 2. ´Irja le az UNIO-HOLVAN adatszerkezetet ´es annak t¨ ombbel, illetve f´akkal (´ ut¨ osszenyom´ as n´elk¨ uli) val´o megval´os´ıt´as´at. Mennyi lesz a m˝ uveletek l´ep´essz´ ama a k´et esetben? (Itt a l´ep´essz´amot nem kell indokolni.) 3. Legyen L = {w ∈ I ∗ : ∃ Mw , LMw = ∅}. Bizony´ıtsa be, hogy L ∈ co RE. olje 4. A G = (V, E) egyszer˝ u, ir´ any´ıtatlan gr´ afban legyen X ⊆ V ´es X = V − X az X halmaz komplementere. Jel¨ m(X) az olyan ´elek sz´ am´ at, melyek X ´es X k¨oz¨ott futnak. Legyen maxv´ag´as = {(G, k) : ∃X ⊆ V, hogy m(X) ≥ k}, maxfelez´es = {(G, k) : ∃X ⊆ V, hogy m(X) ≥ k ´es |X| = |X|}. Igazolja, hogy maxv´ag´as ≺ maxfelez´es. 5. Egy n emberb˝ ol ´ all´ o szervezetben b f´ele bizotts´ag m˝ uk¨odik. Bizotts´ agi u ¨ l´esek id˝opontj´ at akarjuk kit˝ uzni. K´et k¨ ul¨onb¨ oz˝o bizotts´ ag u ¨ l´ese akkor lehet azonos napon, ha nincs olyan ember, aki mindk´et bizotts´agnak tagja. Legyen adott egy k pozit´ıv eg´esz sz´ am ´es minden bizotts´aghoz a tagok n´evsora. Azt szeretn´enk eld¨ onteni, hogy a b bizotts´ agi u ¨ l´es kit˝ uzhet˝ o-e ¨ osszesen legfeljebb k k¨ ul¨onb¨ oz˝o napra. Vagy adjon egy, a k´ıv´ ant beoszt´ ast megtal´al´o polinomi´ alis algoritmust vagy mutassa meg, hogy a feladathoz tartoz´ o nyelv NP-teljes. 6. Van n f´ajlunk, az i-edik f´ ajl hossz´ at jel¨ olje a hi . Tegy¨ uk fel, hogy a hi sz´amok eg´eszek. Ment´eshez k´et egyform´ an L m´eret˝ u lemez ´ all rendelkez´es¨ unkre (L pozit´ıv eg´esz sz´am). A c´el, hogy min´el nagyobb k sz´amra az els˝ o k darab f´ajl mindegyik´et ments¨ uk ki a lemezekre. F´ajlokat sz´etv´ agni nem szabad, minden f´ajl teljes eg´esz´eben ker¨ ul az egyik vagy a m´asik lemezre. Adjon algoritmust, ami adott L ´es hi sz´amokhoz meghat´ arozza, hogy melyik f´ajlt melyik lemezre tegy¨ uk ahhoz, hogy k a lehet˝o legnagyobb legyen. Az algoritmus l´ep´essz´ama legyen O(L2 ).
12
