Algoritmi - uvod

Uvod

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 (tj. "što efikasniji")

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.

U praktičnom smislu, može se reći da razna uputstva za sastavljanje nameštaja i uređaja, recepti u kulinarstvu, propisi za praćenje semafora na raskrsnicama i sl, predstavljaju sasvim adekvatne primere procedura iz spoljnjeg sveta - koje podsećaju na računarske algoritme, a što se tiče 'konkretnijeg' uvodnog 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', takođe je prilično zanimljiv, * i 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.

U idejnom smislu, algoritam je postupak za rešavanje određenog problema, što praktično znači 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), termin 'algoritam' se odnosi 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 razni teoretski modeli koji su zanimljivi sami po sebi i deluju kao 'rešenja', ali, nisu praktično dokazivi, ponekad se oslanjaju na "tehnologije budućnosti" i sl. - što znači da 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 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 ćemo razmotriti 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), računari 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 se poredi 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;
}

printf("Najveći = %d\n", najveci);

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

U gornjem primeru, možemo zapaziti 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 / sreću / "tehnologije budućnosti" - niti smo se nadali tome da će se problem 'rešiti sam od sebe' i sl)

Zarad starijih i iskusnijih čitalaca, navešćemo da nije teško "prepraviti" (to jest uopštiti) prethodno prikazani postupak, tako da se može koristiti za pronalaženje najveće od n unetih vrednosti:

promenljivoj koja skladišti najveću pronađenu vrednost, na početku se dodeljuje 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];
	}
}

printf("Najveći = %d\n", najveci);

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

Donekle smo uprostili programski 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 koja je veća od 1).

Dodatna razmatranja

Za kraj, osvrnućemo se dodatno na efikasnost algoritama i ispravnost podataka koji se 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 tipično 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 najčešće 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 (uskoro) 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 korisnici unose direktno), međutim, svaki algoritam mora imati bar jedan izlazni podatak.

Ukoliko ulazni podaci postoje, potrebno je definisati očekivani tip ulaznih podataka, 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 praktičnom smislu nisu ništa drugo nego apstraktne ideje - mogu poprimiti 'spoljni oblik' 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).

Autor članka Nikola Vukićević Za web portal codeblog.rs

Napomena: Tekstovi, slike, web aplikacije i svi ostali sadržaji na sajtu codeblog.rs (osim u slučajevima gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta codeblog.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo drugo korišćenje u komercijalne svrhe, bez eksplicitnog pismenog odobrenja autora.