Matematika | Felsőoktatás » Papp László - Problémák, Algoritmusok

Problémák, Algoritmusok Papp László BME 2019. december 13 Motiváció Adott valamilyen feladat amit vagy sokszor kell elvégezni, vagy maga a feladat áll sok apró, jól megfogható lépésből. Példa: Navigáció problémája: Adott egy úthálózat, a kiinduló pont és a célállomás, állapítsuk meg, hogy hogyan lehet eljutni a lehető leggyorsabban a kiinduló pontból a célhoz! Navigáció algoritmikus megoldása Naív megközelítések: I Megnézek néhány útvonalat és a legrövidebbet választom. I Végignézem az összes lehetséges útvonalat. Ezen naív módszerek is algoritmusok valójában. Mindkét naív megköelítéssel van probléma. Navigáció algoritmikus megoldása Naív megközelítések: I Megnézek néhány útvonalat és a legrövidebbet választom. Lehet a legrövidebbnél csak sokkal hosszabbat találok. I Végignézem az összes lehetséges útvonalat. Nagyon sok idő és energia ezt megtenni. Ezen naív módszerek is

algoritmusok valójában. Mindkét naív megköelítéssel van probléma. Ezek helyett: Gyakorlait megvalósítás: I Matematikai modell: Irányított élsúlyozott gráf, kezdőcsúcs, célcsúcs, a kettő közötti legrövidebb út keresése. Navigáció algoritmikus megoldása Naív megközelítések: I Megnézek néhány útvonalat és a legrövidebbet választom. Lehet a legrövidebbnél csak sokkal hosszabbat találok. I Végignézem az összes lehetséges útvonalat. Nagyon sok idő és energia ezt megtenni. Ezen naív módszerek is algoritmusok valójában. Mindkét naív megköelítéssel van probléma. Ezek helyett: Gyakorlait megvalósítás: I Matematikai modell: Irányított élsúlyozott gráf, kezdőcsúcs, célcsúcs, a kettő közötti legrövidebb út keresése. I Algoritmikus feladat: A két megadott csúcs között egy legrövidebb irányított út megtalálása. Navigáció algoritmikus megoldása Naív megközelítések: I Megnézek néhány

útvonalat és a legrövidebbet választom. Lehet a legrövidebbnél csak sokkal hosszabbat találok. I Végignézem az összes lehetséges útvonalat. Nagyon sok idő és energia ezt megtenni. Ezen naív módszerek is algoritmusok valójában. Mindkét naív megköelítéssel van probléma. Ezek helyett: Gyakorlait megvalósítás: I Matematikai modell: Irányított élsúlyozott gráf, kezdőcsúcs, célcsúcs, a kettő közötti legrövidebb út keresése. I Algoritmikus feladat: A két megadott csúcs között egy legrövidebb irányított út megtalálása. I Algoritmikus feladat megoldása: Dijkstra algoritmussal Navigáció algoritmikus megoldása Naív megközelítések: I Megnézek néhány útvonalat és a legrövidebbet választom. Lehet a legrövidebbnél csak sokkal hosszabbat találok. I Végignézem az összes lehetséges útvonalat. Nagyon sok idő és energia ezt megtenni. Ezen naív módszerek is algoritmusok valójában. Mindkét naív megköelítéssel van

probléma. Ezek helyett: Gyakorlait megvalósítás: I Matematikai modell: Irányított élsúlyozott gráf, kezdőcsúcs, célcsúcs, a kettő közötti legrövidebb út keresése. I Algoritmikus feladat: A két megadott csúcs között egy legrövidebb irányított út megtalálása. I Algoritmikus feladat megoldása: Dijkstra algoritmussal I Algoritmus outputjának hasznosítása: Ez megfelel egy való életbeli legrövidebb útnak. Forrás: Mi azhttps://doksi.net az algoritmus? Erre nincs matematikailag precíz definíció. Érjük be az alábbi körülírással: Algoritmusnak nevezünk minden olyan véges lépésszámú eljárást amit le lehet programozni és egy tetszőlegesen nagy memóriával rendelkező számítógépen le lehet futtatni. Input Algoritmus Output a,b egészek Euklideszi Algoritmus (a,b) Az algoritmusnak általában van egy inputja (bemenete) amit nekünk kell megadni. Az algoritmus ezzel dolgozik majd kiadja az outputját (kimenetét).

megoldható Algoritmikusan problémák Kérdés: Mi az, hogy probléma? Ezt az algoritmushoz hasonlóan szintén nem fogjuk matematikai precizitással definiálni. Alapvetően egy olyan feladat aminek feltételezzük, hogy van egy vagy több megoldása amit keresünk. A P probléma algoritmikusan megoldható ha létezik olyan A algoritmus amit ha lefuttatunk, akkor az A outputja P-nek a megoldása(i). nem Algoritmikusan megoldható problémák Megjegyzés: Van végtelen sok algoritmikusan nem megoldható probléma is. Itt nem kell feltétlen egzotikus dolgokra gondolni, és sok olyan probléma is algoritmikusan nem megoldható amiről azt hinné ember, hogy létezik rá algoritmus. Megállási probléma: C++ programozási nyelven írunk egy programot. A kérdés az, hogy ez a program véges időben lefut-e egy tetszőlegesen sok memóriával rendelkező számítógépen? Állítás A megállási probléma nem algoritmikusan megoldható. Megjegyzés: A C++ helyett bármilyen

más eléggé erős kifejezőképességű (Turing-teljes) programozási nyelvet is írhattam volna. Egyik esetben sem lehet olyan algoritmust készíteni ami minden adott nyelven írt forráskódról eldönti, hogy az abból fordított program minden lehetséges inputon le fog-e futni egy számítógépen. Problémát megoldó algoritmusok száma Ha egy P probléma algoritmikusan megoldható akkor általában rengeteg, tipikusan végtelen sok különböző algoritmus van ami P-t megoldja. Ezen módszerek közül mi általában a leghatékonyabb algoritmusra vagyunk kiváncsiak. Példa Probléma: Legrövidebb irányított út keresése élsúlyozott irányított gráfban, ahol az élsúlyok pozitívak. Erre tanultunk három különböző algoritmust: I Dijkstra I Ford I Floyd Kérdés: Melyiket válasszuk? Problémát megoldó algoritmusok száma Ha egy P probléma algoritmikusan megoldható akkor általában rengeteg, tipikusan végtelen sok különböző algoritmus van

ami P-t megoldja. Ezen módszerek közül mi általában a leghatékonyabb algoritmusra vagyunk kiváncsiak. Példa Probléma: Legrövidebb irányított út keresése élsúlyozott irányított gráfban, ahol az élsúlyok pozitívak. Erre tanultunk három különböző algoritmust: I Dijkstra I Ford I Floyd Kérdés: Melyiket válasszuk? Feladatfüggő. Általában a leghatékonyabbat Ehhez kell egy vagy több mérték ami a hatékonyságot méri. Hogyan mérjük az algoritmusok hatékonyságát? Adott egy P probléma és ezt meg tudjuk oldani egy A és egy B algoritmussal is. Kérdés: Hogyan döntsük el, hogy az A vagy a B algoritmus a jobb? Ami “kevesebb” erőforrást használ. Hogyan mérjük az algoritmusok hatékonyságát? Adott egy P probléma és ezt meg tudjuk oldani egy A és egy B algoritmussal is. Kérdés: Hogyan döntsük el, hogy az A vagy a B algoritmus a jobb? Ami “kevesebb” erőforrást használ. Kérdés: Milyen erőforrások vannak egy

algoritmus futtatásánál? Hogyan mérjük az algoritmusok hatékonyságát? Adott egy P probléma és ezt meg tudjuk oldani egy A és egy B algoritmussal is. Kérdés: Hogyan döntsük el, hogy az A vagy a B algoritmus a jobb? Ami “kevesebb” erőforrást használ. Kérdés: Milyen erőforrások vannak egy algoritmus futtatásánál? Két legalapvetőbb erőforrás: számítási kapacitás és memória kapacitás. Az előbbi annak felel meg, hogy az algoritmus hány lépést tesz, míg utóbbi annak, hogy maximum hány bitnyi információt szükséges tárolnunk az algoritmus futásának egy időpillanatában. Ebből a tárgyból csak a lépésszámokkal fogunk foglalkozni, a szükséges memória mennyiségével nem. Mindig feltesszük, hogy végtelen sok memóriánk van. Mi számít egy lépésnek? Erre nincs precíz definíció, általában az alkalmazástól illetve kontextustól függ. Ezen tárgy keretében aritmetikai problémáknál általában egy

lépésnek egy bitművelet elvégzése fog számítani. Érdekesség: A valóságban is nehéz univerzálisan meghatározni a lépés fogalmát, mivel a különböző architektúrájú processzorok különböző módon hajtják végre ugyanazokat az utasításokat. Például egy 64-bites processzor képes egy lépésben összeadni az 5.000000000-ot a 6.000000000-al, míg egy 32-bites csak több lépésben tudja ugyanezt a feladatot elvégezni. Az input és a lépésszám kapcsolata Láttuk, hogy az Euklideszi algoritmus vizsonylag gyorsan kiszámítja két egész szám legnagyobb közös osztóját. A 6-nak és a 4-nek a legnagyobb közös osztóját viszont sokkal kevesebb lépésben számítja ki mint a 11123456 és 12123456 -nek a legnagyobb közös osztóját. Utóbbi esetben magának az inputnak az elolvasása is több ideig tart mint a 6, 4 esetben az algoritmus teljes végrehajtása. Következmény: Az algoritmus lépésszámát az input méretének függvényében

célszerű tekinteni. Az input mérete Definíció Input méretén az input leírásához szükséges bitek számát értjük. Példa: Az 1110001 2-es számrendszerben felírt szám mérete a számjegyezinek a száma, azaz 7. Egy tetszőleges számrendszerben felírt a szám mérete pedig log2 a (valójában dlog2 (a + 1)e, de ennek az eltérése a log2 a-tól elhanyagolható), például az 1023 mérete 10. Megjegyzés: Egy 10-es számrendszer beli szám mérete nagyjából a számjegyei száma szorozva 3,3-al, mivel log2 a log10 a = log 10 és log2 10 ≈ 3, 3. 2 Lépésszám az input függvényében Az euklideszi algoritmusnál maradva tekintsük az alábbi két inputot: 40, 10 és 41, 9. Mindkét esetben az input mérete dlog2 (40)e + dlog2 (10)e + 1 = dlog2 (41)e + dlog2 (9)e + 1 = 11. Az algoritmus két futása: 41 = 4 · 9 + 5 40 = 4 · 10 + 0 9=1·5+4 5=1·4+1 4=4·1+0 Látjuk, hogy két ugyan olyan hosszú input esetén is az algoritmus lépésszáma különbözik.

Emiatt a lépésszám nem csak az input méretétől függ. Biztonsági megoldás: Mindig a legroszabb esetettel foglalkozunk, azaz az érdekel, hogy az n hosszú inputon maximum hány lépést tesz az algoritmus. Algoritmusok lépésszáma Definíció: Egy A algoritmus lépésszámfüggvényén azt az fA : N N függvényt értjük ami minden n-re azt az értéket veszi fel, hogy az algoritmus az n hosszú inputok közül a legtöbb lépést igénylő esetben hány lépést tesz. Algoritmusok lépésszáma Definíció: Egy A algoritmus lépésszámfüggvényén azt az fA : N N függvényt értjük ami minden n-re azt az értéket veszi fel, hogy az algoritmus az n hosszú inputok közül a legtöbb lépést igénylő esetben hány lépést tesz. Ha az A algoritmus minden inputon véges időn belül lefut, akkor fA (n) tetszőleges n-re meghatározható. Azonban ezzel két gond is van: I fA (n) meghatározása nagyon sok időt igényel. I Az fA függvény tipikusan

bonyolult. Algoritmusok lépésszáma Definíció: Egy A algoritmus lépésszámfüggvényén azt az fA : N N függvényt értjük ami minden n-re azt az értéket veszi fel, hogy az algoritmus az n hosszú inputok közül a legtöbb lépést igénylő esetben hány lépést tesz. Ha az A algoritmus minden inputon véges időn belül lefut, akkor fA (n) tetszőleges n-re meghatározható. Azonban ezzel két gond is van: I fA (n) meghatározása nagyon sok időt igényel. I Az fA függvény tipikusan bonyolult. Ezért a lépésszám függvényt közelíteni szoktuk. Definíció: Egy A algoritmus lépésszámára felső korlát a g : N N függvény, ha minden n-re g(n) ≥ fA (n). Definíció: Egy A algoritmus lépésszámára alsó korlát a h : N N függvény, ha minden n-re h(n) ≤ fA (n). Ha g felső korlát az A lépésszámára, akkor az A algoritmus egy n hosszú inputtal legfeljebb g(n) lépés után végez. Lépésszámfüggvények osztályozása Definíció:

Az A algoritmus polinom lépésszámú (futásidejű), ha létezik olyan g felsőkorlát az A lépésszámára ami polinomja n-nek, azaz g(n) = ak nk + ak −1 nk −1 + . + a1 n + a0 Megjegyzés: Ekkor felső korlát a cnk függvény is ahol Pk c = i=0 ai . Definíció: Az A algoritmus exponenciális lépésszámú (futásidejű), ha létezik olyan g felsőkorlát és h alsó korlát az A lépésszámára, hogy mindkettő exponenciális függvénye n-nek, azaz g(n) = c1 2c2 n és h(n) = c3 2c4 n , ahol c1 , c2 , c3 , és c4 pozitív konstansok. A polinomiális algoritmus lépésszáma egy polinommal jól közelíthető, az exponenciális algoritmus lépésszáma pedig egy exponenciális függvénnyel közelíthető. Milyen lépésszámú algoritmusokat szeretünk? Alapvetően a polinomiális futásidejő algoritmusokat szeretjük, a nem polinomiális futásisdejű algoritmusokat nem. Miért? Milyen lépésszámú algoritmusokat szeretünk? Alapvetően a

polinomiális futásidejő algoritmusokat szeretjük, a nem polinomiális futásisdejű algoritmusokat nem. Miért? Legyenek az A és B algoritmusok lépésszámfüggvényei fA (n) = n7 és fB (n) = 2n . Tekintsünk egy mai modern processzort. Ez lebegőpontos számokkal kb 1010 műveletet tud elvégezni másodpercenként. Nézzük meg, hogy különböző hosszúságú inputok esetén az A és B algoritmusok lefuttatása legroszabb esetben mennyi időt igényel egy ilyen processzoron: input hossza 10 30 50 70 −3 A algoritmus 10 sec B algoritmus 10−7 sec Milyen lépésszámú algoritmusokat szeretünk? Alapvetően a polinomiális futásidejő algoritmusokat szeretjük, a nem polinomiális futásisdejű algoritmusokat nem. Miért? Legyenek az A és B algoritmusok lépésszámfüggvényei fA (n) = n7 és fB (n) = 2n . Tekintsünk egy mai modern processzort. Ez lebegőpontos számokkal kb 1010 műveletet tud elvégezni másodpercenként. Nézzük meg, hogy

különböző hosszúságú inputok esetén az A és B algoritmusok lefuttatása legroszabb esetben mennyi időt igényel egy ilyen processzoron: input hossza 10 30 50 70 −3 A algoritmus 10 sec 2 sec B algoritmus 10−7 sec 0, 1 sec Milyen lépésszámú algoritmusokat szeretünk? Alapvetően a polinomiális futásidejő algoritmusokat szeretjük, a nem polinomiális futásisdejű algoritmusokat nem. Miért? Legyenek az A és B algoritmusok lépésszámfüggvényei fA (n) = n7 és fB (n) = 2n . Tekintsünk egy mai modern processzort. Ez lebegőpontos számokkal kb 1010 műveletet tud elvégezni másodpercenként. Nézzük meg, hogy különböző hosszúságú inputok esetén az A és B algoritmusok lefuttatása legroszabb esetben mennyi időt igényel egy ilyen processzoron: input hossza 10 30 50 70 −3 A algoritmus 10 sec 2 sec 1, 2 perc B algoritmus 10−7 sec 0, 1 sec 1, 3 nap Milyen lépésszámú algoritmusokat szeretünk? Alapvetően a polinomiális

futásidejő algoritmusokat szeretjük, a nem polinomiális futásisdejű algoritmusokat nem. Miért? Legyenek az A és B algoritmusok lépésszámfüggvényei fA (n) = n7 és fB (n) = 2n . Tekintsünk egy mai modern processzort. Ez lebegőpontos számokkal kb 1010 műveletet tud elvégezni másodpercenként. Nézzük meg, hogy különböző hosszúságú inputok esetén az A és B algoritmusok lefuttatása legroszabb esetben mennyi időt igényel egy ilyen processzoron: input hossza 10 30 50 70 −3 A algoritmus 10 sec 2 sec 1, 2 perc 14 perc B algoritmus 10−7 sec 0, 1 sec 1, 3 nap 3744 év További érv (mese) a polinomiális algoritmusok mellett: Az elmúlt 50 évben a számítási kapactiás másfél évente megduplázódott (Moore-törvény). Tegyük fel, hogy egy mai nap vásárolt gépen 1 óra alatt maximum 1000 méretű inputokra tudjuk lefuttatni az algoritmust. Ha az A algoritmus 3 , akkor egy másfél év múlva lépésszámfüggvénye cn √ 3 várásárolt

gépen már 2 · 1000 = 1260 méretű inputokra is le tudjuk futtatni az algoritmust 1 óra alatt. Ezzel szemben ha az algoritmus lépésszámfüggvénye 2n akkor másfél év múlva 1001 hosszú inputokra le fog futni 1 óra alatt, de 1002 hosszúakra már nem. Forrás: Egészhttps://doksi.net számok összeadása Összead probléma: Input: a és b egész számok, Kérdés: Mennyi a + b? Ez egy algoritmikusan megoldható probléma, hiszen az általános iskolában tanult összeadás algoritmusa hatékonyan megoldja: 147 10010011 +105 +1101001 252 11111100 Forrás: Egészhttps://doksi.net számok összeadása Összead probléma: Input: a és b egész számok, Kérdés: Mennyi a + b? Ez egy algoritmikusan megoldható probléma, hiszen az általános iskolában tanult összeadás algoritmusa hatékonyan megoldja: 147 10010011 +105 +1101001 252 11111100 Ezen problémánál az input hossza n = log2 a + log2 b. Ha egy lépésnek egy bitenkénti összeadást tekintünk, akkor az

algoritmus lépésszámára felső becslés a 2n = 2(log2 a + log2 b) függvény, ami lineáris az input méretében. Forrás: Egészhttps://doksi.net számok összeadása Összead probléma: Input: a és b egész számok, Kérdés: Mennyi a + b? Ez egy algoritmikusan megoldható probléma, hiszen az általános iskolában tanult összeadás algoritmusa hatékonyan megoldja: 147 10010011 +105 +1101001 252 11111100 Ezen problémánál az input hossza n = log2 a + log2 b. Ha egy lépésnek egy bitenkénti összeadást tekintünk, akkor az algoritmus lépésszámára felső becslés a 2n = 2(log2 a + log2 b) függvény, ami lineáris az input méretében. Ennél lényegesen gyorsabb algoritmus nem is készíthető erre a problémára, hiszen már az input elolvasásához szükséges n lépés és ezen probléma megoldásához mindenképpen szükséges elolvasni a teljes inputot. Forrás: Egészhttps://doksi.net számok szorzása Szorzás probléma: Input: a és b egész számok

Kérdés: mennyi a · b? Most pedig az általános iskolában tanult szorzó algoritmust vesszük elő: 147· 343 441 Ezt egy kicsit módosítsuk: A két vonal 588 közötti sorokat párosával adjuk össze, és + 441 nem egyszerre az összeset. 50421 Az input mérete n = log2 a + log2 b. Ha a bitenkénti szorzást illetve összeadást számítjuk egy lépésnek, akkor a fenti példában egy sor kiszámítása legfeljebb 3 log2 a lépés és összesen log2 b sor keletkezik. Végül ezeket össze kell még adni. Minden összeadásban legfeljebb log2 a + log2 b méretű számokat adunk össze, így ez legfeljebb 2 log2 b · 2(log2 b + log2 a) lépés. A lépésszámot tehát felülről becsülhetjük 7(log2 a + log2 b)2 = 5n2 -tel. Ez tehát egy input méretében négyzetes lépésszámú algoritmus. Forrás: Többihttps://doksi.net aritmetikai művelet Állítás Van olyan c konstans és olyan algoritmus ami az a és b egész számokat elosztja maradékosan c(log2 a + log2 b)3

lépés alatt. Forrás: Többihttps://doksi.net aritmetikai művelet Állítás Van olyan c konstans és olyan algoritmus ami az a és b egész számokat elosztja maradékosan c(log2 a + log2 b)3 lépés alatt. Állítás Nincs polinomiális algoritmus egész számok hatványozásra. Forrás: Többihttps://doksi.net aritmetikai művelet Állítás Van olyan c konstans és olyan algoritmus ami az a és b egész számokat elosztja maradékosan c(log2 a + log2 b)3 lépés alatt. Állítás Nincs polinomiális algoritmus egész számok hatványozásra. Bizonyítás: Egy hatványozást megvalósító algoritmus inputja egy a, b számpár bináris alakban, tehát az input mérete log2 a + log2 b. Az output pedig ab bináris alakban aminek a mérete b log2 a. Ennek elemzéséhez rögzítsük a-t 2-nek Ebben az esetben az input mérete 1 + log2 b, míg az output mérete log2 2b = b = 2log2 b = 21 2log2 b+1 . Tehát már az output kiírásához is exponenciális sok lépés

szükséges. Forrás: Miérthttps://doksi.net jó az Euklideszi algoritmus? Legnagyobb közös osztót már korábban számolni a Qk is αtudtunk Qk βi i kanonikus alakokból, hiszen ha a = i=1 pi és b = i=1 pi , Q min(αi ,βi ) akkor (a, b) = ki=1 pi . Forrás: Miérthttps://doksi.net jó az Euklideszi algoritmus? Legnagyobb közös osztót már korábban számolni a Qk is αtudtunk Qk βi i kanonikus alakokból, hiszen ha a = i=1 pi és b = i=1 pi , Q min(αi ,βi ) akkor (a, b) = ki=1 pi . Azonban egy a szám kanonikus alakjának előállítására nem ismerünk polinomiális algoritmust. Ezzel szemben a Euklideszi algoritmus polinomiális algoritmus, hiszen (a, b) meghatározásához semmi mást nem használ mint maradékos osztásokat. Abból sem túl sokat, mivel belátható, hogy a maradék két egymás utáni osztás után legalább a felére csökken. Emiatt a maradék 2 log2 (max(a, b)) + 1 osztás után mindenképpen 0, így az algoritmus is leáll. Forrás:

Gyorshttps://doksi.net algoritmusok létezése Faktorizáció probléma: Adott egy a egész szám és állítsuk elő a kanonikus alakját. Előbb említettük, hogy erre a problémára nem ismert polinomiális algoritmus. Fontos! Az, hogy nem ismert, nem jelenti azt, hogy nem is létezik. Valójában nem tudjuk, hogy létezik-e ilyen algoritmus Vannak olyan problémák amikre régóta kerestek hatékony algoritmust és csak mostanában találtak. Példa: Prím probléma: Adott egy a egész szám. Döntsük el, hogy a prímszám-e! Már az ókori görögök is kerestek hatékony módszert ezen kérdés eldöntésére. 2002-ben 3 indiai olyan polinomiális algoritmust talált ami megoldja ezt a problémát. Tanulság: Az hogy valamit még senki sem csinált meg az nem azt jelenti, hogy lehetetlen!