ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธี"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มีความย่อการแก้ไข ป้ายระบุ: แก้ไขขั้นสูงด้วยอุปกรณ์เคลื่อนที่ |
ไม่มี ป้ายระบุ: ถูกแทน การแก้ไขแบบเห็นภาพ blanking |
||
บรรทัด 1: | บรรทัด 1: | ||
{{ลิงก์ไปภาษาอื่น}} |
{{ลิงก์ไปภาษาอื่น}} |
||
'''ขั้นตอนวิธี''' หรือ'''อัลกอริทึม''' ({{lang-en|algorithm}}) หมายถึง กระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือ[[ฮิวริสติก (วิทยาการคอมพิวเตอร์)|ฮิวริสติก]] (heuristic) |
|||
* |
|||
โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ ([[:en:iterate|iterate]]) หรือ [[ความสัมพันธ์เวียนเกิด|เวียนเกิด]] (recursive) โดยใช้[[ตรรกะ]] (logic) และ/หรือ ในการเปรียบเทียบ ([[:en:comparison|comparison]]) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน |
|||
ในการทำงานอย่างเดียวกัน อาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time) , และขนาด[[หน่วยความจำ]] (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน ([[:en:complexity|complexity]]) ต่างกัน |
|||
การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียน[[โปรแกรมคอมพิวเตอร์]] แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบ[[วงจรไฟฟ้า]], การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง |
|||
หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้ |
|||
# ดูแต่ละจำนวนในรายการ ถ้ามันมีค่ามากกว่า จำนวนที่มีค่ามากที่สุดที่เราเคยพบจดค่ามันไว้ |
|||
# จำนวนที่เราจดไว้ตัวสุดท้าย จะเป็นจำนวนที่มีค่ามากที่สุด |
|||
และนี่คือ[[รหัสเทียม]]สำหรับขั้นตอนวิธีนี้ |
|||
'''Algorithm''' LargestNumber Output: จำนวนเต็มที่มีค่ามากที่สุดในรายการ. |
|||
Input: รายการจำนวนเต็ม. |
|||
''largest'' ← -∞ |
|||
'''for each''' ''item'' '''in''' รายการ, '''do''' |
|||
'''if''' the ''item'' > ''largest'', '''then''' |
|||
''largest'' ← the ''item'' |
|||
'''return''' ''largest'' |
|||
หมายเหตุ |
|||
* "←" หมายถึง[[การกำหนดค่า]] (assignment) ให้ตัวแปร เช่น "''largest'' ← the ''item''" หมายความว่า ให้ ''largest'' มีค่าเป็น ''item'' |
|||
* "'''return'''" เป็นการจบขั้นตอนวิธี และส่งค่าของตัวแปรที่ตามหลัง ออกไปยังขั้นตอนวิธีก่อนหน้าที่เรียกใช้ |
|||
== ประวัติ == |
|||
[[ไฟล์:447px-Abu Abdullah Muhammad bin Musa al-Khwarizmi.jpg|thumb|150px|อัลคอวาริซมีย์]] |
|||
คำว่า ''Algorithm'' มีที่มาจากชื่อของนักคณิตศาสตร์[[เปอร์เซีย|ชาวเปอร์เซีย]]ในยุคศตวรรษที่ 9 อะบู อับดิลลาหฺ อิบน มูซา [[อัลคอวาริซมีย์]] (Abu Abdillah Muhammad ibn Musa al-Khawarizmi) คำว่า al-Khawarizmi ได้เพี้ยนเป็น Algoritmi เมื่องานเขียนของเขาได้รับการแปลเป็นภาษาละติน แล้วกลายเป็น Algorithm ''อัลกอริทึม'' ซึ่งใช้หมายถึงกฎที่ใช้ในการคิดคำนวณเลขคณิต และได้กลายมาเป็นคำ ''ขั้นตอนวิธี'' ในช่วงศตวรรษที่ 18. ในปัจจุบัน คำนี้ได้มีความหมายที่กว้างขึ้น หมายรวมถึง ขั้นตอนวิธีการในการแก้ปัญหาต่างๆ |
|||
ขั้นตอนวิธีแรกสำหรับ[[คอมพิวเตอร์]]นั้น เขียนขึ้นในปี [[ค.ศ. 1842]] โดย [[เอดา ไบรอน]] ใน [[:en:Ada Byron's notes on the analytical engine|notes on the analytical engine]] ทำให้ถือกันว่า เอดาเป็นนักพัฒนาโปรแกรมหรือ[[นักเขียนโปรแกรม]]คนแรกของโลก แต่เนื่องจาก [[ชาร์ลส แบบเบจ]] ไม่ได้สร้าง [[analytical engine]] จนเสร็จ ขั้นตอนวิธีของเอดานั้นจึงไม่ได้มีการใช้จริง |
|||
ถึงแม้ว่าขั้นตอนวิธีนั้นเป็น ขั้นตอนวิธี การแก้ปัญหา ที่ถูกระบุไว้อย่างชัดเจน แต่ก็ขาดรูปแบบการวิเคราะห์ในรูปแบบจำลองทางคณิตศาสตร์ที่ชัดเจน ปัญหาในทางขั้นตอนวิธีนี้โดยส่วนมากจึงมักจะถูกวิเคราะห์โดยใช้ [[เครื่องจักรทัวริง]] ซึ่งเป็นแบบจำลองนามธรรมของคอมพิวเตอร์ คิดค้นขึ้นโดย [[แอลัน ทัวริง]] ซึ่งเป็นเครื่องจักรที่ใช้ในการจำลองการทำงานของขั้นตอนวิธีใดๆ |
|||
[[ราชบัณฑิตยสถาน]] ได้บัญญัติคำว่า'''อัลกอริทึม''' (Algorithm) เป็นภาษาไทยว่า'''ขั้นตอนวิธี'''<ref> |
|||
ราชบัณฑิตยสถาน, พจนานุกรม ฉบับราชบัณฑิตยสถาน พ.ศ. ๒๕๔๖, 2546, หน้า 5</ref> ซึ่งมีความหมายคือ เป็นลำดับของขั้นตอนการคำนวณที่ใช้แก้ปัญหา โดยการเปลี่ยน''ข้อมูลนำเข้า''ของปัญหา (input) ออกมาเป็น''ผลลัพธ์'' (output) ขั้นตอนวิธีดังกล่าวนั้นจะสามารถนำมาเขียนเป็นโปรแกรมในคอมพิวเตอร์ได้<ref>สมชาย ประสิทธิ์จูตระกูล, การออกแบบและวิเคราะห์อัลกอริทึม, 2545, หน้า 1</ref> |
|||
{{clear}} |
|||
== อ้างอิง == |
|||
{{รายการอ้างอิง}} |
|||
{{เริ่มอ้างอิง}} |
|||
* [http://www.vcharkarn.com/vlesson/7 ปัญหาและการแก้ปัญหาด้วยคอมพิวเตอร์] [[วิชาการ.คอม]] - อธิบายขั้นตอนวิธีแบบต่าง ๆ พร้อมตัวอย่างปัญหาประกอบ |
|||
{{จบอ้างอิง}} |
|||
== ดูเพิ่ม == |
|||
* [[วิทยาการคอมพิวเตอร์]] |
|||
* [[การคำนวณ]] |
|||
* [[ผังงาน]] (Flow Chart) |
|||
* [[รายชื่อขั้นตอนวิธี]] ([[:en:List of algorithms|List of algorithms]]) |
|||
** [[:en:Bulletproof algorithm]]s |
|||
** [[ขั้นตอนวิธีการเรียงลำดับ]] |
|||
** [[ขั้นตอนวิธีการค้นหา]] |
|||
** [[ขั้นตอนวิธีการประสาน]] ([[:en:Merge algorithm]]s) |
|||
** [[ขั้นตอนวิธีสายอักขระ]] ([[:en:String algorithms]]) |
|||
** [[ขั้นตอนวิธีเชิงพันธุกรรม]] (Genetic Algorithms) |
|||
** [[ขั้นตอนวิธีแบบสุ่ม]] |
|||
** [[ขั้นตอนวิธีการประมาณ]] |
|||
** [[ขั้นตอนวิธีโรห์ของพอลลาร์ด]] ([[:en:Pollard's rho algorithm]]) |
|||
** [[ขั้นตอนวิธีการค้นหาคำแบบซี (Z-Algorithm)]] |
|||
* [[เส้นเวลาของขั้นตอนวิธี]] [[:en:Timeline of algorithms]] |
|||
* ตรรกะสำหรับคอมพิวเตอร์ [[:en:Computability logic]] |
|||
* [[โครงสร้างข้อมูล]] (Data structure) |
|||
* [https://nungg.com ความน่าสนใจ] |
|||
[[หมวดหมู่:คณิตตรรกศาสตร์]] |
[[หมวดหมู่:คณิตตรรกศาสตร์]] |
รุ่นแก้ไขเมื่อ 13:55, 29 ตุลาคม 2562
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |