狠狠撸

狠狠撸Share a Scribd company logo

Presentation adv theo cs fadhil

?Download as PPT, PDF?
?
Fadhil Sukmadinata
Fadhil Sukmadinata

This document discusses cellular automata and some of its applications. It begins by explaining how John von Neumann and Stanislaw Ulam developed the concept of cellular automata in the 1940s as a way to model self-replicating systems. The document then provides a mathematical definition of cellular automata and examples of simple one-dimensional cellular automata. It discusses Conway's Game of Life as an influential two-dimensional cellular automaton and how it can exhibit complex, emergent behavior through simple rules. The document concludes by noting some fields where cellular automata have been applied, including cryptography, parallel computing, modeling/simulation, and generating multimedia content.

1 of 24
CELLULAR AUTOMATA AND APPLICATIONS –CELLULAR AUTOMATA AND APPLICATIONS – Conway’s Game of LifeConway’s Game of Life Presentation on Adv. Theories of Computer SciencePresentation on Adv. Theories of Computer Science FADHIL NOER AFIF – MC112075FADHIL NOER AFIF – MC112075
Self-replicating SystemSelf-replicating System 2 John von Neumann Stanislaw Ulam ? In 1940s, working on a problem “how to construct a self – replicating system?“ ? Born a mathematical model named Cellular Automata (CA)
Cellular AutomataCellular Automata 3 What is Cellular Automata ? ? Discrete, dynamical system ? Consists of network of finite state cells ? Changes state homogenously depending on states of neighbors and local update rule
Cellular AutomataCellular Automata 4 What is Cellular Automata ? ? Discrete, dynamical system ? Consists of network of finite state cells ? Changes state homogenously depending on states of neighbors and local update rule
Simple Example of CASimple Example of CA 5 One-dimensional CA, ? Two-state automaton (black / white) ? Each cell has three neighbors (including itself) ? Rules : – If all three == WHITE ? WHITE – If all three == BLACK ? WHITE – Else, BLACK ? Initial State :
Simple Example of CASimple Example of CA 6 ? Initial State (1st generation): ? 2nd generation ?
Simple Example of CASimple Example of CA 7 ? 2nd generation : ? 3rd generation ? ? If this continues what will happen ?
Simple Example of CASimple Example of CA 8 ? n th generation : A complex pattern !
Simple Example of CASimple Example of CA 9 ? Another 1-D CA with different rule (rule 30) :
Math. Definition of CAMath. Definition of CA 10 By Definition, CA is a 4-tuple (Kari, 2011) A = (d, S, N, f), where ? dimensional cellular space, d ? Z ? finite state set S, ? neighborhood vector N = (n1, n2, ..., nm), and ? local update rule f: Sm ? S
Cellular AutomataCellular Automata 11 ? What’s interesting about this CA? ? Any applications of CA?
Applications of CAApplications of CA 12 CA has been implemented in fields such as : ? Cryptography ? Parallel Computing ? Modeling and Simulation – Crowd Simulation – Traffic Simulation ? Artificial Life ? Multimedia Content
Conway’s Game of LifeConway’s Game of Life 13 Artificial Life Conway’s Game of Life (1970)
Conway’s Game of LifeConway’s Game of Life 14 Two-dimensional CA, ? Two-state automaton, – Life (denoted by marker) – Dead (no marker) ? Each cell has 8 neighbors (horizontal, vertical, diagonal) n n n n n n n n A LIVE cell with its neighbors
Conway’s Game of LifeConway’s Game of Life 15 Rules : ? A dead cell with exactly three live neighbors becomes live cell (a birth) ? A live cell with two or three live neighbors stays alive (survival) ? In all other cases, a cell dies or remains dead (as if overcrowding or loneliness). n n n n N n n n n n n n n N n n n n n n n n N n n n n n n n n N n n n n
Conway’s Game of LifeConway’s Game of Life 16 Game of Life can create complex behavior by only simple rules. n n n n n n n n cell configuration called “glider” Click here for simulations
GliderGlider 17 A pattern called “glider” ? When simulated, evolves periodically ? But, location is moved in diagonal direction ? Glider “moves” even though there is no rules about movement n n n n n n n n cell configuration called “glider”
R-pentominoR-pentomino 18 A pattern called R-pentomino ? When simulated, grows with a complex manner, creating new pattern through time. ? Shows a complexity of “life” n n n n n n n n cell configuration called R-pentomino
Conway’s Game of LifeConway’s Game of Life 19 Artificial Life Conway’s Game of Life Invented by J. Conway (1970) Shows that patterns can evolve Example of emergence and self-organization Complexity can arise from simple rules Theoretically, model the life itself?? Four-cell Embryo
Applications of CAApplications of CA 20 CA has been implemented in fields such as : ? Cryptography ? Parallel Computing ? Modeling and Simulation ? Artificial Life ? Multimedia Content
OtomataOtomata 21 Multimedia Content Batuhan Bozkurt’s OTOMATA
ConclusionConclusion 22 ? Cellular Automata is a discrete system which states depending on neighbors. ? Potentially able to model complex system. ? Conway’s Game of Life model simulates natural behavior, and probably the complexity, unpredictable behavior of life itself.
23 Thank You - Terima Kasih - Hatur Nuhun Snail named Conus Textile. Researchers believe that the shell exhibits cellular automaton pattern, as shown in example of 1D CA.
ReferencesReferences 24 Miranda, E. (2002) Cellular Automata Music: From Sound Synthesis to Musical Forms. Evolutionary Computer Music. Pp 170-193 Kari, Jarkko. (2011). Cellular Automata. Lecture Notes. Part 1, Taken from http://users.utu.fi/jkari/ca/ Sarkar, Palash. (2000). A Brief History of Cellular Automata, ACM Computing Surveys, 32(1), pp 80-107.

More Related Content

Presentation adv theo cs fadhil

  • 1. CELLULAR AUTOMATA AND APPLICATIONS –CELLULAR AUTOMATA AND APPLICATIONS – Conway’s Game of LifeConway’s Game of Life Presentation on Adv. Theories of Computer SciencePresentation on Adv. Theories of Computer Science FADHIL NOER AFIF – MC112075FADHIL NOER AFIF – MC112075
  • 2. Self-replicating SystemSelf-replicating System 2 John von Neumann Stanislaw Ulam ? In 1940s, working on a problem “how to construct a self – replicating system?“ ? Born a mathematical model named Cellular Automata (CA)
  • 3. Cellular AutomataCellular Automata 3 What is Cellular Automata ? ? Discrete, dynamical system ? Consists of network of finite state cells ? Changes state homogenously depending on states of neighbors and local update rule
  • 4. Cellular AutomataCellular Automata 4 What is Cellular Automata ? ? Discrete, dynamical system ? Consists of network of finite state cells ? Changes state homogenously depending on states of neighbors and local update rule
  • 5. Simple Example of CASimple Example of CA 5 One-dimensional CA, ? Two-state automaton (black / white) ? Each cell has three neighbors (including itself) ? Rules : – If all three == WHITE ? WHITE – If all three == BLACK ? WHITE – Else, BLACK ? Initial State :
  • 6. Simple Example of CASimple Example of CA 6 ? Initial State (1st generation): ? 2nd generation ?
  • 7. Simple Example of CASimple Example of CA 7 ? 2nd generation : ? 3rd generation ? ? If this continues what will happen ?
  • 8. Simple Example of CASimple Example of CA 8 ? n th generation : A complex pattern !
  • 9. Simple Example of CASimple Example of CA 9 ? Another 1-D CA with different rule (rule 30) :
  • 10. Math. Definition of CAMath. Definition of CA 10 By Definition, CA is a 4-tuple (Kari, 2011) A = (d, S, N, f), where ? dimensional cellular space, d ? Z ? finite state set S, ? neighborhood vector N = (n1, n2, ..., nm), and ? local update rule f: Sm ? S
  • 11. Cellular AutomataCellular Automata 11 ? What’s interesting about this CA? ? Any applications of CA?
  • 12. Applications of CAApplications of CA 12 CA has been implemented in fields such as : ? Cryptography ? Parallel Computing ? Modeling and Simulation – Crowd Simulation – Traffic Simulation ? Artificial Life ? Multimedia Content
  • 13. Conway’s Game of LifeConway’s Game of Life 13 Artificial Life Conway’s Game of Life (1970)
  • 14. Conway’s Game of LifeConway’s Game of Life 14 Two-dimensional CA, ? Two-state automaton, – Life (denoted by marker) – Dead (no marker) ? Each cell has 8 neighbors (horizontal, vertical, diagonal) n n n n n n n n A LIVE cell with its neighbors
  • 15. Conway’s Game of LifeConway’s Game of Life 15 Rules : ? A dead cell with exactly three live neighbors becomes live cell (a birth) ? A live cell with two or three live neighbors stays alive (survival) ? In all other cases, a cell dies or remains dead (as if overcrowding or loneliness). n n n n N n n n n n n n n N n n n n n n n n N n n n n n n n n N n n n n
  • 16. Conway’s Game of LifeConway’s Game of Life 16 Game of Life can create complex behavior by only simple rules. n n n n n n n n cell configuration called “glider” Click here for simulations
  • 17. GliderGlider 17 A pattern called “glider” ? When simulated, evolves periodically ? But, location is moved in diagonal direction ? Glider “moves” even though there is no rules about movement n n n n n n n n cell configuration called “glider”
  • 18. R-pentominoR-pentomino 18 A pattern called R-pentomino ? When simulated, grows with a complex manner, creating new pattern through time. ? Shows a complexity of “life” n n n n n n n n cell configuration called R-pentomino
  • 19. Conway’s Game of LifeConway’s Game of Life 19 Artificial Life Conway’s Game of Life Invented by J. Conway (1970) Shows that patterns can evolve Example of emergence and self-organization Complexity can arise from simple rules Theoretically, model the life itself?? Four-cell Embryo
  • 20. Applications of CAApplications of CA 20 CA has been implemented in fields such as : ? Cryptography ? Parallel Computing ? Modeling and Simulation ? Artificial Life ? Multimedia Content
  • 22. ConclusionConclusion 22 ? Cellular Automata is a discrete system which states depending on neighbors. ? Potentially able to model complex system. ? Conway’s Game of Life model simulates natural behavior, and probably the complexity, unpredictable behavior of life itself.
  • 23. 23 Thank You - Terima Kasih - Hatur Nuhun Snail named Conus Textile. Researchers believe that the shell exhibits cellular automaton pattern, as shown in example of 1D CA.
  • 24. ReferencesReferences 24 Miranda, E. (2002) Cellular Automata Music: From Sound Synthesis to Musical Forms. Evolutionary Computer Music. Pp 170-193 Kari, Jarkko. (2011). Cellular Automata. Lecture Notes. Part 1, Taken from http://users.utu.fi/jkari/ca/ Sarkar, Palash. (2000). A Brief History of Cellular Automata, ACM Computing Surveys, 32(1), pp 80-107.