Kiegészítő részelőadás 1. Az algoritmusok hatékonyságának mérése

Számítástudomány

Széchenyi István Egyetem

Kiegészítő részelőadás 1. Az algoritmusok hatékonyságának mérése

Dr. Kallós Gábor

2014–2015 11



Az Ordó jelölés Azt mondjuk, hogy az f(n) függvény eleme az Ordó(g(n)) halmaznak, ha van olyan c konstans (c ≠ 0), hogy valamely n0 felett mindig 0 ≤ f(n) ≤ c·g(n) Másként: f(n) = O(g(n)) vagy az f(n) függvény O(g(n))-es

Feladatok Igaz-e, hogy az f(n) = n függvény O(n2)-es? Igaz-e, hogy az f(n) = n függvény O(n)-es? Igaz-e, hogy az f(n) = 5·n/2 függvény O(n)-es?

Aszimptotikus felső korlát – sokszor keveset mond… Aszimptotikusan éles felső korlát – ez az érdekes számunkra 2



Klasszikus algoritmusok kategorizálása Egy művelet számunkra: hasonlítás, értékadás stb. O(log n)-es algoritmusok Keresés rendezett tömbben – annak eldöntése, hogy egy adott elem benne van-e a tömbben Ötlet: minden lépésben felezzük a még bejáratlan részt Beszúrás rendezett tömbbe

O(n)-es – lineáris – algoritmusok Legnagyobb ill. legkisebb elem megkeresése, adott elem megkeresése – nem rendezett tömbben (elemszám: n); ötlet: egyszer kell végignézni a tömböt Két ill. konstans darab tömb (vektor) összeadása, összehasonlítása n hosszú egészek összeadása *Egyes speciális rendezések

O(n2)-es algoritmusok Klasszikus rendezési algoritmusok, pl. kiválasztásos és buborékos rendezés (a tömb elemszáma: n) – ötlet: két egymásba ágyazott ciklus kell Érdekes lehet még az Ordóban „elrejtett” konstans is (de ez a lényeget már kevésbé befolyásolja)

n×n-es mátrixok összeadása, konstanssal való szorzása n hosszú egészek szorzása (a klasszikus megoldás szerint)

O(n3)-ös algoritmusok Klasszikus mátrixszorzás 3



Klasszikus algoritmusok kategorizálása O(n·log n)-es algoritmusok Gyorsrendezés (általában) n hosszú egészek szorzása gyors Fourier-transzformációval

O(nc)-es algoritmusok, ahol 1 < c < 2 Karacuba módszere n hosszú egészek szorzására

O(nc)-es algoritmusok, ahol 2 < c < 3 Strassen módszere n×n-es mátrixok szorzására Gauss-elimináció megvalósítása n×n-es együtthatómátrix esetén

A polinomiális időben megoldható problémák osztályát P-vel jelöljük Nem polinomiális (hanem exponenciális) algoritmusok Teljes prímfaktorizáció (pl. a klasszikus osztóleválasztásos módszerrel) Mátrix inverzének meghatározása a rekurzív determinánskifejtés módszerével Utazó ügynök probléma (Hamilton-kör létezése) Sakk játék teljes elemzése (hasonlóan: go, dáma stb.)

Összehasonlítás: Tfh. az A algoritmus 2n lépésben működik, B 3000n5 lépésben; gépünk pedig 1012/sec műveletet végez 13

[

]

A megoldható problémák mérete 1 perc alatt: A algoritmussal n ≤ log 2 6 ⋅10 = 45,  6 ⋅1013  B algoritmussal n ≤ 5  = 114 3000   1 óra alatt: A algoritmussal 51, B algoritmussal 260

4



P és NP Az NP problémaosztály Az utazó ügynök probléma megoldható polinomiális időben, ha egy varázsló (orákulum) megmutatja nekünk az utat (és nekünk csak ellenőrizni kell) Mindez több más hasonló problémára igaz, ezeket a problémákat NP-belieknek nevezzük (nem-determinisztikus polinomiális)

Világos, hogy P ⊆ NP Eldöntetlen kérdés ugyanakkor, hogy P = NP?

A co-NP problémaosztály Vannak olyan problémák, amelyeknek a tagadását tudjuk polinom időben igazolni, ha segít a varázsló; pl.: igaz-e, hogy a gráfban nincs Hamilton-kör? Ezek a co-NP-beli problémák

Tudjuk, hogy NP ∩ co-NP nem üres, ide tartozik pl. Van-e egy gráfban teljes párosítás? Síkbarajzolható-e egy gráf? Indoklás 1: a varázsló mutat nekünk egy teljes párosítást, ill. lerajzolja síkba a gráfot *Indoklás 2: a varázsló mutat nekünk egy X részhalmazt, amire |N(X)| < |X| (szomszédok száma), ill. egy részgráfot, ami izomorf valamelyik Kuratowski-gráffal

Az is igaz, hogy P ⊆ NP ∩ co-NP NP-teljes probléma: minden NP-beli probléma visszavezethető rá, és benne van NP-ben 5



P és NP Időnként az exponenciális algoritmusokkal megoldható feladatokkal is boldogulunk Nem feledkeztünk-e el valamiről? – Egyes speciális feltételek teljesülése esetén létezhet NP-beli problémára is polinomrendű, gyors megoldó algoritmus Adott (nem nagyon nagy) n-re akár még le tudjuk futtatni az exponenciális megoldó algoritmust is Gyakran polinomrendű algoritmus ad az optimálishoz közeli megoldást Előfordulhat, hogy tudunk olyan polinomrendű algoritmust készíteni, amely majdnem biztosan helyes választ ad (prímtesztek)

*Nevezetes polinomrendű, ill. NP-teljes feladatok P-beli

NP-teljes

Van-e egy gráfban minimum k darab független él?

Van-e egy gráfban minimum k darab független pont?

Van-e egy gráfban maximum k hosszúságú út?

Van-e egy gráfban minimum k hosszúságú út?

Van-e egy gráfban maximum k hosszúságú kör?

Van-e egy gráfban minimum k hosszúságú kör?

Kiszínezhetőek-e egy gráf pontjai legfeljebb 2 színnel?

Kiszínezhetőek-e egy gráf pontjai legfeljebb k (k ≤ 3) színnel? 6



Egy nem triviális klasszikus algoritmus bemutatása Hogyan lesz általában O(n·log n)-es a gyorsrendezés? Algoritmus és műveletigény-fa

7



Ajánlott irodalom Cormen, Leiserson, Rivest: Algoritmusok, Műszaki Kiadó, Budapest, 1998– (több kiadás) Gács Péter, Lovász László: Algoritmusok, Tankönyvkiadó, Budapest, 1978– (több kiadás) Katona Gyula, Recski András, Szabó Csaba: Gráfelmélet, algoritmuselmélet és algebra, Egyetemi jegyzet, BME, 1997 Katona Gyula, Recski András, Szabó Csaba: A számítástudomány alapjai, Typotex Kiadó, Budapest, 2003

8

Kiegészítő részelőadás 1. Az algoritmusok hatékonyságának mérése

Recommend Documents