prikaz prve stranice dokumenta Teško rješivi problemi odluke
Access restricted to students and staff of home institution
master's thesis
Teško rješivi problemi odluke
Split: University of Split, University of Split, Faculty of science, 2018. urn:nbn:hr:166:530549
Rajčić, Branka
University of Split
Faculty of Science
Department of Mathematics

Institutional repository: Repository of Faculty of Science

Cite this document

Rajčić, B. (2018). Teško rješivi problemi odluke (Master's thesis). Split: University of Split, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić, Branka. "Teško rješivi problemi odluke." Master's thesis, University of Split, Faculty of Science, 2018. https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić, Branka. "Teško rješivi problemi odluke." Master's thesis, University of Split, Faculty of Science, 2018. https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić, B. (2018). 'Teško rješivi problemi odluke', Master's thesis, University of Split, Faculty of Science, accessed 30 June 2024, https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić B. Teško rješivi problemi odluke [Master's thesis]. Split: University of Split, Faculty of Science; 2018 [cited 2024 June 30] Available at: https://urn.nsk.hr/urn:nbn:hr:166:530549

B. Rajčić, "Teško rješivi problemi odluke", Master's thesis, University of Split, Faculty of Science, Split, 2018. Available at: https://urn.nsk.hr/urn:nbn:hr:166:530549

Metadata
TitleTeško rješivi problemi odluke
Title (english)Intractable problems
AuthorBranka Rajčić
MentorMilica Klaričić Bakula (mentor)
Committee memberMilica Klaričić Bakula (predsjednik povjerenstva)
Committee memberJurica Perić (član povjerenstva)
Committee memberAljoša Šubašić (član povjerenstva)
GranterUniversity of Split
Faculty of Science
(Department of Mathematics)
Split
Defense date and country2018-11-06, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
Abstract
U ovom diplomskom radu proučavamo teško rješive probleme odluke. Bavimo se dvjema klasama problema, a to su problemi koji su odlučivi nekim polinomno složenim determinističkim Turingovim strojem (klasa P) i problemi za koje nije poznat deterministički polinomni algoritam (klasa NP). Također bavimo se i NP-potpunim problemima odluke. Uveden je problem ispunjivosti formule logike sudova te je dokazana NP-potpunost tog problema odluke na način da smo jezik bilo kojeg nedeterminističkog Turingovog stroja polinomne vremenske složenosti reducirali na problem ispunjivosti. Budući da se formula logike sudova može zapisati u k-konjunktivnoj normalnoj formi (k ∈N), nameću nam se dva problema odluke CSAT i 3SAT. NP-potpunost navedenih problema odluke potvrdili smo redukcijom instanici SAT problema na instance navedenih problema. Nadalje, razmatrali smo NP-potpunost nekih dodatnih problema odluke (IS, Problem klike, NC, DHC, HC i TSP) i zaključili da se i ti problemi polinomnom redukcijom s nekog drugog NP-potpunog problema potvrđuju kao NP-potpuni problemi odluke.
Abstract (english)
This thesis studies the intractable problems. It deals with two classes of problems solvable in polynomial time by a deterministic Turing machine (class P) and those in which the deterministic polynomial algorithm is not known (class NP). Furthermore, it deals with NP-complete problems. The satisfiability problem has been introduced and its NP-completeness has been proved in a way that the language of any nondeterministic Turing machine solvable in polynomial time has been reduced to a satisfiability problem. Since the Boolean expression can be written in the conjuctive normal form (k ∈ N), two problems emerge CSAT and 3SAT. NP-completeness of the above stated problems has been confirmed by reduction of the SAT problem instances to the instances of the forementioned problems. Furthermore, NP-completeness of some additional intractable problems has been looked into (IS, Clique, NC, DHC, HC i TSP) and the conclusion has been drawn that those problems can be confirmed as NP-complete problems by polynomial reduction from another NP-complete problem.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:166:530549
Study programmeTitle: Mathematics; specializations in: major in pure mathematics, major in computing, major in teaching
Course: major in computing
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsAccess restricted to students and staff of home institution
Terms of useLicence In copyright icon
Created on2019-02-01 16:30:07