Algoritmuselmélet - ZH, 2013.04.03.

A VIK Wikiből
(Algoritmuselmélet 2013.04.03. ZH megoldásai szócikkből átirányítva)


2013.04.03. ZH megoldásai

1. Feladat (Van megoldás)

Mi az a legkisebb r racionális szám, melyre teljesül, hogy 1+2+3+...+n=O(nr)?

Megoldás
  • Először megpróbáljuk felülről becsülni:
    • Felülről becsüljük a sorozatot, ha az elemeket rendre n-nek tekintjük, vagyis:

    • n+n+n+...+n=nn=n1.5=O(n1.5)r=1.5

  • Most pedig megpróbáljuk alulról becsülni:

    • Alulról becsüljük a sorozatot:

    • n21+n2n1+2+3n

    • n21+n2n=O(n1.5)r=1.5.

  • A kettőt együttvéve látszik, hogy r=1.5.

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(n2) 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 ik,jlA[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[i1,j]+B[i,j1]+A[i,j]B[i1,j1] 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 O(n2) lépés)
  • B[1,1]:=A[1,1]. (ez 1 lépés)
  • k=l=1 és aktmax=B[1,1].
  • Először kitöltjük az 1. sort B[i,1]:=B[i1,1]+A[i,1],i=2n. (ez 2(n1)=O(n) lépés)
  • Majd kitöltjük az 1. oszlopot B[1,i]:=B[1,i1]+A[1,i],i=2n. (ez 2(n1)=O(n) lépés)
  • Minden további cellában pedig B[i,j]=B[i1,j]+B[i,j1]+A[i,j]B[i1,j1]. (ez 4(n1)(n1)=O(n2) lépés)
  • A keresett k,l párost pedig folyamat nyilván tartjuk: ha B[i,j]aktmaxk=i,l=j,aktmax=B[i,j]. (ez n21=O(n2) lépés)
  • 1+2O(n)+3O(n2)=O(n2) lépésszámú algoritmusunk van, tehát jók vagyunk.
  • 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)jobb(x)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.
  • 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(n2) 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(n2) lépésben keres legrövidebb utat, ebben az esetben O((2n)2)=4O(n2)=O(n2).
    • Így a feladat ezzel meg is oldva.
    G gráfF gráf

    Talán egyszerűbben: mivel 0 az utazási idő (élsúlyok) és bármerre megyünk egy csúcsból, ugyanannyit kell várni, ezért tekinthetjük a csúcsból kimenő élek súlyának a csúcsban töltött időt (A-ból 0, mivel itt nem várakozunk, B-ből nem megyünk tovább...). Így az eredeti gráfon (az élsúlyok beírása után) alkalmazható a Dijkstra algo.

    --Deák Zsolt (vita) 2015. április 8., 12:22 (UTC)

    5. Feladat

    Adjacencia-mátrixával adott n csúcsú, élsúlyozott, irányítatlan gráfként ismerjük egy ország úthálózatát (a csomópontok a városok, az élek a közvetlen összeköttetések a városok között). Az élek súlya a városok közti távolságot adja meg. (Feltehetjük, hogy a távolságok egészek.) Adjon egy O(n6) lépésszámú algoritmust, ami eldönti, hogy lehetséges-e úgy kiválasztani öt várost, hogy ezektől bármely más város legfeljebb 50 kilométerre van. (Ezekbe a városokba lenne érdemes hókoztrókat telepíteni.)

    Megoldás
    • A megoldáshoz először Floyd algoritmussal páronként meghatározzuk az összes város távolságát, ez O(n3).
    • A város irányítatlan gráfként van megadva, de ezen könnyen segíthetünk úgy, hogy a jelenlegi élek helyett felveszünk két irányítottat, azonos súllyal. Ez O(n2).
    • Ezek után brute force módszerrel az összes csúcsötösre ellenőrizzük, hogy azok öten lefedik-e (legfeljebb 50 km-re vannak) az összes várost.
      • n5 városötös van, mindegyikre le kell ellenőrizni, hogy jók-e. Az ellenőrzés során végignézzük, az összes csúcsra (n db.), hogy el lehet-e érni. Ez tehát O(n5*n)=O(n6).
    • Összességében ezért O(n6) lépésszámú az algoritmus.

    6. Feladat (Van megoldás)

    Egy tömbben adott n darab 0-tól különböző egész szám (lehetnek negatívak is köztük) és adott egy k egész szám is. Adjon O(nlogn) lépésszámú algoritmust, ami eldönti, hogy melyik az a k elem a tömbben, melyek szorzata maximális.

    Megoldás
    • Első lépésben csökkenő sorrendbe rendezzük az elemeket azok abszolút értéke szerint. (O(nlogn) pl. összefésüléses rendezéssel. )
    • Vesszük az első k szám szorzatát.
      • Ha ez pozitív, akkor jók vagyunk, nincs más dolgunk.
      • Ha ez negatív, akkor kiválasztjuk a listából a legkisebb pozitív (A+) és negatív (A) elemet, a maradék listából pedig a legnagyobb pozitív (B+) és negatív (B) elemet. Most meg kell nézni, hogy mit éri meg lecserélni? A pozitívat negatívra, vagy a negatívat pozitívra?
        • Ha (AB)<(A+B+), akkor a listából kivesszük A-t, és berakjuk B+-t
        • Ha (A+B+)<(AB), akkor a listából kivesszük A+-t, és berakjuk B-t
        • Ha nincs a listában pozitív szám, akkor kivesszük a A-t, és berakjuk B+-t
        • Ha nincs az egész listában pozitív szám, akkor a legnagyobb számot akkor kapjuk, ha a k darab utolsó elemet vesszük be.

    7. Feladat (Van megoldás)

    Az A[12013] tömbben egy kupac adatstruktúrát tárolunk, minden tárolt elem különböző. Tudjuk, hogy ebben a kupacban a legnagyobb elem A[i]. Határozza meg i összes lehetséges értékét!

    Megoldás
    • Kupac egyik jó tulajdonsága, hogy teljes bináris fa, így az elem számból kiszámolható, hogy milyen magas a fa.
      • Tudjuk, hogy :2m1n2m1.
      • Ebben az esetben 2m120132m1m=11.
    • A legnagyobb elem vagy a legalsó szinten van, vagy ha az nem "telített", akkor az előtte lévő szinten olyan csúcsok is szóba jöhetnek, akiknek nincsen gyereke.
      • Mivel tudjuk, hogy a fa magassága 11, ezért:
        • A kupacban összesen 2047 elemnek van hely, tehát még 34 elem férne el. Ebből pedig az következik, hogy a 10. szinten 17 olyan csúcs van, aminek nincsen fia, így ők még játszhatnak a legnehezebb elem díjáért.
        • A 11. szinten 1024 elem férne el, de tudjuk, hogy hiányzik 34, tehát a 11. szinten csak 990 elem van, amik a legnehezebbek lehetnek a fában.
    • Ha a kupacot tömbbe írjuk, akkor azt fentről-lefele, balról-jobbra töltjük fel.
      • Az előzőek alapján tudjuk, hogy a 11. szinten 990, a 10. szinten pedig 17 csúcs jöhet szóba, így összesen 1007 helyen lehet a legnehezebb elem. A tömbös elrendezés alapján ez azt jelenti, hogy az i(20131007+1)i1007.
    Avagy...
    • Avagy bebizonyítható, hogy a legnagyobb elem az az utolsó n2 helyen állhat.

    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.