ขั้นตอนวิธี

ในสาขาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ ขั้นตอนวิธี หรือ อัลกอริทึม (อังกฤษ: algorithm) คือ ชุดลำดับคำสั่งที่ใช้แก้ลำดับชั้นปัญหาอย่างใดอย่างหนึ่ง หรือ ใช้ในการคำนวณเพื่อให้ได้ผลลัพธ์ทางคณิตศาสตร์ เป็นกระบวนการแก้ปัญหาที่สามารถอธิบายออกมาเป็นขั้นตอนที่ชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร  กระบวนการนี้ ประกอบด้วย วิธีการเป็นขั้นๆ และ ส่วนที่ต้องวนซ้ำ (loop) จนกระทั่งเสร็จสิ้นการทำงานและได้ผลลัพธ์  อัลกอริทึมที่ดีจะต้องมีความชัดเจนไม่คลุมเครือ การแก้ปัญหาโดยใช้อัลกอริทึมตรงข้ามกับการแก้ปัญหาโดยใช้สามัญสำนึก (ในทางวิทยาการคอมพิวเตอร์เรียกว่า การแก้ปัญหาแบบฮิวริสติก (heuristic)) ที่รับประกันคุณภาพความถูกต้องของคำตอบหรือความเร็วในการแก้ปัญหาไม่ได้

อัลกอริทึมสามารถใช้เขียนโปรแกรม เพื่อสั่งการคอมพิวเตอร์ให้ทำงานที่มอบหมายให้สำเร็จได้ ยกตัวอย่างเช่น การคำนวณทางคณิตศาสตร์, การประมวลผลข้อมูล, การให้เหตุผลโดยอัตโนมัติ และ งานอื่น ๆ ที่คอมพิวเตอร์สามารถทำได้

อัลกอริทึมเป็นวิธีการที่มีประสิทธิภาพ การเขียนอัลกอริทึมสามารถเขียนออกมาได้เป็นภาษาทางการ (formal language) โดยใช้ระยะเวลาและพื้นที่การเขียนที่จำกัด เพื่อที่จะคำนวณฟังก์ชันอย่างใดอย่างหนึ่ง เริ่มจากข้อความเริ่มต้น (initial state) และ อินพุตเริ่มต้น (initial input) ชุดคำสั่ง และพอผ่านข้อความคำสั่งต่าง ๆ ที่เรียงเป็นลำดับคำสั่งไว้แล้ว จะสามารถให้เอาต์พุตที่ต้องการได้ โดยทั่วไป อัลกอริทึม ประกอบด้วย วิธีการเป็นขั้น ๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน

ในการทำงานอย่างเดียวกัน อาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time) , และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน

การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง

หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้

1. ดูแต่ละจำนวนในรายการ ถ้ามันมีค่ามากกว่า จำนวนที่มีค่ามากที่สุดที่เราเคยพบจดค่ามันไว้
2. จำนวนที่เราจดไว้ตัวสุดท้าย จะเป็นจำนวนที่มีค่ามากที่สุด

และนี่คือรหัสเทียมสำหรับขั้นตอนวิธีนี้

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" เป็นการจบขั้นตอนวิธี และส่งค่าของตัวแปรที่ตามหลัง ออกไปยังขั้นตอนวิธีก่อนหน้าที่เรียกใช้

ประวัติ

อัลคอวาริซมีย์

คำว่า Algorithm มีที่มาจากชื่อของนักคณิตศาสตร์ชาวเปอร์เซียในยุคศตวรรษที่ 9 อะบู อับดิลลาหฺ อิบน มูซา อัลคอวาริซมีย์ (Abu Abdillah Muhammad ibn Musa al-Khawarizmi) คำว่า al-Khawarizmi ได้เพี้ยนเป็น Algoritmi เมื่องานเขียนของเขาได้รับการแปลเป็นภาษาละติน แล้วกลายเป็น Algorithm อัลกอริทึม ซึ่งใช้หมายถึงกฎที่ใช้ในการคิดคำนวณเลขคณิต และได้กลายมาเป็นคำ ขั้นตอนวิธี ในช่วงศตวรรษที่ 18 ในปัจจุบัน คำนี้ได้มีความหมายที่กว้างขึ้น หมายรวมถึง ขั้นตอนวิธีการในการแก้ปัญหาต่าง ๆ

ขั้นตอนวิธีแรกสำหรับคอมพิวเตอร์นั้น เขียนขึ้นในปี ค.ศ. 1842 โดย เอดา ไบรอน ใน notes on the analytical engine ทำให้ถือกันว่า เอดาเป็นนักพัฒนาโปรแกรมหรือนักเขียนโปรแกรมคนแรกของโลก แต่เนื่องจาก ชาร์ลส แบบเบจ ไม่ได้สร้าง analytical engine จนเสร็จ ขั้นตอนวิธีของเอดานั้นจึงไม่ได้มีการใช้จริง

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

ราชบัณฑิตยสถาน ได้บัญญัติคำว่าอัลกอริทึม (Algorithm) เป็นภาษาไทยว่าขั้นตอนวิธี ซึ่งมีความหมายคือ เป็นลำดับของขั้นตอนการคำนวณที่ใช้แก้ปัญหา โดยการเปลี่ยนข้อมูลนำเข้าของปัญหา (input) ออกมาเป็นผลลัพธ์ (output) ขั้นตอนวิธีดังกล่าวนั้นจะสามารถนำมาเขียนเป็นโปรแกรมในคอมพิวเตอร์ได้

การประยุกต์ใช้อัลกอริทึม

อัลกอริทึมชื่อว่า Logical NAND ใช้ในการทำงานของชิป 7400

อัลกอริทึมส่วนใหญ่มีจุดประสงค์เพื่อการเขียนโปรแกรมคอมพิวเตอร์ และจุดประสงค์อื่น ๆ ที่เกี่ยวข้องกับการออกแบบทางคอมพิวเตอร์ นอกเหนือจากการประยุกต์ใช้ทางวิทยาการคอมพิวเตอร์ ยังมีการใช้อัลกอริทึมกับการศึกษาโครงข่ายประสาททางชีววิทยา (เช่น การวิเคราะห์การทำงานของสมองมนุษย์และสมองสัตว์), วงจรไฟฟ้า และ ในเครื่องจักรกล

อัลกอริทึมในระบบคอมพิวเตอร์

ในระบบคอมพิวเตอร์ อัลกอริทึมคือการเขียนระบบตรรกะในซอฟต์แวร์ที่เขียนโดยนักพัฒนาซอฟต์แวร์ เพื่อให้มีประสิทธิภาพในการส่งออกเอาต์พุต (Output) จากอินพุต (Input) ที่คอมพิวเตอรืได้รับ โปรแกรมที่มีการเขียนอัลกอริทึมประสิทธิภาพสูง อาจรันในฮาร์ดแวร์รุ่นเก่าแล้วได้ผลลัพธ์ที่เร็วกว่าอัลกอริทึมที่ประสิทธิภาพต่ำว่า แต่รันบนฮาร์ดแวร์รุ่นใหม่ จากปัจจัยที่กล่าวมา อัลกอริทึมจึงถูกนับเป็นเทคโนโลยีรูปแบบหนึ่ง ไม่ยิ่งหย่อนไปกว่าฮาร์ดแวร์คอมพิวเตอร์

อ้างอิง

• ปัญหาและการแก้ปัญหาด้วยคอมพิวเตอร์ เก็บถาวร 2008-04-10 ที่ เวย์แบ็กแมชชีน วิชาการ.คอม - อธิบายขั้นตอนวิธีแบบต่าง ๆ พร้อมตัวอย่างปัญหาประกอบ

ดูเพิ่ม

• วิทยาการคอมพิวเตอร์
• การคำนวณ
• ผังงาน (Flow Chart)
• รายชื่อขั้นตอนวิธี (List of algorithms)
  • en:Bulletproof algorithms
  • ขั้นตอนวิธีการเรียงลำดับ
  • ขั้นตอนวิธีการค้นหา
  • ขั้นตอนวิธีการประสาน (en:Merge algorithms)
  • ขั้นตอนวิธีสายอักขระ (en:String algorithms)
  • ขั้นตอนวิธีเชิงพันธุกรรม (Genetic Algorithms)
  • ขั้นตอนวิธีแบบสุ่ม
  • ขั้นตอนวิธีการประมาณ
  • ขั้นตอนวิธีโรห์ของพอลลาร์ด (en:Pollard's rho algorithm)
  • ขั้นตอนวิธีการค้นหาคำแบบซี (Z-Algorithm)
• เส้นเวลาของขั้นตอนวิธี en:Timeline of algorithms
• ตรรกะสำหรับคอมพิวเตอร์ en:Computability logic
• โครงสร้างข้อมูล (Data structure)
• ความน่าสนใจ เก็บถาวร 2019-08-20 ที่ เวย์แบ็กแมชชีน