Algoritam

Izvor: Wikipedija

Algoritam ili postupnik^[1] je konačni niz dobro definiranih i slijednih pravila za rješavanje nekog problema. U životu se često susrećemo s problemima koji se mogu algoritamski opisati. Takve situacije zahtjevaju od čovjeka poštivanje zadanog niza pravila, jer samo takvo ponašanje dovodi do očekivanog kraja ili rezultata. Nezaobilazna je primjena algoritama u računalstvu gdje čine velik dio tog dijela znanosti.

[uredi] Kuhanje čaja kao primjer algoritma

Najčešći primjer algoritma iz svakodnevnog života jest kuhanje čaja. Svaki korak pripremanja čaja mora biti ispravno izvršen kako bi mogli prijeći na idući te u konačnici dobiti topao i ukusan čaj. Ovaj se primjer može naći u većini početničke literature kao lako shvatljiv primjer osnovnih svojstava algoritama.

Kako najlakše skuhati čaj? Evo odgovora:

Stavi lonac s vodom na vatru
Čekaj dok ne uzavre
Pazi da voda ne pokipi
Kad uzavre voda, ugasi vatru
Stavi kesice čaja u vodu
Ako želiš, dodaj šećera
Ako želiš, dodaj limun
Posluži se

I to je to! Dobili smo šalicu vrućeg čaja pa ćemo lakše podnijeti prehladu koja nas danima muči. Iz ovog se jednostavnog primjera jasno vidi slijednost i konačnost algoritma. Naime, nema previše koristi od algoritma koji nikad ne završava. Očito je da algoritam definira način kako se neki problem rješava.

[uredi] Kratka povijest

Riječ "algoritam" dolazi od latinskog prijevoda imena arapskog matematičara Muhammad al‑Khwarizmija, koji se bavio trigonometrijom, astronomijom, zemljopisom, kartografijom, a smatra se ocem algebre jer je definirao osnovna pravila rješavanja linearnih i kvadratnih jednadžbi. Njegovi radovi su osnova razvoja mnogih matematičkih i prirodnih disciplina, među njima i računalstva..

Prvi zapis algoritma prilagođen računalu pripada Adi Byron iz 1842 (pa se zbog ovoga smatra prvom programerkom), a računao je Bernoullijeve brojeve. Računalo za koje je napisan je bio analitički stroj, kojeg je zamislio, ali nikad u potpunosti proveo u djelo, Englez Charles Babbage. Analitički stroj je trebalo biti prvo programabilno računalo, sastavljeno u potpunosti od mehaničkih dijelova. Mehanički dijelovi i fizička glomaznost su glavni razlozi zašto nikad nije završen.

Nedostatak čvrste matematičke forme pravio je određene probleme matematičarima i logičarima 19. i 20. stoljeća prilikom analiziranja algoritama. Definicija Turingovog stroja je riješila većinu tih problema, a predstavio ju je engleski matematičar Alan Turing. Turingov stroj omogućava izvođenje većine današnjih algoritama (uz određene prilagodbe), a dodatno olakšava i analizu složenosti zbog svoje jednostavnosti izvedbe (glava, funkcija pomaka glave te beskonačna ili jako duga traka za čitanje/pisanje).

Primjenom Turingovog stroja kao idealnog modela definirani su mnogi moderni problemi vezani uz analizu algoritama, kao npr. Turingov problem zaustavljanja ili klase NP-teških i NP-potpunih problema.

Ovaj dio članka je nedovršen ili treba nadopune. Pomozite Wikipediji i dopunite ga.

[uredi] Algoritmi u računarstvu

Moderno računarstvo je nezamislivo bez primjene algoritama, njihove matematičke analize te postupcima ubrzavanja njihova izvođenja (optimiranje, optimiziranje). Sva su ta područja povezana i međusobno se nadopunjuju.

Ovaj dio članka je nedovršen ili treba nadopune. Pomozite Wikipediji i dopunite ga.

[uredi] Analiza složenosti algoritama

Analiza složenosti algoritama vrlo je važna disciplina zboga toga što omogućuje vrlo dobro predviđanje resursi potrebnih da dani algoritam obradi dani set unosa. Uobičajeno je složenost algoritama izražavati kao matematičku funkciju koja veličinu unosa pretvara u količinu vremena potrebnu da se algoritam završi (vremenska složenost) ili količinu prostora potrebnu da se algoritam završi (memorijska složenost). Vrlo često se analiza složenosti algoritama provodi isključivo uz pomoć papira i olovke bez osvrtanja na pojedinačne implementacije u pojedinim programskim jezicima.

Ovaj dio članka je nedovršen ili treba nadopune. Pomozite Wikipediji i dopunite ga.

[uredi] Klasifikacija algoritama

Algoritme je moguće klasificirati po raznim kriterijima:

Klasifikacija prema implementaciji Jedan način klasifikacije algoritama je prema načinu implementacije.

Rekurzivni ili iterativni: Rekurzivni algoritam je algoritam koji poziva samog sebe sve dok se ne postigne određen uvjet. Rekurzivni algoritmi su vrlo često usko vezani uz implementaciju pojedine matematičke funkcije na primjer Fibbonačijeve funkcije. Iterativni algoritmi su algoritmi koji ne pozivaju samog sebe već se oslanjaju na konstrukte poput petlji i dodatne strukture podataka kao što je stog ili red da bi riješili problem. Važno je napomenuti da je svaki rekurzivni algoritam moguće pretvoriti u iterativni, i da je svaki iterativni algoritam moguće pretvoriti u rekurzivni, iako ponekad pretvaranje može biti vrlo kompleksno.

Serijski ili paralelni: Većina današnjih računala sadrži samo jedan procesor te stoga obavlja naredbe jednu po jednu, to jest serijski. Algoritmi koji su dizajnirani sa namjerom da se izvršavaju u takvom okruženju shodno tome se nazivaju serijski algoritmi. Suprotno njima su paralelni algoritmi koji sa sve većim probojem višeprocesorskih računala dobivaju sve veću važnost. Paralelni algoritmi koriste mogućnost višeprocesorskog sustava na taj način da problem rascijepe na više malih potproblema koje svaki procesor rješava zasebno te se zatim rezultati spajaju. Paralelni algoritmi uz resurse potrebne za obradu podataka također imaju i malu potrošnju resursa na komunkaciju između više procesora. Algoritmi za sortiranje su jedan od primjera algoritama koje je moguće znatno poboljšati upotrebom paralelnih procesora, dok je probleme poput problem tri tijela sasvim nemoguće riješiti paralelnim algoritmom.

Deterministički ili stohastički: Deterministički algoritam je algoritam koji će pri svakom izvršavanju u bilo kojim uvjetima od istog unosa doći do istog izlaza sljedeći svaki put identičan niz naredbi. Stohashički algoritmi je algoritam koji barem u jednom dijelu izvršavanja donese neku odluku slučajnim odabirom.

Točan ili približan: Iako algoritmi u principu daju točan rezultat, ponekad algoritam traži približno rješenje koje je dovoljno blizu točnom, ili je točno rješenje nemoguće naći.