„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés

A VIK Wikiből
95. sor: 95. sor:
}}
}}


===6. Feladat===
===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 <math>O(n^2)</math> 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).
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 <math>O(n^2)</math> 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).
{{Rejtett
{{Rejtett
101. sor: 101. sor:
|szöveg=
|szöveg=


TODO
*Első lépésben az élsúly legyen a <math> Profit = -(Bevetel - Kiadas) .</math>
*Vegyük fel az összes profitot termelő, vagy legalábbis veszteséget nem termelő éleket <math> (Profit \geq 0 )</math> <math> \Rightarrow O(n^2) </math> 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 <math> O(n^2) </math> 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 <math> O(n^2) </math> időben megmondjuk, hogy mely hajójáratok indításával lesz az évi bevétel a legmagasabb.
}}
}}



A lap 2013. június 17., 19:25-kori változata


2013.06.06. vizsga megoldásai

1. Feladat

TODO

Megoldás
TODO

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. Fájl:2 3 2.png
      • 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. Fájl:2 3 3.png
      • 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).
Fájl:2 3 pelda.PNG

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

, ahol a fa szintszáma.

Bizonyítás:

    • Minden belső csúcsnak legalább 2 fia van, így az szinten legalább csúcs van, tehát:
    • Minden belső csúcsnak maximum 3 fia van, így az szinten maximum csúcs van, tehát:

3. Feladat

TODO

Megoldás
TODO

4. Feladat (Van megoldás)

Van egy tábla x kockákból álló. Az x -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 kocka csoki, és darab mogyoró van, a másikban pedig kocka csoki és darab mogyoró, akkor az igazságtalansági faktor . Adjon 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 mátrixból vagy ha összeadást, illetve kivonást hajtunk végre két számon.)

Megoldás

Algel vizsga1 2013tavasz 4 csoki.PNG

  • Hozzunk létre egy elemű tömböt, ahol az cellában az szerepel, hogy az mátrix annyiadik oszlopában mennyi a . (ez kiolvasás, és összeadás, vagyis .
  • Hozzunk létre egy elemű tömböt, ahol az cellában az szerepel, hogy az mátrix annyiadik sorában mennyi a . (ez kiolvasás, és összeadás, vagyis .

Algel vizsga1 2013tavasz 4 tn tm.PNG

  • Hozzunk létre egy x -es tömböt, ahol az 1. sorban balról jobbra nézzük, mennyi a , a 2. sorban pedig jobbról balra. 1. sor a , 2. sor pedig a hozzá tartozó
    • majd .
    • majd .
  • Hozzunk létre egy x -es tömböt, ahol az 1. sorban fentről lefele nézzük, mennyi a , a 2. sorban pedig alulról felfele. 1. sor a , 2. sor pedig a hozzá tartozó
    • majd .
    • majd .

Algel vizsga1 2013tavasz 4 N M.PNG

  • Az és tömbök létrehozása és lépést igényel.
  • Nincs is más dolgunk, mint végigmenni az és tömbökön úgy, hogy az 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 és lépés.
  • Összesen tehát lépéssel megoldottuk a feladatot.
Algel vizsga1 2013tavasz 4 1.PNG Algel vizsga1 2013tavasz 4 2.PNG

5. Feladat (Van megoldás)

Egy algoritmus lépésszámáról tudjuk, hogy és tudjuk azt is, hogy . Bizonyítsa be, hogy .

Megoldás

Van olyan és , hogy esetén

Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:
, ahol , vagyis

ha (A lényeg, hogy felülről becsüljük!)

Tehát

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 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
  • Vegyük fel az összes profitot termelő, vagy legalábbis veszteséget nem termelő éleket 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 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 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