Napredni algoritmi i strukture podataka
Prikazani su podaci za akademsku godinu: 2023./2024.
Nositelji
Predavanja
Dr. sc.
Dalibor Krleža
Auditorne vježbe
Laboratorijske vježbe
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
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)
Izborni predmeti
(1. semestar)
(3. semestar)
[FER3-HR] Elektronika - profil
Izborni predmeti
(1. semestar)
(3. semestar)
Izborni predmeti
(1. semestar)
(3. semestar)
Izborni predmeti
(1. semestar)
(3. semestar)
Izborni predmeti
(1. semestar)
(3. semestar)
(1. semestar)
[FER3-HR] Računalno inženjerstvo - profil
(1. semestar)
(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
- prepoznati i analizirati problem koji treba riješiti primjenom računala
- povezati postavljeni problem s istovrsnim ili sličnim već riješenim problemima
- odabrati najbolji algoritam za već riješeni (poznati) problem
- dizajnirati vlastiti algoritam za nepoznati problem
- ocijeniti valjanost vlastitog rješenja, u smislu procjene konvergencije i složenosti algoritma
- usporediti svoju ideju algoritma s možebitnim drugim idejama
- 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
Laboratorijslož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
- Uravnotežena stabla (npr. AVL stabla. crveno-crna stabla. podesiva stabla. prioritetna stabla)
- Napredne podatkovne strukture (npr. B-stabla. Fibonaccijeve gomile)
- Strukture podataka i algoritmi zasnovani na znakovnim nizovima (npr. sufiksni nizovi. sufiksna stabla. trie stabla)
- 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)
- Linearno programiranje (npr. dualnost. simpleksna metoda. algoritmi s unutarnjom točkom)
- Dinamičko programiranje
- Pohlepni algoritmi, Projekt, Algoritmi za kompresiju s gubicima i kompresiju bez gubitaka
- Međuispit
- Međuispit
- Nasumični algoritmi, Stohastički algoritmi
- Grafovi (npr. topološko sortiranje. pronalaženje čvrsto povezanih komponenti. podudarnost), Bloomovi filtri
- Grafovi (npr. topološko sortiranje. pronalaženje čvrsto povezanih komponenti. podudarnost)
- 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
- Redukcija: transformiraj i zavladaj, Približni algoritmi
- 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
0 Vježbe tjelesnog odgoja
Ocjenjivanje
90 izvrstan
80 vrlo dobar
65 dobar
50 dovoljan