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

A VIK Wikiből
← Régebbi szerkesztés
VizuálisWikiszöveges
Arklur (vitalap | szerkesztései)
381 szerkesztés
Geriboss (vitalap | szerkesztései)
29 szerkesztés
a elírások javítva
 
(20 közbenső módosítás, amit 4 másik szerkesztő végzett, nincs mutatva)
1. sor: 1. sor:
{{Vissza|Algoritmuselmélet}}
==2013.04.24. PZH megoldásai==
==2013.04.24. PZH megoldásai==
===1. Feladat (Van megoldás)===
===1. Feladat (Van megoldás)===
6. sor: 8. sor:
|szöveg=
|szöveg=


<math> T(n) = T\left(\left \lfloor  \frac{n}{4} \right \rfloor\right) + O(n^2) = T\left(\left \lfloor  \frac{n}{16} \right \rfloor\right) + O\left(\frac{n^2}{4} \right) + O(n^2)=...=1 + O(n^2)*\left(\sum_{i=0}^{\left \lfloor log_4n \right \rfloor} \left (\frac{1}{4}  \right )^i\right)</math><br>
Van olyan <math> c > 0</math> és <math> n_0</math>, hogy <math> n>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:<br>
Azt kell észrevennünk, hogy ez tulajdonképpen egy mértani sor, amire van képletünk:<br>
<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 = 0.25</math>, vagyis <math>\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25}</math><br>
<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><br>
<math> \lim_{n \to \infty}\frac{1-0.25^{\left \lfloor log_4n \right \rfloor+1}} {1-0.25} = \frac{1}{0.75}</math><br>
 
Tehát <math> T(n)=...=1+\frac{1}{0.75}O(n^2)=O(n^2)</math>
<math>\frac{1-\frac{1}{16}^{\left \lfloor log_4n \right \rfloor+1}} {1-\frac{1}{16}} < 2 ,</math><big>ha</big> <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===
===2. Feladat (Van megoldás)===
TODO
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 lehető legnagyobb az összes ilyen csúcs közül.
{{Rejtett
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
|szöveg=
 
{{Rejtett
TODO
|mutatott=<big>''Megjegyzések a feladathoz''</big>
|szöveg=
*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) > 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) < x</math> VAGY <math>JOBB(x) < 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).''
Mivel minden csúcsot csak egyszer látogatunk meg, így <math>O(n)</math> lépésben megyünk végig a gráfon.
}}
}}


25. sor: 44. sor:
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
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?
'''(a)''' inorder bejárással kiolvasva 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?
'''(b)''' preorder bejárással kiolvasva a két fát ugyanazt a számsorozatot kapják?
35. sor: 54. sor:
*'''a)'''
*'''a)'''


[[File:egyik.png|200px]]    [[File:masik.png|200px]]
[[File:Algel_pzh_2013tavasz_Egyik.png|200px]]    [[File:Algel_pzh_2013tavasz_Masik.png|200px]]


Mindkét gráfot A-B-C-D-E sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.
Mindkét gráfot A-B-C-D-E sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.
41. sor: 60. sor:
*'''b)'''
*'''b)'''


[[File:egyik_1.png|200px]]    [[File:masik_2.png|200px]]
[[File:Algel_pzh_2013tavasz_Egyik_1.png|200px]]    [[File:Algel_pzh_2013tavasz_Masik_2.png|200px]]


Mindkét gráfot F-G-H-J-K sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.
Mindkét gráfot F-G-H-J-K sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.
48. sor: 67. sor:


===4. Feladat===
===4. Feladat===
TODO
Éllistá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 azt adja meg, hogy hány (egész) perc alatt tudjuk megtenni az adott útszakaszt. Nagy havazás várható, de szerencsére pontosan tudjuk a következő k percre, hogy mely élek (utak) mikortól nem lesznek járhatóak. Ha egyszer járhatatlanná válnak, akkor úgy is maradnak, ezután már az úton nem lehet közlekedni, és ha épp az adott élen vagyunk, amikor az járhatatlanná válik, akkor elakadunk.
Adjon O(k(n+e)) lépést használó algoritmust, ami az adatok ismeretében el tudja dönteni, hogy el lehet-e jutni A városból B városba, ha most azonnal elindulunk!
{{Rejtett
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|mutatott=<big>'''Megoldás'''</big>
56. sor: 76. sor:
}}
}}


===5. Feladat===
===5. Feladat (Van megoldás)===
TODO
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!
{{Rejtett
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
|szöveg=


TODO
*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.
:::::::::::::::::[[File:algel_pzh_2013tavasz_5_1.PNG|400px]]
}}
}}


===6. Feladat===
===6. Feladat (Van megoldás)===
TODO
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> )<sup>1</sup> összehasonlítást használó algoritmust, ami meghatározza <math> k </math> értékét.
 
''<sup>1</sup> A feladatban <math> O(logk) </math> szerepel, de az csak elgépelés.''
{{Rejtett
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
|szöveg=


TODO
*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<sup><big>(1)</big></sup> 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>.
 
<sup><big>(1)</big></sup> '' 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.''
:::::::::::[[File:algel_pzh_2013tavasz_6_1.PNG|400px]]
 
*Az algoritmus működése alapján belátható, hogy <math> O(logk) </math> időben fut.
}}
}}


===7. Feladat===
===7. Feladat===
TODO
Adott egy n és egy k elemet tartalmazó kupac. Adjon olyan O(n + k) összehasonlítást használó algoritmust, ami létrehoz egy olyan kupacot, ami a két kupacban tárolt elemek halmazának unióját tartalmazza. (TFH a két kupacban csupa különböző számocska áll.)
{{Rejtett
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|mutatott=<big>'''Megoldás'''</big>
83. sor: 130. sor:
}}
}}


===8. Feladat===
===8. Feladat (Van megoldás)===
TODO
Bizonyítsa be, hogy egy piros-fekete fában egy levél testvére vagy levél, vagy piros csúcs!
{{Rejtett
{{Rejtett
|mutatott=<big>'''Megoldás'''</big>
|mutatott=<big>'''Megoldás'''</big>
|szöveg=
|szöveg=


TODO
*Összesen 5 felállás lehet: [[File:algel_pzh_2013tavasz_8_1.png|400px]]
**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: [[File:Algel pzh 2013tavasz 8 2.png|100px]]
**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.
}}
}}
[[Kategória:Infoalap]]

A lap jelenlegi, 2014. március 30., 17:34-kori változata


2013.04.24. PZH megoldásai

1. 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

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 lépésben megkeres egy olyan csúcsot a fában, aminek a részfája kupac, és aminek a magassága a lehető legnagyobb az összes ilyen csúcs közül.

Megoldás
Megjegyzések a feladathoz
  • 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 .
  • 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle (JOBB(x), BAL(x))} .
    • Megnézzük, hogy nagyobbak-e, mint x, majd megnézzük, hogy kupac tulajdonsággal bírnak-e:
      • Ha Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle BAL(x),JOBB(x) > x;BAL(x).B=JOBB(x).B=IGAZ\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := IGAZ} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle BAL(x) < x} VAGY Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle JOBB(x) < x} VAGY Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle BAL(x).B=HAMIS} VAGY Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle JOBB(x).B=HAMIS\Rightarrow\Rightarrow x.M := BAL(x).M+1, x.B := HAMIS} . 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).
Mivel minden csúcsot csak egyszer látogatunk meg, így Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(n)} lépésben megyünk végig a gráfon.

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 kiolvasva 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?

Megoldás

Mindkét esetben 1-1 ellenpéldát kell szolgáltatni:

  • a)

Mindkét gráfot A-B-C-D-E sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.

  • b)

Mindkét gráfot F-G-H-J-K sorrendben olvassuk ki, de mégsem egyeznek meg, tehát nem következik.

4. Feladat

Éllistá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 azt adja meg, hogy hány (egész) perc alatt tudjuk megtenni az adott útszakaszt. Nagy havazás várható, de szerencsére pontosan tudjuk a következő k percre, hogy mely élek (utak) mikortól nem lesznek járhatóak. Ha egyszer járhatatlanná válnak, akkor úgy is maradnak, ezután már az úton nem lehet közlekedni, és ha épp az adott élen vagyunk, amikor az járhatatlanná válik, akkor elakadunk. Adjon O(k(n+e)) lépést használó algoritmust, ami az adatok ismeretében el tudja dönteni, hogy el lehet-e jutni A városból B városba, ha most azonnal elindulunk!

Megoldás
TODO

5. Feladat (Van megoldás)

Egy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n} soros és kettő oszlopos táblázatban adott Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(n)} lépésben megoldja a feladatot!

Megoldás
  • Rendezzük a tömböt az 1. oszlop szerint növekvően.
  • A továbbiakban minden Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i.} lépésben megkeressük az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i.} legkisebb elemet, és a helyére tesszük.
    • Megkeressük a 2. oszlopban az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i.} legkisebbet, az ő helye a tömbben legyen Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k}
    • Mivel az 1. oszlop szerint növekvően vannak a számpárok, így ahhoz, hogy a Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k.} elem az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i.} helyre kerüljön, a számokat csökkenő sorrendbe kell rendezni az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle [i \rightarrow k] } intervallumon.
    • Ha ezt megcsináltuk, akkor az első Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i} helyen már rendezve lesz a tömb.
    • Az Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle [i+1 \rightarrow n]} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle \approx 2n} alkalommal használjuk:
    • Először növekvő sorrendbe rendeztük az egész tömböt.
    • Utána minden Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle i.} 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(n)} lépéssel rendezi a számpárokat a 2. oszlop szerint.

6. Feladat (Van megoldás)

Adott egy Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle n } hosszú tömb. Tudjuk, hogy a tömb első néhány (Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k } darab) elem 0, a többi 1, de Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k } értékét nem ismerjük. Adjon Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(logk) } (nem Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(logn) } )1 összehasonlítást használó algoritmust, ami meghatározza Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k } értékét.

1 A feladatban Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle O(logk) } szerepel, de az csak elgépelés.

Megoldás
  • Először nézzük meg, hogy az első 2 elem Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 0-1} -e, ha igen, akkor Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle k=1 } .
  • Ha nem, akkor minden további lépésnél ugorjunk a 2x annyiadik cellába (ez legyen Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle m } ), 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 Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 0-0-0} -t látunk, akkor ugrunk megint 2x akkorát (ugyanazzal a kritériummal, mint előbb).
    • Ha Értelmezés sikertelen (SVG (a MathML egy böngészőkiegészítővel engedélyezhető): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) https://wikimedia.org/api/rest_v1/ szervertől:): {\displaystyle 0-0-1} -t látunk, akkor .
    • Ha -t látunk, akkor .
    • Ha -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 , vagy felállást, és a értékét a látottak alapján beállítjuk vagy .

(1) Ha -t lát, jobbra lép, ha -t, akkor balra, másik 2 esetben pedig találatunk van.

  • Az algoritmus működése alapján belátható, hogy időben fut.

7. Feladat

Adott egy n és egy k elemet tartalmazó kupac. Adjon olyan O(n + k) összehasonlítást használó algoritmust, ami létrehoz egy olyan kupacot, ami a két kupacban tárolt elemek halmazának unióját tartalmazza. (TFH a két kupacban csupa különböző számocska áll.)

Megoldás
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!

Megoldás
  • Ö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.
A lap eredeti címe: „https://vik.wiki/index.php?title=Algoritmuselmélet_-_PZH,_2013.04.24.&oldid=180150”