 |
del.icio.us |
 |
Digg |
 |
Furl |
 |
|
 |
Rojo |
| Add to OnlyWire |
ขั้นตอนวิธี หรือ อัลกอริทึม (algorithm) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic)
โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive)โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน
ในการทำงานอย่างเดียวกัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time) , และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน
การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง
เนื้อหา |
ตัวอย่าง
หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้
- ดูแต่ละจำนวนในรายการ ถ้ามันมีค่ามากกว่า จำนวนที่มีค่ามากที่สุดที่เราเคยพบเจอ ให้จดค่ามันไว้
- จำนวนที่เราจดไว้ตัวสุดท้าย จะเป็นจำนวนที่มีค่ามากที่สุด
และนี่คือรหัสเทียมสำหรับขั้นตอนวิธีนี้
Algorithm LargestNumber
Input: รายการจำนวนเต็ม.
Output: จำนวนเต็มที่มีค่ามากที่สุดในรายการ.
largest ← -∞
for each item in รายการ, do
if the item > largest, then
largest ← the item
return largest
หมายเหตุ:
- "←" เป็นเครื่องหมายแทนคำว่า "ให้มีค่าเป็น" เช่น "largest ← the item" หมายความว่า ให้ largest มีค่าเป็น item
- "return" เป็นการจบขั้นตอนวิธี และส่งค่าของตัวแปรที่ตามหลัง ออกไปยังขั้นตอนวิธีก่อนหน้าที่เรียกใช้
ประวัติ
คำว่า Algorithm มีที่มาจากชื่อของนักคณิตศาสตร์ชาวเปอร์เซียในยุคศตวรรษที่ 9 อะบู อับดิลลาหฺ บิน มูซา อัลคอวาริซมีย์ (Abu Abdillah Muhammad bin Musa al-Khawarizmi) คำว่า al-Khawarizmi ได้เพี้ยนเป็น Algoritmi เมื่องานเขียนของเขาได้รับการแปลเป็นภาษาละติน แล้วกลายเป็น Algorithm อัลกอริทึม ซึ่งใช้หมายถึงกฎที่ใช้ในการคิดคำนวณเลขคณิต และได้กลายมาเป็นคำ ขั้นตอนวิธี ในช่วงศตวรรษที่ 18. ในปัจจุบัน คำนี้ได้มีความหมายที่กว้างขึ้น หมายรวมถึง ขั้นตอนวิธีการในการแก้ปัญหาต่างๆ
ขั้นตอนวิธีแรกสำหรับคอมพิวเตอร์นั้น เขียนขึ้นในปี ค.ศ. 1842 โดย เอดา ไบรอน ใน notes on the analytical engine ทำให้ถือกันว่า เอดาเป็นนักพัฒนาโปรแกรมหรือโปรแกรมเมอร์คนแรกของโลก แต่เนื่องจาก ชาร์ลส แบบเบจ ไม่ได้สร้าง analytical engine จนเสร็จ ขั้นตอนวิธีของเอดานั้นจึงไม่ได้มีการใช้จริง
ถึงแม้ว่าขั้นตอนวิธีนั้นเป็น ขั้นตอนวิธี การแก้ปัญหา ที่ถูกระบุไว้อย่างชัดเจน แต่ก็ขาดรูปแบบการวิเคราะห์ในรูปแบบจำลองทางคณิตศาสตร์ที่ชัดเจน ปัญหาในทางขั้นตอนวิธีนี้โดยส่วนมากจึงมักจะถูกวิเคราะห์โดยใช้ เครื่องจักรทัวริง ซึ่งเป็นแบบจำลองนามธรรมของคอมพิวเตอร์ คิดค้นขึ้นโดย แอลัน ทัวริง ซึ่งเป็นเครื่องจักรที่ใช้ในการจำลองการทำงานของขั้นตอนวิธีใดๆ
ดูเพิ่ม
- วิทยาการคอมพิวเตอร์
- การคำนวณ
- แผนภูมิสายงาน (Flow Chart)
- รายชื่อขั้นตอนวิธี (List of algorithms)
- เส้นเวลาของขั้นตอนวิธี en:Timeline of algorithms
- ตรรกะสำหรับคอมพิวเตอร์ en:Computability logic
- โครงสร้างข้อมูล (Data structure)
อ้างอิง
- รายการผลงานวิชาการสำคัญเกี่ยวกับขั้นตอนวิธี (ภาษาอังกฤษ)
- ปัญหาและการแก้ปัญหาด้วยคอมพิวเตอร์ วิชาการ.คอม - อธิบายขั้นตอนวิธีแบบต่าง ๆ พร้อมตัวอย่างปัญหาประกอบ
 |
ขั้นตอนวิธี เป็นบทความเกี่ยวกับ คณิตศาสตร์ ที่ยังไม่สมบูรณ์ ต้องการตรวจสอบ เพิ่มเนื้อหา หรือเพิ่มแหล่งอ้างอิง คุณสามารถช่วยเพิ่มเติมหรือแก้ไข เพื่อให้สมบูรณ์มากขึ้น ข้อมูลเกี่ยวกับ ขั้นตอนวิธี ในภาษาอื่น อาจสามารถหาอ่านได้จากเมนู ภาษาอื่น ด้านซ้ายมือ หรือ ดูเพิ่มที่ สถานีย่อย:คณิตศาสตร์ |
 |
ขั้นตอนวิธี เป็นบทความเกี่ยวกับ คอมพิวเตอร์ อุปกรณ์คอมพิวเตอร์ หรือ เครือข่าย ที่ยังไม่สมบูรณ์ ต้องการตรวจสอบ เพิ่มเนื้อหา หรือเพิ่มแหล่งอ้างอิง คุณสามารถช่วยเพิ่มเติมหรือแก้ไข เพื่อให้สมบูรณ์มากขึ้น ข้อมูลเกี่ยวกับ ขั้นตอนวิธี ในภาษาอื่น อาจสามารถหาอ่านได้จากเมนู ภาษาอื่น ด้านซ้ายมือ หรือ ดูเพิ่มที่ สถานีย่อย:เทคโนโลยีสารสนเทศ |
