กลับไปหน้าบทความ

อ่าน 1 นาที

แบบจำลองการคำนวณ

ใน วิทยาการคอมพิวเตอร์ และโดยเฉพาะอย่างยิ่งใน ทฤษฎีความสามารถในการคำนวณ และ ทฤษฎีความซับซ้อนของการคำนวณ แบบจำลองการคำนวณ คือ แบบจำลองที่อธิบายว่าผลลัพธ์ของ ฟังก์ชันทางคณิตศาสตร์...

แบบจำลองการคำนวณ

ในวิทยาการคอมพิวเตอร์และโดยเฉพาะอย่างยิ่งในทฤษฎีความสามารถในการคำนวณและทฤษฎีความซับซ้อนของการคำนวณแบบจำลองการคำนวณ คือ แบบจำลองที่อธิบายว่าผลลัพธ์ของฟังก์ชันทางคณิตศาสตร์ถูกคำนวณอย่างไรเมื่อได้รับอินพุต แบบจำลองการคำนวณอธิบายว่าหน่วยการคำนวณ หน่วยความจำ และการสื่อสารถูกจัดระเบียบอย่างไร[ 1 ]ความซับซ้อนของการคำนวณของอัลกอริทึมสามารถวัดได้เมื่อกำหนดแบบจำลองการคำนวณ การใช้แบบจำลองช่วยให้สามารถศึกษาประสิทธิภาพของอัลกอริทึมได้อย่างอิสระจากความแปรผันที่เฉพาะเจาะจงกับการใช้งาน เฉพาะ และเทคโนโลยีเฉพาะ

หมวดหมู่

แบบจำลองการคำนวณสามารถจำแนกได้เป็นสามประเภท ได้แก่ แบบจำลองเชิงลำดับ แบบจำลองเชิงฟังก์ชัน และแบบจำลองเชิงขนาน

แบบจำลองลำดับ

แบบจำลองเชิงลำดับประกอบด้วย:

แบบจำลองเชิงฟังก์ชัน

แบบจำลองการทำงานประกอบด้วย:

แบบจำลองพร้อมกัน

รูปแบบการใช้งานพร้อมกัน ได้แก่:

แบบจำลองเหล่านี้บางส่วนมีทั้ง แบบ กำหนดได้และ แบบ ไม่กำหนดได้แบบจำลองแบบไม่กำหนดได้ถูกนำมาใช้ในการศึกษาความซับซ้อนในการคำนวณของอัลกอริทึม

แบบจำลองแต่ละแบบมีความแตกต่างกันในด้านความสามารถในการแสดงผล ตัวอย่างเช่น ฟังก์ชันทุกฟังก์ชันที่สามารถคำนวณได้ด้วยเครื่องสถานะจำกัดก็สามารถคำนวณได้ด้วยเครื่องทัวริง เช่นกัน แต่ในทางกลับกันนั้นทำไม่ได้

การใช้งาน

ในสาขาการวิเคราะห์เวลาการทำงานของอัลกอริทึมเป็นเรื่องปกติที่จะระบุแบบจำลองการคำนวณในแง่ของการดำเนินการพื้นฐานที่อนุญาตซึ่งมีต้นทุนต่อหน่วย หรือเรียกง่ายๆ ว่าการดำเนินการที่มีต้นทุนต่อหน่วยตัวอย่างที่ใช้กันทั่วไปคือเครื่องเข้าถึงแบบสุ่ม (random-access machine ) ซึ่งมีต้นทุนต่อหน่วยสำหรับการอ่านและการเขียนข้อมูลในเซลล์หน่วยความจำทั้งหมด ในแง่นี้ มันแตกต่างจากแบบจำลองเครื่องทัวริงที่กล่าวถึงข้างต้น

ดูเพิ่มเติม

อ่านเพิ่มเติม

  • เฟอร์นันเดซ, มาริเบล (2009). แบบจำลองการคำนวณ: บทนำสู่ทฤษฎีความสามารถในการคำนวณ . หัวข้อระดับปริญญาตรีในวิทยาการคอมพิวเตอร์. สปริงเกอร์. ISBN 978-1-84882-433-1.
  • Savage, John E. (1998). แบบจำลองของการคำนวณ: สำรวจพลังของการคำนวณ . Addison-Wesley. ISBN 978-0201895391.
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Model_of_computation&oldid=1332452856 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ แบบจำลองการคำนวณ

ใน วิทยาการคอมพิวเตอร์ และโดยเฉพาะอย่างยิ่งใน ทฤษฎีความสามารถในการคำนวณ และ ทฤษฎีความซับซ้อนของการคำนวณ แบบจำลองการคำนวณ คือ แบบจำลองที่อธิบายว่าผลลัพธ์ของ ฟังก์ชันทางคณิตศาสตร์...

หมวดหมู่

แบบจำลองการคำนวณสามารถจำแนกได้เป็นสามประเภท ได้แก่ แบบจำลองเชิงลำดับ แบบจำลองเชิงฟังก์ชัน และแบบจำลองเชิงขนาน

การใช้งาน

ในสาขา การวิเคราะห์เวลาการทำงานของอัลกอริทึม เป็นเรื่องปกติที่จะระบุแบบจำลองการคำนวณในแง่ของ การดำเนินการพื้นฐาน ที่อนุญาตซึ่งมีต้นทุนต่อหน่วย หรือเรียกง่ายๆ ว่า การดำเนินการที่มีต้นทุนต่อหน่วย ตัวอย่างที่ใช้กันทั่วไปคือ เครื่องเข้าถึงแบบสุ่ม (random-access...

ดูเพิ่มเติม

เครื่องจักรเรียงซ้อน (เครื่องจักรแบบไม่มีตัวดำเนินการ) เครื่องจักรสะสมพลังงาน (เครื่องจักรแบบตัวดำเนินการเดียว) เครื่องลงทะเบียน (เครื่องตัวดำเนินการ 2, 3, ...