prikaz prve stranice dokumenta Teško rješivi problemi odluke
Pristup korisnicima matične ustanove
diplomski rad
Teško rješivi problemi odluke
2018. urn:nbn:hr:166:530549
Rajčić, Branka
Sveučilište u Splitu
Prirodoslovno-matematički fakultet
Odjel za matematiku

Citirajte ovaj rad

Rajčić, B. (2018). Teško rješivi problemi odluke (Diplomski rad). Split: Sveučilište u Splitu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić, Branka. "Teško rješivi problemi odluke." Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, 2018. https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić, Branka. "Teško rješivi problemi odluke." Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, 2018. https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić, B. (2018). 'Teško rješivi problemi odluke', Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, citirano: 19.11.2024., https://urn.nsk.hr/urn:nbn:hr:166:530549

Rajčić B. Teško rješivi problemi odluke [Diplomski rad]. Split: Sveučilište u Splitu, Prirodoslovno-matematički fakultet; 2018 [pristupljeno 19.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:166:530549

B. Rajčić, "Teško rješivi problemi odluke", Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, Split, 2018. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:166:530549

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:166:530549
Prijavite se u repozitorij kako biste mogli spremiti objekt u svoju listu.
Podaci o radu
NaslovTeško rješivi problemi odluke
Naslov (engleski)Intractable problems
AutorBranka Rajčić
MentorMilica Klaričić Bakula (mentor)
Član povjerenstvaMilica Klaričić Bakula (predsjednik povjerenstva)
Član povjerenstvaJurica Perić (član povjerenstva)
Član povjerenstvaAljoša Šubašić (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Splitu
Prirodoslovno-matematički fakultet
(Odjel za matematiku)
Split
Datum i država obrane2018-11-06, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
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.
Sažetak (engleski)
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.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:166:530549
Studijski programNaziv: Matematika; smjerovi: teorijski, računarski, nastavnički
Smjer: računarski
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 pristupaPristup korisnicima matične ustanove
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2019-02-01 16:30:07