细胞自动机cellularautomata.ppt

細胞自動機細胞自動機 (Cellular Automata)格狀自動機格狀自動機 Sierpinskis Triangle Sierpinskis Triangle is a very famous fractal thats been seen by most advanced math students.This fractal consists of one large triangle,which contains an infinite amount of smaller triangles within.The infinite amount of triangles is easily understood if the fractal is zoomed in many levels.Each zoom will show yet more previously unseen triangles embedded in the visible ones.Creating the fractal requires little computational power.Even simple graphing calculators can easily make this image.The fractal is created pixel by pixel,using random numbers;the fractal will be slightly different each time due to this.Although,if you were to run the program repeatedly,and allow each to use an infinite amount of time,the results would be always identical.No one has an infinite amount of time,but the differences in the finite versions are very small.To generate this fractal,a few steps are involved.First,initial X and Y values should be chosen,either by the program or the user.The values used have little effect on the fractal.Regardless of whats chosen,the same triangle will be created.Next,the program must create a random number,between 0 and 1.Then,three possible routes can be taken.If the random number is less then 1/3,then the following equations should be applied to X and Y.xn=0.5*(xn-1+1)yn=0.5*yn-1 If the random number is between 1/3 and 2/3,then these equations should be used.xn=xn-1*0.5 yn=yn-1*0.5 If the number is greater than 2/3,the the following equations should be applied.xn=0.5*(xn-1+0.5)yn=0.5*(yn-1+1)Now that X and Y have changed,the point should be plotted on the screen.Finally,loop back to the random number generation and start over again.Only a few hundred iterations are needed to begin to see the triangles.A few thousand pixels will produce a good image.Sierpinskis Triangle 細胞自動機細胞自動機(cellular automata;CA)1.細胞自動機的定義與組成 2.細胞自動機的發展歷史 3.細胞自動機的特點 4.細胞自動機的運作 5.細胞自動機的發展 細胞自動機的定義與組成細胞自動機的定義與組成 一種十分新穎的數學演算法。在網格資料結構上（將每一個網格視為一個細胞），利用其空間近鄰性，模擬其空間的自動演化過程。這是一個抽象的圖案產生機制。給定初始值，即可按預先設定的規則，隨時間改變形狀。以人工生命的角度來看，細胞自動機可視為一個讓許多生命生存繁殖的世界(world)，類似地球孕育各種生物一般。它包含許多細胞，各取一值（通常是二值的 0或1），其值與周圍細胞互相影響，整個平面即在不同時刻顯出不同特徵（例如，0表燈滅，1表燈明，則可構成各細胞格子有明有暗的圖型）。細胞自動機是由規則（rules）所控制的數位建構，可產生各種類型（pattern）；它的細胞會死（關掉）、再生（影響周圍細胞成一樣），整體表現類似同時互動、平行處理。設計一個細胞自動機需包含兩部份：1.各個細胞的初始狀態(即整個自動機的初始形狀)2.根據舊細胞產生新細胞的規則.細胞自動機的發展歷史細胞自動機的發展歷史 人稱電腦之父的馮諾曼（John von Neumann）在1940年代開始研究細胞自動機（cellular automaton）或譯格子自動機，於1950 年代便發明細胞自動機以求發展具有自我複製能力的計算工具，促成self-replicating automata 的發展。因為它狀似一大片格子，原為離散的（discrete）時空模型，做為模擬任何系統之用，例如，模擬生物細胞活動、組織族群；模擬化學分子系統與結晶成長的動力學；模擬物理粒子互動；模擬電腦科學中的平行處理等。1970 年，John Conway 依據Von Neumann 的想法進一步發展成電腦上的生命遊戲（Game of Life），從此CA 的概念逐漸普及到相關領域。細胞自動機的人工生命具有動態、自我複製的特性，而其宏觀（Macro）的演化現象是由微觀(Micro)層次的作用力在主導，而所謂的微觀作用是一個演化單元和其周遭環境中的關係，演化過程呈現一種具演化規則的明確機制。其演化的本身具有空間交互作用的特性，CA 所模擬或預測的現象也就具有空間幸，是一種具空間觀點的演化模式。巨觀的環境變化則需透過細胞的屬性變化與演化規則的調整來調適。馮紐曼(von Neumann)Von Neumann（1903-1957），匈裔美籍數學家，生於布達佩斯，卒於華盛頓特區。他是廿世紀少見的數學科學通才，在許多領域都有重要的基本貢獻。Von Neumann 是猶太人。原姓Neumann，因為父親買下爵位，才加上貴族專稱的von。他自幼穎異，記憶力過人，對數學有驚人的天份，但父親希望他從商，幾經折衝，他同時在布達佩斯大學學數學，又在柏林大學學化學（後轉到蘇黎士學化工）。但即使在蘇黎士，他仍與知名數學家 Weyl 與 Polya 交遊。Polya 曾經這樣描述 Von Neumann 他是我唯一害怕的學生。在課堂如果我提出一個當時未解的問題，通常他在下課後就會直接來找我，給我幾頁完整的解答。1926年 Von Neumann 以一篇集合論的論文獲得布達佩斯大學的博士學位，然後以 Rockefeller 獎學金前往哥廷根大學跟隨 Hilbert 作博士後研究，並在柏林，漢堡講學。Von Neumann 在廿餘歲時已經是數學圈中公認的年輕天才。1930年 Von Neumann 應 Veblen 之邀，到普林斯頓大學客座，1931年普林斯頓大學即授予教授職位，1933年他成為新成立的普林斯頓高等研究院終身職院士。Von Neumann 的家庭宴會在普林斯頓非常熱鬧知名，這在數學家中是很少見的。綜論 Von Neumann 的數學成就，大致如下：（1）初期工作以數理邏輯（尤其是公設集合論）、測度論、實分析為主。（2）在Mathematische Grundlagender Quantenmachanik（1932）中，Von Neumann 為當時的量子力學打下堅實的數學基礎。（3）自1929起，Von Neumann 即從事算子代數的先驅性工作，在1930-40年間 Von Neumann 與 Murray 為後來所謂的 Von Neumann 代數寫下系列基本的文章。（4）Von Neumann 為對局論的發明人，他首先証明零和對局的 minmax 定理，並與 Morgenstern 合著對局論與經濟行為，對社會科學、生命科學影響深遠。（5）Ergdic（遍歷性）定理的証明（1938）。（6）Von Neumann 對應用數學的興趣，從流體力學始，並對非線性偏微分方程產生莫大的興趣。而對他而言，數值計算是最可能的實驗方法，這也使 Von Neumann 成為今日電腦之奠基者，並因此發展 cellular automata 的理論。另外 Von Neumann 也是氫彈的催生者，1940年起他即熱心 參與美國的各項國防計劃或實驗室，也因此獲得各式各樣的數學或非數學的獎章。Are mathematical equations the best way to model nature?For many years it had been assumed that they were.But in the early 1980s,Stephen Wolfram made the radical proposal that one should instead build models that are based directly on simple computer programs.Wolfram made a detailed study of a class of such models known as cellular automata,and discovered a remarkable fact:that even when the underlying rules are very simple,the behavior they produce can be highly complex,and can mimic many features of what we see in nature.And based on this result,Wolfram began a program to develop what has become A New Kind of Science.The results of Wolframs work found many applications,from the so-called Wolfram Classification central to fields such as artificial life,to new ideas about cryptography and fluid dynamics.This book is a collection of Wolframs original papers on cellular automata and complexity.Some of these papers are widely known in the scientific community;others