อัลกอริทึมการระบุการผันกลับของเซลลูลาร์ออโตมาตาหนึ่งมิติด้วยกราฟสับเซตย่อยภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่า

One-dimensional reversible cellular automata determination algorithm based on subset graph under null boundary condition

Name: วรยุทธ วงศ์นิล

ThaSH: เซลลูลาร์ออโตมาตา

ThaSH: ปัญหาค่าขอบ

Abstract: เซลลูลาร์ออโตมาตาถือเป็นโมเดลทางคณิตศาสตร์ที่สามารถทำงานแบบระบบพลวัต ซึ่งประกอบไปด้วยสถานะจำกัดที่เรียงตัวกันอย่างเป็นระบบเรียกเซลล์ แต่ละเซลล์จะเปลี่ยนสถานะไปยังสถานะใหม่พร้อมกันด้วยการอาศัยกฎการส่งผ่านที่ขึ้นอยู่กับเซลล์รอบ ๆ ด้วยเวลาแบบเต็มหน่วย แม้ว่าเซลลูลาร์ออโตมาตามีโครงสร้างและนิยามในแบบพื้นฐาน แต่สามารถสร้างระบบที่พฤติกรรมมีความซับซ้อนได้ สมบัติในการผันกลับได้ของเซลลูลาร์ออโตมาตาถือเป็นสมบัติสำคัญที่ได้รับความสนใจในหลายงานวิจัยและสามารถนำไปประยุกต์ใช้ได้ในงานหลาย ๆ ด้านในทางวิทยาศาสตร์ แต่สำหรับเซลลูลาร์ออโตมาตาหนึ่งมิติภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่ายังถือมีข้อจำกัดของจำนวนกฎที่มีไม่มากที่มีสมบัติดังกล่าว ในงานวิจัยนี้ศึกษาและเสนออัลกอริทึมการระบุการผันกลับของเซลลูลาร์ออโตมาตาหนึ่งมิติด้วยกราฟสับเซตย่อยภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่านิยามเซลล์เพื่อนบ้านด้วยเวกเตอร์ ด้วยการแทนเซลลูลาร์ออโตมาตาด้วยกราฟสับเซตย่อยเราเสนอวิธีในการระบุสมบัติการผันกลับได้ในกราฟโดยการพิจารณาเส้นเชื่อมและจุดยอดที่เชื่อมถึงกัน นอกจากนี้งานวิจัยนี้ยังเสนอวิธีในการคำนวณสถานะก่อนหน้าสำหรับสถานะใด ๆ ของเซลลูลาร์ออโตมาตาหนึ่งมิติที่มีสมบัติผันกลับได้ภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่า ซึ่งวิธีที่ได้เสนออยู่บนพื้นฐานของการพิจารณาลักษณะของเซลล์เพื่อนบ้านด้วยการคำนวณทางเดินบนกราฟด้วยการดำเนินการของเมตริกซ์

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.

จุฬาลงกรณ์มหาวิทยาลัย. สำนักงานวิทยทรัพยากร

Address: กรุงเทพมหานคร

Email: cuir@car.chula.ac.th

Name: อรรถสิทธิ์ สุรฤกษ์

Role: ที่ปรึกษา

Created: 2563

Modified: 2023-02-23

Issued: 2566-02-14

วิทยานิพนธ์/Thesis

application/pdf

URL: http://cuir.car.chula.ac.th/handle/123456789/77068

tha

DegreeName: วิศวกรรมศาสตรดุษฎีบัณฑิต

Level: ปริญญาเอก

Descipline: วิศวกรรมคอมพิวเตอร์

Grantor: จุฬาลงกรณ์มหาวิทยาลัย

©copyrights จุฬาลงกรณ์มหาวิทยาลัย

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	5871418521.pdf	3.03 MB

ใช้เวลา

0.031662 วินาที