11. Efektivita algoritmov

• Aké druhy efektivity rozlišujeme?

• Ako hodnotíme efektivitu algoritmov? Na konkrétnom algoritme ukážte spôsob hodnotenia efektivity.

• Uveďte príklad, ktorý je možné riešiť pomocou pažravej metódy a uveďte riešenie.

• Aké druhy efektivity rozlišujeme?

 

       Ak chceme, aby naše programy bežali rýchlo , či dokonca , aby sme sa dožili ich úspešného ukončenia, mali by sme dbať o ich efektivitu. Tá sa dá merať časovou a pamäťovou zložitosťou.

Príklad: Na vyučovaní matematiky dostali asi 10-roční žiaci úlohu spočítať prvých 100 prirodzených čísiel. (Učiteľ’ si chcel v kľude prečítať noviny, a keby nestihol, zvýši počet.) Žiaci postupovali väčšinou podľa jeho predpokladov: sčítali postupne 1+2+3+4+5+… a trvalo im to úmerne ich “sčítacím” schopnostiam. Našiel sa však žiak, nazvyme ho malý Gauss, ktorý prevrátil plány učiteľa naruby. Nekonal hneď, ale rozmýšľal: 1+100=101,2+99=101, 3+88=101,… a takýchto dvojíc je polovica z počtu čísiel, teda 50. Vynásobenie 50×101 = 5 050 bolo otázkou okamihu.

 Neefektívnym algoritmom  bolo postupné sčítavanie:          1+2+…+99+100 = 5050.

ü  Omnoho efektívnejším spôsobom  bol výpočet:                    (1+100)*50 = 5050.

Prichádza hneď do úvahy zovšeobecnenie riešenia tak, aby bol postup hromadný, teda riešil problém pre ľubovoľný počet prvých prirodzených čísel N. Tu je:

SÚČET = N/2 x (N+1)

      Jeho efektívnosť je optimálna – nech je počet prirodzených čísiel ľubovoľne veľký, pre zistenie súčtu stačí jedno sčítanie, jedno násobenie a jedno delenie.

Každý správny programátor by mal poznať nielen programovací jazyk, ale aj zásady pre tvorbu algoritmu. Tie by mali spĺňať šesť základných vlastností:

  • · elementárnosť – jednoduchosť a zrozumiteľnosť jednotlivých krokov,
  • · determinovanosť – jednoznačne definovaný nasledujúci krok,
  • · rezultatívnosť – pre rovnaké vstupy tie isté výsledky,
  • · konečnosť – algoritmus skončí po vykonaní konečného počtu krokov,
  • · hromadnosť algoritmus platí pre čo najväčší rozsah rozdielnych vstupných hodnôt,
  • · efektívnosť.

Efektívny algoritmus je taký algoritmus, ktorého vykonávanie je čo najrýchlejšie a nároky na operačnú pamäť sú minimálne. V praxi je veľmi ťažké zladiť dohromady obidve kritéria. Väčšinou je algoritmus buď veľmi rýchly, ale využíva pomerne veľa premenných – je časovo efektívny, alebo nie je čo najrýchlejší, ale zato všetky jeho premenné zaberajú minimálnu veľkosť operačnej pamäte – je pamäťovo efektívny. Ak porovnávame dva algoritmy, ktoré riešia správne tú istú úlohu, potom je časovo efektívnejší ten, ktorého vykonávanie pre rovnaké vstupné údaje trvá kratšie. Pamäťovo efektívnejší bude zasa ten, ktorého všetky premenné zaberajú menšiu operačnú pamäť. Úprava algoritmu na efektívnejší tvar sa nazýva optimalizáciou.

• Ako hodnotíme efektivitu algoritmov? Na konkrétnom algoritme ukážte spôsob hodnotenia efektivity.

 

Kritériá, ktoré sa obyčajne používajú pri hodnotení efektivity algoritmov, sa nazývajú

časová a pamäťová zložitosť algoritmov.

Pamäťovú zložitosť definujeme ako závislosť pamäťových nárokov algoritmu na veľkosti riešeného problému alebo vstupných údajov. Meriame ju spravidla v jednotkách veľkosti pamäti, teda v bitoch alebo bytoch.. Je to funkcia, ktorá každej hodnote vstupných údajov priraďuje počet pamäťových miest potrebných na uskutočnenie výpočtu.

Časovú  zložitosť určujeme počtom elementárnych operácií, ktoré budú uskutočnené pri výpočte programu so vstupnými údajmi. Je to  funkcia, ktorá každej hodnote N udávajúcej veľkosť konkrétneho problému priraďuje počet operácií vykonaných pri výpočte daného algoritmu. Táto funkcia je spravidla rastúca. Výborným  nástrojom pri  analýze časovej zložitosti algoritmov sú úlohy typu „koľko hviezdičiek program vypíše“.  Vhodné vloženie riadku vypisujúceho hviezdičky do programu umožňuje zistiť potrebný počet výpisov hviezdičiek, teda počet krokov algoritmu.

Napr.  Koľko hviezdičiek vypíše nasledujúca časť programu, ak premenná N obsahuje hodnotu 20?

   for i := 1 to N do

       for j := i + 1 to N do

write(‘*’);

Ľahkou simuláciou programu dostaneme , že počet výpisov riadkov je 190, teda aj taký počet hviezdičiek. Náš program obsahuje dva vnorené for-cykly, pričom rozsah každého z nich je nanajvýš  N . Dokopy teda tento algoritmus vykoná nanajvýš  N2  iterácií, a teda je jeho časová zložitosť nanajvýš  kvadratická od N . Toto môžeme matematicky zapísať: „tento algoritmus má časovú zložitosť O(N2).

Iste všetci z matematiky poznáme pojem najväčší spoločný deliteľ. Algoritmus výpočtu NSD pre dve zadané hodnoty,

Riešenie 1:

V tele cyklu sa robí jediný príkaz, znižovanie premennej NSD o 1.  Pre dvojicu čísel 24 a 42 by sme vykonali telo cyklu 18-krát.

 

Riešenie 2:

 Využime pre hľadanie NSD vylepšený Euklidov algoritmus. Jeho podstata je veľmi jednoduchá a matematicky by sme ju mohli zapísať takto:

             pre a<b je NSD(a,b-a)

NDS(a,b) =  pre a=b je a

            pre a>b je NSD(a-b,b)

 Ukážme si to na príklade čísel 24 a 42.

   a=24, b=42,         keďže 24<42, tak

   a=24, b=42 – 24 =18     keďže 24>18, tak

   a=24 – 18 =6, b=18      keďže 18>6, tak

   a=6, b=18 – 6=12       keďže 18>12, tak

   a=18 – 12=6, b=12        keďže 12>6, tak

   a=6, b=12 -6 =6        keďže 6=6, tak NSD(24,42)=6

 

       Program Euklidovho algoritmu pre výpočet NSD vyzerá takto:

       Pre dvojicu čísel 24 a 42 by sme vykonali telo cyklu 4-krát. Toto riešenie je oproti predošlému nielen časovo efektívnejšie, ale aj pamäťovo efektívne, lebo sme ušetrili jednu premennú.

Časová a pamäťová zložitosť algoritmu sa nedá nikdy presne určiť, vždy sa odhaduje iba približne. Napr. ak potrebujeme vykonať cyklus N-krát, potom jeho časová zložitosť O je N.t, kde t je konštanta, ktorá predstavuje čas vykonania tela cyklu. Veľakrát sa konštanta t zanedbáva a preto časová zložitosť takéhoto algoritmu je O(N) – ide o  funkciu tA takú,  že hodnota tA (N)  je najmenší počet krokov, ktoré  algoritmu stačia na spracovanie ľubovoľného vstupu veľkosti  N. Pri stanovení zložitosti algoritmov je  podstatná  rýchlosť rastu príslušnej funkcie. Napr. o algoritme, ktorého časovú zložitosť charakterizuje predpis 2N2 +3N + 1 stačí zistiť, že s rastúcim N sú jeho časové nároky úmerné N2 , čiže príslušná funkcia časovej zložitosti je kvadratická, čo zapisujeme v tvare O(N2).

V praxi používané algoritmy majú väčšinou niektorú z nasledujúcich zložitostí:

  • O(log N) – logaritmická
  • O(N) – lineárna
  • O(N log N) – lineárnologaritmická
  • O(N2) – kvadratická
  • O(N 3) – kubická
  • všeobecne O(NX) – polynomiálna
  • všeobecne O(XN) – exponenciálna.

Uvedené typické zložitosti algoritmov sú usporiadané vzostupne podľa rýchlosti rastu. Algoritmy, ktorých funkciu časovej zložitosti môžeme zhora obmedziť polynómom v N nazývame polynomiálne. Algoritmy s väčšou časovou zložitosťou nazývame exponenciálne. Ich typická časová zložitosť je  O(2N).

Aj keď majú dva algoritmy približne rovnakú časovú zložitosť je lepšie vybrať lepší, najmä ak pracujeme s veľkým počtom údajov. Typickým príkladom je triedenie údajov. Jednoduchšie triedenia majú časovú zložitosť O(N2), kým tie lepšie O(N.log N).,čiže prvý z nich urobí pri utriedení N čísel N2 operácií porovnania a druhý N. log N porovnaní . Pokiaľ by na istom počítači trvalo jedno porovnanie 0,1 ms, potom pri utriedení 100 čísel pomocou prvého algoritmu by trvalo  1 sekundu a pomocou druhého algoritmu 0,07 s.  Toto nie je veľký rozdiel, avšak ak by sme potrebovali utriediť 100 000 čísel rozdiel medzi oboma algoritmami bude zásadný: program s kvadratickou zložitosťou by počítal viac ako 11 dní, zatiaľ čo druhý algoritmus urobí prácu za necelé tri minúty.

Skúsme si teraz položiť otázku opačne: ak vieme, akú má náš program časovú zložitosť a vieme, ako dlho ho sme ochotní nechať bežať, aký najväčší vstup ešte stihne spracovať? V nasledujúcej tabuľke uvádzame názorný prehľad odpovedí na túto otázku pre niekoľko zaujímavých časových zložitostí.

Uvedieme ešte jeden príklad na výpočet časovej zložitosti konkrétneho algoritmu

Napr.: Danica vlani dostala od šéfa za úlohu zistiť, či nemajú v databáze zákazníkov nejakého zákazníka omylom viackrát. Túto úlohu vyriešila tak, že napísala program, ktorý porovnal každú dvojicu zákazníkov. Keď ho spustila, program necelé dve minúty bežal a na záver vypísal, že žiadne duplikáty nenašiel. Dnes má firma trikrát toľko zákazníkov ako pred rokom. Ak by dnes Danica spustila svoj program (na tom istom počítači ako vlani), ako dlho by čakala, kým program dobehne?

Riešenie : O Danicinom programe opäť môžeme rozumne predpokladať len jediné: že jeho časová zložitosť je kvadratickou funkciou od počtu zákazníkov. Teraz už len stačí, keď si uvedomíme, že nič viac ani vedieť nepotrebujeme. Ak si počet zákazníkov označíme  N, tak pre dostatočne veľké N,   bude časová zložitosť Danicinho programu takmer presne priamo úmerná N2. Stačí si uvedomiť, že počet krokov, ktoré program vykoná pre 3N zákazníkov, musí byť s rovnakým koeficientom priamo úmerný číslu (3N)2. A keďže (3N)2 = 9N2,  bude to programu trvať 9-krát dlhšie ako v prvom prípade — čiže približne štvrť hodiny.

Uveďte príklad, ktorý je možné riešiť pomocou pažravej metódy a uveďte riešenie

 

Niektoré typy algoritmických príkladov môžeme riešiť pažravou metódou. Ak riešime úlohu pažravo, znamená to, že v každej situácii sa snažíme nájsť najlepšie možné riešenie a dúfame, že výsledné riešenie bude tiež najlepšie možné.

Príklad 1 : Úloha o zlate

Skúste si napríklad ručne vyriešiť nasledovný prípad: Máme v hotovosti 300eur. Dnešná cena zlata je 34eur za gram. V nasledujúcich  dňoch sa táto cena bude meniť nasledovne: zajtra 32eur/g, pozajtra 30eur/g, v ďalších dňoch to bude postupne 35, 33 , 32 ,  38,  40 a 37 eur/g. Viete mať na konci posledného dňa 400eur? A dá sa dosiahnuť ešte viac?

Optimálne riešenie: Počkáme, kým cena  klesne na 30 eur za gram. Vtedy nakúpime za všetky peniaze 10 gramov zlata. Na druhý deň ho zase všetko  predáme, takže budeme mať 350 eur. Znova počkáme, kým cena klesne na 32 eur/g. Vtedy nakúpime zlato, budeme ho mať zhruba10,9  gramu. Počkáme si na cenu 40 eur/g a všetko zlato predáme, čím dostaneme výslednú sumu 437,5 eura.

Všimnime si, že v našej stratégii na riešenie úlohy sa striedajú dva kroky: počkáme  na lacné zlato a nakúpime; počkáme na drahé zlato a predáme. Ako ale exaktne definovať, čo je „lacné zlato , a teda kedy nakupovať a kedy predávať? Vo všeobecnosti sa algoritmus na nájdenie optimálneho zárobku dá sformulovať až prekvapujúco jednoducho. Všimnime si, že každú noc sa akosi zmení cena zlata. Ak narastie, chceme tú noc vlastniť zlato, aby sme rastom ceny zarobili. Ak klesne, chceme tú noc vlastniť peniaze, aby sme neprerobili.

Takto sa teda každý večer môžeme pažravo rozhodnúť, či chceme zlato alebo peniaze, a podľa toho nakúpiť alebo predať. V tejto jednoduchej úlohe sme sa teda stretli so situáciou, kedy sme globálne optimálne riešenie zostrojili tak, že sme postupne urobili niekoľko lokálne optimálnych rozhodnutí. (K najvyššiemu záverečnému kapitálu sme sa dopracovali  tak, že sme každý deň zodpovedali otázku: „Čo spraviť, aby som mal zajtra čo najviac peňazí? )

Veštica Teodora, ktorá sa nikdy nemýli, nám predpovedala, ako sa bude vyvíjať cena zlata v nasledujúcich dňoch. Ako s ním obchodovať, aby sme si čo najviac zarobili?

 

Príklad 2 : Dláždenie mesta

Bolo raz jedno mesto a to malo cesty nevydláždené. Akonáhle sa strhla búrka, všetky cesty boli zablatené.

Magistrát mesta sa rozhodol s touto situáciou niečo spraviť– vydláždiť niektoré cesty. Peňazí však nikdy nie je nazvyš, a tak chcú použiť čo najmenej dlaždíc. Na papieri dostanete obrázok mesta a cesty medzi domčekmi. Pre každú cestu z obrázka vidíte, koľko dlaždíc treba na jej vydláždenie. Vyfarbite cesty, ktoré chcete vydláždiť. Tieto cesty vyberte tak, aby sa po nich dalo dostať z každého domčeka do každého. Pokúste sa položiť čo najmenej dlaždíc.

Jedno možné riešenie :

Začneme z ľubovoľného domčeka. K nemu pripojíme jeho najbližšieho suseda (t. j. toho, ku ktorému vedie cesta s najmenej dlaždicami). Teraz nájdeme spomedzi zvyšných domčekov ten, ktorý vieme najlacnejšie pripojiť k jednému z prvých dvoch, a pripojíme ho k nim. Postup opakujeme, až kým k vznikajúcej cestnej sieti postupne nepripojíme všetky domčeky.

Príklad 3 : Navrhnite nejakú sadu nominálnych hodnôt mincí, pre ktorú pažravý algoritmus nefunguje – teda existuje suma, ktorá sa dá zaplatiť menej mincami ako povie pažravý algoritmus.

Riešenie : Takouto sadou  mincí môže byť napríklad  sada obsahujúca hodnoty 6 korún, 4 koruny a 1 koruna. Ak by sme chceli zaplatiť sumu 8 korún, pažravý algoritmus by nám poradil zaplatiť troma mincami: 6, 1, 1. Lepšie by však bolo zaplatiť dvoma mincami, 4 a 4.

 

Čo to teda sú tie pažravé algoritmy?

Ak riešime úlohu pažravo, znamená to, že v každej situácii sa snažíme nájsť najlepšie možné riešenie a dúfame, že výsledné riešenie bude tiež najlepšie možné. V úlohe o zlate to znamenalo, že v každej situácii sme nakupovali na poslednú chvíľu, kým ešte cena klesala a predávali na poslednú chvíľu, kým cena stúpala.

V úlohe o dláždení mesta sme dláždili tie cesty, na ktoré stačilo použiť najmenej dlaždíc.

Takýto postup je prirodzený, lebo väčšina ľudí sa správa pažravo „od prírody―, či už pre uspokojenie svojich potrieb alebo potrieb rodiny. Ak však chceme nachádzať optimálne riešenia, musíme si dávať pozor na to, či pažravá stratégia dáva naozaj optimálne riešenie pre konkrétnu úlohu.

 

Reklamy

Pridaj komentár

Zadajte svoje údaje, alebo kliknite na ikonu pre prihlásenie:

WordPress.com Logo

Na komentovanie používate váš WordPress.com účet. Odhlásiť sa / Zmeniť )

Twitter picture

Na komentovanie používate váš Twitter účet. Odhlásiť sa / Zmeniť )

Facebook photo

Na komentovanie používate váš Facebook účet. Odhlásiť sa / Zmeniť )

Google+ photo

Na komentovanie používate váš Google+ účet. Odhlásiť sa / Zmeniť )

Connecting to %s