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

B. Robič, Aproksimacijski algoritmi, Založba FE in FRI, 2.izd., 2009.
D.P. Williamson, D.B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press, 2011.
V. V. Vazirani, Approximation Algorithms, Springer, 2004.
D. Hochbaum, Approximation Algorithms for NP-hard Problems, Course Technology, 1996.
R. Motwani, P.Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
M. Mitzenmacher, E. Upfal, Probability and Computing: Randomized algorithms and Probabilistic Analysis, Cambridge University Press, 2005.

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