Please use this identifier to cite or link to this item:
https://cuir.car.chula.ac.th/handle/123456789/77068
| Title: | อัลกอริทึมการระบุการผันกลับของเซลลูลาร์ออโตมาตาหนึ่งมิติด้วยกราฟสับเซตย่อยภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่า |
| Other Titles: | One-dimensional reversible cellular automata determination algorithm based on subset graph under null boundary condition |
| Authors: | วรยุทธ วงศ์นิล |
| Advisors: | อรรถสิทธิ์ สุรฤกษ์ |
| Other author: | จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์ |
| Subjects: | เซลลูลาร์ออโตมาตา ปัญหาค่าขอบ Cellular automata Boundary value problems |
| Issue Date: | 2563 |
| Publisher: | จุฬาลงกรณ์มหาวิทยาลัย |
| Abstract: | เซลลูลาร์ออโตมาตาถือเป็นโมเดลทางคณิตศาสตร์ที่สามารถทำงานแบบระบบพลวัต ซึ่งประกอบไปด้วยสถานะจำกัดที่เรียงตัวกันอย่างเป็นระบบเรียกเซลล์ แต่ละเซลล์จะเปลี่ยนสถานะไปยังสถานะใหม่พร้อมกันด้วยการอาศัยกฎการส่งผ่านที่ขึ้นอยู่กับเซลล์รอบ ๆ ด้วยเวลาแบบเต็มหน่วย แม้ว่าเซลลูลาร์ออโตมาตามีโครงสร้างและนิยามในแบบพื้นฐาน แต่สามารถสร้างระบบที่พฤติกรรมมีความซับซ้อนได้ สมบัติในการผันกลับได้ของเซลลูลาร์ออโตมาตาถือเป็นสมบัติสำคัญที่ได้รับความสนใจในหลายงานวิจัยและสามารถนำไปประยุกต์ใช้ได้ในงานหลาย ๆ ด้านในทางวิทยาศาสตร์ แต่สำหรับเซลลูลาร์ออโตมาตาหนึ่งมิติภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่ายังถือมีข้อจำกัดของจำนวนกฎที่มีไม่มากที่มีสมบัติดังกล่าว ในงานวิจัยนี้ศึกษาและเสนออัลกอริทึมการระบุการผันกลับของเซลลูลาร์ออโตมาตาหนึ่งมิติด้วยกราฟสับเซตย่อยภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่านิยามเซลล์เพื่อนบ้านด้วยเวกเตอร์ ด้วยการแทนเซลลูลาร์ออโตมาตาด้วยกราฟสับเซตย่อยเราเสนอวิธีในการระบุสมบัติการผันกลับได้ในกราฟโดยการพิจารณาเส้นเชื่อมและจุดยอดที่เชื่อมถึงกัน นอกจากนี้งานวิจัยนี้ยังเสนอวิธีในการคำนวณสถานะก่อนหน้าสำหรับสถานะใด ๆ ของเซลลูลาร์ออโตมาตาหนึ่งมิติที่มีสมบัติผันกลับได้ภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่า ซึ่งวิธีที่ได้เสนออยู่บนพื้นฐานของการพิจารณาลักษณะของเซลล์เพื่อนบ้านด้วยการคำนวณทางเดินบนกราฟด้วยการดำเนินการของเมตริกซ์ |
| Other Abstract: | Cellular automata (CA) are mathematical dynamical systems that are comprising numerous finite state automata represented by cells. Each cell is updated to the new state simultaneously according to the current states of its neighbors at a discrete time. Although CA has a simple structure and definition, but it can generate a complex behavior. Reversibility of CA is an important property of the CA, which is attracted by many researchers and has been applied to a wide range of fields in science. In the case of a one-dimensional CA under null boundary condition, there are not many rules that emerge with that property. This dissertation studies and proposes one-dimensional reversible CA determination algorithm based on subset graph under null boundary condition with a vector-defined neighborhood. With the representation of subset graph of CA, we propose a method for determining the reversible property of a graph by considering its connected edges and vertices. The reversible rule can be considered on the path in the graph. In addition, we also introduce a method for calculating the previous state of a given state of a reversible CA under null boundary condition. The proposed method is based on the considering the de Bruijn graph path with the matrix operation. |
| Description: | วิทยานิพนธ์ (วศ.ด.)--จุฬาลงกรณ์มหาวิทยาลัย, 2563 |
| Degree Name: | วิศวกรรมศาสตรดุษฎีบัณฑิต |
| Degree Level: | ปริญญาเอก |
| Degree Discipline: | วิศวกรรมคอมพิวเตอร์ |
| URI: | http://cuir.car.chula.ac.th/handle/123456789/77068 |
| URI: | http://doi.org/10.58837/CHULA.THE.2020.1133 |
| metadata.dc.identifier.DOI: | 10.58837/CHULA.THE.2020.1133 |
| Type: | Thesis |
| Appears in Collections: | Eng - Theses |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 5871418521.pdf | 3.11 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.