Napredni algoritmi i strukture podataka

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.

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

Studijski programi

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

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

Predavanja

Auditorne vježbe

Laboratorijske vježbe

Za studente

Izvedba

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

Ocjenjivanje

90 izvrstan
80 vrlo dobar
65 dobar
50 dovoljan