Napredni algoritmi i strukture podataka

Opis predmeta

Strukture podataka: preskočne liste, samoorganizirajuće liste, rijetko popunjene tablice, uravnotežena stabla (rotacije u stablima, AVL stabla i crveno-crna stabla), višestruka stabla, B stabla, struktura Trie. Odabrane optimizacijske metode i algoritmi: dinamičko programiranje (problem naprtnjače), genetski algoritmi (bojanje grafova i problem trgovačkog putnika), osnove neuronskih mreža, linearno programiranje i simpleks algoritam. Operacije nad skupovima. Odabrani algoritmi nad grafovima: obilazak grafa, pretraživanje prvo u dubinu (DFS), pretraživanje prvo u širinu (BFS), najkraći putevi, detekcija ciklusa i povezanost, razapinjajuća stabla, Eulerovi grafovi, Hamiltonovi grafovi (problem trgovačkog putnika), uparivanje u grafovima. Protok u mrežama.

Opće kompetencije

Predmet je nadgradnja predmeta "Algoritmi i strukture podataka" iz preddiplomskog studija, a namijenjen je studentima koji žele proširiti i produbiti razumijevanje najvažnijih algoritama i struktura podataka. Obrađuju se složeniji algoritmi na koje se nailazi u raznim primjenama, s naglaskom na razumijevanje logike algoritama i njihove teorijske podloge. Konkretna programska rješenja se razmatraju u okviru laboratorijskih vježbi. Usvajanjem gradiva, studenti će uvelike proširiti svoje znanje i sposobnost rješavanja složenijih programskih zadataka koji zahtijevaju pravilan odabir i učinkovito usklađivanje različitih algoritama.

Ishodi učenja

  1. prepoznati i analizirati problem koji treba riješiti primjenom računala
  2. povezati postavljeni problem s istovrsnim ili sličnim već riješenim problemima
  3. odabrati najbolji algoritam za već riješeni (poznati) problem
  4. osmisliti vlastiti algoritam za nepoznati problem
  5. ocijeniti valjanost vlastitog rješenja, u smislu procjene konvergencije i složenosti algoritma
  6. usporediti svoju ideju algoritma s možebitnim drugim idejama
  7. preporučiti algoritam za nepoznati problem na temelju usporedbe predloženih rješenja

Oblici nastave

Predavanja

Predavanja se održavaju tijekom 15 tjedana, u što su uračunata dva tjedna za međuispite. U pravilu, predavanje se održava jednom tjedno u bloku od tri sata.

Provjere znanja

Provjere znanja su pismene i usmene.

Auditorne vježbe

Održavaju se ako se jave studenti-demostratori.

Laboratorijske vježbe

Obvezatne, odrađuju se kod kuće, a kolokviraju kod asistenata.

Konzultacije

Po dogovoru.

Seminari

Po dogovoru. Studenti mogu održati kratke prezentacije o odabranim algoritmima ili svojim rješenjima.

Način ocjenjivanja

Kontinuirana nastava Ispitni rok
Vrsta provjere Prag Udio u ocjeni Napomena / komentar Udio u ocjeni
Sudjelovanje u nastavi 0 % 8 % 0 % 0 %
Međuispit: Pismeni 25 % 42 % 0 %
Završni ispit: Pismeni 30 % 50 %
Ispit: Pismeni 70 % 50 %
Ispit: Usmeni 50 %

Tjedni plan nastave

  1. Uvodni sat. Preskočne liste. Samoorganizirajuće liste. Rijetko popunjene tablice. Stablo odlučivanja i granična brzina sortiranja. Brisanje čvorova u binarnom stablu, uparivanje, kopiranjem. Uravnotežavanje stabla, uravnotežavanje pripremom ulaznih podataka. DSW algoritam.
  2. Samopodešavajuća stabla. AVL stabla. B-stabla.
  3. Višestruka stabla. B-stabla. Crveno-crna stabla.
  4. Struktura trie. Uvod u optimizacije. Genetski algoritmi.
  5. Genetski algoritmi. Primjer bojanja grafa i problem trgovačkog putnika. Uvod u neuronske mreže.
  6. Neuronske mreže.
  7. Dinamičko programiranje na primjeru problema naprtnjače.
  8. Međuispit.
  9. Međuispit
  10. Linearno programiranje i simpleks algoritam.
  11. Linearno programiranje i simpleks algoritam.
  12. Pretraživanje unazad. Indikacije za primjenu pretraživanja unazad. Problem 8 kraljica i izlaska iz labirinta - usporedba. Uvod u algoritme nad grafovima, prikazi grafa. Obilazak grafa; prvo u dubinu, prvo u širinu. Najkraći put (Dijkstra, Bellman-Ford).
  13. Najkraći put (Warshall-Floyd-Ingermanov algoritam). Razapinjajuća stabla. Operacije nad skupovima (unija, pretraživanje) na primjeru povezanosti grafa. Eulerovi grafovi - uvod.
  14. Fleuryev algoritam, eulerizacija grafa, problem kineskog poštara. Opis problema uparivanja u grafovima. Protok u mrežama (Algoritam Forda i Fulkersona) i primjena na uparivanje u grafu.
  15. Hamiltonovi grafovi. Problem trgovačkog putnika.

Studijski programi

Obradba informacija -> Informacijska i komunikacijska tehnologija (Profil)

Telekomunikacije i informatika -> Informacijska i komunikacijska tehnologija (Profil)

Telekomunikacije i informatika -> Informacijska i komunikacijska tehnologija (Profil)

Programsko inženjerstvo i informacijski sustavi -> Računarstvo (Profil)

Računalno inženjerstvo -> Računarstvo (Profil)

Računarska znanost -> Računarstvo (Profil)

Literatura

Cormen, Leiserson, Rivest, Stein (2009.), Introduction to algorithms, MIT Press
Adam Drozdek (2004.), Data Structures and Algorithms in C++, Thomson Course Technology
Simon Haykin (2009.), Neural Networks and Learning Machines, Prentice Hall
D.Kalipć, V.Mornar (1996.), Operacijska istraživanja, Zues
E.K.P. Chong, S.H.Żak (2008.), An Introduction to Optimization, Wiley Interscience

Bodovi i izvedba

5 ECTS
R1 Engleski jezik
R1 E-učenje
45 Predavanja
0 Auditorne vježbe
0 Laboratorijske vježbe

Ocjenjivanje

90 izvrstan
75 vrlo dobar
60 dobar
50 dovoljan