261407 Fundamentals of Computation

Tentative syllabus: https://www.overleaf.com/read/rqfjgbtxxmmm

ทุกสิ่งมีข้อจำกัด คอมพิวเตอร์ก็มีข้อจำกัด ไม่ได้ทำทุกๆ อย่างได้เสมอไป ในคอร์สนี้ เราจะมาดูกันว่ามีปัญหาอะไรที่คอมพิวเตอร์แก้ไม่ได้บ้าง

แล้วจะรู้ปัญหาที่คอมพิวเตอร์แก้ไม่ได้ไปทำไม ดูเหมือนว่าเราไม่เห็นจะต้องแก้สักหน่อย

ปัญหาพวกนี้ใกล้ตัวกว่าที่ท่านอาจจะคิดครับ หากเราไปเรียน grammar ของสักภาษาหนึ่ง แล้วเราสงสัยว่า grammar ของภาษานั้นมันสามารถสร้างประโยคที่กำกวมได้หรือไม่ (เช่น ฉันเห็นเธอที่ยอดเขา: ตกลงใครอยู่ที่ยอดเขา) ปัญหานี้ คอมพิวเตอร์ตอบไม่ได้ครับ

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

นอกจากนี้ ปัญหาที่แก้ไขได้ อาจจะใช้ทรัพยากรต่างๆ ทั้งเวลาและหน่วยความจำ เกินกว่าจะรับได้ เราจะมาดูกันว่า ปัญหาใดที่มีคุณสมบัติดังกล่าวบ้าง เพื่อที่เวลาเราจำเป็นจะต้องแก้มันจริงๆ จะได้หาวิธีประมาณการคำตอบ ที่อาจจะคลาดเคลื่อนไปบ้าง แต่อย่างน้อยก็เสียเวลาหรือเนื้อที่คิดไม่มาก

รายละเอียดเพิ่มเติม ดูได้จากอัลบั้มภาพประกอบ และจากร่าง syllabus ตามลิงก์ข้างบนครับ (ยังเปลี่ยนแปลงได้ตลอดเวลา จนกว่าคอร์สจะจบ)