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
