Aproksimacijski in naključnostni algoritmi

Pogojev za vključitev v delo ni.

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

1. D. Hochbaum, ed.: Approximation algorithms for NP-hard problems, Boston : : PWS : International Thomson Publishing, cop. 1997.
2. M. Mitzenmacher, E. Upfal: Probability and computing : randomized algorithms and probabilistic analysis, Cambridge : Cambridge University Press, 2005.
3. R. Motwani, P.Raghavan: Randomized algorithms, Cambridge : Cambridge Univ., cop. 1995.
4. V. V. Vazirani: Approximation algorithms, Berlin : Springer, cop. 2001.

Slušatelji bodo na teoretičnem nivoju in prek praktičnih primerov osvojili znanja za približno in naključnostno reševanje praktičnih problemov, ki so v razumnem času drugače neobvladljivi.

Znanje in razumevanje:
Študent bo po opravljenem predmetu:

-- razumel razloge za aproksimacijski in/ali naključnostni pristop k reševanju nekaterih, predvsem NP-težkih računskih problemov,
-- razumel razliko (in povezave) med odločitvenimi in optimizacijskimi problemi,
-- razumel praktične razloge za aproks. ali naklj. računanje suboptimalnih rešitev problemov,
-- razumel osnovne pojme o aproks. in naklj. algoritmih,
-- razumel razne pristope za določanje kakovosti suboptimalnih rešitev ter omejitve teh pristopov,
-- razumel razrede zahtevnosti odločitvenih in optimizacijskih problemov glede na njihovo odzivnost na aproks. ali naklj. reševanje, in relacije med temi razredi,
-- poznal aproks. In naklj. algoritme za izbrane pomembne NP-težke probleme,
-- usposobljen uporabljati razne metode za razvoj in analizo aproks. in naklj. algoritmov
-- usposobljen za samostojno iskanje in razumevanje novih raziskovalnih rezultatov s področij aproksimacijsega in naključnostnega reševanja računskih problemov.

Predavanja, domače naloge, seminarski način dela pri vajah.

Sprotno preverjanje (domače naloge, praktično delo)
Končno preverjanje (pisni izpit)
(ocene: 5 (negativno), 6-10 (pozitivno), ob upoštevanju Statuta UL)

B.Robič, The Foundations of Computability Theory, Spinger, 2015. (ISBN 978-3662448076)
M.Bezenšek, B.Robič, A survey of parallel and distributed algorithms for the Steiner tree problem. Int. J. Par. Program., 42:287-319, 2013.
J.Mihelič, A.Mahjoub, C.Rapine, B.Robič, Two-stage flexible-choice problems under uncertainty. Eur. J. Oper. Res. 201(2):399-403, 2010.
J.Mihelič, B.Robič, Flexible-attribute problems. Comput. Optim. Appl. 47(3):553-566, 2010.
R.Trobec, M.Šterk, B.Robič, Computational complexity and parallelization of the meshless local Petrov-Galerkin methods. Comput. Struct. 87(1):81-90,2009.
Celotna bibliografija je dostopna na SICRIS: http://sicris.izum.si/search/rsr.aspx?lang=slv&,id=5520