Significations et usages de algoritam

Izvor: Wikipedia

Za istoimenu knjižaru vidi: Knjižara "Algoritam"

U matematici, računarstvu, lingvistici i srodnim disciplinama, algoritam ili postupnik^[1] 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 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 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č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 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.

Klasifikacija algoritama

Algoritme je moguće klasificirati po raznim kriterijima:

Klasifikacija prema implementacijiJedan 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.

Izvori

Nedovršeni članak Algoritam koji govori o matematici treba dopuniti. Dopunite ga prema pravilima Wikipedije.

Nedovršeni članak Algoritam koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.