mislo

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

Aproksimacijski in naključnostni algoritmi

Za predmet Aproksimacijski in naključnostni algoritmi š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 Aproksimacijski in naključnostni algoritmi: 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. Naprednejše teme računske zahtevnosti
  2. Aproksimacijski algoritmi
  3. Naključnostni algoritmi
  4. Druge tehnike spopadanja s kompleksnostjo
  5. ________________________________________
  6. Naprednejše teme računske zahtevnosti
  7. Različne računske modele
  8. Pomembne razrede, kot so P, NP, PH, PSPACE, ECP in NEXP
  9. Vlogo in primere prevedb med temi razredi
  10. Koncept relativizacije (preroki)
  11. Ladnerjev izrek ter primere problemov, kot sta izomorfizem grafov (GI) in faktorizacija
  12. Modeliranje problemov z Booleovim zadovoljevanjem (SAT), celoštevilskim linearnim programiranjem (ILP) in semidefinitnim programiranjem (SDP)
  13. ________________________________________
  14. Aproksimacijski algoritmi
  15. Ta del se bo osredotočil na algoritme, ki zagotavljajo rešitve z določenim odstopanjem od optimalne.
  16. Vsebine so (Definicije aproksimacijskih algoritmov in razreda; Apx)
  17. Metode snovanja, kot so (Požrešni algoritmi; Linearno programiranje; Semidefinitno programiranje; Polinomske aproksimacijske sheme (PTAS); Algoritmi s konstantno aproksimacijo; L-prevedbe v razredu APX; ________________________________________; Naključnostni algoritmi; Uporabo naključnosti pri problemih v razredu P, na primer z algoritmoma Rabin-Miller in Karger, ter preverjanje polinomske identitete; Uporaba naključnosti za aproksimacijo; Metoda color coding; Koncept raznaklučenja (ali "derandomization"), ki naključne algoritme pretvori v deterministične; ________________________________________; Druge tehnike spopadanja s kompleksnostjo; Fiksno-parametrsko sledljivi algoritmi (FPT) in kernelizacija; Kvantni algoritmi; Kompleksnost vezij; Natančni eksponentni algoritmi)

Ocenjevanje

Sprotno preverjanje (domače naloge, praktično delo) 50 %, Končno preverjanje (pisni izpit) 50 %

Literatura

  • Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009
  • D.P. Williamson, D.B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
  • V. Vazirani, Approximation Algorithms, Springer, 2004.
  • Hochbaum, Approximation Algorithms for NP-hard Problems, Course Technology, 1996.
  • Motwani, P.Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
  • Mitzenmacher, E. Upfal, Probability and Computing: Randomized algorithms and Probabilistic Analysis, Cambridge
  • University Press, 2005.

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.