# Aproksimacijski in naključnostni algoritmi

Dobrodošli na repozitoriju predmeta **Aproksimacijski in naključnostni algoritmi**. Na tem mestu bodo sproti objavljeni materiali, ki nastajajo na predavanjih - predvsem prosojnice, občasno tudi koda.

## Vsebina po tednih

1. Uvod in osnovni modeli računanja
2. NP, prevedbe in NP-polnost
3. Še prevedbe, vmesni problemi, diagonalizacija
4. Ladner, Prostorska zahtevnost (L, PSPACE)
5. Savitchev izrek, PSPACE polnost
6. coNP, polinomska hierarhija
   