Atjaunināt sīkdatņu piekrišanu

E-grāmata: Games, Puzzles, and Computation

4.33/5 (18 ratings by Goodreads)
Citas grāmatas par šo tēmu:
  • Formāts - EPUB+DRM
  • Cena: 62,60 €*
  • * ši ir gala cena, t.i., netiek piemērotas nekādas papildus atlaides
  • Ielikt grozā
  • Pievienot vēlmju sarakstam
  • Šī e-grāmata paredzēta tikai personīgai lietošanai. E-grāmatas nav iespējams atgriezt un nauda par iegādātajām e-grāmatām netiek atmaksāta.
  • Bibliotēkām
Citas grāmatas par šo tēmu:

DRM restrictions

  • Kopēšana (kopēt/ievietot):

    nav atļauts

  • Drukāšana:

    nav atļauts

  • Lietošana:

    Digitālo tiesību pārvaldība (Digital Rights Management (DRM))
    Izdevējs ir piegādājis šo grāmatu šifrētā veidā, kas nozīmē, ka jums ir jāinstalē bezmaksas programmatūra, lai to atbloķētu un lasītu. Lai lasītu šo e-grāmatu, jums ir jāizveido Adobe ID. Vairāk informācijas šeit. E-grāmatu var lasīt un lejupielādēt līdz 6 ierīcēm (vienam lietotājam ar vienu un to pašu Adobe ID).

    Nepieciešamā programmatūra
    Lai lasītu šo e-grāmatu mobilajā ierīcē (tālrunī vai planšetdatorā), jums būs jāinstalē šī bezmaksas lietotne: PocketBook Reader (iOS / Android)

    Lai lejupielādētu un lasītu šo e-grāmatu datorā vai Mac datorā, jums ir nepieciešamid Adobe Digital Editions (šī ir bezmaksas lietotne, kas īpaši izstrādāta e-grāmatām. Tā nav tas pats, kas Adobe Reader, kas, iespējams, jau ir jūsu datorā.)

    Jūs nevarat lasīt šo e-grāmatu, izmantojot Amazon Kindle.

The authors show that there are underlying mathematical reasons for why games and puzzles are challenging (and perhaps why they are so much fun). They also show that games and puzzles can serve as powerful models of computation—quite different from the usual models of automata and circuits—offering a new way of thinking about computation. The appendices provide a substantial survey of all known results in the field of game complexity, serving as a reference guide for readers interested in the computational complexity of particular games, or interested in open problems about such complexities.

Recenzijas

" the games also provide an extremely well-suited platform for the introduction of a unified method for determining complexity using constraint logic considers not only mathematically oriented games, but also games that may well be suitable for non-mathematicians The book also contains a comprehensive overview of known results on the complexity of games and therefore with its 177 references is also an excellent reference book on the topic warmly recommended for anyone who likes games and wants to know more about their (mathematical) complexity." Internaionale Mathematische Nachrichten, December 2012

"Games, Puzzles, and Computation will serve well in roles similar to that of Garey and Johnsons book. In particular, the text would work exceedingly well as a reference for whats known in the subfield of game/puzzle complexity or for self-study by someone familiar with basic computational complexity principles who is interested in learning more about the complexity of games and puzzles. It would also serve well as supplementary material to an upper-level undergraduate or entry-level graduate special topics course in game/puzzle complexity. It could also be used as the primary text for such a course (in principle) given extra preparation by the instructor ." Daniel Apon, SIGACT News, September 2011

"The authors show that there are underlying mathematical reasons that games and puzzles are challenging (which perhaps explains why they are so much fun). Complementarily, they also show that games and puzzles can serve as powerful models of computation quite different from the usual models of automata and circuits offering a new way of thinking about computation." L'Enseignement Mathematique, December 2009

" intriguing book Hearn and Demaine present an elegant family of benchmarks they have developed, allowing them to settle open questions on the complexity of various games. and the authors certainly provide plenty to mull over. The publisher A K Peters has done a quite nice job of production, as well. All in all, this is a book well worth looking into." Leon Harkleroad, MAA Reviews, December 2009

"This book will be of interest to advanced readers working in this area." Brian Borchers, CHOICE, February 2010 " the games also provide an extremely well-suited platform for the introduction of a unified method for determining complexity using constraint logic considers not only mathematically oriented games, but also games that may well be suitable for non-mathematicians The book also contains a comprehensive overview of known results on the complexity of games and therefore with its 177 references is also an excellent reference book on the topic warmly recommended for anyone who likes games and wants to know more about their (mathematical) complexity." Internaionale Mathematische Nachrichten, December 2012

"Games, Puzzles, and Computation will serve well in roles similar to that of Garey and Johnsons book. In particular, the text would work exceedingly well as a reference for whats known in the subfield of game/puzzle complexity or for self-study by someone familiar with basic computational complexity principles who is interested in learning more about the complexity of games and puzzles. It would also serve well as supplementary material to an upper-level undergraduate or entry-level graduate special topics course in game/puzzle complexity. It could also be used as the primary text for such a course (in principle) given extra preparation by the instructor ." Daniel Apon, SIGACT News, September 2011

"The authors show that there are underlying mathematical reasons that games and puzzles are challenging (which perhaps explains why they are so much fun). Complementarily, they also show that games and puzzles can serve as powerful models of computation quite different from the usual models of automata and circuits offering a new way of thinking about computation." L'Enseignement Mathematique, December 2009

" intriguing book Hearn and Demaine present an elegant family of benchmarks they have developed, allowing them to settle open questions on the complexity of various games. and the authors certainly provide plenty to mull over. The publisher A K Peters has done a quite nice job of production, as well. All in all, this is a book well worth looking into." Leon Harkleroad, MAA Reviews, December 2009

"This book will be of interest to advanced readers working in this area." Brian Borchers, CHOICE, February 2010

Introduction
1(12)
What is a Game?
3(3)
Computational Complexity Classes
6(3)
Constraint Logic
9(2)
What's Next?
11(2)
I Games in General
13(92)
The Constraint-Logic Formalism
15(10)
Constraint Graphs
16(3)
Planar Constraint Graphs
19(1)
Constraint-Graph Conversion Techniques
20(5)
Constraint-Logic Games
25(14)
Zero-Player Games (Simulations)
26(3)
One-Player Games (Puzzles)
29(2)
Two-Player Games
31(3)
Team Games
34(5)
Zero-Player Games (Simulations)
39(16)
Bounded Games
40(3)
Unbounded Games
43(12)
One-Player Games (Puzzles)
55(16)
Bounded Games
56(5)
Unbounded Games
61(10)
Two-Player Games
71(14)
Bounded Games
72(4)
Unbounded Games
76(5)
No-Repeat Games
81(4)
Team Games
85(16)
Bounded Games
86(3)
Unbounded Games
89(12)
Perspectives on Part I
101(4)
Hierarchies of Complete Problems
101(1)
Games, Physics, and Computation
102(3)
II Games in Particular
105(56)
One-Player Games (Puzzles)
107(34)
TipOver
107(5)
Hitori
112(3)
Sliding-Block Puzzles
115(5)
The Warehouseman's Problem
120(1)
Sliding-Coin Puzzles
120(2)
Plank Puzzles
122(4)
Sokoban
126(3)
Push-2-F
129(4)
Rush Hour
133(3)
Triangular Rush Hour
136(1)
Hinged Polygon Dissections
137(4)
Two-Player Games
141(14)
Amazons
141(5)
Konane
146(3)
Cross Purposes
149(6)
Perspectives on Part II
155(2)
Conclusions
157(4)
Contributions
157(1)
Future Work
158(3)
Appendices
161(56)
A Survey of Games and Their Complexities
163(30)
A.1 Cellular Automata
164(1)
A.2 Games of Block Manipulation
165(5)
A.3 Games of Tokens on Graphs
170(4)
A.4 Peg-Jumping Games
174(1)
A.5 Connection Games
174(1)
A.6 Other Board Games
175(1)
A.7 Pencil Puzzles
175(5)
A.8 Formula Games
180(2)
A.9 Other Games
182(4)
A.10 Constraint Logic
186(1)
A.11 Open Problems
186(7)
B Computational-Complexity Reference
193(10)
B.1 Basic Definitions
193(3)
B.2 Generalizations of Turing Machines
196(3)
B.3 Relationship of Complexity Classes
199(1)
B.4 List of Complexity Classes Used in this Book
199(1)
B.5 Formula Games
200(3)
C Deterministic Constraint Logic Activation Sequences
203(12)
D Constraint-Logic Quick Reference
215(2)
Bibliography 217(13)
Index 230
Robert A. Hearn, Dartmouth College, Hanover, New Hampshire, USA

Erik Demaine, Massachusetts Institute of Technology, Cambridge, USA