在多維細胞自動機-水波法的應用

Multiple-Dimensional Cellular Automata: Applications of Ripples

李道傑(Dau-Jie Lee)

指導教授 ： 何善輝

國立臺北大學/電機資訊學院/電機工程學系/碩士(2016年)

摘要

本研究建立一套以三維細胞自動機水波法之海嘯模擬模式，利用細胞自動機之強大的適應性和直觀的展示功能，可直接觀察到由不同機制交互作用所形成的結果。而海嘯模擬的成果，亦可做為細胞自動機適用於複雜系統模擬之驗證。
CA(Cellular Automata)，全名為細胞自動機，是一個可以產生複雜的自我組織結構的方法。馮紐曼證明了細胞自動機在有限狀態和小範圍的互動下可以建立一個通用計算機。康威也示範了使用兩個狀態就能發展出自行建立複雜時空模型的遊戲”Life”。之後，沃夫曼觀察到細胞自動機可以利用其自身的原理來解決各種複雜問題。因此，細胞自動機之後被使用來發展或擴張成各種新應用來解決各種領域的問題，其中也包括生物學及生物資訊。
在本文中提出了一種新結合兩種方法：(1)三維細胞自動機水波的前進和消失。(2)三維細胞自動機海嘯的前進和消失。在提出的方法中，三維細胞自動細胞機中給定一個明確的初始配置，每個水波或海嘯前進時，可以在不同時間及不同的配置中計算出所有的變化規則。利用計算出的規則，接下來我們利用水波在不同時間產生出的水波規則，歸納出水波一般性規則，及大浪和海嘯規則。這個規則可套用在一些自然現象，像是水波的前進消失、海水漲潮退潮，海嘯或是大浪。利用歸納出來的水波規則可被用來模擬三維細胞自動機海嘯的前進和消失。
在這次研究，利用三維細胞自動機來模擬水波和海嘯前進可以使得觀察水波前進模型更加圖形化及容易。使用生物資訊平台來時做水波前進模型使得不僅在水波前進的動作，在其他自然現象也變得可行。使用三維細胞自動機建構的水波和海嘯前進及消失方法充分利用平行處理的方式來解決時間複雜度的瓶頸，並提高建構任何前進和消失計算的效率。假設N是水波或海嘯前進的步驟次數，使用三維細胞自動機建構水波和海嘯前進及水波消失模型的時間複雜度皆為O(N^3)。

關鍵字

海嘯模擬 ； 水波前進 ； 水波消失 ； 三維細胞自動機 ； 生物資訊

並列摘要

This study successfully established a model of tsunami simulation based on the three-dimensional cellular automata and using powerful applicability and intuitive display function of cellular automata. It can be directly observed by a different mechanism formed by the interaction of the results. The results of tsunami simulation can be used as cellular automata applied to verify the simulation of complex systems.
CA, which named Cellular Automata, can produce very sophisticated self-organized structures. Von Neumann showed that a CA with a finite number of states and short range interactions could build a universal computer in 1951 and Conway in `Life' demonstrated that even a simple two-state CA with purely local interactions could generate arbitrarily complex spatio-temporal patterns. More recently, Wolfram has investigated the theory of CA and made a strong case for their utility in addressing complex problems. For this reason, CA can be developed and expended to various applications to solve many complicating problems on many fields, including biology and bioinformatics.
In this thesis, this is proposed a newly approach combined with two methods: (1) the movement and disappearance of the ripple in three dimensional cellular automata. (2) the movement and disappearance of the Tsunami in three dimensional cellular automata. First proposed method, given a specific initial configuration of cells in three dimensional cellular automata, each ripple or Tsunami movement can have different configurations in different time which are responsible for processing all the computational basis states. Next we take advantage of the rules of ripple in different time to summarize the real rule in ripple and Tsunami. Then, the real rule is used to simulate the movement of Tsunami in three dimensional cellular automata. The approaches are also used the real rule in ripple and Tsunami to simulate the disappearance of Tsunami in three dimensional cellular automata.
In these proposed approaches, the ripple or Tsunami movement in the three-dimensional automata makes observing ripple movement easier and more graphical for researchers from other fields. Bioinformatics approach is not only for ripple or Tsunami movement and disappearance, but also in other phenomenon become possible. This proposed and optimized bioinformatics ripple and Tsunami movement in three-dimensional cellular automata and disappearance approach is fully utilizing parallelism to conquer time complexity bottleneck, and improves any ripple or Tsunami movement simulation and disappearance more efficient. Suppose that N is the number of evolve steps for the ripple movement, the time complexity of ripple and Tsunami movement and backtracking in three-dimensional cellular automata is in O (N^3) polynomial bound.

並列關鍵字

Tsunami simulation ； Ripple movement ； Ripple disappearance ； Three-dimensional Cellular Automata ； Bioinformatics

參考文獻

[18] 陳冠宇，2007， 淺談海嘯及其數值模擬，港灣報導 77: 10-17。

[2] Wolfram, Stephen. "Statistical mechanics of cellular automata." Reviews of modern physics 55.3 (1983): 601.

[3] Von Neumann, John, and Arthur W. Burks. "Theory of self-reproducing automata." IEEE Transactions on Neural Networks 5.1 (1966): 3-14.

[4] Wolfram, Stephen. "Universality and complexity in cellular automata." Physica D: Nonlinear Phenomena 10.1 (1984): 1-35.

[6] Boneh, Dan, et al. "On the computational power of DNA." Discrete Applied Mathematics 71.1 (1996): 79-94.