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

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

dc.contributor.advisor	อรรถสิทธิ์ สุรฤกษ์
dc.contributor.author	วรยุทธ วงศ์นิล
dc.contributor.other	จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์
dc.date.accessioned	2021-09-22T23:25:32Z
dc.date.available	2021-09-22T23:25:32Z
dc.date.issued	2563
dc.identifier.uri	http://cuir.car.chula.ac.th/handle/123456789/77068
dc.description	วิทยานิพนธ์ (วศ.ด.)--จุฬาลงกรณ์มหาวิทยาลัย, 2563
dc.description.abstract	เซลลูลาร์ออโตมาตาถือเป็นโมเดลทางคณิตศาสตร์ที่สามารถทำงานแบบระบบพลวัต ซึ่งประกอบไปด้วยสถานะจำกัดที่เรียงตัวกันอย่างเป็นระบบเรียกเซลล์ แต่ละเซลล์จะเปลี่ยนสถานะไปยังสถานะใหม่พร้อมกันด้วยการอาศัยกฎการส่งผ่านที่ขึ้นอยู่กับเซลล์รอบ ๆ ด้วยเวลาแบบเต็มหน่วย แม้ว่าเซลลูลาร์ออโตมาตามีโครงสร้างและนิยามในแบบพื้นฐาน แต่สามารถสร้างระบบที่พฤติกรรมมีความซับซ้อนได้ สมบัติในการผันกลับได้ของเซลลูลาร์ออโตมาตาถือเป็นสมบัติสำคัญที่ได้รับความสนใจในหลายงานวิจัยและสามารถนำไปประยุกต์ใช้ได้ในงานหลาย ๆ ด้านในทางวิทยาศาสตร์ แต่สำหรับเซลลูลาร์ออโตมาตาหนึ่งมิติภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่ายังถือมีข้อจำกัดของจำนวนกฎที่มีไม่มากที่มีสมบัติดังกล่าว ในงานวิจัยนี้ศึกษาและเสนออัลกอริทึมการระบุการผันกลับของเซลลูลาร์ออโตมาตาหนึ่งมิติด้วยกราฟสับเซตย่อยภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่านิยามเซลล์เพื่อนบ้านด้วยเวกเตอร์ ด้วยการแทนเซลลูลาร์ออโตมาตาด้วยกราฟสับเซตย่อยเราเสนอวิธีในการระบุสมบัติการผันกลับได้ในกราฟโดยการพิจารณาเส้นเชื่อมและจุดยอดที่เชื่อมถึงกัน นอกจากนี้งานวิจัยนี้ยังเสนอวิธีในการคำนวณสถานะก่อนหน้าสำหรับสถานะใด ๆ ของเซลลูลาร์ออโตมาตาหนึ่งมิติที่มีสมบัติผันกลับได้ภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่า ซึ่งวิธีที่ได้เสนออยู่บนพื้นฐานของการพิจารณาลักษณะของเซลล์เพื่อนบ้านด้วยการคำนวณทางเดินบนกราฟด้วยการดำเนินการของเมตริกซ์
dc.description.abstractalternative	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.
dc.language.iso	th
dc.publisher	จุฬาลงกรณ์มหาวิทยาลัย
dc.relation.uri	http://doi.org/10.58837/CHULA.THE.2020.1133
dc.rights	จุฬาลงกรณ์มหาวิทยาลัย
dc.subject	เซลลูลาร์ออโตมาตา
dc.subject	ปัญหาค่าขอบ
dc.subject	Cellular automata
dc.subject	Boundary value problems
dc.subject.classification	Computer Science
dc.title	อัลกอริทึมการระบุการผันกลับของเซลลูลาร์ออโตมาตาหนึ่งมิติด้วยกราฟสับเซตย่อยภายใต้เงื่อนไขการกำหนดขอบเขตแบบไม่มีค่า
dc.title.alternative	One-dimensional reversible cellular automata determination algorithm based on subset graph under null boundary condition
dc.type	Thesis
dc.degree.name	วิศวกรรมศาสตรดุษฎีบัณฑิต
dc.degree.level	ปริญญาเอก
dc.degree.discipline	วิศวกรรมคอมพิวเตอร์
dc.degree.grantor	จุฬาลงกรณ์มหาวิทยาลัย
dc.identifier.DOI	10.58837/CHULA.THE.2020.1133