In den Arbeiten „The convenience of tilings“ und „Domino-Tiling Games“ werden sogenannte Domino-Spiele betrachtet. Domino-Spiele sind für die Komplexitä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ätsklassen zuordnen. Diese Arbeit soll die Ergebnisse der beiden genannten Veröffentlichungen 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 angewendet, so dass seine Komplexität bestimmt werden kann.
Inhaltsverzeichnis
- Einleitung
- Komplexitätstheorie
- Turingmaschinen
- Komplexitätsklassen
- TIME, P und EXPTIME
- NTIMEund NP
- Reduktionen
- NP-Härte und NP-Vollständigkeit
- SPACE und PSPACE
- Domino-Spiele in der Komplexitätstheorie
- Einführung
- Domino-Spiele
- Spielregeln
- BOUNDED TILING
- Vom Berechnungsmodell hin zu den Domino-Spielen
- Zustandsdiagramme
- Reduktion von Turingmaschinen auf BOUNDED TILING
- Zwei-Spieler Domino-Spiele
- Allgemeines über Zwei-Spieler Domino-Spiele
- ZWEI-SPIELER BOUNDED TILING
- ZWEI-SPIELER EXACT COVER
- Reduktion von ZWEI-SPIELER BOUNDED TILING auf ZWEI-SPIELER EXACT COVER
- Schluss
- Literatur
Zielsetzung und Themenschwerpunkte
Die Seminararbeit befasst sich mit der Anwendung von Domino-Spielen in der Komplexitätstheorie. Ziel ist es, die Ergebnisse der Arbeiten „The convenience of tiling" und „Domino-Tiling Games" zu erläutern und für eine eigene Anwendung aufzugreifen. Dabei werden die grundlegenden Begriffe der Komplexitätstheorie, insbesondere Turingmaschinen und Komplexitätsklassen, sowie die Spielregeln und Reduktionen von Domino-Spielen vorgestellt. Die Arbeit soll demonstrieren, wie sich durch die Anschaulichkeit von Domino-Spielen die Komplexität von Problemen, wie beispielsweise das Problem EXACT COVER, bestimmen lässt.
- Komplexitätstheorie und ihre Grundbegriffe
- Domino-Spiele und ihre Spielregeln
- Reduktionen von Turingmaschinen auf Domino-Spiele
- Zwei-Spieler Domino-Spiele und ihre Komplexität
- Anwendung von Domino-Spielen zur Bestimmung der Komplexität von Problemen
Zusammenfassung der Kapitel
Die Einleitung führt in die Thematik der Seminararbeit ein und stellt die Zielsetzung sowie den Aufbau der Arbeit dar. Kapitel 2 behandelt die Komplexitätstheorie und erläutert die grundlegenden Begriffe, die für das Verständnis der weiteren Kapitel notwendig sind. Dazu gehören Turingmaschinen, Komplexitätsklassen wie TIME, P, EXPTIME, NTIME und NP, Reduktionen und die Konzepte der NP-Härte und NP-Vollständigkeit sowie die Klasse SPACE und PSPACE.
Kapitel 3 widmet sich den Domino-Spielen und ihrem Zusammenhang mit der Komplexitätstheorie. Zunächst werden die Spielregeln und verschiedene Domino-Spiel-Typen wie BOUNDED TILING vorgestellt. Im Anschluss wird gezeigt, wie sich Turingmaschinen mit Hilfe von Domino-Spielen darstellen lassen. Dazu werden Zustandsdiagramme eingeführt und eine Reduktion von Turingmaschinen auf BOUNDED TILING erläutert. Der letzte Teil des Kapitels befasst sich mit Zwei-Spieler Domino-Spielen, wobei die Spielregeln für ZWEI-SPIELER BOUNDED TILING und ZWEI-SPIELER EXACT COVER beschrieben werden. Abschließend wird eine Reduktion von ZWEI-SPIELER BOUNDED TILING auf ZWEI-SPIELER EXACT COVER vorgestellt.
Schlüsselwörter
Die Schlüsselwörter und Schwerpunktthemen des Textes umfassen die Komplexitätstheorie, Turingmaschinen, Komplexitätsklassen, Domino-Spiele, BOUNDED TILING, ZWEI-SPIELER BOUNDED TILING, ZWEI-SPIELER EXACT COVER, Reduktionen und die NP-Vollständigkeit. Die Arbeit zeigt, wie Domino-Spiele als anschauliches Werkzeug für die Reduktion von Problemen und die Bestimmung ihrer Komplexität eingesetzt werden können.
- Arbeit zitieren
- Uli Holtmann (Autor:in), 2013, Tiling-Games. Eine Anwendung von Dominospielen und ihre Komplexität, München, GRIN Verlag, https://www.grin.com/document/266205
