5. Definicija i zadatak algoritma
Definicija i zadatak algoritma
** Najkraće rečeno:
** Algoritam - uređen, konačan skup uputstava koji u konačnom broju koraka daje rezultate za proizvolјan izbor dopuštenih ulaznih podataka.
** Program - opis algoritma u nekom programskom jeziku.
Računar je programabilna mašina.
U raznim naučnim disciplinama, ali i u običnom životu često probleme rešavamo prateći precizno definisane postupke. Na primer, dok kuvamo ili pravimo kolače obično pratimo recept koji opisuje postupak koji treba sprovesti da bismo pripremili ukusno jelo. U fizici i matematici koristimo veliki broj formula. Često kažemo da su zadaci koji se mogu rešiti praćenjem nekog postupka „šablonski” i da onaj ko nauči šablon tj. postupak rešavanja, taj može da reši bilo koji zadatak tog tipa. Umesto reči postupak tj. šablon, u matematici i računarstvu se najčešće koristi reč algoritam.
Računari nisu inteligentne mašine. Jedino u čemu su računari dobri je to što mogu jako brzo da sprovode precizno opisane postupke. Dodatno, postupci u računaru uvek govore kako se barata sa brojevima (obično binarno zapisanim) – podsetimo se: računari su digitalni i svi sadržaji kojima pristupamo kodirani su pomoću brojeva. Samim tim, računarski algoritmi su po svojoj prirodi matematički. Da bi računar mogao da sprovede neki algoritam, taj algoritam mora biti opisan na veoma preciznom programskom jeziku, u obliku računarskog programa.
Pojam algoritma
Neformalno, možemo reći da algoritam definiše niz precizno opisanih elementarnih koraka čijim se doslednim sprovođenjem dolazi do rešenja nekog problema.
Definicija 2
Algoritam je konačan i precizno definisan proces, niz dobro definisanih koraka ili pravila, kojom se ulazne vrednosti transformišu u izlazne, ili se opisuje izvršavanje nekog postupka.
Danas se reč algoritam često vezuje za pojam računarstva mada uopšteno algoritam možemo smatrati kao uputstvo kako rešiti neki zadatak ili problem. Tako se i uputstvo za kuvanje kafe sastoji od niza koraka, postupaka, koje treba uraditi i koji vode ispunjenju cilja ili rešavanju problema. Uputstvo može sadržati korake koji se ponavljaju više puta ili korake kada treba doneti neku odluku, na osnovu nekog kriterijuma. Dobro uputstvo predviđa i postupak kada nisu svi uslovi ispunjeni npr. nestalo struje pa ne možemo da uključimo šporet ili nema kafe pa treba da odemo da je kupimo.
Korektno izvršavanje svakog koraka ne rešava zadatak ako je algoritam bio pogrešan.
Različiti algoritmi mogu rešiti isti problem različitim nizom postupaka uz manje ili više napora, za kraće ili duže vreme. S obzirom da je rezultat isti, algoritmi se mogu porediti po svojoj efikasnosti, brzini ili kompleksnosti.
Algoritmi mogu biti prikazani ili realizovani na više načina:
-
prirodnim jezikom (razumljiv samo govornicima tog jezika)
-
Grafički, dijagramom toka (blok-dijagramom)
-
tekstualno - pseudokodom, veštačkim precizno definisanim jezikom koji liči na programski jezik
-
odgovarajućim programskim jezikom.
Načini opisivanja algoritama
Postoje razni načini da se algoritmi opišu. Osnovnu podelu načina opisa algoritama načinićemo na osnovu toga ko taj algoritam treba da sprovede, tj. da li algoritam opisujete čoveku koji na osnovu vašeg opisa treba ga da razume i usvoji ili mašini (tj. računaru) koja taj algoritam treba potpuno automatski da sprovede. Svaki opis algoritma mora biti dovoljno precizan da bi onaj ko treba da ga sprovede mogao da ga sprovede.
Prirodno-jezički opisi
Navedimo primer algoritma iz svakodnevnog života – Recept za palačinke:
1. Uzmi dublju posudu!
2. Sipaj u nju 200g brašna i 2 jaja!
3. Ako imaš mleka, sipaj 2 dl mleka, u suprotnom sipaj 2dl vode.
4. Muti sve dok smesa ne bude bez grudvica.
5. Dodaj 1dl ulja.
6. Promešaj!
Kada se algoritmi opisuju ljudima, opisi su često relativno neprecizni i oslanjaju se na to da je publika dovoljno inteligentna da „popuni rupe”, tj. da razjasni sebi ono što nije baš potpuno precizno opisano i da eventualne greške u opisima primeti i ispravi.
Algoritmi se često „opisuju” samo tako što se navede niz primera koji ilustruju njihov rad (na primer, učiteljica učenike ne uči sabiranju brojeva tako što im da opis algoritma, već tako što im pokaže veliki broj primera sabiranja). Iako su ljudima ovakvi opisi bliski (jer su veoma konkretni), oni često podrazumevaju da je čitalac prilično inteligentan i da će na osnovu primera samostalno uspeti da apstrahuje, precizira i usvoji postupak.
Dešava se često da ljudi umeju ispravno da sprovedu neki postupak, ali da ne umeju da daju njegov precizan opis, pa čak ni na prirodnom jeziku. Na primer, svi učenici umeju da sabiraju ili oduzimaju brojeve, ali kada se od njih traži da taj algoritam opišu precizno na govornom jeziku, samo mali broj učenika ume to da uradi.
Mnogo bolji od opisa algoritama samo kroz primere su eksplicitni opisi agoritma na prirodnom jeziku.
Pošto je prirodni jezik obično neprecizan, i ovakvi opisi su često neprecizni i takođe podrazumevaju određenu inteligenciju čitaoca (samim tim, ne dolaze u obzir kao oblik saopštavanja algoritma računaru).
|
Da ponovimo: Šta je to algoritam? Rešavanje zadataka pomoću računara obuhvata izvršavanje niza tačno određenih radnji u cilju dobijanja željenih rezultata. Dakle, algoritam se može definisati kao tačno određeni i uređeni skup koraka koji vode ka rešavanju datog problema. |
Još jedan primer algoritma iz svakodnevnog života je kuvanje čaja. Svaki korak pripremanja čaja mora biti izvršen pravilno kako bi se moglo preći na sledeći i u konačnom vremenu dobili skuvan čaj.
Algoritam kuvanja čaja glasi:
-
Uzeti lonče i sipati vodu.
-
Uključiti ringlu.
-
Sačekati dok voda ne proključa.
-
Kad voda proključa, skinuti lonče i isključiti ringlu.
-
Staviti kesicu čaja u lonče.
-
Po želji, dodati kašiku šećera, mleko ili limun.
-
Sipati čaj u šolju.
Iz ovog jednostavnog primera može se videti postupnost i konačnost algoritma. Naime, nema previše koristi od algoritma koji se nikada ne završava ili algoritma čije se naredbe izvode nepredvidljivo ili im je rezultat nepredvidljiv.
Opisi u obliku pseudo-koda
Uobičajen način opisa algoritama danas predstavljaju opis u obliku pseudo-koda. Takvi opisi predstavljaju kompromis između fleksibilnosti koju daju neformalni, prirodno-jezički opisi i potpuno preciznih opisa algoritama koje računar može da izvršava. Naredni pseudo-kôd opisuje algoritam za određivanje najvećeg broja i on je dosta blizak programskim kodovima.
broj := unesi_broj
maksimum := broj
ponovi sledeće četiri puta
broj := unesi_broj
ako je broj > maksimum onda
maksimum := broj
saopšti maksimum
Za sprovođenje ovog algoritma je potrebno da se nešto zapamti (memoriše, zapiše). Ako je potrebno da se zapamti više podataka, poželjno je da svaki taj podatak ima jedinstveno ime. Za to se koriste promenljive i skoro svi algoritmi sa kojima ćete se sresti u računarstvu koriste promenljive. U prethodnom pseudokodu koriste se dve promenljive (maksimum i broj).
Pseudokod kombinuje običan, govorni jezik i preciznu, matematičku simboličku notaciju. Naglasimo i to da nije usaglašeno kako pseudokod treba da izgleda, već svaki autor pseudokoda bira jezičke i simboličke konstrukcije koje smatra odgovarajućim (na primer, u navedenom pseudokodu pretpostavili smo da se dodela vrednosti promenljivoj označava simbolom :=, da je jezik za opis naredbi srpski, da se na osnovu uvlačenja linija koda (tzv. indentacije) određuje koje se naredbe ponavljaju određeni broj puta itd.).
Dijagrami toka programa
U drugoj polovini 20. veka veoma popularan način za opis algoritama bili su takozvani dijagrami toka programa (engl. control-flow graphs, flowcharts) tj. dijagrami koda (engl. code-charts).
Dijagrami toka programa spadaju u blok-dijagrame jer se algoritam opisuje dijagramom koji se sastoji od pojedinačnih blokova (predstavljenih pravougaonicima, trapezima, elipsama itd.) povezanih strelicama.
Dijagram toka se u osnovi sastoji od linija koje povezuju blokove koji sadrže neku naredbu u govornom jeziku ili žargonu (često se koriste skraćenice). Ovi blokovi predstavljaju grupe elementernih koraka algoritma, a linije označavaju vezu između tih grupa. Naredbe u blokovima su jednostavni elementarni koraci u algoritmu. Oni se izvršavaju od vrha prema dnu. Linije imaju strelice, koje pokazuju koji će se od različitih blokova izvršavati. Dakle, možemo slediti ove linije i videti tok algoritma. Time je opravdan naziv dijagrama toka. U dijagramu toka u neki od ovih blokova može biti postavljeno pitanje. Različite linije napuštaju ovakav blok i obično se označavaju sa DA ili NE. Kojom linijom će se nastaviti tok izvršavanja algoritma zavisi od odgovora na ovo pitanje. Prednost dijagrama toka je u tome što se jednim pogledom može sagledati cela struktura algoritma.
Dijagrami MIT Scratch/Blockly
Još jedna veoma popularna dijagramska tehnika programiranja – pre svega u obrazovanju mladih programera – pojavila se 2006. u sistemu za učenje programiranja Scratch razvijenom na univerzitetu MIT u SAD. Takođe popularan projekat An hour of code (http://code.org/), koji se bavi popularizacijom programiranja, koristi veoma sličan dijagramski jezik.
Dijagramske opise omogućava biblioteka Blockly kompanije Google. Algoritmi se opisuju slaganjem blokova (poput lego kockica) i obično su takvi da opisuju kretanje neke figure (crtanog junaka) po ekranu. Veći blokovi, koji obuhvataju manje, obično se koriste za opis ponavljanja koraka u manjim blokovima. Naš primer algoritma za pronalaženje maksimuma mogao bi se opisati dijagramom prikazanim na slici
U nastavku je odgovoreno na nekoliko važnih pitanja u vezi algoritama:
Pitanje 1: Koja su ograničenja govornog jezika u predstavljanju algoritma? Pokazati to na odgovarajućem primeru.
Odgovor: Govorni jezik je jezik koji oduvek koristimo, ali nažalost, za pokušaje predstavljanja algoritma ima četiri osnovna nedostatka:
1. Govorni jezik je predugačak
2. Nije jednoznačan (dvosmislen)
3. Ne daje predstavu o osnovnoj strukturi algoritma
4. Mašine ne razumeju govorni jezik.
Teško je reći koji je od navedenih nedostataka govornog jezika ozbiljniji. Po definiciji algoritam mora biti jednoznačan, pa je upotreba nejednoznačnog jezika u algoritmima nelogična.
Da bismo razmotrili problem nejednoznačnosti govornih jezika upotrebićemo sledeći primer:
Rečenica "Vreme leti kao strela!" može imati sledeće interpretacije:
1. U prenesenom značenju to znači da vreme brzo prolazi;
2. To znači da je mehanizam leta vremena ekvivalentan brzini leta strele;
3. Vreme ide u određenom smeru (smeru strele).
Iz navedenog primera se vidi da rečenica "Vreme leti kao strela!" bez navođenja odgovarajućeg konteksta ima višeznačan smisao. Iako je prirodni jezik višeznačan, on se upotrebljava za jednoznačnu komunikaciju između ljudi. Rečenica koju smo naveli dobija značenje u zavisnosti od konteksta u kojem smo je upotrebili. Vrlo je teško objasniti način na koji kontekst određuje smisao rečenice, pa je to osnovna prepreka mehaničkog prevođenja sa jednog govornog jezika na drugi (na primer sa engleskog na ruski ili nemački).
Pitanje2: Zbog čega je potrebno strogo utvrditi osobine algoritama?
Odgovor: Pošto je računar taj koji bi trebao da reši problem, algoritam bi se mogao definisati i kao postupak koji se može prevesti bez razumevanja. To na prvi pogled izgleda kao olakšavajuća okolnost, pošto je bitno reći kako, ali ne i zašto. Međutim, kada nema razumevanja onoga šta se radi, postupak objašnjavanja kako bi to trebalo uraditi mora biti veoma precizan, da bi se dobilo željeno rešenje.
Pitanje3: Od čega se algoritam sastoji?
Odgovor: Algoritam se sastoji od niza elementarnih koraka (operacija), koji sadrže dva uputstva:
- šta bi trebalo uraditi
- koja operacija bi trebalo da sledi iza tog koraka
Zadatak 4: Navesti osnovne osobine algoritma!
Odgovor:
Da bi neko rešenje zaslužilo naziv algoritma potrebno je da su ispunjeni sledeći uslovi:
* Nakon izvođenja svakog koraka, zna se koji korak bi trebalo izvesti kao sledeći
* Postoji jasno definisana početna tačka izvođenja, te jedan ili više mogućih završetaka
* Opisani postupak rešavanja je konačan
* Predloženi postupak rešavanja je jednoznačan (determinisan)
* Algoritam mora uvek dovesti do nekog rešenja
* Za date početne uslove algoritem mora uvek osigurati iste rezultate, inače njegovo izvođenje ne bi imalo smisla
* Algoritam bi se morao primeniti na čitavu klasu srodnih problema sa različitim ulaznim veličinama.
Možete pogledati detaljnije objašnjenje algoritama i cele ove lekcije OVDE (pdf fajl)