|
ขั้นตอนวิธี
ในสาขาคณิตศาสตร์และวิทยาการคอมพิวเตอร์ ขั้นตอนวิธี หรือ อัลกอริทึม (อังกฤษ: algorithm) คือ ชุดลำดับคำสั่งที่ใช้แก้ลำดับชั้นปัญหาอย่างใดอย่างหนึ่ง หรือ ใช้ในการคำนวณเพื่อให้ได้ผลลัพธ์ทางคณิตศาสตร์ เป็นกระบวนการแก้ปัญหาที่สามารถอธิบายออกมาเป็นขั้นตอนที่ชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร กระบวนการนี้ ประกอบด้วย วิธีการเป็นขั้นๆ และ ส่วนที่ต้องวนซ้ำ (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
หมายเหตุ
ประวัติ คำว่า Algorithm มีที่มาจากชื่อของนักคณิตศาสตร์ชาวเปอร์เซียในยุคศตวรรษที่ 9 อะบู อับดิลลาหฺ อิบน มูซา อัลคอวาริซมีย์ (Abu Abdillah Muhammad ibn Musa al-Khawarizmi) คำว่า al-Khawarizmi ได้เพี้ยนเป็น Algoritmi เมื่องานเขียนของเขาได้รับการแปลเป็นภาษาละติน แล้วกลายเป็น Algorithm อัลกอริทึม ซึ่งใช้หมายถึงกฎที่ใช้ในการคิดคำนวณเลขคณิต และได้กลายมาเป็นคำ ขั้นตอนวิธี ในช่วงศตวรรษที่ 18 ในปัจจุบัน คำนี้ได้มีความหมายที่กว้างขึ้น หมายรวมถึง ขั้นตอนวิธีการในการแก้ปัญหาต่าง ๆ ขั้นตอนวิธีแรกสำหรับคอมพิวเตอร์นั้น เขียนขึ้นในปี ค.ศ. 1842 โดย เอดา ไบรอน ใน notes on the analytical engine ทำให้ถือกันว่า เอดาเป็นนักพัฒนาโปรแกรมหรือนักเขียนโปรแกรมคนแรกของโลก แต่เนื่องจาก ชาร์ลส แบบเบจ ไม่ได้สร้าง analytical engine จนเสร็จ ขั้นตอนวิธีของเอดานั้นจึงไม่ได้มีการใช้จริง ถึงแม้ว่าขั้นตอนวิธีนั้นเป็น ขั้นตอนวิธี การแก้ปัญหา ที่ถูกระบุไว้อย่างชัดเจน แต่ก็ขาดรูปแบบการวิเคราะห์ในรูปแบบจำลองทางคณิตศาสตร์ที่ชัดเจน ปัญหาในทางขั้นตอนวิธีนี้โดยส่วนมากจึงมักจะถูกวิเคราะห์โดยใช้ เครื่องจักรทัวริง ซึ่งเป็นแบบจำลองนามธรรมของคอมพิวเตอร์ คิดค้นขึ้นโดย แอลัน ทัวริง ซึ่งเป็นเครื่องจักรที่ใช้ในการจำลองการทำงานของขั้นตอนวิธีใด ๆ ราชบัณฑิตยสถาน ได้บัญญัติคำว่าอัลกอริทึม (Algorithm) เป็นภาษาไทยว่าขั้นตอนวิธี[1] ซึ่งมีความหมายคือ เป็นลำดับของขั้นตอนการคำนวณที่ใช้แก้ปัญหา โดยการเปลี่ยนข้อมูลนำเข้าของปัญหา (input) ออกมาเป็นผลลัพธ์ (output) ขั้นตอนวิธีดังกล่าวนั้นจะสามารถนำมาเขียนเป็นโปรแกรมในคอมพิวเตอร์ได้[2] การประยุกต์ใช้อัลกอริทึม อัลกอริทึมส่วนใหญ่มีจุดประสงค์เพื่อการเขียนโปรแกรมคอมพิวเตอร์ และจุดประสงค์อื่น ๆ ที่เกี่ยวข้องกับการออกแบบทางคอมพิวเตอร์ นอกเหนือจากการประยุกต์ใช้ทางวิทยาการคอมพิวเตอร์ ยังมีการใช้อัลกอริทึมกับการศึกษาโครงข่ายประสาททางชีววิทยา (เช่น การวิเคราะห์การทำงานของสมองมนุษย์และสมองสัตว์), วงจรไฟฟ้า และ ในเครื่องจักรกล อัลกอริทึมในระบบคอมพิวเตอร์ในระบบคอมพิวเตอร์ อัลกอริทึมคือการเขียนระบบตรรกะในซอฟต์แวร์ที่เขียนโดยนักพัฒนาซอฟต์แวร์ เพื่อให้มีประสิทธิภาพในการส่งออกเอาต์พุต (Output) จากอินพุต (Input) ที่คอมพิวเตอรืได้รับ โปรแกรมที่มีการเขียนอัลกอริทึมประสิทธิภาพสูง อาจรันในฮาร์ดแวร์รุ่นเก่าแล้วได้ผลลัพธ์ที่เร็วกว่าอัลกอริทึมที่ประสิทธิภาพต่ำว่า แต่รันบนฮาร์ดแวร์รุ่นใหม่ จากปัจจัยที่กล่าวมา อัลกอริทึมจึงถูกนับเป็นเทคโนโลยีรูปแบบหนึ่ง ไม่ยิ่งหย่อนไปกว่าฮาร์ดแวร์คอมพิวเตอร์ อ้างอิง
ดูเพิ่ม
|
