กำหนดการพลวัตและภาษาโปรล็อก

ทางลัด: ความแตกต่างความคล้ายคลึงกันค่าสัมประสิทธิ์การเปรียบเทียบ Jaccardการอ้างอิง

ความแตกต่างระหว่าง กำหนดการพลวัตและภาษาโปรล็อก

กำหนดการพลวัต vs. ภาษาโปรล็อก

ในคณิตศาสตร์ วิทยาการคอมพิวเตอร์ และเศรษฐศาสตร์ กำหนดการพลวัต (dynamic programming) คือกระบวนการในการแก้ไขปัญหาที่ซับซ้อนโดยการแบ่งปัญหาให้เป็นปัญหาย่อยที่สามารถแก้ได้ง่ายกว่า คุณสมบัติพื้นฐานของปัญหาที่จะใช้กำหนดการพลวัตได้คือจะต้องมีปัญหาย่อยที่ทับซ้อนกัน (overlapping subproblem) และโครงสร้างย่อยที่เหมาะสมที่สุด (optimal substructure) ปัญหาที่ใช้กำหนดการพลวัตในการแก้ปัญหาจะใช้เวลาแก้รวดเร็วกว่าการแก้ปัญหาโดยตรงเป็นอย่างมาก หลักสำคัญของกำหนดการพลวัตมาจากการสังเกตว่าในการแก้ปัญหาที่ซับซ้อนนั้น จำเป็นที่จะต้องแก้ปัญหาที่เล็กกว่า (ปัญหาย่อย) และนำคำตอบของปัญหาย่อยเหล่านั้นมารวมกันเป็นคำตอบของปัญหาใหญ่ และในการดำเนินการแก้ปัญหาย่อยนี้ มีหลายปัญหาที่ปัญหาย่อยบางส่วนเหมือนกันทุกประการ ดังนั้นแทนที่จะแก้ไขปัญหาย่อยเหล่านี้ซ้ำอีกรอบ กระบวนการกำหนดการพลวัตจะใช้วิธีแก้ไขปัญหาย่อยเหล่านี้เพียงแค่ครั้งเดียว และเก็บคำตอบไว้ หรือที่เรียกว่าการจำ (memoization; ระวังสะกดเป็น memorization) เมื่อพบปัญหาย่อยดังกล่าวอีกครั้งก็ไม่จำเป็นต้องคำนวณซ้ำใหม่ แต่สามารถเรียกคำตอบที่เก็บไว้มาใช้ได้เลย กระบวนการนี้จะมีประสิทธิภาพดีเป็นอย่างยิ่งเมื่อปัญหาที่จะแก้มีจำนวนปัญหาย่อยที่ทับซ้อนกันเป็นจำนวนมาก ซึ่งหากไม่ได้ใช้กำหนดการพลวัตจะทำให้จำนวนครั้งในการแก้ปัญหาย่อยเติบโตแบบฟังก์ชันเลขชี้กำลัง ส่งผลให้เวลาในการแก้ไขปัญหาเพิ่มขึ้นเป็นอย่างมาก. ษาโปรล็อก (Prolog) เป็นภาษาสำหรับการเขียนโปรแกรมเชิงตรรกะ ได้ชื่อมาจาก PROgrammation en LOGique (logic programming) สร้างขึ้นโดย Alain Colmerauer ราว ค.ศ. 1972 ภาษาโปรล็อกเกิดจากความพยายามที่จะสร้างภาษาที่อาศัยวิธีการทางตรรกศาสตร์แทนที่จะกำหนดคำสั่งอย่างละเอียดให้กับคอมพิวเตอร์ ภาษาโปรล็อกถูกนำไปใช้ในโปรแกรมสำหรับปัญญาประดิษฐ์ และภาษาศาสตร์เชิงคำนวณ (computational linguistics) โดยเฉพาะการประมวลผลภาษาธรรมชาติ ไวยากรณ์และความหมายของภาษานั้นเรียบง่ายและชัดเจน (เป้าหมายแรกของภาษาคือเป็นเครื่องมือสำหรับนักภาษาศาสตร์ที่ไม่รู้คอมพิวเตอร์) งานวิจัยจำนวนมากที่ทำให้เกิดการพัฒนาภาษาโปรล็อกในปัจจุบันนั้น เป็นผลมาจากโครงการระบบคอมพิวเตอร์ยุคที่ห้า (fifth generation computer systems project - FGCS) ซึ่งเลือกรูปแบบหนึ่งของภาษาโปรล็อกเป็นภาษาแก่น (Kernel Language) ของระบบปฏิบัติการ ภาษาโปรล็อกมีพื้นฐานมาจากแคลคูลัสภาคแสดง (predicate calculus) หรือเรียกเต็ม ๆ ว่า แคลคูลัสภาคแสดงอันดับที่หนึ่ง (first-order predicate calculus) โดยจำกัดให้ใช้เฉพาะอนุประโยคของฮอร์น (Horn clause) การดำเนินการของโปรแกรมโปรล็อก ก็คือการประยุกต์วิธีพิสูจน์ทฤษฎีบทโดยใช้รีโซลูชันอันดับหนึ่ง (first-order resolution) แนวคิดพื้นฐานที่เกี่ยวข้องได้แก่ การทำให้เท่ากัน (unification), การเรียกซ้ำจากส่วนท้าย (tail recursion), การย้อนรอย (backtracking).