FOI Nastava - Strukture podataka

Sadržaj se učitava...

FOI Nastava

apps

mdi-login

Strukture podataka

Data Structures
2015/2016

6 ECTSa

Informacijski i poslovni sustavi 1.1 (PDS)

Katedra za teorijske i primijenjene osnove informacijskih znanosti

3. semestar

Osnovne informacijemdi-information-variant

Izvođači nastavemdi-account-group

Nastavni plan i programmdi-clipboard-text-outline

Model praćenjamdi-human-male-board

Ispitni rokovimdi-clipboard-check-outline

Rasporedmdi-calendar-clock

Konzultacijemdi-account-voice

Izvođenje kolegija

Studij	Studijski program	Semestar	Obavezan
Informacijski i poslovni sustavi 1.1 (PDS)	Informacijski sustavi	3	obavezan
Informacijski i poslovni sustavi 1.1 (PDS)	Poslovni sustavi	3	izborni
Informacijski i poslovni sustavi 1.1 (PDS)	Poslovni sustavi	5	izborni

Cilj kolegija

Cilj kolegija Modeliranje poslovnih pravila je upoznavanje studenata s osnovnim teorijskim postavkama i praktičnim metodama i postupcima konceptualnog i formalnog oblikovanja i implementacije poslovnih pravila i sustava poslovnih pravila, u kontekstu suvremenih alata za razvoj informacijskih sustava, kako klasičnih, tako i suvremenih (sustavi ontologija, sustavi baza znanja i sustavi semantičkog Weba).

Preduvjeti

Programiranje 1 (PDS 1.1)

Norma kolegija

Predavanja

30 sati

Seminar

15 sati

Vježbe u praktikumu

15 sati

Nastavnik	Uloga na kolegiju	Oblik nastave	Tjedana	Sati	Grupa
Čubrilo Mirko	Nositelj	Seminar Predavanja	15 15	1 2	4 2
Konecki Mladen	Suradnik	Vježbe u praktikumu	15	1	5
Lovrenčić Alen	Suradnik	Vježbe u praktikumu	15	1	1
Orehovački Tihomir	Suradnik

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.

Ishodi učenja kolegija

raditi u timu za izgradnju informacijskih sustava
poznavati kritičan broj standardnih struktura podataka
poznavati osnovne metode usporedbe algoritama (ocjena složenosti)
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

Ishodi učenja programa

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 kontekstu
razumjeti i primijeniti ključne aspekte informacijske tehnologije (programiranje, algoritmi, strukture podataka, baze podataka i znanja
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

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.

Slični kolegiji

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

Redoviti studenti

Izvanredni studenti

U kalendaru ispod se nalaze konzultacije predmetnih nastavnika, no za detalje o konzultacijama možete provjeriti na profilu pojedinog predmetnog nastavnika.