Strukture podataka i algoritmi: Uvod

Strukture podataka i algoritmi

1. Uvod

Ovaj predmet je zamisljen da vas nauci efikasnom programiranju. Pretpostavlja se

da poznajete osnove programiranja u C-u,
da znate da pisete, ispravljate i pokrecete jednostavne programe u C-u, i
da imate predstavu o objektno-orijentisanom programiranju.

Uvod (na engleskom) u objektno-orijentisano programiranje pomocu ANSI C standarda se moze naci u dodatnom Object First kursu.

Dobri programi

Postoji vise osobina dobrih programa: oni moraju

da se izvrsavaju ispravno
da se izvrsavaju efikasno
da budu laki za pisanje i razumevanje
da budu laki za ispravljanje i
da budu laki za prepravljanje.

Sta znaci izvrsavati se ispravno ?

Potrebna nam je formalna definicija znacenja ispravnosti: stoga gornji izraz definisemo da znaci

"izvrsavanje u skladu sa specifikacijama".

Prva od ovih osobina je ocigledna - programi koji se ne izvrsavaju ispravno bas i nemaju veliku vrednost. Pod "efikasnoscu" se obicno podrazumeva "za sto krace vreme" - ali se ponekad javljaju i druga ogranicenja, kao sto je kolicina memorije, koje ce biti najvaznije. Kao sto ce se kasnije videti, bolja vremena izvrsavanja ce se, u opstem slucaju, dobiti upotrebom odgovarajucih struktura i algoritama, pre nego "hack-ovanjem", tj. izbacivanjem nekoliko komandi pomocu mudrijeg kodiranja - ili jos gore, programiranjem u asembleru!

Glavni cilj ovog predmeta ce biti efikasno resavanje problema: bice vam predstavljene mnoge osnovne strukture podataka i algoritmi (ili procedure) za njihovo manipulisanje.

Vaznost ostalih osobina dobrih programa je manje ocigledna. Rana istorija mnogih racunarskih instalacija je, u svakom slucaju, svedocanstvo o njihovoj vaznosti. Mnoge studije su procenile enormne troskove izgradnje softverskih sistema koji NISU imali sve date osobine. (Klasicna referenca je Boehm-ova knjiga.) Na zalost, mnogi skorasnji primeri pokazuju da ovi principi jos uvek nisu u potpunosti usvojeni! Svaki pregled Risks foruma bi vas brzo uverio da postoji strasno mnogo loseg softvera u upotrebi. Disciplina softverskog inzinjerstva se bavi izgradnjom velikih softverskih sistema koji se ponasaju onako kako njihovi korisnici ocekuju, koji su pouzdani i laki za odrzavanje. Ovaj predmet ce uvesti neke principe softverskog inzinjerstva, ali cemo se mi koncentrisati samo na pisanje malih programa. Koristeci dobro poznate, efikasne tehnike za resavanje problema, ne samo da stvarate ispravne i brze programe u najkracem vremenu, vec i vasi programi postaju laksi za prepravljanje. Drugom softverskom inzinjeru ce biti mnogo lakse da radi sa dobro poznatim resenjem nego sa necim sto je sklepano zajedno i "podseca" na neki algoritam iz knjige.

Kljucni pojmovi

ispravnost: Ispravan program se izvrsava u skladu sa specifikacijama.
algoritam: Precizno definisana procedura za resavanje odredjenog problema.