Algoritem
Iz E-študij, proste zakladnice študentskega znanja
Algoritem je končno zaporedje natančno določenih ukazov, ki opravijo neko nalogo v končnem številu korakov. Algoritem ima vhodne podatke in vrne rezultat.
Program je Algoritem, ki ga lahko izvajamo na računalniku, ker je zapisan v programskem jeziku.
Vsebina |
Razvoj algoritma
| matematični model | abstraktni podatkovni tipi | podatkovne strukture | ||
| | → | | → | |
| neformalni algoritem | psevdokoda | program |
Izražanje
Algoritem lahko izrazimo na več načinov:
- narišemo z diagrami poteka
- zapišemo človeku razumljivo s psevdokodo
- zapišemo računalniku razumljivo v programskem jeziku
Čeprav večinoma želimo algoritme izvajati na računalniku, želimo da so naši opisi relativno neodvisni od programskega jezika v katerem bo algoritem na koncu zapisan. S tem olajšamo prenosljivost algoritma na druge sisteme.
Zasnova
Pri snovanju algoritma si pomagamo z osnovnimi principi pri reševanju problemov.
- problem moramo razumeti, drugače ga ne moremo reševati
- opis abstrahiramo tako, da se obdržijo samo pomembni podatki
- izberemo ustrezno notacijo, ki omogoči učinkovito reševanje problema
- problem razbijemo na podprobleme, pomagamo si s psevdokodo in metodo zaporednih izboljšav
- uporabimo eno od znanih strategij, npr. strategijo deli in vladaj
- problem poizkušamo transformirani v problem, katerega rešitev že poznamo
Analiza algoritma
Vsak algoritem mora biti pred realizacijo na računalniku analiziran, nekatere analize so koristne že pri zasnovi algoritma, da ne razvijamo algoritma, ki bi bil zaradi neučinkovitosti na koncu neuporaben.
Ugotoviti moramo sistemske zahteve, kakršne bo algoritem potreboval. Najpomembnejši lastnosti sta količina potrebnega pomnilnika in čas izvajanja. S predvidevanjem časa izvajanja se ukvarja analiza časovne zahtevnosti algoritmov.
Pri razvoju algoritma moramo izbirati strategije preiskovanja, katere nam bodo v sprejemljivi količini časa vrnile želeni rezultat.
http://en.wikipedia.org/wiki/Analysis_of_algorithms
Preverjanje algoritma
Preverjanje s testiranjem
Algoritem lahko preizkusim z različnimi vhodnimi podatki. Ta metoda lahko dokaže samo nepravilnost delovanja, kajti v praksi pravilnosti ni možno dokazati, ker je vseh možnih kombinacij vhodnih podatkov enostavno preveč razen v primerih najbolj enostavnih algoritmov.
Formalno dokazovanje algoritma
Formalno dokazovanje se izvaja z algebro. Zaradi zapletenosti in matematične zahtevnosti pa pogosto ni primerno za praktično uporabo in se uporablja le v najbolj pravilnostno-kritičnih sistemih (vesolje, letala ipd).
