Anketa

Na ovoj stranici trenutno nije odabrana niti jedna anketa!

Repozitorij

Repozitorij je prazan

Složenost algoritama

Šifra: 92958
ECTS: 5.0
Nositelji: prof. dr. sc. Mladen Vuković - Predavanja
Engleski jezik:

1,0,0

Nastava se odvija na hrvatskom jeziku u svim svojim elementima, a stranim studentima koji su pridruženi mješovitoj grupi nudi se mogućnost savladavanja predmeta pomoću dodatnih izravnih konzultacija s nastavnikom i asistentima na engleskom jeziku. Pri tome, nastavnik stranog studenta upućuje na odgovarajuću literaturu na engleskom jeziku te mu osigurava mogućnost polaganja predmeta na engleskom jeziku.
Opterećenje:

1. komponenta

Vrsta nastaveUkupno
Predavanja 45
* Opterećenje je izraženo u školskim satima (1 školski sat = 45 minuta)
Opis predmeta:
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.
Literatura:
  1. M. Sipser: Introduction to the Theory of Computation
  2. H. D. Ebbinghaus, J. Flumm: Finite model theory
  3. C. H. Papadimitriou: Computational Complexity
Preduvjeti za:
Upis predmeta :
Položen : Izračunljivost
Položen : Oblikovanje i analiza algoritama
4. semestar
Obavezni predmet - Redovni Studij - Računarstvo i matematika
Termini konzultacija:

SADRŽAJ

Link na stranicu kolegija: 


Obavijesti