diplomsko delo
Povzetek
Najtežje probleme v NP imenujemo NP-polni problemi, za njih pa trenutno velja, da jih ne znamo rešiti v polinomskem času. NP-polne odločitvene probleme najdemo na različnih področjih, od teorije grafov, do izjavne logike, nadalje pa velja, da ob odkritju rešitve enega od problemov znamo rešiti tudi vse druge NP-polne probleme. V diplomskem delu se bomo osredotočili predvsem na NP-polne probleme, povezane z reševanjem miselnih iger in ugank. Naredili bomo pregled nekaterih znanih miselnih iger in pokazali njihovo NP-polnost. Dokaz NP-polnosti izbranih problemov bo temeljil na dejstvu, da med NP-polnimi problemi obstajajo prevedbe. Za vsako miselno igro bomo torej najprej opisali igri pripadajoči odločitveni problem, nato pa reševanje nekega že znanega NP-polnega odločitvenega problema prevedli na reševanje igri pripadajočega odločitvenega problema.
Ključne besede
odločitveni problem;uganka;računska zahtevnost;NP-polnost;prevedba;računalništvo;računalništvo in informatika;računalništvo in matematika;univerzitetni študij;diplomske naloge;interdisciplinarni študij;
Podatki
Jezik: |
Slovenski jezik |
Leto izida: |
2016 |
Tipologija: |
2.11 - Diplomsko delo |
Organizacija: |
UL FRI - Fakulteta za računalništvo in informatiko |
Založnik: |
[S. Pahor] |
UDK: |
004:510.58(043.2) |
COBISS: |
1536772803
|
Št. ogledov: |
893 |
Št. prenosov: |
165 |
Ocena: |
0 (0 glasov) |
Metapodatki: |
|
Ostali podatki
Sekundarni jezik: |
Angleški jezik |
Sekundarni naslov: |
NP-completeness of mind games and puzzles |
Sekundarni povzetek: |
The hardest problems in NP are called NP-complete problems; these are problems that we currently do not know how to solve quickly. There is a variety of NP-complete decision problems in different fields, ranging from graph theory to logic and also note that upon finding a solution to one NP-complete problem, we are able to solve any problem that belongs to the NP-complete class of problems. The thesis will focus on NP-complete problems related to solving puzzles and brain-teasers. We will present a summary of a few well known puzzles and show that they are indeed NP-complete. The proof for their NP-completeness will stem from the existence of transformations (or reductions) between them. For each puzzle we will first present the respective decision problem and then transform the solving of an already proven NP-complete decision problem to solving the decision problem pertaining to each puzzle. |
Sekundarne ključne besede: |
decision problem;puzzle;computational complexity;NP-completeness;reduction;computer science;computer and information science;computer science and mathematics;diploma;interdisciplinary studies; |
Vrsta datoteke: |
application/pdf |
Vrsta dela (COBISS): |
Diplomsko delo/naloga |
Študijski program: |
1000407 |
Konec prepovedi (OpenAIRE): |
1970-01-01 |
Komentar na gradivo: |
Univ. v Ljubljani, Fak. za računalništvo in informatiko |
Strani: |
52 str. |
ID: |
9123189 |