Napredna teorija algoritama i sustava

Opis kolegija

Uvod u napredne strukture podataka i algoritme. Rekurzija, analiza složenosti, sortiranja. Algoritmi sortiranja. Binarna stabla pretraživanja u memoriji: implementacija, balansiranje. Binarna stabla pretraživanja u memoriji: AVL i crveno-crno stablo, analiza, primjena. Indeksiranje pomoću strukture stabla. Strukture stabla za pretraživanje na disku: 2-3-4 stabla, B-stabla, R-stabla. Raspršeno adresiranje: odabrana poglavlja. Prvi kolokvij. Grafovi: osnovni pojmovi, implementacija, pretraživanje na grafu. Grafovi: obilazak u širinu i dubinu, topološko sortiranje, čvrsto povezane komponente. Grafovi: minimalni obuhvat grafa, problem najkraćeg puta. Grafovi: analiza centralnosti. Algoritmi pretraživanja u tekstu. Pregled vrsta i strategija oblikovanja algoritama. Završni kolokvij.

Ishodi učenja

1. usporediti i primijeniti ključne strukture podataka (stabla za pretraživanje, hash tablice, graf reprezentacije, rječnici)
2. osmisliti učinkovito programsko rješenje za različita područja primjene pomoću prikladno odabranog algoritma i strukture podataka.
3. usporediti ključne algoritamske paradigme (golom snagom, podijeli pa vladaj, pretvori i vladaj).
4. formulirati / oblikovati opće algoritamske probleme (sortiranje, traženje).
5. prosuditi empirijskim metodama i primijeniti temeljne algoritme i strukture podataka na stvarnim problemima.
6. preporučiti učinkovite algoritme i strukture podataka na konkretnim projektima.
7. povezati i razumijevati mapiranje stvarnih problema u algoritamska rješenja.

Literatura

Obavezna literatura

• Elektronički sadržaji predavanja u LMS-u predmeta na Tehničkom veleučilištu u Zagrebu, 2023. https://lms-2020.tvz.hr/course/view.php?id=626.
  T. H. Cormen, C. E. Leiserson, R. L. Rivest, Clifford Stein, Introduction to Algorithms, 4th Edition, MIT Press, 2022.
  R. Manger, M. Marušić: Strukture podataka i algoritmi, skripta, 3. izdanje, PMF-MO, 2007. http://web.math.pmf.unizg.hr/nastava/spa/.
  M. T . Goodrich, R . Tamassia, M. H. Goldwasser, Data Structures and Algorithms in Python, Wiley, 2013.
  C. A. Shaffer, Data Structures and Algorithm Analysis, https://people.cs.vt.edu/shaffer/Book
  R. Sedgewick, K. Wayne: Algorithms, 4th edition, Addison-Wesley Professional, 2011..
  R. Sedgewick, P. Flajolet: Analysis of Algorithms, 2th edition, Addison-Wesley Professional, 2013.
  R. Sedgewick: Algorithms in C++ Part 5: Graph Algorithms, 3rd Edition.