1. komponenta

Vrsta nastave	Ukupno
Predavanja	45

* Opterećenje je izraženo u školskim satima (1 školski sat = 45 minuta)

CILJ KOLEGIJA: Upoznavanje s osnovnim klasama složenosti. Nizom primjera algoritama bit će pobliže opisane pojedine klase složenosti. Posebno će biti istaknuti neki otvoreni problemi u teoriji složenosti.

NASTAVNI SADRŽAJI:
1. Složenost. Problemi i algoritmi; vrijeme i prostor, nedeterminizam, klase složenosti, redukcije, potpunost.
2. Osnovne veze. LOGSPACE, P, NP, PSPACE, EXPTIME i NEXPTIME; Cook, Levinov teorem.
3. Primjeri problema. Sortiranje, 2CNF, 3CNF, SAT, HORNSAT, k-obojivost, CLIQUE, Hamiltonovi putevi u grafu, problem ruksaka, problem trgovačkog putnika, problem cjelobrojnog linearnog programiranja.
4. Savitchev teorem. PSPACE=NPSPACE; PSPACE-potpunost, QBF problem, Stockmeyerov teorem.
5. Vjerojatnosni algoritmi. Vjerojatnosni Turingov stroj; klasa BPP; primjeri problema.
6. Kriptografija. Privatni i javni ključevi; jednosmjerne (one way) funkcije.
7. Deskriptivna teorija složenosti. Logike s fiksnim točkama, izražajnost, Faginov teorem.

1. Introduction to the Theory of Computation, M. Sipser, PWS Publishing Company, 1996.
2. Finite model theory, H. D. Ebbinghaus, J. Flumm, Springer Verlag, 1999.
3. Computational Complexity, C. H. Papadimitriou, Addison-Wesley, 1994.

Upis predmeta :
Odslušan : Izračunljivost

Polaganje predmeta :
Položen : Izračunljivost

Obavezni predmet - Redovni Studij - Računarstvo i matematika