„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés
| (9 közbenső módosítás, amit 4 másik szerkesztő végzett, nincs mutatva) | |||
| 1. sor: | 1. sor: | ||
{{Vissza|Algoritmuselmélet}} | |||
==2013.04.03. ZH megoldásai== | ==2013.04.03. ZH megoldásai== | ||
===1. Feladat=== | ===1. Feladat (Van megoldás)=== | ||
Mi az a legkisebb ''r'' racionális szám, melyre teljesül, hogy <math>\sqrt{1} + \sqrt{2} + \sqrt{3} + ...+\sqrt{n} = O(n^{r}) ?</math> | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
*Először megpróbáljuk felülről becsülni: | |||
**Felülről becsüljük a sorozatot, ha az elemeket rendre <math>\sqrt{n}</math>-nek tekintjük, vagyis:<br><br> | |||
**<math>\sqrt{n} + \sqrt{n} + \sqrt{n} + ...+\sqrt{n}=n\cdot\sqrt{n}=n^{1.5}=O(n^{1.5}) \Rightarrow r=1.5</math><br><br> | |||
*Most pedig megpróbáljuk alulról becsülni: <br><br> | |||
**Alulról becsüljük a sorozatot: <br><br> | |||
**<math> \frac{n}{2 } \cdot \sqrt{1}+\frac{n}{2} \cdot \sqrt{n} \leq \sqrt{1} + \sqrt{2} + \sqrt{3} \dots \sqrt{n} </math> <br><br> | |||
**<math> \frac{n}{2 } \cdot \sqrt{1}+\frac{n}{2} \cdot \sqrt{n} = O(n^{1.5}) \Rightarrow r=1.5. </math> <br><br> | |||
*A kettőt együttvéve látszik, hogy <math> r = 1.5 .</math> | |||
}} | }} | ||
| 37. sor: | 46. sor: | ||
*A keresett <math> k,l </math> párost pedig folyamat nyilván tartjuk: ha <math> B[i,j] \geq aktmax \Rightarrow k=i, l=j, aktmax = B[i,j] </math>. ''(ez <math>\Rightarrow n^2-1=O(n^2)</math> lépés)'' | *A keresett <math> k,l </math> párost pedig folyamat nyilván tartjuk: ha <math> B[i,j] \geq aktmax \Rightarrow k=i, l=j, aktmax = B[i,j] </math>. ''(ez <math>\Rightarrow n^2-1=O(n^2)</math> lépés)'' | ||
*<math> 1+2O(n)+ 3O(n^2)=O(n^2)</math> lépésszámú algoritmusunk van, tehát jók vagyunk. | *<math> 1+2O(n)+ 3O(n^2)=O(n^2)</math> lépésszámú algoritmusunk van, tehát jók vagyunk. | ||
:::::::::::::::::[[File: | :::::::::::::::::[[File:Algel zh 2013tavasz A B matrix.PNG|400px]] | ||
}} | }} | ||
| 53. sor: | 62. sor: | ||
*Szokásos rendezést használó bináris keresőfa: <math>bal(x) < x < jobb(x)</math> | *Szokásos rendezést használó bináris keresőfa: <math>bal(x) < x < jobb(x)</math> | ||
*Postorder: | *Postorder: | ||
**Rekurzívan <math> bal(x) \rightarrow jobb(x) \rightarrow x </math>. 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. | **Rekurzívan <math> bal(x) \rightarrow jobb(x) \rightarrow x </math>.''(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'''. | **Egyik fontos tulajdonsága, hogy a '''gyökér''' az mindig a ''(figyelt)'' '''lista végén van'''. | ||
}} | }} | ||
| 64. sor: | 73. sor: | ||
**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 <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet. | **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 <math> < > < </math> sorrend van, ebből következik, hogy ilyen fa nem létezhet. | ||
::::::::::[[File: | ::::::::::[[File:Algel zh 2013tavasz Post tabla.png|400px]] [[File:Algel zh 2013tavasz Graf.png|300px]] | ||
}} | }} | ||
| 81. sor: | 90. sor: | ||
**A Dijkstra-algoritmus <math> O(n^2) </math> lépésben keres legrövidebb utat, ebben az esetben <math> O((2n)^2)=4O(n^2)=O(n^2)</math>. | **A Dijkstra-algoritmus <math> O(n^2) </math> lépésben keres legrövidebb utat, ebben az esetben <math> O((2n)^2)=4O(n^2)=O(n^2)</math>. | ||
*Így a feladat ezzel meg is oldva. | *Így a feladat ezzel meg is oldva. | ||
::::::::::[[File: | ::::::::::[[File:Algel zh 2013tavasz Csucs suly.png|300px|G gráf]][[File:Algel zh 2013tavasz El suly.png|400px|F 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. | |||
--[[Szerkesztő:Deák Zsolt|Deák Zsolt]] ([[Szerkesztővita:Deák Zsolt|vita]]) 2015. április 8., 12:22 (UTC) | |||
}} | }} | ||
===5. Feladat=== | ===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(n<sup>6</sup>) 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.)'' | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
*A megoldáshoz először Floyd algoritmussal páronként meghatározzuk az összes város távolságát, ez O(n<sup>3</sup>).<br> | |||
*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(n<sup>2</sup>).<br> | |||
*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.<br> | |||
**n<sup>5</sup> 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(n<sup>5</sup>*n)=O(n<sup>6</sup>).<br> | |||
*Összességében ezért O(n<sup>6</sup>) lépésszámú az algoritmus. | |||
}} | }} | ||
===6. Feladat=== | ===6. Feladat (Van megoldás)=== | ||
Egy tömbben adott <math>n</math> darab 0-tól különböző egész szám (lehetnek negatívak is köztük) és adott egy <math>k</math> egész szám is. Adjon <math>O(n \cdot logn)</math> lépésszámú algoritmust, ami eldönti, hogy melyik az a <math>k</math> elem a tömbben, melyek szorzata maximális. | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
*Első lépésben csökkenő sorrendbe rendezzük az elemeket azok '''abszolút értéke''' szerint. <math> (O(n \cdot logn) </math> pl. összefésüléses rendezéssel. <math>)</math> | |||
*Vesszük az első <math>k</math> szám szorzatát. | |||
**Ha ez pozitív, akkor jók vagyunk, nincs más dolgunk. [[File:algel_zh_2013tavasz_6_1.PNG|250px]] | |||
**Ha ez negatív, akkor kiválasztjuk a listából a legkisebb pozitív <math>(A^+)</math> és negatív <math>(A^-)</math> elemet, a maradék listából pedig a legnagyobb pozitív <math>(B^+)</math> és negatív <math>(B^-)</math> elemet. Most meg kell nézni, hogy mit éri meg lecserélni? A pozitívat negatívra, vagy a negatívat pozitívra? | |||
***Ha <math> (A^- \cdot B^-) < (A^+ \cdot B^+) </math>, akkor a listából kivesszük <math> A^- </math>-t, és berakjuk <math> B^+ </math>-t | |||
***Ha <math> (A^+ \cdot B^+) < (A^- \cdot B^-) </math>, akkor a listából kivesszük <math> A^+ </math>-t, és berakjuk <math> B^- </math>-t<br>[[File:algel_zh_2013tavasz_6_2.PNG|500px]] | |||
***Ha nincs a listában pozitív szám, akkor kivesszük a <math>A^-</math>-t, és berakjuk <math>B^+</math>-t<br>[[File:algel_zh_2013tavasz_6_3.PNG|500px]] | |||
***Ha nincs az egész listában pozitív szám, akkor a legnagyobb számot akkor kapjuk, ha a <math>k</math> darab utolsó elemet vesszük be.<br>[[File:algel_zh_2013tavasz_6_4.PNG|500px]] | |||
}} | }} | ||
| 160. sor: | 182. sor: | ||
*Nem. A gyökérnek feketének kell lennie. | *Nem. A gyökérnek feketének kell lennie. | ||
}} | }} | ||
[[Kategória:Infoalap]] | |||