Teorija složenosti

Osnovni podaci
Detaljne informacije
Nastava
Termini konzultacija

Šifra:	296813
ECTS:	5.0
Nositelji:	doc. dr. sc. Vedran Čačić
Izvođači:	Predavanja: doc. dr. sc. Vedran Čačić
Prijava ispita:	Studomat

Opterećenje:

1. komponenta

Vrsta nastave Ukupno

Predavanja 45

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

Opis predmeta:

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.

Literatura:

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

Preduvjeti za:

Upis predmeta :
Položen : Matematička logika

1. semestar

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

2. semestar Ne predaje se

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

3. semestar

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

4. semestar Ne predaje se

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

Termini konzultacija:

doc. dr. sc. Vedran Čačić:
Utorkom od 11 do 13 sati. Poželjna najava mailom.
Lokacija: A306

Obavijesti - Arhiva

Povratak

Rezultati 0 - 0 od 0
Stranica 1 od 0

Nema vijesti!

Teorija složenosti

Repozitorij

Anketa

Teorija složenosti

1. komponenta

Obavijesti - Arhiva