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

Sveučilišni diplomski
Obradba informacija (profil)
Teorijski predmeti profila (1. semestar)
Programsko inženjerstvo i informacijski sustavi (profil)
Teorijski predmeti profila (1. semestar)
Računalno inženjerstvo (profil)
Teorijski predmeti profila (1. semestar)
Računarska znanost (profil)
Teorijski predmeti profila (1. semestar)
Telekomunikacije i informatika (profil)
Predmeti specijalizacije profila (1. semestar) (3. semestar)

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

Predavanja

Izvedba

ID 34395
  Zimski semestar
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