1. komponenta

Vrsta nastave	Ukupno
Predavanja	45

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

CILJ KOLEGIJA: Studente osposobiti za:
- Razumijevanje poteškoća koje nastaju zbog vremenske i prostorne složenosti nekog problema
- Upotrebu redukcija (svođenja) za dokazivanje složenosti konkretnog problema

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. Polinomna hijerarhija i sklopovi. PH i sklopovi kao modeli računanja. Karp-Liptonov teorem.
6. Probabilističke klase složenosti. Vjerojatnosni Turingovi strojevi. Klasa BPP. Redukcija greške. Adlemanov teorem.

1. Introduction to the Theory of Computation, 3rd ed., M. Sipser, Cengage Learning, 2013.
2. Computational Complexity: A Modern Approach, S. Arora, B. Barak, Cambridge University Press, 2009.
3. Computational Complexity, C.H. Papadimitrou, Addison Wesley Long., 1994.

Upis predmeta :
Položen : Matematička logika

Ostali izborni predmeti - Redovni Studij - Računarstvo i matematika
Vezani kolegiji A - Redovni Studij - Računarstvo i matematika

Ostali izborni predmeti - Redovni Studij - Računarstvo i matematika
Vezani kolegiji A - Redovni Studij - Računarstvo i matematika

Izborni modul B - Teorijsko računarstvo, 2. godina - Redovni Studij - Računarstvo i matematika
Ostali izborni predmeti - Redovni Studij - Računarstvo i matematika
Vezani kolegiji A - Redovni Studij - Računarstvo i matematika

Izborni modul B - Teorijsko računarstvo, 2. godina - Redovni Studij - Računarstvo i matematika
Ostali izborni predmeti - Redovni Studij - Računarstvo i matematika
Vezani kolegiji A - Redovni Studij - Računarstvo i matematika