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

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

Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/77068

Full metadata record

DC Field	Value	Language
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	-
Appears in Collections:	Eng - Theses

Files in This Item:

File	Description	Size	Format
5871418521.pdf		3.11 MB	Adobe PDF	View/Open

Show simple item record