Aproksimacijski in naključnostni algoritmi

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

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.

Način (pisni izpit, naloge, projekt)

Sprotno preverjanje (domače naloge, praktično delo)

Končno preverjanje (pisni izpit)

5 - 10, pri čemer velja, da je pozitivna ocena od 6 - 10

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.