2007-es vizsgák az 5 éves képzésből

Országok listájaHungaryBudapesti Műszaki és Gazdaságtudományi EgyetemVillamosmérnöki és Informatikai KarMérnök informatikusAlgoritmusok ElméleteVizsgák2007-es vizsgák az 5 éves képzésből

Algoritmusok elm´lete z´rthelyi (5 ´ves k´pz´s) e a e e e 2007. ´prilis 27. a

1. Egy kezdetben ures bin´ris keresf´n hajtsa v´gre az al´bbi mveleteket ´s minden l´p´s ut´n rajzolja le a kapott ¨ a oa e a u e e e a f´t! a ´ ´ ´ ´ ´ ´ BESZUR(6), BESZUR(3), BESZUR(5), BESZUR(15), BESZUR(10), BESZUR(20), ´ ´ ¨ ¨ ´ ¨ ¨ BESZUR(12), BESZUR(14), TOROL(15), BESZUR(4), TOROL(3). 2. Egy piros-fekete f´ban lehets´ges-e, hogy a piros-fekete tulajdons´g megs´rt´se n´lk¨l a e a e e e u (a) n´h´ny fekete cs´csot ´tv´ltoztathatunk pirosra? e a u a a (b) valamelyik (csak egy) fekete cs´csot ´tv´ltoztathatjuk pirosra? u a a (M´st nem v´ltoztatunk a f´n.) a a a 3. Ha adott n sz´m, akkor h´ a ivjuk k¨z¨l¨k k¨z´ps elemnek a rendez´s szerinti n/2 -ediket. o uu o e o e Kezdetben adottak az a1 , a2 , . . . , an eg´sz sz´mok, amikrl tudjuk, hogy az a1 a k¨z´ps elem, egy´bk´nt a sz´mok e a o o e o e e a rendezetlenek. Ezekbl ´p´ o e itsen fel egy adatszerkezetet, amiben k´t mvelet van: e u ´ BESZUR: egy uj elemet illeszt az adatszerkezetbe, ´ ¨ ´ ¨ KOZEPTOR: az aktu´lis k¨z´ps elemet t¨rli. a o e o o Mindk´t mvelet megval´s´ asa O(log k) ¨sszehasonl´ ast haszn´ljon, amikor k t´rolt elem van, az adatszerkezet e u o it´ o it´ a a kezdeti fel´p´ ese legyen O(n) ¨sszehasonl´ as. e it´ o it´ 4. A kezdetben ures M = 9 m´ret hasht´bl´ba a h(x) = x (mod 9) hash-f¨ggv´ny seg´ eg´vel az adott sorrendben ¨ e u a a u e its´ e rakja be a 4, 27, 18, 13, 9, 10, 30 elemeket (a) line´ris pr´b´val; a o a (b) kvadratikus pr´b´val. o a Mindk´t esetben minden l´p´s ut´n ´ le a kapott t¨mb¨t ´s jel¨lje, hogy az aktu´lis elem hol okozott utk¨z´st. e e e a irja o o e o a ¨ o e 5. Tekints¨k az olyan G ir´ny´ u a itott gr´fokat, amelyekben ha eltekint¨nk az ´lek ir´ny´ as´t´l, akkor a kapott ir´ny´ a u e a it´ a o a itatlan G gr´f ¨sszef¨gg. A G gr´f egy m´lys´gi bej´r´s´n´l maxim´lisan h´ny olyan cs´cs lehet, amelyre a m´lys´gi ´s a o u o a e e aaa a a a u e e e a befejez´si sz´m megegyezik? e a 6. Az n × n m´ret t´bla minden mezj´re egy pozit´ eg´sz sz´m van ´ e u a oe iv e a irva, az i-edik sor´nak j-edik elem´re A[i, j], a e ahol 0 i, j < n. Feladat, hogy az els oszlopb´l eljussunk az utols´ oszlopba ugy, hogy egy l´p´sben mindig a o o o ´ e e k¨vetkez oszlopba l´p¨nk, ´s azon bel¨l, ha az i-edik sorban voltunk, akkor a k¨vetkez l´p´sben vagy az (i - 1) o o e u e u o o e e (mod n) vagy az i vagy az (i + 1) (mod n) sz´m´ sorba ker¨lhet¨nk. Adjon O(n2 ) l´p´ssz´m´ algoritmust, ami a u u u e e a u meghat´rozza, hogy az els oszlop melyik elem´bl induljunk, ha azt akarjuk, hogy a bej´rt mezk¨n lev sz´mok a o e o a o o o a o ¨sszege minim´lis legyen (az utols´ oszlop b´rmelyik mezje lehet az utols´ olyan mez, amire r´l´p¨nk). a o a o o o ae u 7. Legyen L = {w#k : Mw Turing-g´p ´s van olyan k hossz´ sz´, amit Mw nem fogad el}. Igazolja, hogy L co RE. e e u o 8. Legyen L = {((s1 , t1 ), . . . , (sn , tn ); k) : si , ti {0, 1} az (si , ti ) p´rokhoz tartoz´ Post megfeleltet´si probl´m´nak a o e e a van legfeljebb k darabb´l ´ll´ megold´sa }. Mutassa meg, hogy az L nyelv rekurz´ o a o a iv.

Algoritmusok Elm´lete vizsgaz´rthelyi (5 ´ves k´pz´s) e a e e e 2007. m´jus 22. a ´ 1. Ismertesse a (bin´ris) kupac adatszerkezetet, sorolja fel a mveleteit ´s ´ le r´szletesen a BESZUR elj´r´s algoa u e irja e aa ´ e e a ritmus´t. Mennyi a BESZUR l´p´ssz´ma ´s mi´rt? a e e 2. ´ le a legr¨videbb utak keres´s´re szolg´l´ Bellman-Ford- algoritmust. Mi az algoritmus alkalmaz´s´nak felt´tele? Irja o ee ao aa e M´trixos megad´s eset´n mennyi az algoritmus l´p´ssz´ma? (Az algoritmus helyess´g´t ´s a l´p´ssz´mot nem kell a a e e e a e e e e e a bizony´ itani.) 3. Defini´lja a Karp-redukci´t ´s mutasson r´ egy p´ld´t. (A p´lda helyess´g´t indokolja is meg.) a o e a e a e e e 4. Az al´bbi f¨ggv´nyeket rendezze olyan sorozatba, hogy ha fi ut´n k¨zvetlen¨l fj k¨vetkezik a sorban, akkor fi (n) = a u e a o u o O(fj (n)) teljes¨lj¨n! u o f1 (n) = 1 2 n log n, 100 f2 (n) = 1010 (log n)3 - 100 log n f3 (n) = 8log n .

(A v´lasz helyess´g´t bizony´ a e e itani is kell!) 5. A G ¨sszef¨gg ir´ny´ o u o a itatlan gr´fnak n cs´csa ´s n + 1 ´le van. A gr´f ´lei s´lyozottak. Adjon O(n) l´p´ses a u e e a e u e e algoritmust, ami az ´llist´val adott G-ben tal´l egy minim´lis s´ly´ fesz´ of´t. e a a a u u it a

6. A Bizonytalan Turing-g´p egy olyan nemdeterminisztikus Turing-g´p, ami minden bemeneten meg´ll, ´s eredm´ny¨l e e a e e u ´ vagy azt adja, hogy igen vagy azt, hogy nem, vagy azt, hogy talan. Ugyanarra a bemenetre a nemdeterminisztikus v´laszt´sokt´l f¨ggen k¨l¨nb¨z sz´m´ asi ´gakon k¨l¨nb¨z eredm´nyt kaphatunk. Egy ilyen g´prl azt mondjuk, a a o u o u o o o a it´ a uo o o e e o hogy elfogadja az L nyelvet, ha ´ (1) minden w L sz´ra az eredm´ny minden agon csak igen vagy talan lehet, ´s van olyan sz´m´ asi ´g, ahol az o e ´ e a it´ a eredm´ny igen, e ´ (2) minden w L sz´ra az eredm´ny minden ´gon csak nem ´s talan lehet, ´s van olyan sz´m´ asi ´g, ahol az o e a e e a it´ a eredm´ny nem. e Igazolja, hogy ha az L nyelv felismerhet egy polinom idkorl´tos Bizonytalan Turing-g´ppel, akkor L NPco NP. o o a e 7. Legyen L egy olyan nyelv, amelyre L co SPACE(log n). Igazolja, hogy ekkor L P . 8. Legyenek adottak az a1 , a2 , · · · , an nem felt´tlen¨l k¨l¨nb¨z pozit´ eg´sz sz´mok, ´s m´g egy k pozit´ eg´sz sz´m. e u uo o o iv e a e e iv e a Adjon algoritmust, ami O(nk) l´p´sben meghat´rozza, hogy a k sz´m h´nyf´lek´ppen ´ll´ e e a a a e e a ithat´ el az ai sz´mok o o a k¨z¨l n´h´ny ¨sszegek´nt. (K´t el´ll´ as k¨l¨nb¨z, ha a megfelel indexek halmaza k¨l¨nb¨zik.) o u e a o e e oa it´ u o o o o uo o

Algoritmusok elm´lete vizsgaz´rthelyi (5 ´ves k´pz´s) e a e e e 2007. j´nius 5. u 1. ´ le a legr¨videbb utak keres´s´re szolg´l´ Dijkstra-algoritmust. Mi az algoritmus alkalmaz´s´nak felt´tele? (Az Irja o ee ao aa e algoritmus helyess´g´t nem kell bizony´ e e itani.) Mennyi az algoritmus l´p´ssz´ma, ha a gr´f a m´trix´val van megadva e e a a a a ´s mi´rt? e e ´ 2. Defini´lja az UNIO-HOLVAN adatszerkezetet. Mennyi az egyes mveletek l´p´ssz´ma t¨mb¨s, illetve f´s (´t¨sszea u e e a o o a uo nyom´s n´lk¨li) megval´s´ as eset´n? (Indokl´s nem sz¨ks´ges.) a e u o it´ e a u e 3. Defini´lja az R ´s RE nyelvoszt´lyokat. Adjon meg egy olyan nyelvet, ami egyikbe sem tartozik ´s bizony´ is ezt a e a e itsa be. 4. Legyen egy v´ges abc ´s f : - egy k¨lcs¨n¨sen egy´rtelm rekurz´ f¨ggv´ny. K¨vetkezik-e ebbl, hogy e e o o o e u iv u e o o f inverze is rekurz´ f¨ggv´ny? iv u e 5. Adott egy n cs´cs´ ´s egy k cs´cs´ piros-fekete fa. A k´t f´ban t´rolt ¨sszes elembl O(n + k) l´p´sben k´sz´ u ue u u e a a o o e e e itsen egy rendezett t¨mb¨t. o o ´ e it´ 6. Ut´p´ eskor a k¨rny´ken sok helyen felszedt´k a j´rd´t. Az ´p´ ok 1-tl n-ig megsz´mozt´k a fontos pontokat o e e a a e it o a a (kapualj, utkeresztezd´s, stb.). A k¨rny´k ´llapot´t k´t n × n t´bl´zat ´ le. A J t´bl´zatban J[i, j] = 1, ha az ´ o e o e a a e a a irja a a i ´s j pontok az utc´n szomsz´dosak ´s megmaradt az ezeket ¨sszek¨t r´szen a j´rda, egy´bk´nt az ´rt´k 0. A P e a e e o oo e a e e e e t´bl´zat az ideiglenesen elhelyezhet pall´kat ´ le: ha az i ´s j pontok ¨sszekt¨thetek egy pall´val, akkor P [i, j] a a o o irja e o o o o ennek a pall´nak a k¨lts´ge. Amennyiben a k´t pont nem k¨thet ¨ssze egy pall´val, akkor a t´bl´zatban szerepel. o o e e o oo o a a (Minden pall´ pontosan k´t pontot ´rint.) Szeretn´nk biztos´ o e e e itani, hogy mindenhonnan mindenhova el tudjunk jutni (hol j´rd´n hol pall´n haladva). Az ´p´ ok c´lja, hogy ugy v´lassz´k meg a pall´k hely´t, hogy min´l kevesebb a a o e it e ´ a a o e e pall´t kelljen haszn´lniuk, ´s ezen bel¨l a pall´k ´rt´keinek ¨sszege minim´lis legyen. ´ o a e u o e e o a Irjon le egy algoritmust, ami O(n2 ) l´p´sben javasol egy ilyen elhelyez´st. (Egy pontra tetszlegesen sok pall´ illeszkedhet, ´s a gyalogosok az e e e o o e egy pontra illeszked pall´k b´rmelyik´rl b´rmelyik´re ´t tudnak l´pni.) o o a eo a e a e 7. Mutassa meg, hogy az al´bbi nyelv P-ben van, vagy azt, hogy NP-teljes: a L = {(F1 , . . . , Fn ; r) : Fi A, |Fi | = 3, az Fi halmazok k¨z¨tt van o o r p´ronk´nt diszjunkt} a e 8. Egy t´glalap alak´ telken n´h´ny fa ´ll. T´rk´p¨nk¨n a telket egy n × k n´gyzetr´cs ´br´zolja, ´s azt l´tjuk, hogy e u e a a e e u o e a a a e a f´k csak r´cspontokban vannak. Egy olyan, a telek oldalaival p´rhuzamos oldal´ t´glalap alak´ h´zhelyet szeretn´nk a a a u e u a e kijel¨lni, aminek cs´csai r´cspontok. C´lunk, hogy a kijel¨lt ter¨let belsej´ben ne legyen fa (a hat´r´n m´r lehet) o u a e o u e aa a ´s a kijel¨lt t´glalap kisebbik oldal´nak hossza a lehet legnagyobb legyen. Adjon O(nk) l´p´ssz´m´ algoritmust e o e a o e e a u egy ilyen h´zhely meghat´roz´s´ra, ha egy list´ban adottak a f´k helyzet´t le´ o r´cspontok koordin´t´i. a a aa a a e ir´ a aa

Algoritmuselm´let vizsgaz´rthelyi (5 ´ves k´pz´s) e a e e e 2007. j´nius 12. u ´ it´ a 1. Defini´lja a piros-fekete f´kat. Mi a kapcsolat egy cs´cs magass´ga ´s fekete magass´ga k¨z¨tt? All´ as´t bizony´ a a u a e a o o itsa is be! 2. ´ le a m´lys´gi bej´r´s algoritmus´t. (A pontok k´tf´le sz´moz´sa ´s az ´lek oszt´lyoz´sa nem kell.) Mennyi az Irja e e aa a e e a a e e a a algoritmus l´p´ssz´ma m´trixos, illetve ´llist´s megad´s eset´n ´s mi´rt? e e a a e a a e e e

3. (a) Defini´lja az univerz´lis ´s a meg´ll´si nyelvet. a a e a a (b) Mi a viszonyuk az RE oszt´lyhoz? (A v´laszt nem kell indokolni.) a a (c) Az univerz´lis nyelv benne van-e az R oszt´lyban? V´lasz´t indokolja is! a a a a 4. Egy A algoritmusr´l azt tudjuk, hogy az n hossz´ bemeneteken a l´p´ssz´ma O(n log n). Lehets´ges-e, hogy o u e e a e (a) van olyan x bemenet, amin a l´p´ssz´ma |x|3 ? e e a (b) minden x bemeneten legfeljebb 2007|x| l´p´st haszn´l? e e a (Szok´s szerint |x| az x sz´ hossz´t jel¨li.) a o a o 5. Legyen L = {0t 1t : t = 1, 2, . . .}. Mutassa meg, hogy van olyan 2 szalagos M Turing-g´p, ami az L nyelvet ismeri e fel ´s amire TM (n) = O(n). e 6. Egy sz´m´ og´ph´l´zatban n sz´m´ og´p van. Minden olyan esem´nyt, hogy az i-edik g´p uzenetet k¨ld a j-ediknek a it´ e a o a it´ e e e ¨ u (i, j, t) form´ban feljegyez¨nk, ahol a t eg´sz sz´m az uzenet k¨ld´s´nek idpontj´t jel¨li. Ugyanabban a t idpontban a u e a ¨ u ee o a o o egy g´p t¨bb g´pnek is k¨ldhet uzenetet. Ha a t idpontban az i-edik g´p v´ e o e u ¨ o e irusos volt, akkor egy (i, j, t) uzenet ¨ hat´s´ra a j-edik g´p megfertzdhet, ami azt jelenti, hogy a t + 1 idpontt´l kezdve m´r a j-edik g´p is v´ aa e o o o o a e irusos lehet. Legyen adott az (i, j, t) h´rmasoknak egy m hossz´ list´ja, valamint x, y ´s t0 < t1 eg´sz sz´mok. Azt kell a u a e e a eld¨nten¨nk, hogy ha az x-edik g´p a t0 idpontban v´ o u e o irusos volt, akkor lehet-e emiatt az y-adik g´p a t1 idpontban e o v´ irusos. Adjon algoritmust, ami ezt a k´rd´st O((t1 - t0 )n + m) l´p´s ut´n megv´laszolja. e e e e a a 7. Igazolja, hogy ha a 3SZ´ nyelv benne van co NP-ben, akkor NP=co NP. IN 8. Egy n ´s egy m karakterbl ´ll´ sz¨vegben meg akarjuk tal´lni a legnagyobb azonos darabot, azaz ha az egyik e o a o o a sz¨veg a1 a2 · · · an ´s a m´sik b1 b2 · · · bm , akkor olyan o e a 1 i n ´s 1 j m indexeket keres¨nk, hogy e u ai+1 = bj+1 , ai+2 = bj+2 , . . . , ai+t = bj+t teljes¨lj¨n a lehet legnagyobb t sz´mra. Adjon erre a feladatra O(mn) l´p´st haszn´l´ algoritmust. u o o a e e ao
2

Algoritmuselm´let vizsgaz´rthelyi (5 ´ves k´pz´s) e a e e e 2007. j´nius 19. u 1. Defini´lja a 2-3 f´t, sorolja fel a mveleteit (az algoritmusokat nem kell le´ a a u irni). Ha n elemet t´rolunk egy 2-3 f´ban, a a akkor mennyi lehet a fa minim´lis, illetve maxim´lis szintsz´ma? V´lasz´t indokolja is meg! a a a a a 2. ´ le az ¨sszes pontp´rra a legr¨videbb ut hossz´t meghat´roz´ Floyd-algoritmust. Mennyi az algoritmus l´p´ssz´ma? Irj o a o ´ a a o e e a (Indokolni nem kell.) 3. Defini´lja a PCP nyelvet. Az R, co R, RE, co RE nyelvoszt´lyok k¨z¨l melyikben van benne ez a nyelv ´s melyikben a a o u e nincs? (Bizony´ itani nem kell.) 4. Adott a s´ ikon n pont, melyek koordin´t´i (a1 , b1 ), (a2 , b2 ), . . . , (an , bn ). Olyan aa P = (x, y) pontot keres¨nk a s´ u ikon, amire az al´bbi ¨sszeg minim´lis. a o a
n

(|ai - x| + |bi - y|)
i=1

Adjon algoritmust, ami O(n log n) l´p´sben meghat´roz egy ilyen P pontot. e e a ´ 5. Az L nyelv minden szava a betk sorozata, azaz L {a} . Alljon az L {0, 1} nyelv az olyan k pozit´ eg´sz u iv e k sz´mok bin´ris alakj´b´l, melyekre a L. Tegy¨k fel, hogy L TIME(n2 ) teljes¨l. Adjon meg egy olyan f (n) a a a o u u f¨ggv´nyt, melyre biztosan igaz, hogy L TIME(f (n)). u e 6. Jel¨lje L1 az ir´ny´ o a itatlan ¨sszef¨gg gr´fokb´l ´ll´ nyelvet ´s L2 a Hamilton-k¨rt tartalmaz´ gr´fokb´l ´ll´ nyelvet. o u o a o a o e o o a o a o Lehets´ges-e, hogy L1 L2 , illetve hogy L2 L1 ? V´lasz´t indokolja is meg! e a a 7. Egy hivatal uj ´p¨letbe fog k¨lt¨zni. Az ´p¨let minden emelet´n ugyanakkora ter¨let haszn´lhat´ fel irod´k ki´ e u o o e u e u a o a alak´ as´ra. Minden r´szleg megmondta, hogy ¨sszesen mekkora irodater¨letre tart ig´nyt. Azt akarjuk eld¨nteni, it´ a e o u e o hogy meg lehet-e oldani a k¨lt¨z´st ugy, hogy egyetlen r´szleg se legyen kett´v´gva, azaz egy r´szleg teljes eg´sz´ben o o e ´ e e a e e e egy emeleten legyen (de egy emeletre ker¨lhet t¨bb r´szleg is). Igazolja, hogy a probl´m´hoz kapcsol´d´ nyelv P-ben u o e e a o o van, vagy azt, hogy a nyelv NP-teljes. ´ e 8. Egy elre r¨gz´ o o itett utvonalon ugy indulunk el, hogy az aut´ L literes tankja tele van. Utic´lunkhoz ugy akarunk ´ ´ o ´ el´rni, hogy legal´bb egy f´l tanknyi benzin maradjon az aut´ban. Tudjuk, hogy az utunkba es n benzink´t k¨z¨l e a e o o u o u melyikben mennyibe ker¨l a benzin, tov´bb´, hogy k´t szomsz´dos benzink´t k¨z¨tt, valamint a kiindul´pontt´l az u a a e e u o o o o els benzink´tig, illetve az utols´ benzink´tt´l a c´lunkig mennyi benzint fogyaszt az aut´. Az egyszers´g kedv´´rt o u o u o e o ue ee ha meg´llunk egy benzink´tn´l, akkor mindig tele tankolunk. Adjon algoritmust, ami O(Ln2 ) l´p´sben megmondja, a u a e e hogy hol ´lljunk meg tankolni ha azt akarjuk, hogy utunk sor´n a benzink¨lts´g minim´lis legyen. a a o e a



Hasonló témájú dokumentumok

Hozzászólások

11.12-1 2009. május 21. 6. gyakorlat alapvizsga anyagszerk beszerzés beugro biomérnöki c nyelv civilizáció csehov csoport diszkrét matematika egyén fazekas gábor fizkém flaubert funkcionalizmus gazdaságföldrajz globalizáció gyak házi doga információelmélet jános kassák képletek kiadott anyag környezettechnikai műveletek és gépek középkor kronológia kulturális ökológia liliidae magyarország mezőgazdaság nitridálás növénynemesítés opkut ordo pdf reakció röviditett struktúra szöveg torlódási hely ttk újság vállalati pénzügyek vektor vetőmag víz