| Tiling-Games. Eine Anwendung von Dominospielen und ihre Komplexität Contributor(s): Holtmann, Uli (Author) |
|
 |
ISBN: 3656563284 ISBN-13: 9783656563280 Publisher: Grin Verlag OUR PRICE: $36.01 Product Type: Paperback Language: German Published: December 2013 |
| Additional Information |
| BISAC Categories: - Computers | Enterprise Applications - General - Computers | Software Development & Engineering - General - Computers | Programming - General |
| Physical Information: 0.07" H x 5.83" W x 8.27" (0.11 lbs) 28 pages |
| Descriptions, Reviews, Etc. |
| Publisher Description: Studienarbeit aus dem Jahr 2013 im Fachbereich Informatik - Software, Note: 1,3, Universit t Bayreuth, Veranstaltung: Seminar Theoretische Informatik, Sprache: Deutsch, Abstract: 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. |
