ผลต่างระหว่างรุ่นของ "ขั้นตอนวิธี"
เนื้อหาที่ลบ เนื้อหาที่เพิ่ม
ไม่มี ป้ายระบุ: ถูกแทน blanking การแก้ไขแบบเห็นภาพ |
ล ย้อนการแก้ไขที่อาจเป็นการทดลอง หรือก่อกวนด้วยบอต ไม่ควรย้อน? แจ้งที่นี่ |
||
บรรทัด 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 ความน่าสนใจ]
[[หมวดหมู่:คณิตตรรกศาสตร์]]
| |||