Teorija programiranja

          Uvod u teorijske osnove programiranja

               Računar može da uradi samo ono za šta mu je korisnik dao instrukciju (program) - niz logičkih i aritmetičkih operacija napisanih na jeziku računara (programskom jeziku). Računar takve instrukcije izvršava brzo i gotovo nepogrešivo, upravo onako kako su zadate.
Razvojem računara usavršavao se i jezik za komuniciranje, od mašinskog do tzv. programskih jezika visokog nivoa.
Programski jezici visokog nivoa daleko su jednostavniji od prirodnih (bosanski, engleski itd.) jezika. Osim toga, "rečenice" jezika za programiranje mogu se opisati strogim pravilima, bez izuzetaka i sa jedinstvenim značenjem. Kada su u pitanju jezici za programiranje bitno je istaći tri stvari:

 

-          leksičku strukturu,

-          sintaktičku strukturu  i

-          semantiku jezika.

 

     Leksička struktura
Definisati leksičku strukturu nekog jezika znači definisati alfabet i rječnik. Alfabet je skup svih znakova koji se koriste u pisanju na tom jeziku. To su slova, brojevi, operacije i specijalni znaci.
Rječnik je skup reči(simbola) definisanih nad tim alfabetom. Riječ (ili simbol) je niz znakova iz alfabeta koji se može posmatrati kao jedinstvena, nedjeljiva cjelina.
Zbog lakšeg sagledavanja leksičke strukture nekog jezika uobičajeno je da se ječnik djeli na klase rječi ili simbola koje imaju neka zajednička svojstva, tj. na konstante, identifikatore, rezervisane rječi, imena funkcija, specijalne simbole itd.

     Sintaktička struktura
Sintaktička (ili sintaksna) struktura jezika utvrđuje grupisanje leksičkih elemenata u šire strukture, koje se nazivaju sintaktičke kategorije. Pravila koja određuju da li niz simbola pripada jeziku ili ne, nazivaju se sintaksa jezika.
Pravilo pisanja ili sintaksa pojedinih naredbi najčešće se zadaje sintaktičkim dijagramom.

     Hijerarhijska struktura jezika
Do sada smo više puta upotrebili termin "jezik za programiranje", a još uvek nismo definisali šta je to. Jezik za programiranje može se definisati kao notaciona tehnika (pismo) kojom se na kompaktan, nedvosmislen i konačan način navodi niz operacija koje će biti izvršene nad nekim objektima - podacima. Određeni niz tih operacija napisan u nekom jeziku naziva se program.
Uopšteno, operacije i podaci, u većini jezika za programiranje, mogu se grupisati hijerarhijski.

     Tipovi i strukture podataka
Podaci se na nivou mašinskog jezika (prirodnog jezika računara) predstavljaju kao nizovi znakova binarnog alfabeta (nule i jedinice). Takvo predstavljanje se na nivou jezika visokog nivoa zanemaruje i uvodi se pojam tipa podatka.
Tip podatka je skup vrednosti koje imaju izvesne zajedničke karakteristike. Najznačajnija od njih je skup operacija koje su definisane nad vrednostima tog tipa. U većini jezika za programiranje susreću se sledeći tipovi podataka: numerički (celobrojni i realni), logički i znakovni.

     Cjelobrojni tip
Celobrojni tip podataka (engl. integer) je podskup skupa celih brojeva. Koji je to tačno podskup, zavisi od realizacije jezika za programiranje. Nad ovim tipom, u većini jezika za programiranje, definisane su standardne operacije celobrojne aritmetike: sabiranje, oduzimanje, množenje, celobrojno deljenje i stepenovanje. Pri izvršavanju tih operacija važe svi zakoni aritmetike, pod uslovom da nije došlo do prekoračenja najveće moguće vrednosti celog broja (što je određeno dužinom mašinske rječi računara).

     Realni tip
Realni tip podataka (engl. real) je podskup skupa realnih brojeva, odnosno skup brojeva oblika

          ± 0.m x 2 ± e ,
     gdje je m mantisa, a e eksponent.

 

Nad realnim tipom definisane su standardne operacije realne aritmetike (sabiranje, oduzimanje, množenje, djeljenje i stepenovanje). Međutim, pri radu sa realnim brojevima, situacija je znatno složenija usljed činjenice da je skup realnih brojeva u svakoj realizaciji na računaru konačan skup, što može imati raznorazne posledice.
Svaki proizvoljno mali interval na realnoj osi sadrži beskonačno mnogo vrednosti realnih brojeva. Realni tip na računaru je konačan skup predstavnika intervala na realnoj osi. Zbog toga se računske operacije ne obavljaju sa tačnim, već sa približnim vrednostima. Posljedica toga je da su rezultati operacija aproksimacija tačnih rezulatata.

     Logički tip
Logički tip podataka (engl. logical) postoji u većini jezika za programiranje. Nad ovim tipom su u većini jezika definisane Boolove operacije (negacija, konjukcija i disjunkcija), a u nekim jezicima i implikacija i još neke druge operacije.

     Znakovni tip
Većina jezika za programiranje poseduje znakovni tip podataka (engl. character), odnosno nizove znakova (engl. string). Znakovne podatke čini konačan skup znakova. Koji je to skup, opet zavisi od računara i realizacije jezika za programiranje. Nad ovim tipom podataka najčešće je definisana samo operacija nastavljanja (engl. concatenation).

     Imena i identifikatori
Na apstraktnom nivou, svaki jezik za programiranje koristi objekte (ili vrijednosti), tj. podatke (cjelobrojne, realne, logičke itd.).
Pogodno je zamisliti da se memorija računara sastoji od ćelija koje mogu da pamte podatak bilo kog tipa. Ćelije su različite dužine, od jednog bajta do nekoliko memoriskih rječi, zavisno od tipa podatka. Svaka ćelija ima ime koje je obično promjenljiva jezika za programiranje. Svako ime označava se identifikatorom, tj. nizom znakova. U većini jezika identifikator je najmanje jedno slovo ili slovo iza koga sljedi niz, sastavljen od slova i brojeva.

     Konstante i promenljive
Uopšteno, podaci bilo kog tipa mogu biti:
     - konstante,
     - promenljive.

Konstante su određene vrednosti koje se ne menjaju tokom izvršavanja programa. Zadaju se eksplicitno, pisanjem konkretne vrijednosti iz skupa svih vrijednosti nekog tipa.

Promjenljiva u matematici ne predstavlja nijednu posebnu vrijednost. Međutim, u jezicima za programiranje pojam "promjenljiva" koristi se za nešto što ima vremensko trajanje i čija je vrijednost u određenom trenutku konstantna.
Promjenljiva je određena svojim imenom i tipom. Tip promjenljive određuje iz kog će se skupa podataka dodjeljivati vrijednosti promjenljivoj. U nekim jezicima tip promjenljive može se definisati početnim slovom, u drugim određenim sufiksom, a u nekim eksplicitnom deklaracijom tipa.

    Strukture podataka
Vrijednosti bez komponenti, koje predstavljaju same sebe i dalje se ne djele, nazivaju se primitivni tipovi. Nosioci primitivnih tipova su konstante ili promjenljive koje se mogu nazvati "primitivne" promjenljive.

Polazeći od prostih tipova, moguće je definisati strukturirane tipove, tj. skupove vrijednosti čija struktura ima određeni smisao. Nosioci strukturiranih podataka su strukturirane promjenljive. One se mogu koristiti tako da se odnose na strukturiranu vrijednost u cjelini ili na pojedine komponente.

Da bi se definisao strukturirani tip, neophodno je definisati metod strukturiranja i tipove komponenti. U većini jezika za programiranje susreću se sljedeći strukturirani tipovi podataka:
     - polje,
     - niz znakova,
     - zapis i
     - datoteka.

Polje (engl. array) je kolekcija elemenata istog tipa (na primer, realnog) objedinjenih u k-dimenzionalnoj strukturi. Elementi polja imaju isto ime, ali k različitih indeksa:

         A (i1, i2, ... , ik)
Ovde je A ime polja, a i1, ... , ik su indeksi elemenata polja.

Jednodimenzionalno polje naziva se vektor a dvodimenzionalno matrica. Svi poznati jezici za programiranje podržavaju rad sa podacima sa strukturom polja, jedino se razlikuju njihove sintakse i djelimično semantike.
Niz znakova (engl. string) je struktura koja se može smatrati specijalnim slučajem jednodimenzionalnog polja čiji su elementi znakovi. Jedina razlika je što se niz znakova može posmatrati kao kompaktna cjelina, pa su definisane i određene operacije nad njom, ili se mogu izvršavati operacije nad djelovima niza.

Zapis (engl. record) ili slog je struktura podataka koju čini kolekcija, u principu, različitih primitivnih ili strukturiranih tipova podataka.

Datoteka (engl. file) je organizovana kolekcija zapisa. Upotreba datoteke obično je povezana sa sekundarnom memorijom (diskom). U mnogim jezicima pojam "datoteka" odnosi se na datoteke kod kojih je pristup zapisima sekvencijalan (u nizu). Osim takvih datoteka, postoje i datoteke sa tzv. direktnim pristupom.

     Izrazi
Izrazi nisu naredbe već sintaktičke strukture koje, uopšteno, sadrže podatke (promjenljive i konstante), operacije i funkcije. Prema tipu podataka i operacija definisanim nad njima u većini jezika za programiranje razlikujemo sljedeće izraze:
     - aritmetičke,
     - znakovne i
     - logičke.

Aritmetički izrazi sadrže cjelobrojne, realne (a u nekim jezicima i kompleksne) tipove podataka i odgovarajuće operatore.

Znakovni izrazi sadrže nizove znakova kao operande i odgovarajuće operatore.

Logički izrazi sadrže relacijske podizraze, logičke konstante i promjenljive te logičke operacije i odgovarajuće operatore.

     Naredbe
Elementarne operacije izračunavanja, dodjeljivanja i kontrole redosljeda izračunavanja zadaju se naredbama (komandama) jezika za programiranje. Naredbe mogu imati različite oblike i značenja. Uobičajena je podjela na primitivne i strukturirane (složene) naredbe.

Ova podjela je odraz sintakse naredbi. Pored nje, naredbe se mogu podjeliti i na osnovu svog značenja na:
     - naredbe za izračunavanja,
     - naredbe za kontrolu toka izvršavanja,
     - naredbe za deklarisanje,
     - ulazno/izlazne naredbe
itd.

     Podprogrami
Podprogrami su takođe strukturirane naredbe. U nekim jezicima primitivne i strukturirane naredbe mogu da se grupišu u podprograme, tj. cjeline po svojoj funkciji i operacijama koje obavljaju.

     Programi
Konačno, stigli smo do vrha hijerarhije, tj. do programa. Program sada možemo definisati kao niz naredbi, primitivnih i složenih, kojim se opisuje postupak unosa, izračunavanja i bilježenja podataka i rezultata izračunavanja.

     Programiranje
Programiranje je proces zadavanja skupa naredbi u nekom jeziku za programiranje da bi se izvršila neka aktivnost, odnosno, rješio određeni problem. Cjeli proces rješavanja problema upotrebom računara obično se sastoji od više koraka.
Prvi korak obično je rezultat shvatanja problema koji treba da se riješi i analize ulaznih podataka koje računar treba da obradi, kao i izlaznih podataka ili rezultata koje računar treba da proizvede.
Drugi korak je smišljanje algoritma, tj. definisanje postupka koji se obično sastoji od nekoliko koraka, na osnovu kojih će računar proizvesti zahtjevani izlaz iz odgovarajućeg ulaza.

Sada se programiranje, u užem smislu, može opisati kao proces koji se sastoji od shvatanja problema i analize ulaza i izlaza, od izbora i oblikovanja algoritma za njegovo rešavanje i od utvrđivanja programske strukture i logike.

Ostali koraci u ovom procesu su: pisanje programa, prevođenje programa, izvršavanje i testiranje programa, kao i kompletiranje programske dokumentacije. Ti koraci se u ovom tekstu neće razmatrati.

     Računarski model (algoritam)
Algoritam predstavlja skup akcija sa definisanim redosledom njihovog obavljanja, koji primjenjen na polazni skup podataka, dovodi do traženih rezultata. U procesu programiranja, skup akcija definisan je mogućnostima računara, odnosno naredbama programskog jezika koji se koristi, dok se redosljed izvršavanja akcija zadaje pomoću algoritamskih (programskih) struktura.

     Elementarne algoritamske strukture
Postoje tri elementarne algoritamske strukture: linijska, razgranata i ciklična. Sve akcije u linijskoj algoritamskoj strukturi se izvršavaju tačno jednom u redosljedu u kome su navedene. Razgranata struktura omogućava da se od više grupa akcija, koje se nalaze u različitim granama razgranate strukture, izabere ona koja će se izvršiti jednom, dok se sve ostale grupe akcija neće izvršiti ni jednom. U cikličnoj strukturi se skup akcija može izvršiti više puta. Poznato je da se algoritamsko rješenje bilo kog problema može uvjek zapisati samo korišćenjem ove tri strukture.

     Kanonične i nekanonične algoritamske strukture
Kombinacijom ove tri strukture formiraju se kanonične, kvazi-kanonične i nekanonične algoritamske strukture. Postoje 4 kanonične, 5 kvazi-kanoničnih i 2 nekanonične algoritamske strukture. Kanonične strukture imaju sljedeće osobine:
Postoji veza u oba pravca između njih i matematičkih modela koji im odgovaraju;
Dalje se ne razlažu na sastavne djelove;
Može se napisati tzv. pseudo-kôd za svaku od njih samo na osnovu naziva.
Kada se u kanoničnim strukturama javljaju pozivi podprograma (skup struktura koji se tretira kao cjelina), radi se o kvazi-kanoničnim strukturama. Kao i kanonične i kvazi-kanonične strukture se ne razlažu na sastavne djelove, ali se ne može uspostaviti veza imeđu njih i matematičkih modela koji im odgovaraju.
Nekanonične strukture nemaju ni jednu od navedenih osobina, tako da ih treba postepeno razlagati do nivoa kanoničnih.

             Kanonične strukture

     Linijska struktura
    Oznaka: L
Definicija: To je elementarna struktura kod koje se svaki algoritamski korak izvršava tačno jednom.

 

Pseudo-kôd (ilustracija):

Akcija1
Akcija2
.
.
.
AkcijaN

     Razgranata struktura
Oznaka: nR
Definicija: To je elementarna razgranata struktura sa n grana kod koje će se akcija na jednoj od grana izvršiti jednom, dok se akcije na ostalih n-1 grana neće izvršiti ni jednom.

Pseudo-kôd (ilustracija za 3R strukturu):

If uslov1 Then
If uslov2 Then
Grupa1 akcija
Else
Grupa2 akcija
Endif
Else
Grupa3 akcija
Endif


3R struktura može se zapisati i na sljedeći način:

case izraz of
vrednost1: Grupa1 akcija
vrednost2: Grupa2 akcija
vrednost3: Grupa3 akcija
endcase

U sastav razgranate strukture nR može ući i L struktura koja prethodi razgranatoj strukturi, ukoliko se njome postavljaju neki početni uslovi.

     Ciklična struktura
Oznaka: mC/{t}
Definicija:
• Jednostruko spregnuta (1C/t), za m=1;
• Dvostruko spregnuta (2C/t), za m=2;
• Trostruko spregnuta (3C/t), za m=3.

Parametar t, koji može imati vrednosti 1, 2, 3 ili 4, ukazuje na oblik odgovarajućeg ciklusa.

Značenje vrijednosti parametra t je sljedeće:
1 - ciklična struktura je tipa: repeat ... until uslov
2 - ciklična struktura je tipa: repeat ... while uslov
3 - ciklična struktura je tipa: until uslov do ... ili
for naz_promenljive := poč_vrednost to
krajnja_vrednost do ...
4 - ciklična struktura je tipa: while uslov do ...

Pseudo-kôd (ilustracija 1C struktura):

Struktura 1C/1:
repeat Akcija1
Akcija2
.
.
.
AkcijaN
until uslov
Struktura 1C/2:
repeat
Akcija1
Akcija2
.
.
.
AkcijaN
while uslov

Struktura 1C/3:
for naz_promjenljive := poč_vrijednost to krajnja_vrednost do
Akcija1
Akcija2
.
.
.
AkcijaN
endfor
Ili
until uslov do
Akcija1
Akcija2
.
.
.
AkcijaN
endutil

Struktura 1C/4:
while uslov do
Akcija1
Akcija2
.
.
.
AkcijaN
endwhile

Ciklična struktura sa razgranatom u okviru je
    Oznaka: mCnR/{t}
Definicija: To je ciklična struktura kod koje se u ciklusu najniže hijerarhije nalazi nR struktura.

Pseudo-kôd (ilustracija):
Struktura 2C2R/4,1:
while uslov1 do
Grupa1 akcija
repeat
If uslov2 Then
Grupa2 akcija
Else
Grupa3 akcija
Endif
until uslov3
Grupa4 akcija
endwhile

     Kvazi-kanonične strukture
Kada se u bilo kojoj kanoničnoj strukturi nađe poziv podprograma, radi se o kvazi-kanoničnoj strukturi. Oznake kvazi-kanoničnih struktura su:
- P,
- LP,
- nRP,
- mCP/{t},
- mCPnR/{t} ili mCnRP/{t} ili mCPnRP/{t}.

P struktura je poziv podprograma bilo kog tipa (procedura, funkcija itd.). Pseudo-kôd za poziv podprograma je:
naz_podprograma (lista argumenata)
Strukture LP, nRP i mCP/{t} su jasne po definiciji. Kod mCnR/{t} strukture pozicija slova P određuje da li se poziv podprograma nalazi u cikličnoj, u razgranatoj ili u obje strukture. Očigledno je da se ni kod jedne kvazi-kanonične strukture pozicija poziva podprograma ne može precizno odrediti.

     Nekanonične strukture
Sve preostale algoritamske strukture, koje se definišu određenom rednom ili paralelnom kompozicijom kanoničnih struktura, nazivaju se nekanoničnim strukturama.
Razmatranje nekanoničnih struktura izlazi izvan okvira ovog teksta, a zainteresovani čitaoci mogu naći detaljnije informacije u stručnoj litarturi.