ความสามารถในการคำนวณ

แนวคิดในวิทยาการคอมพิวเตอร์

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Computability คืออะไร?

ปัญหาที่คำนวณได้

  • มีอัลกอริทึม: มีขั้นตอนที่ชัดเจน
  • ใช้เวลาจำกัด: ได้ผลลัพธ์ภายในจำนวนขั้นตอนที่จำกัด

ปัญหาที่คำนวณไม่ได้

  • ไม่มีอัลกอริทึม: ไม่สามารถแก้ปัญหาได้กับทุก input ที่เป็นไปได้
  • การคำนวณไม่สิ้นสุด: อาจไม่มีทางสรุปผลได้
1 ปัญหาที่คำนวณไม่ได้อาจกลายเป็นปัญหาที่คำนวณได้ เมื่อพบอัลกอริทึมที่เหมาะสม และ/หรือทำให้อัลกอริทึมที่รู้จักสิ้นสุดภายในเวลาจำกัด
แนวคิดในวิทยาการคอมพิวเตอร์

Automata

นิยามของ Automata

  • เครื่องจักรสมมติ
  • ช่วยให้เข้าใจหลักการทำงานของการคำนวณ
  • มีสถานะ (states)
  • มีกฎสำหรับการเปลี่ยนระหว่างสถานะ

ภาพไฟจราจรเป็นอุปมาแทน Automata

แนวคิดในวิทยาการคอมพิวเตอร์

Finite Automata (FA)

Finite Automata (FA)

  • เครื่องจักรอย่างง่าย
  • จำนวนสถานะคงที่
  • ไม่มีหน่วยความจำนอกจากสถานะปัจจุบัน

ภาพไฟจราจรและสถานะเป็นอุปมาสำหรับ Finite Automata

แนวคิดในวิทยาการคอมพิวเตอร์

Pushdown Automata (PDA)

Pushdown Automata (PDA)

  • มีความสามารถมากกว่า
  • มีสถานะ
  • มีหน่วยความจำแบบ stack สำหรับการตัดสินใจที่ซับซ้อนขึ้น

ภาพไฟจราจรและสถานะเป็นอุปมาสำหรับ Pushdown Automata

แนวคิดในวิทยาการคอมพิวเตอร์

สรุป

Finite Automata (FA)

  • เหมาะกับงานอย่างง่าย

Pushdown Automata (PDA)

  • มีความสามารถมากกว่าสำหรับปัญหาที่ซับซ้อน

ความสำคัญ

  • หากปัญหาสามารถสร้างแบบจำลองด้วย Automata ได้ เราก็สามารถสร้างอัลกอริทึมเพื่อแก้ปัญหานั้นได้
แนวคิดในวิทยาการคอมพิวเตอร์

มาฝึกกันเถอะ!

แนวคิดในวิทยาการคอมพิวเตอร์

Preparing Video For Download...