Algoritmuselmélet - ZH, 2013.04.03.

2013.04.03. ZH megoldásai

1. Feladat

TODO

Megoldás

TODO

2. Feladat (Van megoldás)

Egy $A[i,j]$ $n$ x $n$-es táblázat minden mezőjében egy egész szám van írva (nem feltétlenül csak pozitívak). Adjon $O(n^{2})$ lépésszámú algoritmust, ami eldönti, hogy melyik az a téglalap alakú része a táblázatnak, melynek bal felső sarka egybe esik a nagy táblázat bal felső sarkával és benne az elemek összege az egyik legnagyobb.

(Vagyis olyan $k,l$-t keresünk, amire $\sum _{i\leq k,j\leq l}A[i,j]$ maximális.)

Megoldás

Megjegyzések a feladathoz

• Ahogy az többször is segít, úgy most is, hogy felrajzolunk magunknak egy 3x3, vagy 4x4-es táblázatot, és nézegetjük, hogyan kéne dolgozni...
• A feladatban 1-1 lépésnek vettem:
  • 1 művelet ($+,-$) elvégzését (vagyis a $B[i,j]=B[i-1,j]+B[i,j-1]+A[i,j]-B[i-1,j-1]$ 3 lépés).
  • 1 értéke beírása a cellába.
  • 1 összehasonlítás (és esetleges cserék).

Adott az $A$ mátrix.

Létrehozunk egy $B$ mátrixot (szintén $n$ x $n$-es).(ez $\Rightarrow O(n^{2})$ lépés)

$B[1,1]:=A[1,1]$. (ez $\Rightarrow 1$ lépés)

$k=l=1$ és $aktmax=B[1,1]$.

Először kitöltjük az 1. sort $\rightarrow B[i,1]:=B[i-1,1]+A[i,1],i=2\dots n$. (ez $\Rightarrow 2(n-1)=O(n)$ lépés)

Majd kitöltjük az 1. oszlopot $\rightarrow B[1,i]:=B[1,i-1]+A[1,i],i=2\dots n$. (ez $\Rightarrow 2(n-1)=O(n)$ lépés)

Minden további cellában pedig $B[i,j]=B[i-1,j]+B[i,j-1]+A[i,j]-B[i-1,j-1]$. (ez $\Rightarrow 4(n-1)(n-1)=O(n^{2})$ lépés)

A keresett $k,l$ párost pedig folyamat nyilván tartjuk: ha $B[i,j]\geq aktmax\Rightarrow k=i,l=j,aktmax=B[i,j]$. (ez $\Rightarrow n^{2}-1=O(n^{2})$ lépés)

$1+2O(n)+3O(n^{2})=O(n^{2})$ lépésszámú algoritmusunk van, tehát jók vagyunk.

Fájl:A B matrix.PNG

3. Feladat (Van megoldás)

Kaphatjuk-e az 1,7,3,6,11,15,22,17,14,12,9 számsorozatot úgy, hogy egy (a szokásos rendezést használó) bináris keresőfában tárolt elemeket posztorder sorrendben kiolvasunk?

Megoldás

Megjegyzések a feladathoz

• Szokásos rendezést használó bináris keresőfa: $bal(x)<x<jobb(x)$
• Postorder:
  • Rekurzívan $bal(x)\rightarrow jobb(x)\rightarrow x$. Magyarul előbb meglátogatja a gyökérnél kisebbeket, utána a nagyobbakat, és ezután jön csak a gyökér.
  • Egyik fontos tulajdonsága, hogy a gyökér az mindig a (figyelt) lista végén van.

Első lépésnek írjuk fel egy táblázatba a számokat (az oszlopszámot tudjuk, ez esetben 11, sorok száma meg majd alakul...).

A továbbiakban az i. sorban jelöljük, hogy melyik elem a gyökér (=), és hogy melyek a nála kisebbek (<), avagy nagyobbak (>) (a képen keretezéssel jelzem, hogy melyik az éppen figyelt lista). Ez azért hasznos, mert a posztorder bejárás során, ezzel a technikával mindig olyan sorrendet kell kapjunk, hogy $<<<...<<>>...>>=$, vagyis nem állhat fel olyan helyzet, hogy $...<><...=$ vagy $...><>...=$.

• Az 1. sorban a 9 lesz a gyökér. Felrajzoljuk a 9-t gyökérnek. (Bal oldalt lesz a hiba, de gyakorlásképp nézzük inkább a jobb oldalt.)
• A 2. sorban a 12 lesz a gyökér, így a 12-est felrajzoljuk a 9-es jobb fiának. Nála csak a 11 a kisebb (a vizsgált listában), így a 11-t berajzoljuk a 12 bal fiának.
• A 3. sorban 14 lesz a gyökér, így a 14-est felrajzoljuk a 12-es jobb fiának.
• A 4. sorban a 17 lesz a gyökér, így ez a 14-es jobb fia lesz. A 15 és 22 pedig értelemszerűen a bal, és jobb fia lesz 17-nek.
• Az 5. sorban a gyökér a 6 lesz, így azt berajzoljuk a 9-es bal fiának. És itt látszik is, hogy hiba van, hiszen $<><$ sorrend van, ebből következik, hogy ilyen fa nem létezhet.

Fájl:Post tabla.png Fájl:Graf.png

4. Feladat (Van megoldás)

Adjacencia-mátrixával adott $n$ csúcsú, irányított gráfként ismerjük egy város úthálózatát. El szeretnék jutni $A$ pontból $B$ pontba, de sajnos minden csomóponthoz várnunk kell a nagy hóesés miatt, a várakozás hossza minden csomópontra ismert és független attól, hogy merre akarunk továbbmenni. Adjon algoritmust, ami $O(n^{2})$ lépésben eldönti, hogy merre menjünk, hogy a lehető legkevesebbet kelljen várni összességében. (A csomópontok közötti utak hosszának megtétele a várakozáshoz képest elhanyagolható időbe telik, tekintsük 0-nak. $A$-ban és $B$-ben nem kell várakozni.)

Megoldás

• A "probléma", hogy a csúcsoknak van súlya (ill. az éleknek is van, de az 0), amivel nem igen tudunk mit kezdeni. De nem hiába volt BSZ1 (vagy BSZ2?), ahol megtanultuk, hogy könnyedén csinálhatunk a csúcssúlyból élsúlyt.
• Az adott pontot (X) lecseréljük 2 pontra (X1, X2). Ami eddig X-be ment, az menjen X1-be, és ami X-ből ment, az menjen X2-ből. (Vagyis X1-ből csak X2-be megy él, és X2-be csak az X1 megy.)
• A 2 pontot összekötjük, a köztük menő élsúly pedig az X pont súlya lesz.
• Csináljuk hát ezt ezzel a gráffal:
  • Az eredeti $n$ csúcsú G gráfból csinálunk így egy F gráfot, melyben $2n$ csúcs lesz (és az élszám is n-nel nő, de ez most minket annyira nem izgat).
  • Ebben az F gráfban kell megtalálni a legrövidebb utat egy "X2"-ből egy "Y1"-be.
  • A Dijkstra-algoritmus $O(n^{2})$ lépésben keres legrövidebb utat, ebben az esetben $O((2n)^{2})=4O(n^{2})=O(n^{2})$.
• Így a feladat ezzel meg is oldva.

G gráfF gráf

5. Feladat

TODO

Megoldás

TODO

6. Feladat

TODO

Megoldás

TODO

7. Feladat

TODO

Megoldás

TODO

8. Feladat (Van megoldás)

(a) Igaz-e, hogy egy piros-fekete fa tetszőleges belső fekete csúcshoz tartozó részfa (az a részfa, aminek ez a fekete csúcs a gyökere) is egy piros-fekete fa?

(b) Igaz-e ugyanez egy tetszőleges belső piros csúcshoz tartozó részfára?

Megoldás

Megjegyzések a feladathoz

• Avagy mitől is piros-fekete egy piros-fekete fa?

1. Minden nem levél csúcsnak 2 fia van.
2. Elemeket belső csúcsban tárolunk.
3. teljesül a keresőfa tulajdonság.
4. A fa minden csúcsa piros, vagy fekete.
5. A gyökér fekete.
6. A levelek feketék.
7. Minden piros csúcs mindkét gyereke fekete.
8. Minden v csúcsra igaz, hogy az összes v-ből levélbe vezető úton ugyanannyi fekete csúcs van (~fekete magasság).

a) Igaz-e, hogy egy piros-fekete fa tetszőleges belső fekete csúcshoz tartozó részfa (az a részfa, aminek ez a fekete csúcs a gyökere) is egy piros-fekete fa?

• Igaz. (Nem tudom, mennyi magyarázatot, vagy milyen indoklást várnak ide, de a piros-fekete tulajdonságai közül talán csak a fekete magasság szorul magyarázatra (...), a többi elég triviális.)
  • Ha a részgráfra nem állna fenn a fekete magasság kritériuma, akkor pláne nem fog a teljes gráfra teljesülni, hiszen hiába jó a fekete magasság a pontig, ha a pont tönkre teszi azt :/.

b) Igaz-e ugyanez egy tetszőleges belső piros csúcshoz tartozó részfára?

• Nem. A gyökérnek feketének kell lennie.