Algoritmuselmélet - PZH, 2013.04.24.
Tartalomjegyzék
2013.04.24. PZH megoldásai
1. Feladat (Van megoldás)
Egy algoritmus lépésszámáról tudjuk, hogy [math] T(n) = T\left(\left \lfloor \frac{n}{4} \right \rfloor\right) + O(n^2)[/math] és tudjuk azt is, hogy [math] T(1)=T(2)=T(3)=1[/math]. Bizonyítsa be, hogy [math] T(n)=O(n^2)[/math].
Van olyan [math] c \gt 0[/math] és [math] n_0[/math], hogy [math] n\gt n_0[/math] esetén [math] T(n)=T\left(\left \lfloor \frac{n}{4} \right \rfloor\right)+O(n^2) \leq T\left(\left \lfloor \frac{n}{4} \right \rfloor\right)+cn^2 \leq T\left(\left \lfloor \frac{n}{16} \right \rfloor\right)+c\left(n^2+\left(\frac{n^2}{4^2} \right)\right) \leq T\left(\left \lfloor \frac{n}{64} \right \rfloor\right) + c\left(n^2+\left(\frac{n^2}{4^2} \right)+\left(\frac{n^2}{16^2} \right)\right) \leq \dots [/math] [math] \dots \leq 1+cn^2\cdot\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{16} \right )^i\right)[/math]
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:
[math]\sum_{i=0}^{k} r^i = \frac{1-r^{k+1}} {1-r} [/math], ahol [math] k = \left \lfloor log_4n \right \rfloor, r = \frac{1}{16}[/math], vagyis [math]\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}}[/math]
[math]\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} \lt 2 ,[/math]ha [math] n \geq 1[/math] (A lényeg, hogy felülről becsüljük!)
Tehát [math] T(n) = \dots \leq 1+2 \cdot cn^2=O(n^2)[/math]2. Feladat (Van megoldás)
Adott egy teljes bináris fa, a csúcsaiba egész számok vannak írva, összesen n darab (a fa nem feltétlenül bináris keresőfa). Adjon algoritmust, ami [math]O(n)[/math] lépésben megkeres egy olyan csúcsot a fában, aminek a részfája kupac, és aminek a magassága a legető legnagyobb az összes ilyen csúcs közül.
- Bár nem tartozik a feladathoz, talán érdemes megjegyezzem, hogy bináris kereső fa nem is lehetne, hiszen akkor ott kapásból csak a legalsó szinten lévő elemek lehetnek kupacok (egy 1 elemet tartalmazó kupac), hiszen bináris keresőfánál balra kisebbek, jobbra nagyobbak vannak, míg kupacnál balra és jobbra is nagyobbak vannak.
- Továbbá a teljes bináris fára azért van szükség, mert így "jóval egyszerűbb" a feladat, és nem kell szívózni annak vizsgálatával, hogy az adott részfa teljes bináris fa-e (ugyebár ez a kupac egyik fontos tulajdonsága).
Minden csúcsban 3 adatot fogunk számon tartani: Érték (ez persze adott már), részfa magassága (jelüljük M-mel), és egy bool érték (IGAZ/HAMIS, jelöljük B-vel), hogy igaz-e a részfájára, hogy az kupac.
- Első lépésben a legalsó szinteken lévő csúcsok esetén [math]M:=1, B:=IGAZ[/math].
- Legyen egy változónk, amiben tároljuk, hogy melyik csúcsra igaz, hogy a részfája a "legnagyobb" kupac (kezdeti értéke legyen mondjuk az egyik legalsó szinten lévő csúcs).
- Minden további szinten az a feladatunk, hogy megnézzük az adott csúcs (x) bal, és jobb fiát [math](JOBB(x), BAL(x))[/math].
- Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e:
- Ha [math]BAL(x),JOBB(x) \gt x;BAL(x).B=JOBB(x).B=IGAZ\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := IGAZ[/math] majd a változónkba belerakjuk a csúcsot. Vagyis ha mindkettő nagyobb, és mindkettő kupac tulajdonsággal bír, akkor a csúcs részfa magassága 1-gyel nagyobb lesz, mint az egyik (bal, vagy jobb) fia magassága, és kupac tulajdonságú lesz.
- Ha [math]BAL(x) \lt x[/math] VAGY [math]JOBB(x) \lt x[/math] VAGY [math]BAL(x).B=HAMIS[/math] VAGY [math]JOBB(x).B=HAMIS\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := HAMIS[/math]. Vagyis ha bármelyik feltétel nem teljesül (valamelyik fia kisebb, avagy valamelyik gyerekére nem igaz, hogy kupac tulajdonságú), akkor maga a csúcs sem lehet már kupac tulajdonságú (itt a magasságot nem is kéne beállítani, de...hát miért is ne).
- Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e:
3. Feladat (Van megoldás)
Kukori és Kotkoda egy-egy bináris fára gondolnak (nem feltétlenül bináris keresőfákra). Következik-e, hogy a két fa azonos, ha
(a) inorder bejárással kilolvasva a két fát ugyanazt a számsorozatot kapják?
(b) preorder bejárással kiolvasva a két fát ugyanazt a számsorozatot kapják?
4. Feladat
TODO
5. Feladat (Van megoldás)
Egy [math]n[/math] soros és kettő oszlopos táblázatban adott [math]n[/math] számpár (egy sor egy számpárt tartalmaz, a számok mind különböző egész számok a táblázatban). Szeretnénk a táblázat sorait úgy átrendezni, hogy a 2. oszlop szerint növekvő sorrendben legyenek a sorok (számpárok). Egy fajta műveletet hajthatunk végre: kijelölhetünk néhány egymást alatti sort (számpárt) és ezeket rendezhetjük az első oszlop szerint növekvően vagy csökkenően. Adjon algoritmust, ami csak ezt a fajta műveletet használva [math]O(n)[/math] lépésben megoldja a feladatot!
- Rendezzük a tömböt az 1. oszlop szerint növekvően.
- A továbbiakban minden [math]i.[/math] lépésben megkeressük az [math]i.[/math] legkisebb elemet, és a helyére tesszük.
- Megkeressük a 2. oszlopban az [math]i.[/math] legkisebbet, az ő helye a tömbben legyen [math]k[/math]
- Mivel az 1. oszlop szerint növekvően vannak a számpárok, így ahhoz, hogy a [math]k.[/math] elem az [math]i.[/math] helyre kerüljön, a számokat csökkenő sorrendbe kell rendezni az [math][i \rightarrow k] [/math] intervallumon.
- Ha ezt megcsináltuk, akkor az első [math]i[/math] helyen már rendezve lesz a tömb.
- Az [math][i+1 \rightarrow n][/math] intervallumon rendezzük a számokat növekvő sorrendben.
- Ezt addig folytatjuk, míg nincs minden számpár a helyén.
- A műveletet minden lépésben [math]\approx 2n[/math] alkalommal használjuk:
- Először növekvő sorrendbe rendeztük az egész tömböt.
- Utána minden [math]i.[/math] lépésben 2x:
- Egyszer a helyére rakjuk az elemet azzal, hogy csökkenő sorrendbe rakjuk a számpárokat (persze csak a megfelelőket).
- Majd újra növekvőbe a maradék számpárokat.
- Így az algoritmus [math]O(n)[/math] lépéssel rendezi a számpárokat a 2. oszlop szerint.
6. Feladat (Van megoldás)
Adott egy [math] n [/math] hosszú tömb. Tudjuk, hogy a tömb első néhány ([math] k [/math] darab) elem 0, a többi 1, de [math] k [/math] értékét nem ismerjük. Adjon [math] O(logk) [/math] (nem [math] O(logn) [/math] )1 összehasonlítást használó algoritmust, ami meghatározza [math] k [/math] értékét.
1 A feladatban [math] O(logk) [/math] szerepel, de az csak elgépelés.
- Először nézzük meg, hogy az első 2 elem [math]0-1[/math]-e, ha igen, akkor [math] k=1 [/math].
- Ha nem, akkor minden további lépésnél ugorjunk a 2x annyiadik cellába (ez legyen [math] m [/math]), ha pedig túl lépnénk a tömböt ezzel, akkor az utolsóba.
- Vizsgáljuk meg, hogy "hol vagyunk": (az aktuális cellát, és a 2 szomszédját)
- Ha [math]0-0-0[/math]-t látunk, akkor ugrunk megint 2x akkorát (ugyanazzal a kritériummal, mint előbb).
- Ha [math]0-0-1[/math]-t látunk, akkor [math] k=m [/math].
- Ha [math]0-1-1[/math]-t látunk, akkor [math] k=m-1 [/math].
- Ha [math]1-1-1[/math]-t látunk, akkor egy bináris keresés segítségével(1) a 2 legutóbbi vizsgált elem közötti cellákban megkeressük a [math]0-1-1[/math], vagy [math]0-0-1[/math] felállást, és a [math]k[/math] értékét a látottak alapján beállítjuk [math]( k=m-1 [/math] vagy [math] k=m )[/math].
(1) Ha [math]0-0-0[/math]-t lát, jobbra lép, ha [math]1-1-1[/math]-t, akkor balra, másik 2 esetben pedig találatunk van.
- Az algoritmus működése alapján belátható, hogy [math] O(logk) [/math] időben fut.
7. Feladat
TODO
8. Feladat (Van megoldás)
Bizonyítsa be, hogy egy piros-fekete fában egy levél testvére vagy levél, vagy piros csúcs!
- Összesen 5 felállás lehet:
- Ebből az 1. és a 4. jó is (a 4. persze csak akkor, ha X az nem a főgyökér).
- A 3. - kis módosítással - látszik, hogy szintén fenn állhat gond nélkül:
- Egyedül a 2. és az 5. problémás. Ezek viszont rosszak is, hiszen mindkét esetben elmondható, hogy X-nek a fekete magassága jobbra 1, balra viszont legalább 2, mert az Y csúcsnak legalább 1-1 levél fia van. Tehát belső csúcsnál ilyen állapot nem állhat fent.
- Az első 2 esetben azt bizonyítottuk, hogy levél testvére lehet levél, vagy piros csúcs.
- A 3. esetben pedig azt, hogy nem lehet fekete csúcs a levél testvére.
- Így be is bizonyítottuk, hogy levél testvére CSAK levél, vagy piros csúcs lehet.