prikaz prve stranice dokumenta NP-potpuni problemi
  Download
PDF 14.3 MB
master's thesis
NP-potpuni problemi
Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2021. urn:nbn:hr:126:909823
Petrović, Josip
Josip Juraj Strossmayer University of Osijek
Department of Mathematics

Institutional repository: Repository of School of Applied Mathematics and Informatics

Cite this document

Petrović, J. (2021). NP-potpuni problemi (Master's thesis). Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics. Retrieved from https://urn.nsk.hr/urn:nbn:hr:126:909823

Petrović, Josip. "NP-potpuni problemi." Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2021. https://urn.nsk.hr/urn:nbn:hr:126:909823

Petrović, Josip. "NP-potpuni problemi." Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, 2021. https://urn.nsk.hr/urn:nbn:hr:126:909823

Petrović, J. (2021). 'NP-potpuni problemi', Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, accessed 21 December 2024, https://urn.nsk.hr/urn:nbn:hr:126:909823

Petrović J. NP-potpuni problemi [Master's thesis]. Osijek: Josip Juraj Strossmayer University of Osijek, Department of Mathematics; 2021 [cited 2024 December 21] Available at: https://urn.nsk.hr/urn:nbn:hr:126:909823

J. Petrović, "NP-potpuni problemi", Master's thesis, Josip Juraj Strossmayer University of Osijek, Department of Mathematics, Osijek, 2021. Available at: https://urn.nsk.hr/urn:nbn:hr:126:909823

Metadata
TitleNP-potpuni problemi
Title (english)NP-Complete Problems
AuthorJosip Petrović
MentorZoran Tomljanović (mentor)
Committee memberDomagoj Ševerdija (predsjednik povjerenstva)
Committee memberZoran Tomljanović (član povjerenstva)
Committee memberIvana Kuzmanović Ivičić (član povjerenstva)
GranterJosip Juraj Strossmayer University of Osijek
Department of Mathematics
Osijek
Defense date and country2021-09-30, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Mathematical Logic and Accounting
Abstract
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.
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:126:909823
Study programmeTitle: Mathematics; specializations in: Financial and Statistical Mathematics, Mathematics and Computer Science, Industrial and Applied Mathematics
Course: Financial and Statistical Mathematics
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsOpen access
Terms of useLicence In copyright icon
Created on2021-10-25 06:02:12