• Šifra predmeta:63557
  • Kreditne točke:6
  • Semester: poletni
  • Vsebina

Predmet bo vseboval naslednje vsebine:

•    Uvod
    Računska zahtevnost odločitvenih in optimizacijskih problemov
    NP-polni in NP-težki problemi
    Hevristični algoritmi, kakovost suboptimalnih rešitev,  (ne)obstoj zagotovila za kakovost
•    Približno reševanje NP-težkih probl.
    Aproksimacijski algoritmi
    Kakovost približnih rešitev
    Razred APX
    Tehnika z vrzeljo
    Aproksimacijske sheme
    Razreda PTAS in FPTAS
    Meje približnega reševanja
•    Razvoj aproksimacijskih algoritmov
    Požrešna metoda
    Osredotočanje na podporobleme
    Zaporedno razdeljevanje
    Dinamično programiranje
•    Naključnostno reševanje NP-težkih probl.
    Las Vegas in Monte Carlo algoritmi
    Razredi RP, co-RP,  ZPP, PP, BPP
•    Razvoj naključnostnih algoritmov
    Naključno vzorčenje
    Zagotavljanje obilice prič
    Naključno preurejanje vhoda
    Zgoščanje
    Enakomerno porazdeljevanje bremen
 

  • Študijski programi
  • Porazdelitev ur na semester
45
ur
predavanj
30
ur
laboratorijskih vaj
  • Izvajalci
Nosilec predmeta
Prostor:R2.05 - Kabinet
Asistent
Prostor:R2.31