32

´ magvalos´ ´ ıtasok ´ Algoritmusok es

¨ Dr. Schuster Gyorgy OE-KVK-MAI [email protected]

´ 10. 2015. februar

¨ ´ magval)os´ ´ ıtasok ´ Dr. Schuster Gyorgy (OE-KVK-MAI [email protected] Algoritmusok es

´ 10. 2015. februar

1 / 32

Alapfogalmak

Algoritmus

Algoritmus

Defin´ıcio´ ´ ´ u´ lep ´ esekb ´ ˝ all ´ o´ Algoritmuson olyan megengedett vegessz am ol ´ ´ sorozatot, reszletes ´ ´ receptet modszert, utas´ıtas utmutat ´ ast, ´ unk, ´ ´ ara ´ ert ¨ amely valamely felmerult ¨ problema megoldas alkalmas.


´ 10. 2015. februar

2 / 32

Alapfogalmak

Algoritmus

Algoritmus ´ Tulajdonsagai: 1 2 3 4

´ as ´ egyertelm ´ ´ ¨ Az eljar uen ˝ le´ırhato´ veges szoveggel. ´ as ´ minden lep ´ ese ´ tenylegesen ´ ˝ Az eljar kivitelezheto. ´ as ´ minden idopontban ˝ ´ ´ ´ Az eljar veges sok tarat hasznal. ´ as ´ veges ´ ´ esb ´ ol ˝ all. ´ Az eljar sok lep

¨ ´ Kovetkezm eny: 1

2

Az algoritmus ugyanarra a bemenetre mindig ugyanazt az ´ eredmenyt adja. ˝ ´ ¨ ´ es. ´ Minden idopontban egyertelm uen ˝ adott a kovetkez o˝ lep


´ 10. 2015. februar

3 / 32

Alapfogalmak

Algoritmus

Adatstruktura ´

Algoritmus ⇒ adatstruktura ´ Az algoritmus az elemi muveletek ˝ sorozata. ´ dolgozik. Az algoritmus adatok alapjan Az adatstruktura ´ ´ ¨ ´ ıtott Az elerhet o˝ adatok egy szisztematikusan ossze all´ szerkezete.


´ 10. 2015. februar

4 / 32

Alapfogalmak

Algoritmusok anal´ızise

˝ Jellemzok: ´ ido˝ Futasi ˝ ´ osz ˝ am. ´ ˝ ´ Elsodleges mer Az ido˝ az egyik legfontosabb eroforr as. ´ ´ as ´ a leheto˝ legkisebb idofelhaszn ˝ ´ as. ´ Termeszetes elvar al ´ ´ as: ´ Tarfelhaszn al ´ ´ osz ˝ am. ´ ˝ Belefer ´ unk-e ´ Lenyeges mer Hardver fugg ¨ o. ¨ a tarba, vagy nem. ´ hatt ´ erbe ´ ´ ´ Manapsag szorul, mivel a memoria egyre olcsobb. ´ Megjegyzes: ´ sebesseg ´ es ´ a tarfelhaszn ´ ´ as ´ egymasnak ´ A futasi al ellentmondo´ ¨ ´ kovetelm enyek. ¨ ´ magval)os´ ´ ıtasok ´ Dr. Schuster Gyorgy (OE-KVK-MAI [email protected] Algoritmusok es

´ 10. 2015. februar

5 / 32

Alapfogalmak


´ sebesseg ´ Futasi

˝ fugg? Mitol ¨ ´ atol, ´ a bementek szam ´ at ´ ol, ´ a muveletek ˝ szam ´ at ´ ol. ´ a kimenetek szam


´ 10. 2015. februar

6 / 32

Alapfogalmak



´ esek ´ Tapasztalati mer ´ vannak: Hasznos, de korlatai ´ szam ´ u´ teszt bemenet hasznalhat ´ ´ limitalt o, ´ algoritmus nehezen hasonl´ıthato´ ossze, ¨ ket hacsak nem ´ szoftver kornyezetben ¨ ´ azonos hardver es vizsgaljuk, ´ es ´ futtatni kell azert, ´ hogy a az algoritmust implementalni ´ est ´ el lehessen vegezni. ´ mer


´ 10. 2015. februar

7 / 32

Alapfogalmak



´ eshez: ´ Feladatok a tapasztalati mer ´ ´ ese, ´ a lehetseges bemenetek felmer ´ ´ anak ´ ¨ ese, ´ ˝ az algoritmus hatekonys ag eldont illetoleg ¨ ´ hardver- es ´ szoftver kornyezett ¨ ˝ osszehasonl´ ıtasa ol fuggetlen ¨ ul, ¨ ´ implementaci ´ o´ nelk ´ ul. az algoritmus magas szintu˝ le´ırasa ¨


´ 10. 2015. februar

8 / 32

Alapfogalmak



Komponensek: ´ o´ nyelve, az implementaci ´ ıtasi ´ modell, amelyben az algoritmus fut, a szam´ ´ osz ˝ am, ´ ´ uk ´ sebesseget, ´ a mer amelyben merj ¨ a futasi ¨ ıtes, ´ amely alapjan ´ a futasi ´ idot ˝ az a megkozel´ ´ mgehatarozzuk, a rekurz´ıv algoritmusokat is.


´ 10. 2015. februar

9 / 32

Alapfogalmak

´ Pszeudo kod

´ Pszeudo´ kod ´ Pelda: Algorithm arrayMax(A, n): Input: An array A storing n 1 integers. Output: The maximum element in A. currentMax <- A[0] for i <- 1 to n

1 do

if currentMax < A[i] then currentMax <- A[i] return currentMax ¨ ´ magval)os´ ´ ıtasok ´ Dr. Schuster Gyorgy (OE-KVK-MAI [email protected] Algoritmusok es

´ 10. 2015. februar

10 / 32

Alapfogalmak

´ Pszeudo kod

´ Pszeudo´ kod

Mi is ez? ´ egyfajta kevereke ´ a termeszetes ´ ´ A pszeudo´ kod nyelv(ek)nek es ´ ´ nyelvnek. egy magasszintu˝ szabvanyos programozasi


´ 10. 2015. februar

11 / 32

Alapfogalmak

´ Pszeudo kod

´ Pszeudo´ kod Elemei: ´ ´ matematikai kifejezesekre ´ ´ Kifejezesek: a logikai es szabvanyos matematikai ¨ esek, ´ jelol ´ ´ oja: ´ ´ parameter ´ Metodusok deklaraci az algoritmus neve es lista, ¨ esi ´ struktur ´ szabvanyos ´ ´ else kifejezesek, ´ Dont ´ ak: if, then es ´ do muvelet, While ciklus: while feltetel ˝ ´ Repeat ciklus: repeat muvelet ˝ until feltetel, ´ ´ do muvelet, For ciklus: for valtoz o´ - inkremens to feltetel ˝ ¨ ´ A[i], Tomb indexeles: ´ ´ Metodus h´ıvas: metodus(argumentumok), ´ ´ es: ´ Metodus visszater return(v´ altoz´ o).


´ 10. 2015. februar

12 / 32

Alapfogalmak

´ Pszeudo kod

RAM (Random Access Machine) ´ kell: Miert ´ ´ pontossag ´ u´ es ´ hatekonys ´ ´ u. ´ A kiserleti anal´ızis limitalt ag ´ Ezert ´ eljar ´ ast ´ nehez ´ osszehasonl´ ¨ ˝ ´ nelk ´ ul. ket ıtani - foleg futtatas ¨ Muveleti ˝ primit´ıvek: ´ ´ ´ ekad ´ ´ valtoz onak ert as, ´ ´ metodus h´ıvas, ´ ´ aritmetikai muvelet ˝ vegrehajt asa, ´ szam ´ osszehasonl´ ¨ ´ ket ıtasa, ¨ ´ tomb indexeles, ´ objektum referencia kezelese, ´ ´ visszater ´ es. ´ metodusb ol ¨ ´ magval)os´ ´ ıtasok ´ Dr. Schuster Gyorgy (OE-KVK-MAI [email protected] Algoritmusok es

´ 10. 2015. februar

13 / 32

Alapfogalmak

´ Pszeudo kod

RAM (Random Access Machine)

´ Defin´ıcio: ´ ´ feltetelezi, hogy a CPU a RAM modellben barmelyik muveleti ˝ ´ ´ esben ´ ´ primit´ıvet veges lep vegre tudja hajtani.

´ ekekt ´ ˝ A muveletek ˝ nem fuggnek ¨ a bemeneti ert ol.


´ 10. 2015. februar

14 / 32

Alapfogalmak

´ Pszeudo kod

RAM (Random Access Machine) ´ ´ a muveleti Szamol as ˝ primit´ıvekkel ´ ´ A pelda alapjan: ´ ekkel ´ ´ A[0]-t a CurrentMax ert inicializalja, ´ al ´ ot ´ 1-el inicializalja, ´ azi-t ciklusszal ˝ a ciklustorzsbe ¨ ´ ellenorzi, ˝ mielott belep hogy i
- inedxel, ¨ - osszehasonl´ ıt CurrentMax-al, ´ CurrentMax-al (indexel es ´ ert ´ eket ´ - A[i]-t esetleg csereli ad), ´ a CurrentMax ert ´ ekkel. ´ visszater ´ Legalabb

Legfeljebb

2 + 1 + n + 4(n − 1) + 1 = 5n

2 + 1 + n + 6(n − 1) + 1 = 7n − 2


´ 10. 2015. februar

15 / 32

Alapfogalmak

´ Pszeudo kod

´ Atlagos eset vagy legrosszabb eset ´ Atlagos eset ´ ´ sebesseg ´ egy adott nagyreszt ´ ´ Az atlagos futasi veletlenszer u˝ ´ statisztikai vizsgalatokat, ´ bemeneti halmazra vonatkozik es ˝ ´ ınus ´ szam´ ´ ıtasi ´ modszereket ´ ´ illetoleg valosz´ ˝ eg igenyel.

A legrosszabb eset ´ sebesseg ´ bemeneti halmaza A legroszabb (leghosszabb) futasi ´ ´ ´ ´ıgy a kalkulaci ´ o´ pontosan gyakran egyertelm uen ˝ megallap´ ıthato, ´ ˝ elvegezhet o.


´ 10. 2015. februar

16 / 32

Alapfogalmak

´ Pszeudo kod

Rekurz´ıv algoritmusok anal´ızise

´ ´ A pelda rekurz´ıv megoldasa: Algorithm recursiveMax(A,n) Input: An array A storing n ≥ 1 itegers. Output: The maximum element in A if n=1 then return A[0] return max{recursiveMax(A,n-1),A[n-1]} ´ ido: ˝ A futasi T (n) =

3 T (n − 1) + 7

ha n = 1. ´ ent. ´ egyebk


´ 10. 2015. februar

17 / 32

Alapfogalmak

¨ esek ´ Aszimptotikus jelol


´ Miert? 1 2

3

4

´ as ´ nagyon munkaigenyes, ´ a pontos meghataroz ´ szamos ´ ´ minden egyes magasszintu˝ utas´ıtas elemi utas´ıtast tartalmaz, ´ ´ ´ az elemi utas´ıtasok szama nem mindig hatarozhat o´ meg (JIT compile), ¨ ıtes ´ is, foleg ˝ ¨ ´ sokszor elegendo˝ egy kozel´ osszehasonl´ ıtasok ´ eseten.


´ 10. 2015. februar

18 / 32

Alapfogalmak



Nagy O defin´ıcio´ ´ g(n) fuggv ´ ´ ´ ol ´ a valos ´ Legyenek f (n) es ¨ enyek, amelyek nem negat´ıv egeszek halmazar ´ ´ kepeznek ´ szamok halmazara le. ´ ´ egy n ≥ n0 , ahol f (n) akkor O(g(n)), ha letezik egy olyan c ∈ R, hogy c > 0 es ´ f (n) ≤ c g(n). n, n0 ∈ Z+ , hogy ∀n ≥ n0 eseten Ekkor mondjuk, hogy f (n) O(g(n)), vagy f (n) nagy ordo g(n). ´ Pelda: 7n − 2 az O(n)

´ Bizony´ıtas: ´ n0 ≥ 1, hogy 7n − 2 ≤ c n, ha n ≥ n0 -ra. Keressuk ¨ c > 0 es ´ ´ ´ a c = 7 es ´ az n0 = 1. Celszer u˝ valaszt as


´ 10. 2015. februar

19 / 32

Alapfogalmak


¨ esek ´ Aszimptotikus jelol 20n3 + 10n log n + 5 az O(n3 ) 20n3 + 10n log n + 5 ≤ 35n3 ∀n ≥ 1 ´ Megjegyzes: ´ az O(nk ). Minden ak nk + ak −1 nk −1 + · · · + a1 n + a0 polinom 3 log n + log log n az O(log n) 3 log n + log log n ≤ 4 log n, ha n ≥ 2 2100 az O(1) 2100 ≤ 2100 , ha n ≥ 1 5n log n + 2n az O(n log n) 5n log n + 2n ≤ 7n log n, ha n ≥ 2 ¨ ´ magval)os´ ´ ıtasok ´ Dr. Schuster Gyorgy (OE-KVK-MAI [email protected] Algoritmusok es

´ 10. 2015. februar

20 / 32

Alapfogalmak



´ Szabalyok: 1

´ O(f (n)) minden a > 0-ra, ha d(n) az O(f (n)), akkor ad(n) szinten

2

´ e(n) az O(g(n)), akkor d(n) + e(n) az O(f (n) + g(n)), ha d(n) az O(f (n)) es

3

´ e(n) az O(g(n)), akkor d(n) e(n) az O(f (n) g(n)), ha d(n) az O(f (n)) es

4

ha d(n) az O(f (n)), akkor f (n) az O(g(n)),

5

ha ak nk + ak −1 nk −1 + · · · + a1 n + a0 , akkor f (n) az O(nk ),

6

´ ¨ ıtett x > 0 es ´ a > 1-re, ha f (n) = nx , akkor O(an ), barmilyen rogz´

7

´ ¨ ıtett x > 0-ra, ha log nx az O(log n) barmilyen rogz´

8

´ ¨ ıtett x > 0 es ´ y > 1-re. ha logx n az O(ny ) barmilyen rogz´


´ 10. 2015. februar

21 / 32

Alapfogalmak



´ Pelda: 2n3 + 4n2 log n az O(n3 ) ´ log n az O(n), 8. szabaly, 2 3 ´ 4n log n az O(4n ), 3. szabaly, 3 2 3 ´ an + 4n log n az O(2n + 4n3 ), 2. szabaly, + 3 3 ´ 1. szabaly, ´ 2n 4n az O(n ), 5. es 3 2 3 ´ 2n + 4n log n az O(n ), 4. szabaly.


´ 10. 2015. februar

22 / 32

Alapfogalmak



´ Terminologia: O(log n) O(n) O(n2 ) O(nk ) O(an )

logaritmikus, ´ linearis, kvadratikus, ´ (k ≥ 1), polinomialis ´ (a > 1) exponencialis


´ 10. 2015. februar

23 / 32

Alapfogalmak


¨ esek ´ Aszimptotikus jelol ¨ es ´ Ω jelol ´ g(n) fuggv ´ ´ ´ ol ´ a valos ´ Legyenek f (n) es ¨ enyek, amelyek nem negat´ıv egeszek halmazar ´ ´ kepeznek ´ szamok halmazara le. ´ ´ konstans f (n) akkor Ω(g(n)), ha g(n) O(f (n)), amely szerint letezik olyan c > 0 valos ´ egy n ≥ n0 (n0 ≥ 1) egesz ´ kusz ¨ ´ es ¨ obsz am, amelyre igaz az, hogy f (n) ≥ cg(n) ∀n ≥ n0 . ˝ e´ teszi, hogy ket ´ algoritmus egy adott c konstans erejeig ´ Ez a defin´ıcio´ lehetov ˝ ¨ ´ aszomptotikusan egyenloek, illetve osszehasonl´ ıthatoak.

¨ es ´ Θ jelol ´ g(n) fuggv ´ ´ ´ ol ´ a valos ´ Legyenek f (n) es ¨ enyek, amelyek nem negat´ıv egeszek halmazar ´ ´ kepeznek ´ szamok halmazara le. ′

′′

´ ´ c >0 f (n) akkor Ω(g(n)), ha g(n) O(f (n)), amely szerint leteznek olyan c > 0 es ´ konstansok es ´ egy n ≥ n0 (n0 ≥ 1) egesz ´ kusz ¨ ´ valos ¨ obsz am, amelyre igaz az, hogy ′ ′′ c g(n) ≤ f (n) ≤ c g(n) ∀n ≥ n0 .


´ 10. 2015. februar

24 / 32

Alapfogalmak


¨ esek ´ Aszimptotikus jelol Kis o defin´ıcio´ ´ g(n) fuggv ´ ´ ´ ol ´ a valos ´ Legyenek f (n) es ¨ enyek, amelyek nem negat´ıv egeszek halmazar ´ ´ kepeznek ´ szamok halmazara le. ´ egy n ≥ n0 , ahol n, n0 ∈ Z0,+ , hogy ´ f (n) akkor o(g(n)), ha barmely olyan c ∈ R+ es ´ f (n) ≤ c g(n). ∀n ≥ n0 eseten Ekkor mondjuk, hogy f (n) az o(g(n)), vagy f (n) kis ordo g(n). ω defin´ıcio´ ´ Akkor mondjuk, hogy f (n) az ω(g(n)), ha g(n) az o(f (n)), vagyis ha barmely olyan ´ egy n ≥ n0 , ahol n, n0 ∈ Z0,+ , hogy ∀n ≥ n0 eseten ´ g(n) ≤ c f (n). c ∈ R+ es ´ Megjegyzes: ´ a kisebb egyenlo, ˝ az ω(·) analog ´ a nagyobb aszimptotikus ´ ¨ ıtessel. ´ o(·) analog kozel´


´ 10. 2015. februar

25 / 32

Alapfogalmak


¨ esek ´ Aszimptotikus jelol ´ ω(n) f (n) = 12n2 + 6n az o(n3 ) es 1

fn(n) az o(n3 ) ˝ n0 = (12 + 6)/c = 18/c legyen c > 0 ebbol ˝ 18 < cn n ≥ n0 , ebbol f (n) = 12n2 + 6n ≤ 12n2 + 6n2 = 18n2 ≤ cn3 . ´ f (n) az o(n3 ). Tehat

2

f (n) az ω(n) ˝ n0 = c/12 legyen c > 0 ebbol egy n ≥ n0 12n ≥ c, ´ıgy f (n) = 12n2 + 6n ≥ 12n2 ≥ cn. ´ f (n) az ω(n). Tehat

´ Megjegyzes: ´ csak akkor o(g(n)), ha Vagis f (n) akkor es lim

n→∞

f (n) =0 g(n)


´ 10. 2015. februar

26 / 32

Alapfogalmak

´ ´ Matematikai attekint es

¨ ´ Osszegz es ´ Defin´ıcio: b X

f (i) = f (a) + f (a + 1) + f (a + 2) + · · · + f (b)

i=a

Gyakori!!

´ o˝ linearisan ´ ˝ Ha ciklussal dolgozunk, akkor a futasid no. ´ jo´ tudni, hogy: Ezert Pn

i 2 n i=0 a = 1 + a + a + · · · + a =

Pn−1 i=0

Pn

i=1

1 + an+1 , ha a > 0, 1−a

= 1 + 2 + 4 + 8 + · · · + 2n−1 = 2n − 1, = 1+ 2 +3 + 4+ ··· + n − 1 + n =

n(n + 1) , ha n ≥ 1, 2


´ 10. 2015. februar

27 / 32

Alapfogalmak


´ Esettanulmany ´ osseg ¨ Egyszeru˝ resz algoritmus sj,k = aj + aj+1 + · · · + ak =

k X

ai

i=j

Algorithm MaxsubSlow(A): Input: An n-element array A of numbers, indexed from 1 to n. Output: The maximum subarray sum of array A. m ← 0 // the maximum found so far for j ← 1 to n do for k ← j to n do s ← 0 // the next partial sum we are computing for i ← j to k do s ← s + A[i] if s > m then m ← s return m Ez O(n3 ).


´ 10. 2015. februar

28 / 32

Alapfogalmak


´ Esettanulmany ´ osszeg ¨ Jav´ıtott resz algoritmus Input: An n-element array A of numbers, indexed from 1 to n. Output: The maximum subarray sum of array A. S0 ← 0 // the initial prefix sum for i ← 1 to n do Si ← Si1 + A[i] m ← 0 // the maximum found so far for j ← 1 to n do for k ← j to n do s = Sk - Sjx 1 if s > m then m ← s return m Ez O(n2 ).


´ 10. 2015. februar

29 / 32

Alapfogalmak


´ Esettanulmany ´ ideju˝ resz ´ osszeg ¨ Linearis algoritmis Mt = max{0, Mt−1 + A[t]} Algorithm MaxsubFastest(A): Input: An n-element array A of numbers, indexed from 1 to n. Output: The maximum subarray sum of array A. M0 ← 0 // the initial prefix maximum for t ← 1 to n do Mt ← max{0, Mt1 + A[t]} m ← 0 // the maximum found so far for t ← 1 to n do m ← max{m, Mt } return m Ez O(n)


´ 10. 2015. februar

30 / 32

Alapfogalmak



´ 10. 2015. februar

31 / 32

Alapfogalmak



´ 10. 2015. februar

32 / 32

32

Recommend Documents