Asp01 5ud63

ALGORITMI I STRUKTURE PODATAKA -U v o d – Prof. Dušan Starčević

Literatura • Dejan Živković, Osnove dizajna i analize algoritama, CET, Beograd, 2007 • Siniša Nešković, Strukture podataka i algoritmi, FON Beograd, 2006, skripta • Robert Manger, Miljenko Marušić, Strukture podataka i algoritmi, PMF Zagreb, skripta • ppt prezentacije D. Kalpića i kolega sa FER-a, Zagreb

Algoritmi • Koreni algoritma: Abu Ja'far Mohammed ibn Musa al Khowarizmi – ‫أبو جعفر محمد بن موسى الخوارزمي‬ – Muhamed, otac Jafarov, sin Muse iz Khwarizma

• • •

rođen u Khwarizmu, danas Khiva, Uzbekistan, oko 780. g. umro u Bagdadu, oko 850. godine. jedan od 10 najcjenjenijih matematičara svih vremena – ‫أبو جعفر محمد بن موسى الخوارزمي‬ – Muhamed, otac Jafarov, sin Muse iz Khwarizma

• rođen u Khwarizmu, danas Khiva, Uzbekistan, oko 780. g. • umro u Bagdadu, oko 850. godine. • jedan od 10 najcenjenijih matematičara svih vremena

Doprinosi al Khowarizmi-ja • • •

potiče korišćenje hindu, odnosno arapskih brojeva uvodi nulu u Bagdadu oko 825. godine napisao knjigu “Hidab al-jabr w'almuqubala” – ‫الكتاب المختصر في حساب الجبر والمقابلة‬ – Znanost o prenošenju i poništenju – jabr - prenošenje na suprotnu stranu jednadžbe • x - 2 = 12  x = 12 + 2

– muqubala - poništenje jednakih izraza s lijeve i desne strane jednadžbe • x+y=y+7x=7

– – –

al-jabr -> algebra nematematički (maursko porijeklo): algebrista  namještač kostiju

Doprinosi al Khowarizmi-ja • verovao da se bilo koji matematički problem može raščlaniti na korake, tj. niz pravila • u latinskom prevodu knjige (12. vek) ispred svakog pravila piše – Dixit Algorizmi - rekao je Al Kowarzimi  – algoritam glasi

• u početku algoritmom se nazivaju samo pravila računanja s brojevima, kasnije i pravila obavljanja ostalih zadataka u matematici • u XX veku, pojavom računara, pojam se proširuje na računarstvo, a zatim i na druga područja • pravila za postizanje željenog rezultata

Šta je algoritam? • • •

precizno opisuje način rešavanja nekog problema jednoznačno određuje što treba napraviti moraju biti definisani početni objekti koji pripadaju nekoj klasi objekata na kojima se obavljaju operacije – kao ishod algoritma pojave se završni objekti ili rezultati – konačni broj koraka; svaki korak opisan naredbom ili instrukcijom – obavljanje je algoritamski proces • upotrebljiv, ako se rezultat dobije u konačnom vremenu Primeri nedopuštenih naredbi: – izračunaj 5/0 – uvećaj x za 6 ili 7

Još o algoritmu! • •

•

•

algoritam mora biti efektivan ili delotvoran: – u konačnom vremenu može se dobiti traženi rezultat koristeći olovku i papir. primeri: – sabiranje celih brojeva je efektivno – rad sa realnim brojeva nije, može se pojaviti broj s beskonačno mnogo cifara uz razumevanje problema kojeg rešava i sa znanjem programiranja, student može napisati efektivan algoritam – cilj ovog predmeta je naučiti kako se oblikuje i programira efektivan algoritam. razlika između značenja reči efektivan (delotvoran) i efikasan – efektivan = ono što smo dobili sadrži sve što smo tražili – efikasan = uspešan s obzirom na utrošene resurse - vrijeme, procesor, disk, memoriju) • množenje se može svesti na ponavljanje zbrajanja – efektivno, ali nije efikasno!

Procedura • procedura je postupak koji ima sva svojstva kao i algoritam, ali koji se ne mora završiti u konačnom broju koraka – primer: naći zbir svih prirodnih brojeva

• primeri procedura: – operativni sistem računara – editor teksta

Procedura

Algoritam

• vreme izvođenja mora biti "razumno" • primer: – algoritam koji bi izabirao potez igrača šaha tako što bi ispitao sve moguće posledice tog poteza, zahtevao bi milijarde godina rada i na najbržem zamislivom računaru

Algoritmi i programi • •

Niklaus Wirth: Program = Algoritam + Strukture podataka Program - opis algoritma koji u nekom programskom jeziku jednoznačno određuje što računar treba napraviti • Programiranje – proces prevođenja opšteg rešenja problema u računarski čitljiv oblik – – – – – –

•

kako osmisliti algoritam? kako strukturirati podatke? kako formalno specificirati algoritam? kako verifikovati algoritam? kako analizirati algoritam? kako proveriti napisani program?

Postupci izrade algoritama nisu jednoznačni. Traže kreativnost! Donald Knuth: Art of Programming Za opis algoritama koristićemo pseudokod

Opšti postupak rešavanja problema Verbalni

Matematički model

Programski model

Neformalno opisan proces rešavanja problema posredstvom prirodnog jezika

Formalno specificirano rešenje problema posredstvom matematičkog jezika (pseudojezika)

Konkretna implementacija formalno specificiranog rešenja problema posredstvom programskog jezika

Slobodan tekst Rečenica definiše predmet rada i vrstu radnje

Algoritam Operacija nad apstraktnim tipovima podataka

Programski kod Kod operacije i programske strukture podataka

Osnovni pojmovi • Apstraktna struktura podataka (ASP, eng. ADT) – matematički model, specifikacija, skupa objekata zajedno sa skupom operacija koje su definisane u tom modelu • Struktura podataka – implementacija apstraktne strukture podataka u nekom programskom jeziku – Implementacija obuhvata i pitanja predstavljanja konkretnog podataka u memoriji računara • Tip podataka – označava pripadnost nekog podataka, kao uređenog skupa vrednosti, određenoj apstraktnoj strukturi podataka, ali u praksi i njenoj implementaciji odnosno programskoj strukturi podataka

Specifikacija i implementacija • Za isti apstraktni tip podataka obično se može smisliti više različitih implementacija koje se razlikuju po tome što koriste različite strukture podataka za prikaz podataka, odnosno različite algoritme za izvršavanje operacija • Specifičnosti implementacije u proceduralno orijentisanim jezicima i objektno orijentisanim jezicima – u proceduralno orijentisanom jeziku podatak kao objekat je “vidljiv” spolja i programer je odgovoran za pravilnu upotrebu odgovarajućeg koda operacije, – u objektno orijentisanom jeziku podatak je enkapsuliran (“začauren”) i programer samo bira neku od unapred dozvoljenih operacija (metoda) za rad sa podatkom

Primitivni tipovi podataka • Apstraktne strukture podataka su generalizacija primitivnih struktura podataka, a apstraktne procedure generalizacija primitivnih operacija • Primitivni tipovi podataka – prirodni brojevi, – celi brojevi, – realni brojevi • Primitivne operacije – sabiranje, – oduzimanje, – množenje – ....

Tipovi podataka • Tip podataka u proceduralnom jeziku određuje domen definisanosti kao skup mogućih vrednosti podatka • Operandi i rezultati mogućih operacija su podaci određenih tipova Primer: podatak tipa int može uzeti vrednost samo iz skupa celih brojeva. U praksi: Apstraktna struktura podataka je koncept u domenu analize problema, dok je struktura podataka koncept u domenu programiranja

Program = Algoritam + Strukture podataka • Struktura podataka – skup varijabli u nekom programu i veza među tim varijablama • Algoritam – konačni niz naredbi, od kojih svaka ima jasno značenje i može biti izvršena u konačnom vremenu – iste naredbe mogu se ponavljati bilo eksplicitnim navođenjem ili korišćenjem odgovarajućih naredbi za ponavljanje • Važan uslov ! – za bilo koje vrednosti ulaznih podataka algoritam mora da završi rad nakon konačnog broja koraka

Elementi od kojih se grade strukture podataka • Strukture podataka reprezentuju različite tipove podataka u radnoj memoriji računara • Strukture podataka mogu biti različite složenosti • Strukture podataka se mogu međusobno povezivati, tako što se manje celine udružuju u veće • Strukture podataka se međusobno povezuju vezama • Elementi od kojih se grade strukture podataka: – – – – –

Ćelija, Polje, Slog, Pointer (pokazivač), Kursor.

• Strukture podataka se grafički prikazuju dijagramima

Ćelija • Struktura podataka koji promatramo kao zasebnu celinu, varijabla • Podatak, pa time i pripadajuća ćelija podatka, je određenog tipa • Zasebna celina je relativan pojam, nešto se u jednom trenutku može smatrati ćelijom, a kasnije se može gledati unutrašnja grada te iste celine • Svaka ćelija ima svoj tip i adresu • Grafički prikaz ćelije:

Polje • • • • • •

Vid mehanizma za udruživanje manjih delova strukture podataka u veće Polje čini više ćelija podataka istog tipa postavljenih na susednim memorijskim adresama Broj ćelija je unapred zadat i nepromjenljiv Jedna ćelija se zove element polja i jednoznačno je određena pripadnom vrijednošću indeksa Po ugledu na programski jezik C, uzimamo da su indeksi 0, 1, 2, ... , N-1, gdje je N celobrojna konstanta. Grafički prikaz polja:

Slog ili zapis • •

Mehanizam za objedinjavanje jednostavnijih struktura podataka Slog sadrži više ćelija, istog ili različitog tipa, koje su zapisane na susednim memorijskim lokacijama • Broj, redosled i tip ćelija je unaprijed zadan i nepromjenljiv • Pojedina ćelija se zove komponenta zapisa • Polja i zapisi se mogu kombinirati Na primer: polje zapisa, zapis čije pojedine komponente su polja, polje od polja, zapis čija komponenta je zapis, i slično. •

Grafički prikaz sloga:

Pointer ili pokazivač • Služi za uspostavljanje veze između delova strukture • Pointer je posebna ćelija koja pokazuje na neku drugu ćeliju • Sadržaj pointera je adresa ćelije koju treba pokazati • Grafički prikaz pokazivača:

Kursor • Također služi za uspostavljanje veze izmedu delova strukture • Kursor je ćelija tipa int, celobrojna veličina, koja pokazuje na element nekog polja • Sadržaj kursora je indeks elementa kojeg treba pokazati • Grafički prikaz kursora:

Primer strukture podataka • Niz slogova povezanih pomoću pointera sa još jednim poljem slogova • Slogovi su međusobno povezani i kursorima

Primer : Apstraktni tip podataka COMPLEX • scalar - bilo koji tip za koji su definisane operacije sabiranja i množenja • complex - podaci ovog tipa su uređeni parovi podataka tipa scalar • operacija ADD(z1,z2,&z3) za zadate varijable z1,z2 tipa complex računa njihov zbir z3, također tipa complex • Dakle, za z1 oblika (x1,y1), z2 oblika (x2,y2), dobiva se z3 oblika (x3,y3), tako da bude x3=x1+x2, y3=y1+y2

Primer : Apstraktni tip podataka COMPLEX • operacija MULT(z1,z2,&z3) - za zadate z1,z2 tipa complex računa njihov umnožak z3, također tipa complex •

Dakle, za z1 oblika (x1,y1), z2 oblika (x2,y2), dobiva se z3 oblika (x3,y3), takav da je x3=x1*x2-y1*y2, y3=x1*y2+y1*x2

Primer : Apstraktni tip podataka COMPLEX • Specifikacija: struktura podataka pogodna za prikaz kompleksnog broja bila bi formalno u programskom jeziku C specificirana kao tip complex: typedef struct { scalar re; scalar im; } COMPLEX; Grafički prikaz strukture podataka:

Primer : Apstraktni tip podataka COMPLEX • Kompletna implementacija apstraktnog tipa podataka COMPLEX se sastoji od prethodne definicije tipa podataka COMPLEX typedef struct { scalar re; scalar im; } COMPLEX; kao i od implementacija operacija nad podacima tipa COMPLEX u formi funkcija oblika: void ADD (COMPLEX z1, COMPLEX z2, COMPLEX *z3) {...} void MULT (COMPLEX z1, COMPLEX z2, COMPLEX *z3) {...}

ALGORITMI I STRUKTURE PODATAKA -U v o d – Prof. Dušan Starčević