U matematici, računarstvu, lingvistici i srodnim disciplinama, algoritam ili postupnik je konačan slijed dobro definiranih naredbi za ostvarenje zadatka, koji će za dano početno stanje terminirati u definiranom konačnom stanju.

Koncept algoritma je potekao kao sredstvo zapisivanja postupaka za rješavanje matematičkih problema, poput pronalaženja zajedničkog djelitelja dvaju ili više brojeva ili množenja dvaju brojeva. Koncept je formaliziran 1936. u vidu Turingovog stroja Alana Turinga i lambda računa Alonza Churcha, koji su jedan za drugim postavili temelje računarstva.

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.

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.

Kratka povijest

Riječ “algoritam” dolazi od latinskog prijevoda imena iranskog matematičara Al‑Hvarizmija 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čunarstva..

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, koji 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.

Svojstva

Algoritmi imaju slijedeća svojstva:

• diskretnost — u odvojenim koracima izvode se diskretne operacije algoritma koje vode ka konačnom cilju;
• konačnost — označava sposobnost algoritma da nakon konačnog broja koraka daje izlazne podatke odnosno rezultate;
• determiniranost — za iste ulazne podatke algoritam uvijek daje iste rezultate
• masovnost — algoritam je primjenjiv na veći broj ulaznih vrijednosti.

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.

Analiza složenosti algoritama

Analiza složenosti algoritama vrlo je važna disciplina zboga toga što omogućuje vrlo dobro predviđanje resursa 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.

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.

Algoritmi s obzirom na metodologiju dizajna

Brute force algoritmi – “čistom silom” računala isprobavaju sve mogućnosti i traže odgovarajuće rješenje. Najneefikasnijji algoritmi.

Podijeli i vladaj algoritmi tzv. Divide and conquer, podijeli i vladaj. Problem se dijeli na više istih, manjih problema. Podjela teče tako dugo dok se ne dođe do malog problema kojeg je jednostavno riješiti (obično rekurzijom).

Dinamički algoritmi – Metodama dinamičkog programiranja rješavaju se višefazni procesi, tj. procesi u kojima se donosi niz međusobno ovisnih odluka za pojedine godine određenog razdoblja ili za pojedine aktivnosti zadanog problema. Dinamičko programiranje poznato je i pod nazivom metoda donošenja višefaznih, odnosno višestupnjevanih odluka.

Pohlepni algoritmi tzv. greedy – Pohlepni algoritam je algoritam koji se koristi metaheuristiku za rješavanje problema, takvu da u svakom koraku bira lokalno najbolje rješenje, u nadi da će tako iznaći globalni optimum. Ovi algoritmi često ne daju najbolje rješenje već brzu aproksimaciju najboljeg rješenja.

Algoritmi za sortiranje i pobrojavanje tzv. search and enumeration – Algoritmi sortiranja služe za brzo sortiranje podataka, npr. niza brojeva. Mnogi se problemi mogu rješavati teorijom grafova.