mislo

Fakulteta za računalništvo in informatiko · Univerza v Ljubljani

Algoritmi in podatkovne strukture 2

Za predmet Algoritmi in podatkovne strukture 2 še ni zapiskov.

Imaš svoje zapiske? Objavi jih: ceno določiš ti, z naročnino ti ostane cela, DDV se doda kupcu.

Objavi zapiske

Čakaš na zapiske? Prijavi se in povej. Ko jih kdo objavi, dobiš sporočilo.

Želim zapiske

Kaj lahko narediš že danes

Naloži svoje gradivo za predmet Algoritmi in podatkovne strukture 2: Mai ga prebere in ti iz njega naredi kartice, kviz in razlago, ko ti kaj ni jasno. Če zapiske kasneje objaviš, jih prodajaš tukaj.

Naloži svoje gradivo

Učni načrt

Podatki so iz učnega načrta, ki ga objavlja Fakulteta za računalništvo in informatiko. Prebrano 7. 9. 2026. Poglej izvirnik

6 kreditnih točk

Obveznosti v urah

  • Predavanja45 ur
  • Vaje30 ur
  • Samostojno delo105 ur

Vsebina

  1. Računska zahtevnost algoritmov: motivacija, asimptotična notacija z definicijami in primeri.
  2. Deli in vladaj: krovni izrek z dokazom, algoritem za hitro iskanje k-tega najmanjšega elementa (quickselect), Karacubov algoritem za hitro množenje, Strassenovo množenje matrik.
  3. Dinamično programiranje: ponovitev osnovnih pristopov, primeri s kompleksnejšim opisom stanja (problem trgovskega potnika, barvanje grafov), primeri z zahtevnejšim računanjem (delnih) rezultatov (najdaljše naraščajoče podzaporedje, spuščanje jajc).
  4. Problem maksimalnega pretoka: definicija, Ford-
  5. Fulkersonova metoda, Edmonds-Karpov algoritem, uporaba (npr. pri problemu prirejanja v dvodelnih grafih).
  6. Iskanje po znakovnih zaporedjih: naivna metoda, Rabin-Karpov algoritem, Knuth-Morris-Prattov algoritem.
  7. Metode za indeksiranje besedila: drevo trie, priponska tabela, priponsko drevo.
  8. Računska geometrija: osnovni geometrijski objekti (točke, premice, večkotniki ...), razdalje, presečišča, ploščine, konveksna ovojnica, geometrijske podatkovne strukture (npr. k-d-drevesa).
  9. Linearno programiranje: formulacija s sistemom linearnih neenačb, predstavitev optimizacijskih problemov z linearnimi programi, simpleksni algoritem.

Ocenjevanje

Sprotno preverjanje: domače naloge 20 %, Končno preverjanje: pisni in ustni izpit 80 %

Literatura

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 4th
  • Edition. MIT Press, 2022.
  • Dodatna literatura:
  • Adam Jones. Advanced Techniques in Dynamic Programming: A Comprehensive Guide for Java Developers. 2024.
  • Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Computational Geometry: Algorithms and Applications, 3rd Edition. Springer, 2008.
  • Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge
  • University Press, 1997.

Kako deluje

  1. Zapiske kupiš enkrat in ostanejo tvoji.
  2. V aplikaciji iz njih dobiš kartice, kvize in Mai, ki pozna gradivo.
  3. Ceno določi avtor. Prodajalec je Mislo AI, račun dobiš od nas.