prikaz prve stranice dokumenta NP-potpuni problemi
  Preuzmi
PDF 14.3 MB
diplomski rad
NP-potpuni problemi
Osijek: Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, 2021. urn:nbn:hr:126:909823
Petrović, Josip
Sveučilište Josipa Jurja Strossmayera u Osijeku
Odjel za matematiku

Institucijski repozitorij: Repozitorij Fakulteta primijenjene matematike i informatike

Citirajte ovaj rad

Petrović, J. (2021). NP-potpuni problemi (Diplomski rad). Osijek: Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:126:909823

Petrović, Josip. "NP-potpuni problemi." Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, 2021. https://urn.nsk.hr/urn:nbn:hr:126:909823

Petrović, Josip. "NP-potpuni problemi." Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, 2021. https://urn.nsk.hr/urn:nbn:hr:126:909823

Petrović, J. (2021). 'NP-potpuni problemi', Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, citirano: 19.06.2024., https://urn.nsk.hr/urn:nbn:hr:126:909823

Petrović J. NP-potpuni problemi [Diplomski rad]. Osijek: Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku; 2021 [pristupljeno 19.06.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:126:909823

J. Petrović, "NP-potpuni problemi", Diplomski rad, Sveučilište Josipa Jurja Strossmayera u Osijeku, Odjel za matematiku, Osijek, 2021. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:126:909823

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:126:909823
Podaci o radu
NaslovNP-potpuni problemi
Naslov (engleski)NP-Complete Problems
AutorJosip Petrović
MentorZoran Tomljanović (mentor)
Član povjerenstvaDomagoj Ševerdija (predsjednik povjerenstva)
Član povjerenstvaZoran Tomljanović (član povjerenstva)
Član povjerenstvaIvana Kuzmanović Ivičić (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište Josipa Jurja Strossmayera u Osijeku
Odjel za matematiku
Osijek
Datum i država obrane2021-09-30, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Matematička logika i računarstvo
Sažetak
Ovaj rad se bavi teorijom računarstva. Najprije se upoznajemo s jednostavnijim modelima računanja: konačnim i potisnim automatom. Nakon toga definiramo Turingov stroj koji predstavlja opći model računanja kao i njegovu nedeterminističku verziju. Zatim definiramo vremensku složenost i upoznajemo se sa klasama P i NP te uz pomoć njih i vremenski polinomijalne redukcije definiramo NP-potpunost. Centralni dio ovog rada se odnosi na dokaz da je problem ispunjivosti (SAT) NP-potpun, a na kraju ćemo još spomenuti neke zanimljive probleme koji su također NP-potpuni.
Sažetak (engleski)
This paper deals with the theory of computation. Firstly, we introduce simpler computational models: finite and pushdown automata. Then we define a Turing machine which represents a general model of computation as well as its nondeterministic counterpart. After that we define time complexity and introduce classes P and NP. Using these classes together with polynomial time reducibility we define the NP-completeness. The central point of this paper is to prove that the satisfiability problem (SAT) is NP-complete. Lastly, we will mention a few more interesting problems that belong to the NP-complete class as well.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:126:909823
Studijski programNaziv: Matematika; smjerovi: Financijska matematika i statistika, Matematika i računarstvo, Industrijska i primijenjena matematika
Smjer: Financijska matematika i statistika
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra matematike (mag.math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaOtvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2021-10-25 06:02:12