ขั้นตอนวิธี

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

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

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

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

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

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

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

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

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

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

 อ้างอิง 

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

 ดูเพิ่ม 
 วิทยาการคอมพิวเตอร์
 การคำนวณ
 ผังงาน (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)
 ความน่าสนใจ 

หมวดหมู่:คณิตตรรกศาสตร์
ขั้นตอนวิธี
หมวดหมู่:วิทยาการคอมพิวเตอร์เชิงทฤษฎี