Algoritmuselmélet - Vizsga, 2013.05.30.

A VIK Wikiből


2013.06.06. vizsga megoldásai

1. Feladat

Ebben a feladatban a Floyd algoritmussal kapcsolatos kérdésekre kell válaszolnia. (A Floyd-algoritmus egy grában minden pontpárra meghatározza a köztük levő legrövidebb út hosszát.)

(a) Mit jelöl az Fk mátrix Fk[i,j] eleme?

(b) Hogyan kell kiszámolni az Fk1 mátrixból az Fk mátrixot?

(c) Igazolja, hogy ez a kiszámítási mód helyes!

(d) Mennyi a lépésszáma a (b) lépés egyszeri végrehajtásának? (A lépésszámot nem kell igazolni.)

Megoldás

a) Fk[i,j] azon ij utak legrövidebbjeinek a hosszát tartalmazza, amelyek közbülső pontjai k-nál nem nagyobb sorszámúak. (Magyarul: Az Fk[i,j] azt mondja meg, hogy i-ből j-be mennyi a legrövidebb út összsúlya, ha csak az első k darab csúcsot használtuk.)

b) Fk[i,j]:=min{Fk1[i,k]+Fk1[k,j],Fk1[i,j]} (Vagyis vagy az ikj lesz a legrövidebb út, vagy "marad a régi" ij.)

c) Tulajdonképpen az előzőből következik. Hiszen vagy nem változik az új csúccsal a legrövidebb út a 2 pont között (ij), vagy ha igen, akkor az a (ik)+(kj) lesz az.

d) O(n2). (Maga az algoritmus O(n3), de csúcsonként O(n2), vagyis nO(n2)=O(n3)).

2. Feladat (Van megoldás)

Adja meg a 2-3 fa definícióját! Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!

Megoldás

Adja meg a 2-3 fa definícióját!

  • Elemeket csak a levelekben tárolunk.
  • Az elemek balról jobbra növekvő sorrendben állnak.
  • Minden belső csúcsnak 2, vagy 3 fia lehet, se több, se kevesebb. (Kivéve, ha csak 1 elemet tárolunk a fában, mert akkor a gyökérnek csak 1 fia van.)
  • A fa levelei a gyökértől egyenlő távolságra vannak (vagyis a levelek 1 szinten vannak).
  • A belső csúcsokban mutatókat (M) és 1, vagy 2 kulcsot (S) tárolunk.
    • Ha a csúcsnak 2 fia van, akkor 2 mutatót, és egy kulcsot tárol.
      • A bal részfában az elemek kisebbek, mint S1.
      • A jobb részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1).
    • Ha a csúcsnak 3 fia van, akkor 3 mutatót, és 2 kulcsot tárol.
      • A bal részfában az elemek kisebbek, mint S1.
      • A középső részfában az elemek nagyobb-egyenlőek, mint S1 (vagyis az 1. elem S1), de kisebbek, mint S2.
      • A jobb részfában az elemek nagyobb-egyenlőek, mint S2 (vagyis az 1. elem S2).

Adjon felső becslést a fa szintszámára n tárolt elem esetén, állítását bizonyítsa is!

log2n+1mlog3n+1, ahol m a fa szintszáma.

$$$ Ez nem pont fordítva van a dián? $$$

Bizonyítás:

  • log2n+1m
    • Minden belső csúcsnak legalább 2 fia van, így az i. szinten legalább 2i1 csúcs van, tehát: 2m1nm1log2nmlog2n+1
  • mlog3n+1
    • Minden belső csúcsnak maximum 3 fia van, így az i. szinten maximum 3i1 csúcs van, tehát: 3m1nm1log3nmlog3n+1

3. Feladat

TODO

Megoldás
TODO

4. Feladat (Van megoldás)

Van egy tábla (n x m kockákból álló). Az A n x m-es mátrixban adott, hogy az egyes kockákban hány mogyoró van (a mogyorók nem lógnak át egyik kockából a másikba). Két gyerek akar osztozkodni a csokin, úgy, hogy a csokit kéfelé törik (egyenes vonal mentén, párhuzamosan a tábla valamelyik szélével). Egy osztkozkodás igazságtalansági faktorát a következőképpen kaphatjuk: ha az egyik darabban k1 kocka csoki, és m1 darab mogyoró van, a másikban pedig k2 kocka csoki és m2 darab mogyoró, akkor az igazságtalansági faktor |(k1+m1)(k2+m2)|. Adjon O(nm) lépést használó algoritmust, ami eldönti, hogy melyik szétosztásnak a legkisebb az igazságtalansági faktora. (Egy lépésnek számít, ha kiolvasunk egy értéket az A mátrixból vagy ha összeadást, illetve kivonást hajtunk végre két számon.)

Megoldás

  • Hozzunk létre egy n elemű TN tömböt, ahol az i. cellában az szerepel, hogy az A mátrix annyiadik oszlopában mennyi a k+m. (ez n*m kiolvasás, és n*(m1) összeadás, vagyis O(nm).
  • Hozzunk létre egy m elemű TM tömböt, ahol az i. cellában az szerepel, hogy az A mátrix annyiadik sorában mennyi a k+m. (ez m*n kiolvasás, és m*(n1) összeadás, vagyis O(nm).

  • Hozzunk létre egy (n1) x 2-es N tömböt, ahol az 1. sorban balról jobbra nézzük, mennyi a k+m, a 2. sorban pedig jobbról balra. (1. sor a (k1+m1), 2. sor pedig a hozzá tartozó (k2+m2).)
    • N[1,1]=TN[1] majd N[i,1]=N[i1,1]+TN[i],i=2...(n1).
    • N[1,2]=i=2nTN[i] majd N[i,2]=N[i1,2]TN[i],i=2...(n1).
  • Hozzunk létre egy (m1) x 2-es M tömböt, ahol az 1. sorban fentről lefele nézzük, mennyi a k+m, a 2. sorban pedig alulról felfele. (1. sor a (k1+m1), 2. sor pedig a hozzá tartozó (k2+m2).)
    • M[1,1]=TM[1] majd M[i,1]=M[i1,1]+TM[i],i=2...(m1).
    • M[1,2]=i=2mTM[i] majd M[i,2]=M[i1,2]TM[i],i=2...(m1).

  • Az N és M tömbök létrehozása O(n) és O(m) lépést igényel.
  • Nincs is más dolgunk, mint végigmenni az N és M tömbökön úgy, hogy az i. oszlopban vesszük a 2 szám különbségének abszolút értékét, vagyis az igazságtalansági faktort számoljuk, és mindig elmentjük egy változóba a minimumot, és a ehhez tartozó törésvonalat. Ez is O(n) és O(m) lépés.
  • Összesen tehát O(nm)+O(nm)+O(n)+O(m)+O(n)+O(m)=O(nm) lépéssel megoldottuk a feladatot.

5. Feladat (Van megoldás)

Egy algoritmus lépésszámáról tudjuk, hogy T(n)=T(n4)+O(n2) és tudjuk azt is, hogy T(1)=T(2)=T(3)=1. Bizonyítsa be, hogy T(n)=O(n2).

Megoldás

Van olyan c>0 és n0, hogy n>n0 esetén T(n)=T(n4)+O(n2)T(n4)+cn2T(n16)+c(n2+(n242))T(n64)+c(n2+(n242)+(n2162)) 1+cn2(i=0log4n(116)i)

Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:
i=0kri=1rk+11r, ahol k=log4n,r=116, vagyis 1116log4n+11116

1116log4n+11116<2,ha n1 (A lényeg, hogy felülről becsüljük!)

Tehát T(n)=1+2cn2=O(n2)

6. Feladat (Van megoldás)

Egy ország n kis szigetből áll. Szeretnénk néhány hajójáratot indítani a szigetek között úgy, hogy bárhonnan bárhova el lehessen jutni (esetleg átszállással). Ehhez ismerjük bármely két szigetre, hogy mennyibe kerül egy évben a hajójárat fenntartása közöttük, illetve azt, hogy mekkora az itt várható éves bevétel. Adjon algoritmust, ami ezen adatok ismeretében O(n2) időben meghatározza, hogy hol indítsuk el a hajójáratokat, ha a lehető legnagyobb várható éves hasznot (vagy a lehető legkisebb veszteséget) szeretnénk elérni. (Egy szigeten egy hajóállomás van csak).

Megoldás
  • Első lépésben az élsúly legyen a Profit=(BevetelKiadas).
  • Vegyük fel az összes profitot termelő, vagy legalábbis veszteséget nem termelő éleket (Profit0) O(n2) lépés. Ez legyen mondjuk a G gráf.
  • Két eshetőség áll fenn:
    • Ha a G gráf összefüggő, akkor jók is vagyunk, nincs további teendőnk, meg is vagyunk.
    • Ha nem összefüggő, akkor:
      • Az egyes komponenseket tekintsük egy pontnak. Minden olyan él, ami ebbe a komponensbe megy, menjen ebbe a pontba. Így kapunk egy F gráfot.
      • Erre az F gráfra hívunk meg egy Prim-algoritmust, ami O(n2) időben keres az F gráfban egy minimális feszítőfát (vagyis a komponenseket - ami most jelenleg 1-1 pont a gráfban - a lehető legkisebb költségű élekkel köti össze).
  • Tehát Prim-algoritmussal, vagy anélkül O(n2) időben megmondjuk, hogy mely hajójáratok indításával lesz az évi bevétel a legmagasabb.

7. Feladat

TODO

Megoldás
TODO

8. Feladat

TODO

Megoldás
TODO