Algoritem je navodilo, s katerim rešujemo nek problem. Običajno je zapisan kot seznam korakov, ki nas pripeljejo do rešitve problema. Kako podrobno razdelamo korake, je odvisno od tega, ali izvaja algoritem človek ali računalnik. Če algoritem izvaja računalnik, potem govorimo o računalniškem programu. Primer algoritma iz vsakdanjega življenja je kuharski recept.

Značilnosti algoritma

1. (lahko) ima podatke,
2. (običajno) vrne rezultat,
3. je natančno določen,
4. je končen,
5. je izvedljiv.

Kategorije algortimov

1. deli in vladaj
2. dinamično programiranje
3. požrešna metoda
4. linearno programiranje
5. verjetnostni algoritmi

Historia est mater studiorum - zgodovina je mati modrosti

Če je tvoja vojska desetkrat številčnejša od sovražnikove, ga obkoli, če je petkrat močnejša, napadi, če je dvakrat večja, razbij njegovo na dva dela. Armado 100000 mož je veliko lažje premagati, če jo razbiješ na dva dela po 50000 mož in premagaš vsak del zase. Če želiš vladati, poskrbi, da so tvoji sovražniki med seboj razdeljeni in ne združeni. V sovražnikove vrste vnesi neenotnost – razdeli jih in lahko jih boš premagal.

Deli in vladaj kot strategija algoritmov

Pri metodi deli in vladaj nalogo rešujemo tako, da jo razdelimo na manjše naloge istega problema in iz rešitev manjših nalog sestavimo rešitev prvotne naloge. Postopek nadaljujemo rekurzivno, dokler ne dobimo dovolj majhne naloge, ki jih rešimo neposredno. Kot že samo ime pove, deluje tako, da problem, ki se ga lotimo, razdelimo (faza deli) in ga nato rešimo (faza vladaj).

FAZA DELI osnovni problem razbije na dva podproblema. Če sta tudi ta dva prevelika, ju razbijemo na nove podprobleme. Postopek nadaljujemo, dokler ne pridemo do problemov, ki jih obvladamo.

FAZA VLADAJ rešitve preprostih problemov združuje v neko končno rešitev. S takšnim postopkom lahko pridemo tudi do rekurzivnih rešitev. A to ni pravilo. Če je problem dovolj enostaven, lahko do rešitve pridemo tudi brez metode deli in vladaj.

Pri strategiji deli in vladaj se pojavljata dve skupini problemov. V prvo skupino sodijo problemi, pri katerih je rešitev enega od podproblemov kar rešitev začetnega problema, kar pomeni, da združevanje rešitev ni potrebno. V drugo skupino sodijo problemi, za katere končno rešitev dobimo tako, da z nekim postopkom združujemo rešitve podproblemov. Klasičen primer metode deli in vladaj, kjer je rešitev enega od podproblemov hkrati rešitev začetnega problema, je iskanje elementa v urejenem zaporedju s pomočjo bisekcije. Urejanje z zlivanjem pa je klasičen primer metode deli in vladaj, kjer končno rešitev dobimo z združevanjem rešitev podproblemov.

Splošen rekurziven algoritem metode deli in vladaj, kjer moramo rešitve podproblemov združiti, bi lahko opisali z naslednjo pseudokodo: Metoda  RazdeliProblem()  razdeli problem na dva podproblema, ki ju po potrebi znova delimo, kar je prikazano z rekurzivnim klicem za oba podproblema. Ko podproblema rešimo, rašitvi posameznih podproblemov združimo v rešitev začetnega problema.

Pseudokoda za skupino problemov, kjer je rešitev začetnega problema rešitev enega od podproblemov, kar pomeni, da združevanje ni potrebno, je:

1. Urejanje podatkov (hitro urejanje podatkov, urejanje z zlivanjem)
2. Iskanje (bisekcija, poišči najmanjšega/največjega, iskanje k-tega elementa po velikosti)
3. Algotirmi nad dvojiškimi drevesi
4. Moženje polinomov in matrik
5. Računska geometrija

Dana naj bo zvezna funkcija na intervalu , zanjo naj velja . To pomeni, da ima funkcija na tem intervalu vsaj eno ničlo, saj je v krajiščih intervala različno predznačena.

Radi bi poiskali ničlo.

Ideja je, da na danem intervalu preverimo, ali velja pogoj . Če je pogoj izpolnjen, dani interval razdelimo na pol. Tako dobimo nova intervala in . Za oba intervala preverimo pogoj: ali velja ali . Interval, za katerega velja, da je produkt funkcijskih vrednosti pri njegovih mejah negativen, delimo naprej. Postopek nadaljujemo, dokler ne ugotovimo, da je ničla ena od meja intervala ali sredinska točka. Da bi se postopek res končal, moramo omejiti velikost najmanjšega podintervala. Ko pridemo do takšnega najmanjšega intervala, za katerega je pogoj o predznaku izpolnjen, vrnemo kot ničlo sredino tega intervala.

Pseudokoda:

Koliko faz ima metoda deli in vladaj?

Nazaj Naprej

Izberi kategorije algoritmov.

Nazaj Preveri Naprej

Vsak začetek stavka v levem stolpcu dopolnite z ustreznim nadaljevanjem na desni strani.

Nazaj Preverite Naprej

• http://sl.wikipedia.org/wiki/Algoritem

• http://wiki.fmf.uni-lj.si/wiki/Metoda_deli_in_vladaj

• http://matematika-racunalnistvo.fnm.uni-mb.si/Lists/novice/Attachments/159/sklop02.pdf

• Lokar, Matija. Deli in vladaj, strategija razvoja algoritmov (prosojnice s predavanj)