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

* Iako ne postoji opšteprihvaćeni dogovor oko porekla termina "algoritam", tipično se smatra da je u pitanju kombinacija neadekvatnog prevoda i 'opšte ležernosti': Muhamed Al Horezmi je autor dela "Račun sa Hindu brojkama" (cca. 825), koje je prevedeno na latinski jezik u 12. veku, međutim, prevod naslova je glasio "Algoritmi de numero indiorum" ('Algoritmi' o indijskim brojevima), pri čemu možemo samo pretpostaviti da je naslov trebalo da glasi: "Al Khwarizmi de numero indiorum" (to jest, "Al Horezmi o indijskim brojevima"). U pomenutom delu prikazani su postupci za obavljanje različitih operacija sa 'indijskim brojevima' (koji su u ono vreme bili zanimljiva novotarija), i stoga je, "nekako", tokom vremena, reč algoritam postala sinonim za 'postupak za rešavanje određenog problema'.

Detaljnija analiza (sa primerima)

Pre svega (kao što je već navedeno), 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 da se zadati brojevi zapišu 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

		
// 1:
a = 9;
b = 4;
c = 17;

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

// 3:
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, mogu se zapaziti odlike koje su navedene ranije:

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 najvećom vrednošću koja je pronađena do tada
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, razmotrićemo 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).

Pored svega do sada navedenog, 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), a ako ulazni podaci postoje (što je najtipičniji slučaj), potrebno je definisati očekivani tip ulaznih podataka, i dozvoljeni raspon vrednosti. *

Međutim, nasuprot "opcionalnosti" ulaznih podataka, u svakom algoritmu mora postojati bar jedan izlazni podatak.

Što se tiče ispravnosti rezultata, algoritamski postupci 'po definiciji' proizvode korektne rezultata ukoliko su ulazne vrednosti ispravne, međutim, potrebno je (pogotovo u praktičnom smislu, tj. u smislu svakodnevne eksploatacije računarskih programa), 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).

Što se tiče (ranije pomenute) mogućnosti da ulazni podaci izostanu - što može delovati pomalo čudno na prvi pogled - u pitanju je pojava koja se u praksi sreće prilično često, što ćemo ilustrovati preko nekoliko primera.

Ukoliko je (npr) zadatak da se generiše prvih 100 decimala broja π (ili prvih 100 prostih brojeva i sl), vrednost 100 je (praktično) deo programskih instrukcija tj. nije nešto što unose korisnici (najjednostavnije: program treba da generiše 100 decimala broja π svaki put kada se pokrene, za razliku od programa koji bi trebalo da generiše n decimala broja π, i da pri tom n bude vrednost koju korisnici programa upisuju pre nego što se pokrene rutina za generisanje decimala).

Pored svega do sada navedenog, postavlja se i pitanje prikazivanja rezultata, što (ponovo) možemo razmotriti uz osvrt na program koji ne zahteva korisnički unos.

Na primer, program koji očitava tačno vreme, ni na koji način ne zavisi od podataka koje korisnici unose, ali - budući da se na kraju izvršavanja programa moraju pojaviti izlazni podaci - bilo bi veoma čudno kada bi 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). :)

Međutim, iako se rezultati izvršavanja programa tipično prikazuju korisnicima na neposredan način ("na ekranu"), ne mora uvek biti tako, to jest, rezultat može biti zapisan u datoteku i sl.

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.