Algoritmi - uopšteno

Termin 'algoritam', koji se često sreće u matematici i još češće u računarskoj tehnici, označava precizno definisan postupak preko koga se dolazi do rešenja za određeni problem, pri čemu važe sledeća pravila.

postupak mora biti konačan (to jest, mora se sastojati iz konačnog broja koraka)
pojedinačni koraci moraju biti nedvosmisleni i precizno definisani
pojedinačni koraci moraju biti ostvarivi (na računaru)
ulazi i izlazni podaci moraju biti precizno definisani
postupak mora biti efikasan

Pored do sada navedenih stavki, pravila nalažu i to da algoritam mora proizvesti iste izlazne vrednosti svaki put kada se ulazne vrednosti ponove, kao i to da mora važiti za veći broj različitih ulaznih vrednosti.

Može se reći da su razna uputstva za sastavljanje nameštaja i uređaja, recepti u kulinarstvu i sl, sasvim adekvatni primeri procedura iz spoljnjeg sveta - koje podsećaju na računarske algoritme, a što se tiče 'konkretnijeg' primera iz oblasti računarske tehnike (sa kojim se možete upoznati odmah posle uvodnog članka), predlažemo osvrt na algoritam binarne pretrage.

Sam naziv 'algoritam', vezuje se za prezime persijskog matematičara Muhameda Al Horezmija (Muhhamad ibn Musa al-Khwarizmi, cca. 780-850), * koji se kolokvijalno smatra ocem moderne algebre.

Ako je algoritam (u idejnom smislu), postupak za rešavanje određenog problema, može se smatrati da je program realizacija (tj. ostvarenje) algoritma.

U nastavku, detaljnije ćemo razmotriti pojedinačne kriterijume koji su izneti na početku ....

Detaljnija analiza (sa primerima)

Pre svega (kao što smo već naveli), pojam 'algoritam' odnosi se na postupke koji su konačni, ostvarivi i nedvosmisleno usmereni ka postizanju određenog rezultata, to jest, na postupke koji, posle konačnog broja uzastopnih koraka - pod uslovom da su ulazni podaci ispravni - dovode do rešenja (drugim rečima: postoje i različiti teoretski modeli, koji su zanimljivi sami po sebi, ali, nisu praktično dokazivi, ponekad se oslanjaju na "tehnologije budućnosti" i sl, i stoga - ne predstavljaju algoritme).

Iz prethodnih konstatacija, praktično proizilaze i pravila koja se tiču pojedinačnih koraka, koji moraju biti jasni, nedvosmisleni i izvodljivi, pri čemu redosled pojedinačnih koraka mora biti jasno definisan, a takođe je potrebno i da pojedinačni koraci budu nezavisni od (konkretnih) programskih jezika (to jest, potrebno je da pojedinačne naredbe u algoritmima budu prilagođene uobičajenim naredbama kakve se sreću u većini programskih jezika).

Na kraju, ukoliko je "plan": ostvariv, konačan i precizno definisan, svakako je (veoma) bitno da bude i efikasan.

U nastavku, razmotrićemo jednostavan praktičan primer (posle čega ćemo se dodatno osvrnuti na efikasnost algoritama i ispravnost ulaznih podataka).

Primer

Uzmimo za primer postupak preko koga je potrebno utvrditi najveću od tri zadate vrednosti, pri čemu je (nadamo se :)), jasno da računari nemaju sposobnost 'uvida', to jest, sposobnost da među nasumičnim brojevima kao što su (npr) 9, 4 i 17, neposredno prepoznaju broj 17 kao najveći.

Računari raspolažu memorijom (što znači da se podaci mogu skladištiti), takođe raspolažu logičkim kolima koja su u stanju da porede brojčane vrednosti, i stoga je programerima omogućeno da samostalno osmisle proceduru za rešavanje zadatka:

za početak, potrebno je zadate brojeve zapisati u memoriju
nakon upisa, prva dva broja se porede i pamti se veća od dve vrednosti
rezultat iz prethodnog koraka poredi se sa trećom ulaznom vrednošću i ponovo se pamti veći od dva broja
rešenje je rezultat poređenja iz 3. koraka

		
a = 9;
b = 4;
c = 17;

if (a > b) {
	najveci = a;
}
else {
	najveci = b;
}

if (c > najveci) {
	najveci = c;
}

Slika 1. - Programski kod preko koga se pronalazi najveći od tri uneta broja

U gornjem primeru možemo zapaziti sledeće odlike (koje smo ranije naveli):

postupak je konačan i efikasan, sa precizno definisanim pojedinačnim koracima (svega dva poređenja; prvo poređenje približava nas rešenju, a drugo dovodi do rešenja)
postupak je ostvariv na računaru (korišćeni su računarski resursi i nismo se oslanjali na ljudsku intuiciju, "tehnologije budućnosti" .... niti smo se nadali tome da će se problem 'rešiti sam od sebe' i sl)

Zarad starijih i iskusnijih čitalaca, navedimo da prethodno prikazani postupak lako može biti "prepravljen", to jest uopšten, tako da se dobije algoritam koji pronalazi najveću od n unetih vrednosti:

promenljivoj koja skladišti najveću pronađenu vrednost, dodeljuje se vrednost prvog elementa niza
potom se svi elementi - od drugog do poslednjeg - porede sa do tada najvećom pronađenom vrednošću
ukoliko se u nekom koraku pronađe nova najveća vrednost, promenljivoj najveci dodeljuje se pronađena vrednost

		
int a[10]   = { -1, 3, 12, 4, -5, 7, 14, 15, -1, 10 };
int najveci = a[0];
int i       = 1;   // indeks se postavlja na 2. element niza
int g       = 10;  // granica (to jest, ukupan broj elemenata) 

while (i < g) {
	if (a[i] > najveci) {
		najveci = a[i];
	}
}

Slika 2. - Programski kod preko koga se pronalazi najveći od n unetih brojeva.

Donekle smo uprostili kod (izostavljanjem dela koji se tiče učitavanja), ali, princip pretrage i dalje važi (petlja koja prolazi kroz niz, obaviće pretragu za bilo koju vrednost promenljive g, veću od 1).

Dodatna razmatranja

Za kraj, osvrnućemo se dodatno na efikasnost algoritama i ispravnost podataka koji su unose u programe (to jest, na to kako program treba da reaguje ukoliko ulazni podaci nisu ispravni).

Efikasnost algoritama

Kada je u pitanju efikasnost algoritama, počnimo od sledeće konstatacije: ukoliko je određeni problem moguće rešiti uopšte, gotovo je sigurno da se dati problem može rešiti na više načina, iz čega praktično proizilazi da je optimalan postupak, najčešće, * onaj postupak koji podrazumeva najmanje vreme izvršavanja i najmanje dodatno memorijsko zauzeće.

U teoriji, algoritmi se ne klasifikuju shodno tome koliko vremena je potrebno za izvršavanje, to jest, shodno memorijskom zauzeću (pri čemu vreme izvršavanja i memorijsko zauzeće svakako jesu bitni faktori), već se algoritmi tipično klasifikuju shodno tome na koji način vreme izvršavanja zavisi od količine ulaznih podataka, odnosno, po tome na koji način dodatno memorijsko zauzeće zavisi od količine ulaznih podataka.

U praktičnom smislu, potreba za što efikasnijim postupcima za rešavanje računarskih problema, nešto je što programere prati tokom celog 'radnog veka' (jedni se trude da iznađu što efikasnija rešenja, a drugi, da što lakše iskoriste već postojeća).

Možemo pretpostaviti i to da većina (budućih) programera intuitivno razume potrebu za primenom efikasnih postupaka, ali, ukoliko vas zanima da se odmah upoznate detaljnije sa time kako primena različitih postupaka utiče na vreme izvršavanja, odnosno, sa time zašto je upotreba efikasnih algoritama, i dalje - i te kako bitna, možete ispratiti početnu diskusiju u uvodnom članku o binarnim stablima pretrage (koji smo još na početku preporučili vašoj pažnji).

Na samom kraju, vraćamo se na pitanje pravilnog formatiranja ulaznih i izlaznih podataka.

Još koja reč o ulaznim i izlaznim podacima

U najosnovnijem smislu, algoritmi mogu - ali i ne moraju - imati ulazne podatke (to jest, ne moraju postojati podaci koje korisnik unosi direktno), međutim, svaki algoritam mora imati bar jedan izlazni podatak.

Ukoliko ulazni podaci postoje, potrebno je definisati očekivani tip ulaznih podataka, kao i dozvoljeni raspon vrednosti.

Algoritamski postupak 'po definiciji' proizvodi korektan rezultat ukoliko su ulazne vrednosti ispravne, međutim, potrebno je (pogotovo u praktičnom smislu), da algoritam proizvede odgovarajući rezultat i onda kada ulazne vrednosti nisu ispravne (u navedenoj situaciji, odgovarajući rezultat je, najčešće - poruka o grešci).

Prethodno smo pomenuli da ulazni podaci mogu izostati, što, iako možda deluje pomalo čudno na prvi pogled, zapravo predstavlja pojavu koja se u praksi sreće prilično često.

Na primer, program koji očitava tačno vreme, ni na koji način ne zavisi od podataka koje korisnik unosi, ali - budući da se na kraju moraju pojaviti izlazni podaci - bilo bi veoma čudno kada bi pomenuti program "zadržao za sebe" informaciju o tačnom vremenu, to jest, izlazni podatak do koga se dolazi očitavanjem sistemskog časovnika (ili, prostije: bilo bi čudno kada program, na kraju, ne bi prikazao korisniku tačno vreme). :)

Algoritamski postupci - koji u pravom smislu reči nisu ništa drugo nego apstraktne ideje - mogu se realizovati na nekoliko načina: mogu se opisati rečima (kao što smo činili u ovom članku, i kao što ćemo činiti u mnogim budućim člancima), mogu se "pretočiti" u programe (kao što smo već pomenuli na početku), a kada su u pitanju jednostavniji algoritmi, postoji način da se ceo postupak predstavi i grafičkim putem, preko tzv. dijagrama toka (kojima smo posvetili kraći zaseban članak).