Extrait
Angewandte Informatik VII
Seminararbeit
Eine Anwendung von Domino-
Spielen und ihre Komplexität
Uli Holtmann
Inhaltsverzeichnis
1
Einleitung
1
2
Komplexitätstheorie
1
2.1
Turingmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2.2
Komplexitätsklassen . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2.1
TIME, P und EXPTIME . . . . . . . . . . . . . . . . . .
3
2.2.2
NTIME und NP . . . . . . . . . . . . . . . . . . . . . . .
3
2.3
Reduktionen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.4
NP-Härte und NP-Vollständigkeit . . . . . . . . . . . . . . . . . .
5
2.5
SPACE und PSPACE . . . . . . . . . . . . . . . . . . . . . . . .
5
3
Domino-Spiele in der Komplexitätstheorie
5
3.1
Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.2
Domino-Spiele
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.2.1
Spielregeln . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.2.2
BOUNDED TILING . . . . . . . . . . . . . . . . . . . . .
8
3.3
Vom Berechnungsmodell hin zu den Domino-Spielen . . . . . . .
8
3.3.1
Zustandsdiagramme . . . . . . . . . . . . . . . . . . . . .
9
3.3.2
Reduktion von Turingmaschinen auf BOUNDED TILING
10
3.4
Zwei-Spieler Domino-Spiele . . . . . . . . . . . . . . . . . . . . .
12
3.4.1
Allgemeines über Zwei-Spieler Domino-Spiele . . . . . . .
13
3.4.2
ZWEI-SPIELER BOUNDED TILING . . . . . . . . . . .
13
3.4.3
ZWEI-SPIELER EXACT COVER . . . . . . . . . . . . .
14
3.4.4
Reduktion von ZWEI-SPIELER BOUNDED TILING auf
ZWEI-SPIELER EXACT COVER . . . . . . . . . . . . .
15
4
Schluss
18
1
Einleitung
In den Arbeiten ,,The convenience of tilings" [1] und ,,Domino-Tiling Games" [2]
werden sogenannte Domino-Spiele betrachtet. Domino-Spiele sind für die Kom-
plexitätstheorie interessant, da sie dank ihrer Einfachheit und Anschaulichkeit
Ansätze für diverse Reduktionen liefern. Auch lassen sich die verschiedenen
Domino-Spiel-Typen gerade deshalb leicht unterschiedlichen Komplexitätsklas-
sen zuordnen. Diese Arbeit soll die Ergebnisse der beiden genannten Veröffent-
lichungen erläutern und für eine eigene Anwendung aufgreifen.
Dazu folgt zunächst eine Einführung in die Komplexitätstheorie, welche
die Grundbegriffe erläutert, die für den weiteren Verlauf der Arbeit notwendig
sind. Im zweiten Teil der Arbeit werden Domino-Spiele sowie ihre Zwei-Spieler-
Varianten und ihr Zusammenhang mit Turingmaschinen, und damit auch mit
der Komplexitätstheorie, beschrieben. Zuletzt wird das zuvor gewonnene Wissen
auf eine erfundene Zwei-Spieler-Version des Problems EXACT COVER ange-
wendet, so dass seine Komplexität bestimmt werden kann.
2
Komplexitätstheorie
Die Komplexitätstheorie untersucht die algorithmische Schwierigkeit von Be-
rechnungsproblemen formalisiert als Sprachen. Sie fasst dazu Probleme ver-
gleichbarer Schwierigkeit in Komplexitätsklassen zusammen.
Im folgenden Kapitel sollen einige Grundbegriffe der Komplexitätstheorie
beschrieben werden, die für den weiteren Verlauf dieser Arbeit notwendig sind.
2.1
Turingmaschinen
Die Turingmaschine ist eines der wichtigsten mathematischen Rechnermodelle.
Sie modelliert die Arbeitsweise eines Computers und repräsentiert einen Algo-
rithmus bzw. ein Programm. Einzelne Berechnungen bestehen dabei aus schritt-
weisen Manipulationen von Symbolen, die nach bestimmten Regeln auf ein
Speicherband geschrieben und von dort eingelesen werden. Funktionen, die an-
hand einer Turingmaschine berechnet werden können, werden Turing-berechenbar
genannt. Es wird die Definition der Turingmaschine mit wenigen Anpassungen
aus [3] (Kapitel 1.4, S. 73ff.) und [4] (Kapitel 7.2, S. 148ff.) übernommen und
um eine Markierung für einen linken Rand des Eingabebandes erweitert.
Eine nichtdeterministische Turingmaschine M = (Q, , , , q
0
,
£, , F ) be-
steht aus einer endlichen Menge von Zuständen Q, einer endlichen Menge von
erlaubten Bandsymbolen mit dem linken Rand
£ , dem Blank-Symbol
und einer Menge von Eingabesymbolen \ {£, }, der Übergangsre-
lation
Q××Q××{L, R, 0}, dem Anfangszustand q
0
und einer Menge von
Endzuständen F
Q. Für eine deterministische Turingmaschine ist eine Über-
gangsfunktion : Q
× Q××{L, R, 0}, da hier, im Gegensatz zur nichtde-
terministischen Variante, für einen Zustand und ein eingelesenes Symbol jeweils
nur ein Übergang möglich ist. Weiterhin besitzt eine Turingmaschine ein in Fel-
1
der unterteiltes Eingabeband und einen Bandkopf. Das Eingabeband hat ein am
weitesten links stehendes Feld, gekennzeichnet durch das Symbol
£, ist aber un-
endlich zur rechten Seite. Jedes Feld des Eingabebandes kann genau ein Symbol
aus enthalten. Zu Beginn enthalten die n
0 auf £ folgenden, am weitesten
links stehenden Felder die Eingabe w = w
1
, . . . , w
n
,
i {1, . . . , n} : w
i
und die verbleibenden unendlich vielen Felder enthalten ein Blank. Mit jedem
Berechnungsschritt wird das Symbol an der Position des Bandkopfes eingelesen.
Abhängig davon schreibt die Turingmaschine ein neues Symbol auf dieses Feld,
bewegt den Bandkopf nach links (L), rechts (R) oder lässt ihn verweilen (0) und
ändert anschließend ihren Zustand.
Jede Bewegung des Bandkopfes ist ein Teil der Übergangsrelation und
wird als 5-Tupel (q, s, q , s , m) definiert, wobei die Turingmaschine im Zustand
q
Q das Symbol s einliest, dieses durch das Symbol s ersetzt und
in den Zustand q
Q übergeht [1] (Kapitel 2, S. 3). Die Bewegungsrichtung
gibt m
{L, R, 0} an. Im Fall s = £ wurde der linke Rand des Eingabebandes
erreicht, der nicht nach links überschritten werden darf. Folglich ist s =
£ und
die Bewegungsrichtung muss m = L sein.
Die Konfiguration einer Turingmaschine M wird
1
(q, a)
2
geschrieben und
gibt zu einem Zeitpunkt den aktuellen Zustand der Turingmaschine sowie den
Inhalt des Eingabebandes an. Dabei ist q
Q der gegenwärtige Zustand von M,
a
das Symbol an der Position des Bandkopfes,
1
die Zeichenkette, die
den Bandinhalt vom einschließlich linken Rand bis zum Symbol links des Kopfes
darstellt, und
2
die Zeichenkette, die den Bandinhalt vom Symbol rechts
des Kopfes bis zum am weitesten rechts stehenden und vom Blank verschiedenen
Symbol darstellt. Die Startkonfiguration ist
£(q
0
, w
1
)w
2
. . . w
n
für Startzustand
q
0
und Eingabe w = w
1
. . . w
n
,
i {1, . . . , n} : w
i
der Länge n.
Nun werden Übergänge zwischen Konfigurationen betrachtet. Man sagt, dass
Konfiguration
1
(q
1
, a)
2
der Turingmaschine M die Konfiguration
1
(q
2
, b)
2
in 1 Rechenschritt ergibt genau dann, wenn es eine entsprechende Regel in
gibt, die dies zu einem gültigen Übergang macht. Formal gesehen ist eine Konfi-
guration
1
(q
2
, b)
2
erreichbar von
1
(q
1
, a)
2
in 1 Rechenschritt genau dann,
wenn es eine Bewegung (q
1
, a, q
2
, a , m) in M gibt, so dass
·
1
=
1,1
. . .
1,i-1
, b =
1,i
und
2
= a
2,1
. . .
2,j
(m = L) oder
·
1
=
1,1
. . .
1,i-1
a , b =
2,1
und
2
=
2,2
. . .
2,j
(m = R) oder
·
1
=
1
, b = a und
2
=
2
(m = 0).
Das Symbol a wird dabei vom Bandkopf mit dem Symbol a überschrieben. Ein
solcher Übergang zwischen zwei Konfigurationen wird
1
(q
1
, a)
2
M
1
(q
2
, b)
2
geschrieben. Ist eine Konfiguration
1
(q
3
, c)
2
erreichbar von
1
(q
1
, a)
2
in k
Rechenschritten, so schreibt man
1
(q
1
, a)
2
k
M
1
(q
3
, c)
2
. Dann ist
M
der
transitive und reflexive Abschluss [5] (Kapitel 2.1, S. 22).
L(M ) bezeichnet die von der Turingmaschine M akzeptierten Sprache. Sie
ist die Menge der Wörter aus
, die M veranlassen in einen Endzustand über-
zugehen:
{w | £(q
0
, w
1
)w
2
. . . w
n
M
1
(p, a)
2
,
i {1, . . . , n} : w
i
, p
F,
1
,
2
}.
2
Im Laufe dieser Arbeit werden Turingmaschinen erneut aufgegriffen. Dabei
wird gezeigt, dass eine Turingmaschine durch das Domino-Spiel ausgedrückt
bzw. kodiert werden kann.
2.2
Komplexitätsklassen
In der Komplexitätstheorie werden Probleme bzw. ihre entscheidbaren Sprachen
in Komplexitätsklassen zusammengefasst, um ein gemeinsames Maß für Kom-
plexität zu erhalten. Die Definition der einzelnen Komplexitätsklassen werden
aus [3] (Kapitel 3.1, S. 144ff.) übernommen.
2.2.1
TIME, P und EXPTIME
Sei f :
N N eine Funktion. Die Klasse TIME(f(n)) besteht aus allen Sprachen
A, für die es eine deterministische Turingmaschine M gibt mit A = L(M ) und
time
M
(w)
f(n). Hierbei ist time
M
:
N eine Funktion, so dass time
M
(w)
die Anzahl der Rechenschritte von M bei Eingaben w bezeichnet. Oder anders
formuliert: Es gibt keine erreichbaren Konfigurationen in M , die in mehr als
time
M
(w) Rechenschritten von der Startkonfiguration
£(q
0
, w
1
)w
2
, . . . , w
n
aus
erreicht werden.
Das heißt, die Funktion f (n) ist eine obere Zeitschranke. Sie gibt die ma-
ximale Ausführungszeit eines Programms auf einer Turingmaschine M mit der
Eingabe w der Länge n an. Die tatsächliche Ausführungszeit time
M
(w) des
Programms auf dieser Turingmaschine ist also immer kleiner oder gleich die-
ser maximalen Anzahl von Rechenschritten. Man sagt auch: Turingmaschine M
entscheidet Sprache S in Zeit f . Dabei bedeutet M entscheidet S, dass für alle
Wörter w
gilt:
· w S M akzeptiert w und
· w S M lehnt w ab.
Alle Sprachen, für die diese Zeitschranke gilt, werden von der Klasse TIME(f (n))
zusammengefasst.
Für Probleme, die polynomiale oder sogar exponentielle Komplexität besit-
zen, werden zwei Komplexitätsklassen eingeführt. Ein Polynom ist eine Funktion
p :
N N der Form p(n) = a
k
n
k
+a
k-1
n
k-1
+. . .+a
1
n+a
0
, a
i
N, k N. Damit
wird die Komplexitätsklasse P wie folgt definiert: P=
p Polynom
TIME(p(n)).
Um zu zeigen, dass ein Algorithmus polynomiale Komplexität hat, genügt es zu
zeigen, dass seine Komplexität O(n
k
) für eine Konstante k ist [3] (Kapitel 3.1, S.
145). Analog lässt sich eine Komplexitätsklasse für Sprachen mit exponentiellem
Aufwand definieren: EXPTIME=
p Polynom
TIME(2
p(n)
).
2.2.2
NTIME und NP
Weiterhin gibt es Probleme, für deren Lösung alle möglichen Eingaben durch-
probiert werden müssen, bis eine gültige Lösung gefunden wird. Das bedeutet,
3
Fin de l'extrait de 21 pages
- Citation du texte
- Uli Holtmann (Auteur), 2013, Tiling-Games. Eine Anwendung von Dominospielen und ihre Komplexität, Munich, GRIN Verlag, https://www.grin.com/document/266205
Textes similaires
Devenir un auteur
✕
Extrait de
21
pages
Commentaires