FOI nastava
FOI logo

Lista kolegija iz:

ak.god:
2014/2015
semestar:
3. semestar

2014/2015

6ECTSa

Preddiplomski

Informacijski/Poslovni sustavi v1.1

Program Obavezan
Informacijski sustavi IS Da
Poslovni sustavi PS Ne
3. semestar
2. nastavna godina

Strukture podataka npp:61772

Engleski naziv

Data Structures

Katedra

Katedra za teorijske i primijenjene osnove informacijskih znanosti

Kategorija ("boja")

RI

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).

Nastava

Predavanje
30sati
Seminar
15sati
Laboratorijske vježbe
15sati

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
Nastavnik Oblik nastave Tjedana Sati tjedno Grupa
Čubrilo Mirko Predavanje 15 2 1
Seminar 15 1 3
Orehovački Tihomir Laboratorijske vježbe 15 1 7
Izvanredni rok
Datum: 21.11.2019.
Vrijeme: 16:00
Napomena:
Izvanredni rok
Datum: 29.04.2020.
Vrijeme: 16:00
Napomena:
Predavanje Seminar Auditorne vježbe Laboratorijske vježbe Vježbe (jezici, tzk) Ispit Kolokviji Nadoknade Demonstrature
Copyright © 2015 FOI Varaždin. All Rights Reserved. Sva prava pridržana.
Povratak na vrh