¡Oferta!

Message Passing Cellular Automata

24,06 

Otras opciones
Accede gratis al libro
24,06 

En Stock

  • ISBN: 9788426729972
  • Tipo de Encuadernación: Rústica
  • Dimensiones de producto: 17x1x24
  • Número de páginas: 176

Libro físico

  • Envíos a todo el mundo
  • Suscriptores obtienen descuentos en la compra de libros físicos, envíos gratuitos en España Peninsular y Baleares y acceso a todo el catálogo digital de Marcombo.
    ¿No estás suscrito? ¡Suscríbete!

Suscripción

  • Prueba gratis por 7 días. Planes desde 7,99 €/ mes
  • Accede a todo el catálogo de Marcombo
  • Lectura online y offline
  • Acceso a contenidos previos a su publicación
  • Envíos gratuitos y descuentos especiales para compras en la tienda

Suscribirse
Suscribirse
¿Quieres un descuento? ¡Hazte en miembro!

Más información

Descripción

Índice

Detalles

Colecciones

Categorías

Características

  • Autor: Severino Fernández Galán
  • Fecha de publicación: 28/06/2020

Descripción

Cellular automata have been used in computer science since the 1940s. A cellular automaton consists of many identical

simple processing units that interact with each other in a local way and in discrete time. Cellular automata have been applied to a wide variety of tasks and, due to the growing interest of the scientific community, a good number of relevant journals and conferences are dedicated to their study and development. One of the main characteristics of cellular automata is their simplicity, which makes them relatively easy to program. Nonetheless, despite their simplicity, cellular automata are able to generate complex results in many domains, even in the context of artificial life. Another remarkable characteristic of cellular automata is that they are suitable for parallel implementation.

The present book deals with the fundamentals of cellular automata. Additionally, a new approach to extending cellular

automata with the use of message passing is introduced. Each of the seven chapters of this book includes a number of

figures, bibliographic references, and exercises of interest to the reader. The book offers students, practitioners and

researchers a concise but broad coverage of the main aspects of cellular automata.

The author of the book is an associate professor in the Department of Artificial Intelligence at UNED (Spanish Open

University). Since the middle 1990s, he has performed teaching and research activities within the field of artificial

intelligence, mainly in the areas of Bayesian networks and evolutionary computation. This book is the result of a long journey that started when the author became interested in NetLogo. NetLogo is an agent]based programming environment well suited for modeling and inspecting complex systems developing over time.

Información adicional

Peso 0,35 kg
Dimensiones 24 × 17 × 1 cm

Índice

Preface ix
1 Introduction to Cellular Automata 1
1.1 History of Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Components of a Cellular Automaton . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Lattice of Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2 States of Cells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Transition Function . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.4 Updating Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Second-Order Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . 7
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 One-Dimensional Classical Cellular Automata 9
2.1 Elementary Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Ternary One-Dimensional Cellular Automata . . . . . . . . . . . . . . . . 14
2.3 Continuous One-Dimensional Cellular Automata . . . . . . . . . . . . . . 18
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3 One-Dimensional Message Passing Cellular Automata 23
3.1 General Denition of Message Passing Cellular Automaton . . . . . . . . 23
3.2 Message Passing in One Dimension . . . . . . . . . . . . . . . . . . . . . . 24
3.3 Elementary Message Passing Cellular Automata . . . . . . . . . . . . . . . 26
3.4 Ternary One-Dimensional Message Passing Cellular Automata . . . . . . 35
3.5 Continuous One-Dimensional Message Passing Cellular Automata . . . . . 39
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4 Two-Dimensional Classical Cellular Automata 45
4.1 Basic Two-Dimensional Cellular Automata . . . . . . . . . . . . . . . . . . 45
4.2 Majority Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Parity Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.4 Game of Life . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5 Two-Dimensional Message Passing Cellular Automata 59
5.1 Message Passing in Two Dimensions . . . . . . . . . . . . . . . . . . . . . 59
5.2 Message Passing Cellular Automata with Fixed Messages . . . . . . . . . 62
5.3 Message Passing Cellular Automata with Sender-Dependent Messages . . 64
5.4 Message Passing Cellular Automata with Receiver-Dependent Messages . 64
5.5 Message Passing Cellular Automata with Link-Dependent Messages . . . 69
5.6 Message Passing Cellular Automata with Neighborhood-Dependent Messages 69
5.6.1 Rotation Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.6.2 Reection Messages . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.6.3 Majority Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.6.4 Parity Messages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.6.5 Extensions of the Game of Life . . . . . . . . . . . . . . . . . . . . 77
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6 Applications of Classical Cellular Automata 83
6.1 Applications in Physics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.1.1 Partial Dierential Equations . . . . . . . . . . . . . . . . . . . . . 83
6.1.1.1 Diusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.1.1.2 Reaction-Diusion . . . . . . . . . . . . . . . . . . . . . . 87
6.1.1.3 Waves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.1.1.4 Wavefronts . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6.1.2 Fluids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.1.2.1 Lattice Gas Model . . . . . . . . . . . . . . . . . . . . . . 92
6.1.2.2 Lattice Boltzmann Model . . . . . . . . . . . . . . . . . . 95
6.1.3 Ising Spin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
6.1.4 Sandpile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.1.5 Diusion-Limited Aggregation . . . . . . . . . . . . . . . . . . . . 103
6.2 Applications in Excitable Media . . . . . . . . . . . . . . . . . . . . . . . 103
6.2.1 Brian's Brain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.2.2 Greenberg-Hastings Model . . . . . . . . . . . . . . . . . . . . . . . 105
6.2.3 Threshold Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.2.4 Cyclic Cellular Automata . . . . . . . . . . . . . . . . . . . . . . . 108
6.2.5 Hodgepodge Machine . . . . . . . . . . . . . . . . . . . . . . . . . 109
6.3 Applications in Biology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6.3.1 Seashell Pigmentation Patterns . . . . . . . . . . . . . . . . . . . . 110
6.3.2 Bacterial Growth . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.3.3 Predator-Prey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.4 Applications in Social Science . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.4.1 Schelling Segregation Model . . . . . . . . . . . . . . . . . . . . . . 115
6.4.2 Evacuation Dynamics . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.4.2.1 Floor Fields Based on Shortest Paths . . . . . . . . . . . 117
6.4.2.2 Floor Fields Based on Quickest Paths . . . . . . . . . . . 120
6.4.2.3 Fast Evacuation Method . . . . . . . . . . . . . . . . . . 121
6.4.3 Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.4.4 Evolutionary Computation . . . . . . . . . . . . . . . . . . . . . . 124
6.5 Applications in Mathematics . . . . . . . . . . . . . . . . . . . . . . . . . 128
6.5.1 Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7 Applications of Message Passing Cellular Automata 135
7.1 Message Passing Versions of Classical Cellular Automata Applications . . 135
7.2 Message Passing Diusion of Innovations . . . . . . . . . . . . . . . . . . . 136
7.3 Message Passing Schelling Segregation Model . . . . . . . . . . . . . . . . 139
7.4 Message Passing Cellular Evolutionary Algorithms . . . . . . . . . . . . . 140
7.5 Message Passing Graph Layout . . . . . . . . . . . . . . . . . . . . . . . . 143
7.6 Message Passing Fractals . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Bibliography 153
Index 161