Algoritmuselmélet - Vizsga, 2013.06.06.

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? Vizsgán megjegyzést fűztek hozzá: irányított gráfokra kell gondolni.
• (c) Bizonyítsa be, hogy irányítatlan gráf mélységi bejárásánál nincsenek keresztélek!

Megoldás

(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 $(msz[y]<msz[x])$ és $(bsz[y]>0)$, 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 $(msz[y]<msz[x])$ és $(bsz[y]>0)$, 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.

Fájl:Keresztel 2.PNG

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?

Megoldás

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:

todo

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!

Megoldás

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:

todo

4. Feladat

Pista bácsi fel akar ugrálni egy n hosszú, fekete illetve fehér fokokból álló csigalépcsőn. Legfeljebb k fokot tud ugrani, de arra vigyáznia kell, hogy páros (>=2) sok foknyi ugrás után páratlan sokat és páratlan sok után mindig páros (>=2) sokat ugorjon. Adjon O(nk) lépésszámú algoritmust, amely megmondja, hogy fel tud-e úgy ugrálni a csigalépcső tetejére, hogy csak egyféle színű lépcsőfokot használ. (A lépcső fokai rendszertelenül vannak színezve, a színezést ismerjük.) Vizsgán megjegyzést fűztek hozzá: a talaj és a legteteje nem színes, csak a lépcsők; csak fölfele (előrefele) ugrál, visszafele nem.

Megoldás

todo

5. Feladat

A hátizsák probléma órán tanult algoritmusát futtattuk egy konkrét inputon, melyben 3 tárgy szerepel. Mi lehetett ez a konkrét input, ha az alábbi táblázat keletkezett? Vizsgán megjegyzést fűztek hozzá: rengetegen odahívták a felügyelőket, hogy márpedig itt el vannak írva a számok, mert semmi nem jön ki. Emiatt hangosan elmondták a felügyelők, hogy jók a számok. Személyes hozzáfűzésem: kell mondani 3 számot, melyek közül 0-át 1-et 2-őt vagy 3-at kiválasztva és ezeket összeadva előállnak ezek a számok: 0, 5, 10, 13, 15, 18. Ezek mondjuk lehetnének az 5, 8 és 10. Viszont ezekkel ellentmondásba keveredhetünk. :-(((

	0	1	2	3	4	5	6	7
1	0	0	0	0	10	10	10	10
2	0	0	5	5	10	10	15	15
3	0	0	5	5	13	13	18	18

Megoldás

todo

6. Feladat

Egy irányítatlan, élsúlyozott gráf az alábbi éllistával adott (zárójelben az élsúlyok):

$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).$

• (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. Vizsgán megjegyzést fűztek hozzá: az élsúlyok pozitív egész számok, a pozitív szót kifelejtették véletlenül.
• (b) Mely éleket és milyen sorrendben választja ki a Kruskal algoritmus? (Ha több megoldás is van, akkor az összeset adja meg!)

Megoldás

Fájl:2013 06 06 V2 6.png

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

1. A fához hozzáadjuk a BE élt.
2. Most az ED élt választottuk. Ez alapján x értéke csak 1 lehet, így $x=1$. (Feladatból kihagyták, hogy pozitív egészekről van szó, amúgy $x\leq 1$ lehetne.)
3. Most az AB élt adjuk hozzá, ez alapján $y\geq 1$.
4. Most a BC élt adjuk hozzá, ez alapján $y\geq 3$, így végül $y\geq 3$.

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 $y=3$)

Az összes megoldás:

1. Az 1 súlyú éleket $3!=6$ féleképpen veheti fel az algoritmus (nem lehet belőlük kört csinálni, így itt nincsen para).
2. 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).
3. Maradtak a BC, EC és DC oldalak.
   1. Ha $y=3$, akkor ezeket szintén 6 féleképpen veheti fel, tehát összesen 36 féleképpen futhat az algoritmus.
   2. Ha $y\geq 3$, 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

Létezik-e olyan X eldöntési probléma, amire X ∉ NP és X ≺ SAT egyszerre fennáll?

Megoldás

(Nem kérdezték, csak kieg.) NP osztály?
todo

(Nem kérdezték, csak kieg.) SAT probléma?
todo

A feladat megoldása:

todo

8. Feladat

TODO