Tiling-Games. Eine Anwendung von Dominospielen und ihre Komplexität
Dec 2013 · GRIN Verlag
5.0star
1 reviewreport
Ebook
21
Pages
family_home
Eligible
info
reportRatings and reviews aren’t verified Learn More
About this ebook
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.
Ratings and reviews
5.0
1 review
Rate this ebook
Tell us what you think.
Reading information
Smartphones and tablets
Install the Google Play Books app for Android and iPad/iPhone. It syncs automatically with your account and allows you to read online or offline wherever you are.
Laptops and computers
You can listen to audiobooks purchased on Google Play using your computer's web browser.
eReaders and other devices
To read on e-ink devices like Kobo eReaders, you'll need to download a file and transfer it to your device. Follow the detailed Help Center instructions to transfer the files to supported eReaders.
