Ishodi učenja predmeta

• izabrati najpogodniju izvedbu tipa podataka u konkretnoj situaciji s obzirom na složenost očekivano čestih operacija
• moći izgraditi složeniji računalni program koji se temelji na algoritmu i korisnički definiranim tipovima podataka
• poznavati kritičan broj standardnih struktura podataka
• poznavati osnovne metode usporedbe algoritama (ocjena složenosti)
• raditi u timu za izgradnju informacijskih sustava

Ishodi učenja programa

• analizirati stanje, identificirati prilike i definirati probleme s kojima se susreću organizacije i pojedinci u primjeni ICT, te formulirati rješenja uz primjenu ICT analizirati stanje, identificirati prilike i definirati probleme s kojima se susreću organizacije i pojedinci u primjeni ICT, te formulirati rješenja uz primjenu ICT
• razumjeti i primijeniti ključne aspekte informacijske tehnologije (programiranje, algoritmi, strukture podataka, baze podataka i znanjarazumjeti i primijeniti ključne aspekte informacijske tehnologije (programiranje, algoritmi, strukture podataka, baze podataka i znanja
• razumjeti stanje i trendove razvoja suvremenih informacijskih i komunikacijskih tehnologija (ICT), razumjeti njihov utjecaj na pojedinca, organizaciju i društvo te procijeniti njihovu primjenjivost u zadanom konteksturazumjeti stanje i trendove razvoja suvremenih informacijskih i komunikacijskih tehnologija (ICT), razumjeti njihov utjecaj na pojedinca, organizaciju i društvo te procijeniti njihovu primjenjivost u zadanom kontekstu

Sadržaj predavanja

•     Osnovni pojmovi, pregled sadržaja kolegija i literatura
  Pojam strukture podataka. Pojam algoritma. Međuodnos struktura podataka i algoritama. Povijest razvoja struktura podataka i algoritama. Pregled sadržaja kolegija. Upoznavanje s literaturom i izvorima na Webu.
•     Povijesni razvoj struktura podataka i algoritama. Modeli algoritama
  Povijesni razvoj struktura podataka i teorije algoritama. Univerzalni modeli algoritama. Turingov stroj i njjegova struktura. Primjeri realizacija algoritama na Turingovom stroju u odabranom simulacijskom programu (JFLAP). Univerzalni Turingov stroj.
•     Algoritamska nerješivost, rješivost i složenost
  Pojmovi algoritamske nerješivosti, rješivosti i složenosti. Algoritamski nerješivi problemi. Algoritamski rješivi problemi. Mjere složenosti algoritama. O-notacija. Priručne mjere složenosti algoritama.
•     Osnovna klasifikacija struktura podataka
  Kriteriji klasifikacije (linearnost, nelinearnost). Osnovne klase struktura podataka (linearne liste, stabla, grafovi)
•     Linearne liste
  Definicija opće klase linearnih lista i njezinih podklasa (stog, red, red sa dva kraja (DEQ)). Apstraktna reprezentacija. Pregled primjena.
•     Primjene stoga kao strukture podataka
  Izabrane primjene stoga kao strukture podataka (pravilnost građe algebarskih izraza s obzirom na raspored zagrada, postfiksni zapis (linearizacija) algebarskih izraza, računanje vrijednosti algebarskih izraza temeljem njihovog postfiksnog zapisa, zbrajanje vrlo velikih brojeva, modeliranje traženja izlaza iz labirinta).
•     Vezane liste, cirkularne liste i red
  Jednostruko vezane liste (modeliranje osnovnih operacija). Dvostruko vezane liste (modeliranje osnovnih operacija). Cirkularne liste (modeliranje osnovnih operacija). Modeliranje reda cirkularnom listom.
•     Relativna izražajna snaga podklasa klase linearnih lista
  Mjera relativne izražajne snage pojedinih podklasa klase linearnih lista (broj permutacija niza od n elemenata koje se daju realizirati dotičnom podklasom klase linearnih lista). Klasifikacija podklasa klase linearnih lista s obzirom na mjeru relativne izražajne snage.
•     Stabla
  Motivacijski primjer uvođenja stabla kao nelinearne strukture podataka (primjer pronalaženja duplikata u nizu brojeva, primjer sortiranja niza). Rekurzivna definicija stabla. Grafički prikaz stabla. Binarno stablo. Osnovni pojmovi vezani zu pojam binarsnog stabla.
•   Binarna stabla i njihova primjena
  Načini obilaska (obrade informacijskog sadržaja) čvorova binarnog stabla („najprije u dubinu“, „simetrični načn“ i „najprije u širinu“). Reprezentacija bilo kojeg stabla u obliku binarnog stabla. Binarna stabla pretraživanja. Binarna stabla sortiranja.
•   Grafovi
  Definicija grafa i osnovnih pojmova vezanih uz graf (čvorovi, bridovi, putevi, usmjerenost, neusmjerenost,…). Modeli reprezentacije grafova (kao skupa čvorova i skupova pripadajućih susjednih čvorova i u obliku matrice „sudjednosti“ čvorova). Načini obilaska grafova.
• Algoritmi sortiranja
  Pojam uređaja na skupu. Tipovi uređaja. Osnovne klase algoritama sortiranja i njihova složenost (mjehuričasto sortiranje, sortiranje spajanjem, sortiranje umetanjem, brzo sortiranje)
• Algoritmi pretraživanja
  Osnovni pojmovi vezani az algoritme pretraživanja (skup podataka, ključ,…). Neki osnovni algoritmi pretraživanja (sekvencijalno pretraživanje, pretraživanje usporedbom ključeva, heširanje).
• Ad hoc mjere složenosti algoritama
  Složenost Euklidovog algoritma
• Statističke mjere složenosti algoritama
  Pojam slučajne varijable vezane za algoritam. Statističke mjere ponašanja slučajne varijable (očekivanje, standardna devijacija i varijanca). Statistička složenost Knuthovog algoritma M.

Sadržaj seminara/vježbi

• Generirajuće funkcije nizova
  Generirajuće funkcije nizova predstavljaju alat za istraživanje statističke složenosti algoritama. Statistički parametri (očekivanje, standardna devijacija i varijanca) vežu se uz izabranu slučajnu varijablu u sklopu algoritma koji se istražuje, a izražavaju se kroz vrijednosti generirajuće funkcije pripadajućih vjerojatnosti i vrijednosti njezinih derivacija (prve i druge)
• Formalizacije intuitivnog pojma algoritma
  Potreba za formalizacijom intuitivnog pojma algoritma. Masovni algoritamski problemi i njihova rješivost, odnosno nerješivost. Osnovne klase vremenske složenosti algoritama.
• Turingovi strojevi kao modeli algoritama
  Opis rada Turingovog stroja. Univerzalni Turingov stroj. Modeliranje Turingovih strojeva u alatu JFLAP.
• Statistička složenost algoritama
  Računanje statističke složenosti izabranih algoritama. Izbor slučajne varijable. Oblikovanje generirajuće funkcije niza vjerojatnosti za vrijednosti izabrane slučajne varijable. Računanje složenosti.
• Knuthov računalni stroj MMIX
  Opis Knutovog računalnog stroja MMIX. Realizacija izabranih struktura podataka i algoritama u programskom jeziku računala MMIX.
• Programsko okružje LEDA
  Programsko okružje LEDA suvremeno je programsko okružje, razvijeno za potrebe modeliranja struktura podataka i algoritama te njihovu vizualizaciju. Ova tema izlaže osnovnu strukturu programskog okružja LEDA i neke njegove primjene.
• Asocijativne strukture podataka
  Pojam asocijativne strukture podataka. Prikaz programskog jezika Lua i njegove asocijativne strukture podataka. Modeliranje standardnih apstraktnih tipova podataka asocijativnom strukturom podataka u jeziku Lua.
• Kombinatorni objekti kao strukture podataka
  Potreba za kombinatornim objektima kao strukturama podataka. Osnovni tipovi kombinatornih objekata (permutacije, kombinacije, varijacije). Algoritmi za generiranje kombinatornih objekata.
• Strukture podataka i algoritmi polinomske aritmetike
  Važnost algoritama polinomske aritmetike. Osnovne strukture podataka za prikaz polinoma. Osnovni algoritmi za rad s polinomima. Primjene polinomske aritmetike.
• Slučajni brojevi i njihove primjene
  Pojam algoritamskih slučajnih brojeva (tj. pseudoslučajnih brojeva). Neki algoritmi za generiranje slučajnih brojeva. Neke primjene slučajnih brojeva.
• Stabla igara kao struktura podataka
  Stablo igre. Različite reprezentacije stabla igre kao strukture podataka. Ilustracija na igri križiž-kružić. Korisne operacije na stablima igara.

Alati koji se koriste na predmetu

• C++
  Open Source C++ okruženje DEV-C++
• LEDA
  Specijalno programsko okružje, razvijeno za modeliranje i vizualizaciju struktura podataka i pripadajućih algoritama. Izgrađeno u jeziku C++. Koristit će se za potrebe nekih tema seminarskih radova.
• JFLAP
  Programsko okružje za modeliranje konačnih automata i Turingovih strojeva. Koristit će se za potrebe nekih tema seminarskih radova.
• MMIX
  Knuthov model računala. Koristit će se za potrebe nekih seminarskih radova.

Osnovna literatura

• Keogh, J., Davidson, K. Data Structures Demystified. McGraw-Hill/Osborne, New York, 2004.
• Knuth, D. E. The Art of Computer Programming, Volume 1 : Fundamental Algorithms. Addison-Wesley, Reading, 1997.
• Knuth, D. E. The Art of Computer Programming, Volume 3 : Sorting and Searching. Addison-Wesley, Reading, 1997.

Dopunska literatura

• Divjak, B., Lovrenčić, A. Diskretna matematika s teorijom grafova.TIVA-FOI, Varaždin, 2005.
• Drozdek, A. Data Structures and Algorithms in C++. Course Technology, Boston, 2004.
• Rodger, S. H., Finley, T. W. JFLAP : An Interactive Formal Languages and Automata Package. Jones and Bartlett, Sudbury, 2006.
• Introduction to alrogithms. Cormen, T. H., Lieserson, C. E., Rivest, R. L., Stein, C. 2nd ed. MIT, Cambridge, 2001.

Preduvjeti

• Programiranje 1
  Predmet predstavlja temeljne koncepte programiranja, temeljna znanja rada prevodilaca i interpretatora programskih jezika, metode rješavanja programskih problema te osnove objektnog pristupa

Slični predmeti

• Strukture podataka i algoritmi – PMF-Zagreb
• Algoritmi i strukture podataka-FER-Zagreb
• Algoritmi i strukture podataka-Filozofski fakultet Zagreb, Odsjek za informacijske znanosti
• Strukture podataka i algoritmi-Visoka škola za informacijske tehnologije Zagreb
• Algoritmi i strukture podataka-Filozofski fakultet Rijeka-Odsjek za informatiku