Naslov
Računalna složenost i izračunljivost teških problema
(Computational complexity and computability of hard problems)

Autori
Vidačković, Ines

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad, diplomski

Fakultet
Fakultet elektrotehnike i računarstva

Mjesto
Zagreb

Datum
15.06

Godina
2011

Stranica
71

Mentor
Bogunović, Nikola

Neposredni voditelj
Bogunović, Nikola

Ključne riječi
računalna složenost i izračunljivost; SAT problem; NP problemi
(computer complexity and computability; SAT problem; NP problems)

Sažetak
Teorija složenosti nastoji dati uvid u razinu inherentne algoritamske složenosti problema. Istraživanja složenosti i izračunljivosti imaju veliku praktičnu vrijednost jer omogućuju estimaciju računalnih resursa (vrijeme i memorijski prostor) potrebnih za rješavanje nekog problema. U radu su definirani osnovni pojmovi iz teorije složenosti, opisan je formalni računalni model kao alat za rješavanje te temeljem toga modela dana je klasifikacija razreda složenosti. Posebna pažnja posvećena je SAT problemu te pored tradicijskih pokazani su neki stohastički ili aproksimativni postupci rješavanja.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA