FOI nastava
FOI logo

Lista kolegija iz:

ak.god:
2017/2018
semestar:
3. semestar

2017/2018

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 2
Seminar 15 1 4
Lovrenčić Alen 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:

Strukture podataka - Redovni studenti

Studij: Informacijski/Poslovni sustavi
Akademska godina: 2017/2018

Praćenje rada studenata

Elementi praćenjaBodova
Domaće zadaće40
Kolokviji30
Seminarski rad30
ZBROJ100


Bodovna skala ocjena

OdDoOcjena
0 49 nedovoljan (1)
50 60 dovoljan (2)
61 75 dobar (3)
76 90 vrlo dobar (4)
91 100 odličan (5)



Kolokviji

Naziv / Tjedan 1234567891011121314151617 1. razdoblje
udio (%)
2. razdoblje
udio (%)
3. razdoblje
udio (%)
Trajanje Pismeni Usmeni
Prvi kolokvij + 100.0 0.0 0.0 60 +
Drugi kolokvij + 20.0 80.0 0.0 60 +


Opis elemenata praćenja

Elementi praćenja Bodovi Uvjet Opis Nadoknada
Granica Opis Rok
Prisustvovanje na laboratorijskim vježbama 0 15 Na laboratorijskim vježbama provjerava se prisustvovanje. Studenti su dužni prisustvovati svim laboratorijskim vježbama.
3 izostanka Dodatni zadaci. Javiti se nastavniku nakon objave evidencije prisustvovanja. Nadoknade će se održavati u posljednjem tjednu 3. međuispitnog razdoblja. Zadnji dan 3. međuispitnog razdoblja
Laboratorijske vježbe 40 0 Tijekom semestra student pristvuje na 4 laboratorijske vježbe koje se ocjenjuju i svaka nosi 10 bodova. Student dobiva praktični zadatak i rješava ga na računalu u roku od 90 minuta. Pri tome student koristi pripremljene biblioteke sa strukturama podataka koje su obrađene tijekom predavanja i vježbi. Nema nadoknada
Prvi kolokvij 15 0 Rješavanje teorijskih i praktičnih zadataka otvorenog tipa koja vrednuju razumijevanje gradiva. Prepisivanje je zabranjeno te povlači disciplinsku odgovornost.
Drugi kolokvij 15 0 Rješavanje teorijskih i praktičnih zadataka otvorenog tipa koja vrednuju razumijevanje gradiva. Prepisivanje je zabranjeno te povlači disciplinsku odgovornost.
Seminarski rad 30 0 Studenti odabiru temu seminarskog rada. Svaki student treba prezentirati odabranu temu u sklopu seminarske nastave. Student koji nije spreman prezentirati temu rada gubi bodove iz seminarskog rada. Korištenje tuđeg rješenja (plagijat) je zabranjeno te povlači disciplinsku odgovornost. Tjedan dana prije prijavljenog ispitnog roka


Strukture podataka - Izvanredni studenti

Studij: Informacijski/Poslovni sustavi
Akademska godina: 2017/2018

Praćenje rada studenata

Elementi praćenjaBodova
Domaće zadaće40
Kolokviji30
Seminarski rad30
ZBROJ100


Bodovna skala ocjena

OdDoOcjena
0 49 nedovoljan (1)
50 60 dovoljan (2)
61 75 dobar (3)
76 90 vrlo dobar (4)
91 100 odličan (5)



Kolokviji

Naziv / Tjedan 1234567891011121314151617 1. razdoblje
udio (%)
2. razdoblje
udio (%)
3. razdoblje
udio (%)
Trajanje Pismeni Usmeni
Prvi kolokvij + 100.0 0.0 0.0 60 +
Drugi kolokvij + 20.0 80.0 0.0 60 +


Opis elemenata praćenja

Elementi praćenja Bodovi Uvjet Opis Nadoknada
Granica Opis Rok
Prisustvovanje na laboratorijskim vježbama 0 15 Na laboratorijskim vježbama provjerava se prisustvovanje. Studenti su dužni prisustvovati svim laboratorijskim vježbama.
3 izostanka Dodatni zadaci. Javiti se nastavniku nakon objave evidencije prisustvovanja. Nadoknade će se održavati u posljednjem tjednu 3. međuispitnog razdoblja. Zadnji dan 3. međuispitnog razdoblja
Laboratorijske vježbe 40 0 Tijekom semestra student pristvuje na 4 laboratorijske vježbe koje se ocjenjuju i svaka nosi 10 bodova. Student dobiva praktični zadatak i rješava ga na računalu u roku od 90 minuta. Pri tome student koristi pripremljene biblioteke sa strukturama podataka koje su obrađene tijekom predavanja i vježbi. Nema nadoknada
Prvi kolokvij 15 0 Rješavanje teorijskih i praktičnih zadataka otvorenog tipa koja vrednuju razumijevanje gradiva. Prepisivanje je zabranjeno te povlači disciplinsku odgovornost.
Drugi kolokvij 15 0 Rješavanje teorijskih i praktičnih zadataka otvorenog tipa koja vrednuju razumijevanje gradiva. Prepisivanje je zabranjeno te povlači disciplinsku odgovornost.
Seminarski rad 30 0 Studenti odabiru temu seminarskog rada. Svaki student treba prezentirati odabranu temu u sklopu seminarske nastave. Student koji nije spreman prezentirati temu rada gubi bodove iz seminarskog rada. Korištenje tuđeg rješenja (plagijat) je zabranjeno te povlači disciplinsku odgovornost. Tjedan dana prije prijavljenog ispitnog roka


Opis elemenata praćenja - Model 2 - izvanredni studenti

Elementi praćenja Bodovi Uvjet Opis Nadoknada
Granica Opis Rok
Seminarrad 100 tudent treba odabrati temu iz šireg područja programiranja, struktura podataka ili algoritama te istu tijekom konzultacija prijaviti kod predmetnog nastavnika. Nakon što predmetni nastavnik odobri temu, student može pristupiti izradi seminarskog rada. Seminarski rad treba imati najmanje 15 stranica te se sastojati od uvoda, razrade teme, zaključka i literature koja je u tekstu citirana. Tekst u radu treba biti obostrano poravnat, pisan Times New Roman fontom veličine 12, sa proredom od 1.5 između redaka. Seminarski rad se brani u kabinetu predmetnog nastavnika u vrijeme usmenog dijela ispita. Na obranu je potrebno donijeti uvezenu tiskanu verziju rada i PowerPoint prezentaciju. Ukoliko seminarski rad sadrži praktičnu komponentu, implementaciju je potrebno pohraniti na CD/DVD medij te isti priložiti uz tiskanu verziju rada. Prilikom odabira teme i izrade seminarskog rada, studenti mogu konzultirati osnovnu i dopunsku literaturu, materijale objavljene na sustavu za e-učenje Moodle i wiki sustavu kolegija te bilješke demonstratora. U slučaju neuspješne obrane, student treba ponoviti cijeli postupak odabira i odobravanja teme te pisanja i obrane rada. Korištenje tuđeg rada (seminarskog, završnog, diplomskog i sl.) i predstavljanje kao svojeg (plagijat) je zabranjeno te povlači disciplinsku odgovornost. Tjedan dana prije prijavljenog ispitnog roka


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