Algoritmuselmélet - Vizsga, 2013.06.06.
Tartalomjegyzék
2013.06.06. vizsga megoldásai
1. Feladat
Ebben a feladatban a mélységi bejárással kapcsolatos kérdésekre kell válaszolni.
- (a) Adja meg a keresztél definícióját!
- (b) A mélységi bejárás során hogyan lehet a mélységi és a befejezési számok alapján felismerni a keresztéleket?
- (c) Bizonyítsa be, hogy irányítatlan gráf mélységi bejárásánál nincsenek keresztélek!
(a)
Tekintsük a G irányított gráf egy mélységi bejárását és a kapott T mélységi feszítő erdőt. Ezen bejárás szerint G egy x → y éle keresztél, ha x és y nem leszármazottjai egymásnak.
(b)
msz - mélységi szám
bsz - befejezési szám
Ha [math] (msz[y] \lt msz[x]) [/math] és [math](bsz[y] \gt 0) [/math], akkor az x → y egy keresztél.
Fájl:Keresztel 1.png
(c)
A b) rész alapján könnyen belátható. Ha lenne keresztél, az azt jelentené, hogy van olyan x → y él, amire fennáll, hogy [math] (msz[y] \lt msz[x]) [/math] és [math](bsz[y] \gt 0) [/math], vagyis y-ban előbb jártunk, mint x-ben, és y-nak van befejezési száma. Ennél fogva nem lehet keresztél, hiszen ha lenne, akkor y-ból eljuthattunk volna még x-be, mielőtt befejeztük volna.
Másképpen mondva: Nem fejezhettük volna be y-t anélkül, hogy ne jártunk volna x-ben.
2. Feladat
Milyen műveletek vannak a nyitott címzésű hash-elésnél? Hogyan kell megvalósítani a keresést, ha a nyitott címzésű hashelésnél kvadratikus maradék próbát használunk?
Nyitott címzésű hash-elés műveletei:
todo
(Nem kérdezték, csak kieg.) Mi az a nyitott címzésű hash-elés?
todo
(Nem kérdezték, csak kieg.) Mi az a kvadratikus maradék próba, nyitott címzésű hash-elésnél?
todo
keresés megvalósítása nyitott címzésű hash-elés esetén kvadratikus maradék próbánál:
3. Feladat
Adja meg az UNIÓ-HOLVAN adatszerkezet definícióját! (A fákkal való implementálást nem kell leírnia.) Mutassa meg, hogy mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban!
UNIÓ-HOLVAN adatszerkezet definíciója:
todo
(Nem kérdezték, csak kieg.) Mi az a Kruskal algoritmus?
todo
Mikor és hogyan használjuk az UNIÓ és a HOLVAN műveleteket a Kruskal algoritmusban:
4. Feladat
TODO
5. Feladat
TODO
6. Feladat
Egy irányítatlan, élsúlyozott gráf az alábbi éllistával adott (zárójelben az élsúlyok):
[math]A:B(1), D(3), E(2); B:A(1), C(3), D(y); D:A(3), C(y), E(x); E:A(2), B(1), D(x).[/math]
- (a) Mi lehet x és y értéke, ha tudjuk, hogy az élsúlyok egész számok, és azt is tudjuk, hogy a B csúcsból indított Prim algoritmus az alábbi sorrendben vette be az értékeket: BE, ED, BA, BC.
- (b) Mely éleket és milyen sorrendben választja ki a Kruskal algoritmus? (Ha több megoldás is van, akkor az összeset adja meg!)
a) Prim algoritmus - Ugyebár úgy dolgozik, hogy az aktuális fához a vele szomszédos élek közül a legkisebb súlyút veszi be. Prim: BE → ED → BA → BC
- A fához hozzáadjuk a BE élt.
- Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így [math]x = 1[/math]. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy [math]x \le 1[/math] lehetne.)
- Most az AB élt adjuk hozzá, ez alapján [math]y \ge 1[/math].
- Most a BC élt adjuk hozzá, ez alapján [math]y \ge 3[/math], így végül [math]y \ge 3[/math].
b) Kruskal algoritmus - Éleket nagyság szerint sorrendbe rakjuk, és növekvő sorrendben felvesszük a fához az éleket, vigyázva, hogy ne csináljunk kört.
1 súlyú - AB, BE, ED
2 súlyú - AE
3 súlyú - BC, AD, EC (és DC, ha [math]y = 3[/math])
Az összes megoldás:
- Az 1 súlyú éleket [math]3! = 6[/math] féleképpen veheti fel az algoritmus (nem lehet belőlük kört csinálni, így itt nincsen para).
- Utána megpróbálná felvenni az AE élt, de azzal egy kört kapna, így nem veszi fel. Az AD éllel szintén így járna (~ezeket kéne pirosra színezni, ha olyan lenne a feladat).
- Maradtak a BC, EC és DC oldalak.
- Ha [math]y = 3[/math], akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
- Ha [math]y \ge 3[/math], akkor a DC oldal kiesik, a maradék 2 élt 2 féleképpen veheti fel, így 12 féleképpen futhat az algoritmus.
7. Feladat
TODO
8. Feladat
TODO
