OSTALI SEMINARSKI RADOVI
IZ PROGRAMIRANJA: |
|||||||||||
|
|||||||||||
ALGORITMI
(pojam, strukture, kodiranje i programske strukture)
Algoritam predstavlja skup akcija sa definiranim redoslijedom njihovog
obavljanja, koji primijenjen na polazni skup podataka, dovodi do traženih
rezultata.
U procesu programiranja, skup akcija definiran je mogućnostima računala,
odnosno naredbama programskog jezika koji se koristi, dok se redoslijed
izvršavanja akcija zadaje pomoću algoritamskih (programskih) struktura.
ALGORITAM
Algoritam je skup pravila ili pravilo sa svojstvom preciznošću,
jednoznačnosti te obuhvaća konačan broj koraka, a svaki korak je opisan
instrukcijom. Instrukcije moraju biti izvedive i jednoznačne.Algoritam
opisuje rješavanje nekoga problema.
Postupak obavljanja algoritma je algoritamski proces. Algoritam ima
definirane početne objekte nad kojima se obavljaju operacije, a ishod
toga je skup rezultata tj. završnih objekata i on je djelotvoran.
Da bi algoritam bio učinkovit rezultat se mora dobiti u prihvatljivom
ili razumnom vremenu. Insturkcije se mogu izvršiti nekoliko puta te
instrukcije morajuu pokazivati na ponavljanje, ali za bilo koju vrijednost
ulaznih podataka algoritam završava nakon konačnog broja ponavljanja.
Kod zapisivanja algoritama upotrebljava se programski jezik C, riječ
je o nedovršenom kodu gdje su neki nizovi naredbi zamijenjeni tekstom.
Analiza algoritma podrazumijeva procjenu vremena za izvršavanje toga
algoritma, a vrijeme se poistivjećuje sa brojem operacija koje odgovarajući
program treba obaviti i on se izražava kao funkcija.
Algoritam se zapisuje u :
• Obliku pseudo jezika ( govornog jezika koji oponaša
programski jezik)
• Grafičkom obliku tzv. Blok dijagram ili dijagram tijeka programa
Slika: BLOK DIJAGRAM
OBLIKOVANJE ALGORITMA
Oblikovanje algoritama se dijeli na tehnike: podijeli pa vladaj, dinamičko programiranje, pohlepni pristup i backtracking. Svaka od ovih metoda ne garantira točno rješenje problema i zbog toga se uvijek treba napraviti provjera.
PODIJELI PA VLADAJ
Metoda podijeli pa vladaj se dijeli na tri primjera: sortiranje sažimanjem, traženjem elemenata u listi i množenje dugačkih cijelih brojeva. Algoritam merge za sortiranjem liste se može tumačiti da što je lista dulja to ju je teže sortirati, velika sortirana lista se dobiva relativno jednostavnim postupkom sažimanja malih sortiranih lista.
Primjer 1.
Sortiranje sažimanjem
PROGRAMSKE STRUKTURE
Postoje tri programske strukture a to su:
1. Linijska (slijed)
2. Razgranata (selekcija)
3. Ciklička (iteracija)
1. Linijska (slijed) programska struktura:
-sve akcije se izvršavaju točno jednom u redoslijedu u kome su navedene.
SHEMA: Linijska programska struktura
2. Razgranata (selekcija) programska 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.
Shema: Razgranata algoritamska struktura
3.Ciklička (iteracija) programska struktura:
skup akcija može se izvršiti više puta.
Shema: Ciklička programska struktura
Algoritamsko rješenje bilo kojeg problema može se uvijek zapisati korištenjem
samo ove tri strukture.
ALGORITAMSKE STRUKTURE
1. Slijedna (linearne ili sekvencijalne)
• Početak i kraj
• Definiranje varijabli i konstanti
• Ulaz
• Izlaz
• Aritmetičke i logičke operacije
2. Struktura bezuvjetnog skoka
3. Struktura grananja (sadrži logičke operacije) kombinira
se sa:
- Slijednom strukturom
- Strukturom bezuvjetnog skoka
4. Struktura iteracije (ponavljanja ili petlje)
STRUKTURA BEZUVJETNOG SKOKA (narušavanje linearnosti)
-
Koristi se za testiranje algoritma (preskače dio algoritma)
-
Izaziva grešku bezuvjetnog ponavljanja( tzv. Beskonačna petlja ili iteracija)
-
Kombinira se s strukturom grananja radi narušavanja linearnosti / uspostavljanja ponavljanja (dijela) algoritma.
PSEUDO JEZIK |
BLOK DIJAGRAM |
∫ |
|
x. Idi na y |
|
Gdje su x i y brojevi linija algoritma |
bez obzira na smjer |
Struktura bezuvjetnog skoka |
SLOŽENE ALGORITAMSKE STRUKTURE
Složene algoritamske strukture nastaju kada se u elementarnim
strukturama pojedini algoritamski koraci zamjene drugim algoritamskim
koracima ili dugim elementarnim strukturama. Tako se na osnovama navedenog
principa nadgradnje mogu dati pravila za dobijanje složenih algoritamskih
struktura.
To se postiže:
1) kada se u prostoj linijskoj strukturi u sastavu razgranate linijske
ili ciklične strukture algoritamski korak prve vrste (ne dovodi do grananja
algoritma i ima jedan ulaz i jedan izlaz) zamjeni algoritamskim korakom
druge vrste (dovodi do grananja algoritma i ima jedan ulaz i više izlaza)
2) kada se u prostoj linijskoj strukturi u sastavu razgranate linijske ili ciklične strukture algoritamski korak prve vrste zamjeni novom razgranatom linijskom ili cikličnom strukturom;
3) zamjenom algoritamskog koraka proizvoljne elementarne strukture algoritamskim korakom za poziv potprograma
4) kada se u već formiranim algoritamskim strukturama
ponavljaju zamjene iz pravila danih u točkama (1), (2) i (3).
Primjenom navedenih pravila mogu se formirati najraznovrsnije složene
algoritamske strukture.
Jedna od mogućih klasifikacija ovih struktura je:
- složene razgranate linijske strukture
- složene ciklične strukture
- složene razgranate i ciklične strukture
- algoritamske strukture sa potprogramim
Napomena: Za složene algoritamske strukture dobijene principom nadgradnje se može postaviti i zahtjev da budu strukturirane (da imaju jedan ulaz i jedan izlaz) čime se zadovoljava princip strukturnosti primjenom tog zahtjeva u većini slučajeva algoritamske strukture postaju logički preglednije i pogodnije za programsku realizaciju.
KANONSKE I NEKANONSKE ALGORITAMSKE STRUKTURE
Kombinacijom elementarnih struktura formiraju se kanonske, kvazi-kanonske
i nekanonske algoritamske strukture.
Postoje 4 kanonske, 5 kvazi-kanonskih i 2 nekanonske algoritamske
strukture a to su :
1. kanonske algoritamske strukture
- kanonska linijska struktura
- kanonska razgranata struktura
- kanonska ciklička struktura
2. kvazi- kanonske algoritamske strukture
3. nekanonske algoritamske strukture
TESTIRANJE ALGORITMA
Izvodi se kao i u matematici uvrštavanjem vrijednosti u algoritam.Algoritam se testira sekvencijalno praćenjem svakog reda (instrukcije) algoritma od početka do kraja, uz zapisivanje vrijednosti koje varijable usput poprimaju, da bi se u konačnici i saznala konačna vrijednost izlaznih varijabli.
Pr. Zadatka:
Kolika je vrijednost varijable s nakon izvođenja algoritma, ako za x učitamo 2, a za y učitamo 5:
1. X=0, Y=0, S=0
2. Učitaj X
3. Učitaj Y
4. S=S+Y
5. Ispiši S S
= 5
KODIRANJE
Algoritam započinje s praznim rječnikom, no uzmimo neki
trenutak u tijeku kodiranja, kad rječnik već sadrži neke stringove. Analiziramo
prefiks koji slijedi u ulaznoj struji, počevši sa praznim prefiksom. Ako
njemu odgovarajući string (prefiks + sljedeći znak, odnosno P+Z) postoji
u rječniku, proširujemo prefiks P znakom Z. Proširenje ponavljamo sve
dok ne dobijemo string koji ne postoji u rječniku. Tada na izlaz pošaljemo
kodnu riječ koja odgovara P-u, a zatim i znak Z. Sljedeći prefiks koji
analiziramo direktno se nastavlja na obrađeni.
Poseban je slučaj ako u rječniku ne postoji ni početni string od samo
jednog znaka (to se uvijek događa na početku kodiranja). Tada se na izlaz
alje posebna kodna riječ koja označava prazni string. Iza nje se šalje
dotični znak i taj se znak dodaje u rječnik.
Izlaz iz algoritma su parovi kodna riječ-znak (K,Z). Svaki put kad se
taj par pošalje na izlaz, string iz rječnika koji odgovara kodnoj riječi
K proširi se znakom Z i taj novi string se doda u rječnik. To znači da
u trenutku kad dodajemo neki string, u rječniku već postoje svi stringovi
dobiveni oduzimanjem znakova s kraja tog stringa.
Algoritam za kodiranje
1. Na početku su rječnik i P prazni;
2. Z := sljedeći znak u ulaznoj struji;
3. Postoji li string P+Z u rječniku?
a. ako postoji, P := P+Z (P proširi Z-om);
b. ako ne postoji,
--u izlaznu struju pošalji dva podatka, i to:
- kodnu riječ stringa jednakog P-u (ako je P prazan, šalji nulu);
- Z, u istom obliku kao što je učitan iz ulazne struje;
--na prvo prazno mjesto u rječniku zapii string P+Z;
--isprazni P;
c. ima li još znakova u ulaznoj struji?
--ako ima, vrati se na korak 2;
--ako nema:
- ako P nije prazan, u izlaznu struju pošalji kodnu riječ stringa jednakog P-u;
- KRAJ
ZAKLJUČAK
Algoritamske strukture važan dio programiranja, pomoću njih se zadaje
redoslijed izvršavanja akcija, tj. problema. One su bitan dio algoritama,
jer se algoritmi nikako ne mogli strukturirati , tj rješavati. Algoritam
je postupak kojim se u konačnom broju koraka i u konačnom vremenu dolazi
do rješenja problema ili spoznaje da rješenja nema. Svaka vrsta stroja
za obradu podataka ima svoj jezik i ne može se koristiti na drugom stroju,
čak ni na različitim strojevima istog proizvođača.
LITERATURA
http://bs.wikipedia.org/wiki/Programiranjehttp://www.pmfst.hr/~stankov/Programiranje_I_WWW/Osnove%20programiranja/APL_SW2.PDF
http://www.pmfst.hr/~stankov/Programiranje_I_WWW/Ppt_prezentacije/strukture.pdf
Grbavac, V., Informatika
preuzmi seminarski
rad u wordu » » »
Besplatni Seminarski Radovi