1. PARALELNI ALGORITMI
Pojam algoritma predstavlja temelj za razumijevanje računarstva općenito i stoga mu
je u ovom dijelu posvećena posebna pažnja.
1.1.
Neformalni algoritmi
Obzirom na naučeno gradivo trebali bi znati definirati algoritam koji, primjerice,
pretvara različite formate numeričkih podataka, upravlja raspodjelom procesorskog vremena u
višezadaćnom okruženju i sl. Algoritmom možemo opisati i izvođenje samog algoritma u
stroju kao: Sve dok se ne pojavi instrukcija za zaustavljanje, ponavljaj:
Dohvaćaj instrukciju
Dekodiraj instrukciju
Izvedi instrukciju
Algoritmi nisu ograničeni samo na tehničke aktivnosti. Pomoću algoritma možemo
opisati mađioničarski trik ili neku svakodnevnu aktivnost, primjerice čišćenje graška kao:
Uoči košaru sa neočišćenim graškom i praznu zdjelu
Sve dok ima graška u košari, radi:
Uzmi mahunu iz košare
Prelomi je da se na njoj pojavi otvor
Istresi grašak u zdjelu
Baci mahunu
Mnogi istraživači vjeruju da je bilo koja aktivnost ljudskog uma, uključujući
zamišljanje, kreativnost i donošenje odluka, u osnovi rezultat izvođenja nekog od algoritama
što je za posljedicu imalo razvoj znanstvene discipline poznate pod imenom Umjetna
inteligencija.
Da bi specificirali značenje i važnost algoritma za računarstvo, uvedimo formalnu
definiciju: Algoritam je uređeni skup jednoznačnih (nedvosmislenih), izvedivih koraka.
4
Analizirajmo definiciju detaljnije:
Kako je riječ o uređenom skupu, logično je da se koraci algoritma trebaju izvoditi
određenim redoslijedom. Međutim to ne znači da se koraci algoritma uvijek izvode
sekvencijalno, u nizu. Postoje i tzv. paralelni algoritmi koji sadrže takozvane «niti»
(thread) koje izvodi pojedini procesor, pa se određeni koraci mogu izvoditi
istovremeno, ovisno o tome kako se niti granaju i ovisno o tome kako pojedini
procesori izvode svoj dio zadatka. Osim što algoritam može izvoditi procesor, I
bistabilni sklopovi mogu izvoditi specifične algoritme, tako da svaka vrata izvode
jedan korak u algoritmu. Ovdje su koraci izvođenja uvijek uvjetovani uzrokom i
posljedicom, pošto se izlazi iz jednih vrata šire kao novi signal ekektroničkim
sklopom.
Pojam "jednoznačan" (nedvosmislen) u okviru definicije podrazumijeva da za vrijeme
izvođenja algoritma informacija o stanju procesa mora biti dovoljna da jednoznačno I
potpuno definira akciju koja slijedi. Drugim riječima, izvođenje (napredovanje)
algoritma ne smije se temeljiti na kreativnosti (procesora, osobe koja ga slijedi), nego
mora biti rezultat slijeđenja uputa.
1.2.
Izuzeci od formalne definicije:
Definicija podrazumijeva izvođenje konačnog procesa, procesa koji ide prema nekom
cilju. Stavljanjem naglaska na konačnost izvođenja, dotiču se pitanja kojima se i inače bavi
teorija računarstva, tipa:
Koje je krajnje ograničenje algoritama i koji su dosezi stroja općenito?
Na ovaj su način u okvirima računarstva razdvojeni problemi koji se mogu riješiti
algoritamski od onih koji nadilaze mogućnosti algoritama i s tim u vezi, razgraničeni su
procesi koji rezultiraju odgovorom na pitanja(e), od onih na koje odgovori ne postoje. Životno
iskustvo, međutim, pokazuje da postoje smislene aplikacije (temeljene na odgovarajućim
algoritmima) koje uključuju odvijanje nekakvog beskonačnog procesa, primjerice, nadziranje
životnih funkcija hospitaliziranih pacijenata ili automatski pilot koji održava visinu letjelice.
5
1.4.
Primitive
Za predstavljanje algoritma potrebna nam je nekakva forma slična jeziku. Ako ljudi
jedan drugom objašnjavaju algoritam, onda mogu koristiti riječi običnog, govornog jezika ili
jezik slika. Mana takvog načina komunikacije je mogućnost da određene riječi budu shvaćene
drugačije zbog višeznačnosti koja inače karakterizira riječi prirodnog jezika ili zbog
kompozicije riječi unutar rečenice koja se može shvatiti na različite načine.
Algoritam pripremljen za računalo bit će jasan ukoliko se koriste specifični oblici (tzv.
primitive) za točno definiranu vrstu funkcije koju odgovarajući oblik predstavlja. Taj skup
osnovnih oblika, zajedno sa skupom pravila koja definiraju kako se osnovni oblici mogu
koristiti čine programski jezik. (50-tih i 60-tih bili su vrlo popularni tzv. blok dijagrami za
predstavljanje algoritama, ali kako se često događalo da zbog nepreglednosti ispisa izmakne
temeljni smisao algoritma, predstavljanje pomoću blok dijagrama je danas gotovo
zanemareno i uglavnom zamijenjeno predstavljanjem pomoću pseudokoda). Svaka primitiva
sastoji se od dva osnovna dijela: sintakse i semantike. Sintaksa omogućava simboličku oznaku
primitive, a semantika joj daje značenje. Primjerice, sintaksa za ZRAK su 4 slova, a
semantika bi označavala plinovitu mješavinu koja okružuje svijet. Da bi definirali skup
primitiva kojima predstavljamo algoritam na računalu, mogli bi odabrati naredbe iz
instrukcijskog skupa, što naravno nije zgodno, pa se zato koriste primitive "viših
(apstraktnijih) nivoa".
1.5.
Pseudo kod
Zamijenimo li formalnu, strogu strukturu programskog jezika, manje formalnim
sustavom označavanja, dobili smo sustav za predstavljanje algoritma poznat pod nazivom
PSEUDO KOD pomoću kojeg ideje možemo izraziti (zapisati) na lakši i manje formalan
način tijekom postupka razvijanja (smišljanja) samog algoritma. Jedan od načina
predstavljanja algo. pseudokodom je izostavljanje pravila iz naredbi koja prate svaki formalni
programski jezik. Ovaj se način obično koristi kada znamo koji ćemo programski jezik
koristiti, pa je tako semi-sintaktička struktura kojom opisujemo algoritam velikim dijelom
nalik, ali je manje formalna od programskog jezika.
7
