Aproksimacijski in naključnostni algoritmi

Pogojev za vključitev v delo ni.

Struktura predmeta
Naprednejše teme računske zahtevnosti
Aproksimacijski algoritmi
Naključnostni algoritmi
Druge tehnike spopadanja s kompleksnostjo

Naprednejše teme računske zahtevnosti
Predmet se bo poglobil v hierarhijo računske kompleksnosti. Obravnavali bomo:
Različne računske modele
Pomembne razrede, kot so P, NP, PH, PSPACE, ECP in NEXP
Vlogo in primere prevedb med temi razredi
Koncept relativizacije (preroki)
Ladnerjev izrek ter primere problemov, kot sta izomorfizem grafov (GI) in faktorizacija
Modeliranje problemov z Booleovim zadovoljevanjem (SAT), celoštevilskim linearnim programiranjem (ILP) in semidefinitnim programiranjem (SDP)

Aproksimacijski algoritmi
Ta del se bo osredotočil na algoritme, ki zagotavljajo rešitve z določenim odstopanjem od optimalne. Vsebine so:
Definicije aproksimacijskih algoritmov in razreda APX
Metode snovanja, kot so:
Požrešni algoritmi
Linearno programiranje
Semidefinitno programiranje
Polinomske aproksimacijske sheme (PTAS)
Algoritmi s konstantno aproksimacijo
L-prevedbe v razredu APX

Naključnostni algoritmi
Raziskovali bomo, kako lahko naključnost pomaga pri reševanju zahtevnih problemov. To vključuje:
Uporabo naključnosti pri problemih v razredu P, na primer z algoritmoma Rabin-Miller in Karger, ter preverjanje polinomske identitete
Uporaba naključnosti za aproksimacijo
Metoda color coding
Koncept raznaklučenja (ali "derandomization"), ki naključne algoritme pretvori v deterministične

Druge tehnike spopadanja s kompleksnostjo
Na koncu bomo spoznali še druge pristope, kot so:
Fiksno-parametrsko sledljivi algoritmi (FPT) in kernelizacija
Kvantni algoritmi
Kompleksnost vezij
Natančni eksponentni algoritmi

Arora, Sanjeev, and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 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.

Študent bo po opravljenem predmetu:

Razumel razloge za uporabo aproksimacijskih in naključnostnih pristopov pri reševanju kompleksnih problemov, kot so NP-težki problemi.

Poglobljeno razumel hierarhijo razredov računske zahtevnosti (P, NP, PH, PSPACE, itd.), relacije med njimi ter vlogo različnih tipov prevedb.

Razumel teoretične osnove aproksimacijskih algoritmov, vključno z definicijami, metodami snovanja (požrešni algoritmi, linearno in semidefinitno programiranje) in načini ocenjevanja kakovosti rešitev (razred APX, PTAS, L-prevedbe).

Razumel vlogo naključnosti pri razvoju algoritmov in razlikoval med različnimi tipi naključnostnih algoritmov ter razredi kompleksnosti, ki jih opisujejo.

Spoznal druge sodobne tehnike za spopadanje z računsko zahtevnostjo, kot so fiksno-parametrski algoritmi, kvantni algoritmi, kompleksnost vezij in natančni eksponentni algoritmi.

Usposobljen za uporabo različnih metod za razvoj in analizo tako aproksimacijskih kot naključnostnih algoritmov.

Sposoben samostojno poiskati in razumeti nove raziskovalne rezultate s področja aproksimacijskega 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)

1. ČIBEJ, Uroš, LI, Aaron, MIKLÓS, István, NASIR, Sohaib, SRIKANTH, Varun. Constructing bounded degree graphs with prescribed degree and neighbor degree sequences. Discrete Applied Mathematics, 2023.
2. ČIBEJ, Uroš, SLIVNIK, Boštjan, ROBIČ, Borut. The complexity of static data replication in data grids. Parallel Computing, 2007.
3. ČIBEJ, Uroš, ROBIČ, Borut, MIHELIČ, Jurij. Empirical estimation of the halting probabilities. Computability in Europe, 2014.
4. ČIBEJ, Uroš, MIHELIČ, Jurij. Improvements to Ullmann’s algorithm for the subgraph isomorphism problem. International Journal of Pattern Recognition and Artificial Intelligence.
5. ČIBEJ, Uroš, MIHELIČ, Jurij. A polynomial-time algorithm for recognizing subgraph-symmetry-compressible graphs. MATCOS, 2019.
6. ČIBEJ, Uroš, FÜRST, Luka, MIHELIČ, Jurij. A symmetry-breaking node equivalence for pruning the search space in backtracking algorithms. Symmetry, 2019.