Aproksimacijski in naključnostni algoritmi

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