Napredni algoritmi i strukture podataka

Prikazani su podaci za akademsku godinu: 2023./2024.

Nositelji

Doc. dr. sc.
Mario Brčić

Predavanja

Dr. sc.
Dalibor Krleža

Auditorne vježbe

Kristijan Poje
mag. ing.
Mihael Kovač
mag. ing.

Laboratorijske vježbe

Kristijan Poje
mag. ing.
Mihael Kovač
mag. ing.

Opis predmeta

Uravnotežena stabla (rotacije u stablima, AVL stabla i crveno-crna stabla), višestruka stabla, B stabla. Odabrani algoritmi nad grafovima. Odabrani geometrijski algoritmi. Odabrani algoritmi nad tekstom. Pohlepni algoritmi, dinamičko programiranje i redukcije. Protok u mrežama. Linearno programiranje i simpleks algoritam. Stohastički, aproksimacijski i randomizirani algoritmi. Diferencijabilno programiranje. Bloomovi filtri. Odabrani algoritmi za kompresiju podataka.

Studijski programi

Sveučilišni diplomski
[FER3-HR] Audiotehnologije i elektroakustika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Automatika i robotika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektroenergetika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektroničko i računalno inženjerstvo - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektronika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektrostrojarstvo i automatizacija - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Informacijsko i komunikacijsko inženjerstvo - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Komunikacijske i svemirske tehnologije - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Programsko inženjerstvo i informacijski sustavi - profil
(1. semestar)
[FER3-HR] Računalno inženjerstvo - profil
(1. semestar)
[FER3-HR] Računalno modeliranje u inženjerstvu - profil
(1. semestar)
[FER3-HR] Računarska znanost - profil
(1. semestar)
[FER3-HR] Znanost o mrežama - profil
(1. semestar)
[FER3-HR] Znanost o podacima - profil
(3. semestar)
[FER2-HR] Obradba informacija - profil
Teorijski predmeti profila (1. semestar)
[FER2-HR] Programsko inženjerstvo i informacijski sustavi - profil
Teorijski predmeti profila (1. semestar)
[FER2-HR] Računalno inženjerstvo - profil
Teorijski predmeti profila (1. semestar)
[FER2-HR] Računarska znanost - profil
Teorijski predmeti profila (1. semestar)
[FER2-HR] Telekomunikacije i informatika - profil
Predmeti specijalizacije profila (1. semestar) (3. semestar)

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

popraćena materijalima i prezentacijom stavljenom na web-stranicu predmeta

Laboratorij

složeni laboratorijski zadaci koji obuhvaćaju predavano gradivo

Način ocjenjivanja

Kontinuirana nastava Ispitni rok
Vrsta provjere Prag Udio u ocjeni Prag Udio u ocjeni
Laboratorijske vježbe 30 % 30 % 15 % 10 %
Međuispit: Pismeni 30 % 30 % 0 %
Završni ispit: Pismeni 30 % 40 %
Ispit: Pismeni 50 % 50 %
Ispit: Usmeni 40 %
Napomena / komentar

kratke provjere znanja idu u sumu povrh osnovnih 100%

Tjedni plan nastave

  1. Uravnotežena stabla (npr. AVL stabla. crveno-crna stabla. podesiva stabla. prioritetna stabla)
  2. Napredne podatkovne strukture (npr. B-stabla. Fibonaccijeve gomile)
  3. Strukture podataka i algoritmi zasnovani na znakovnim nizovima (npr. sufiksni nizovi. sufiksna stabla. trie stabla)
  4. Geometrijski algoritmi (npr. točke. odsječci pravaca. poligoni. pronalaženje konveksne ljuske. prostorna razložba / dekompozicija. otkrivanje preklapanja / kolizije. geometrijsko traženje i bliskost)
  5. Linearno programiranje (npr. dualnost. simpleksna metoda. algoritmi s unutarnjom točkom)
  6. Dinamičko programiranje
  7. Pohlepni algoritmi, Projekt, Algoritmi za kompresiju s gubicima i kompresiju bez gubitaka
  8. Međuispit
  9. Međuispit
  10. Nasumični algoritmi, Stohastički algoritmi
  11. Grafovi (npr. topološko sortiranje. pronalaženje čvrsto povezanih komponenti. podudarnost), Bloomovi filtri
  12. Grafovi (npr. topološko sortiranje. pronalaženje čvrsto povezanih komponenti. podudarnost)
  13. Grafovi (npr. topološko sortiranje. pronalaženje čvrsto povezanih komponenti. podudarnost), Protoci u mrežama (npr. Ford-Fulkersonov algoritam. maksimalni protok - minimalni rez. maksimalno bipartitno podudaranje), Približni algoritmi
  14. Redukcija: transformiraj i zavladaj, Približni algoritmi
  15. Završni ispit

Literatura

Thomas H. Cormen (2009.), Introduction to Algorithms, MIT Press
Adam Drozdek (2012.), Data Structures and Algorithms in C++, Thomson Course Technology
Steven S. Skiena (2008.), The Algorithm Design Manual, Springer-Verlag New York Incorporated
R. Sedgewick, K. Wayne (2011.), Algorithms 4th ed., Addison-Wesley
D. Kalpić, V. Mornar (1996.), Operacijska istraživanja, Zeus
J. Matousek, B.Gartner (2006.), Understanding and Using Linear Programming, Springer
Vijay V. Vazirani (2002.), Approximation Algorithms, Springer Science & Business Media
R. Motwani, P. Raghavan (1995.), Randomized Algorithms, Cambridge University Press
I. Goodfellow, Y. Bengio and A. Courville (2015.), Deep Learning, MIT press

Za studente

Izvedba

ID 222496
  Zimski semestar
5 ECTS
R1 Engleski jezik
R2 E-učenje
45 Predavanja
0 Seminar
6 Auditorne vježbe
15 Laboratorijske vježbe
0 Konstrukcijske vježbe

Ocjenjivanje

90 izvrstan
80 vrlo dobar
65 dobar
50 dovoljan

Sličan predmet