ขั้นตอนวิธี

ขั้นตอนวิธี (algorithm)

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

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

อัลควาริชมี (al-Khwarizmi) คือใคร

อัลควาริชมี (al-Khwarizmi) หรือ มูฮัมหมัด อิบนุ มูซา (Muhammad Ibn Musa) นักคณิตศาสตร์ นักดาราศาสตร์ชาวเปอร์เซีย เป็นผู้คิดค้นวิชาพีชคณิต (Algebra) และอัลกอริทึม (algorithm) ซึ่งหนังสือของเขาได้รับการแปลเป็นภาษาละตินในคริสตศวรรษที่ 12 และช่วยเชื่อมโยงคณิตศาสตร์ของฮินดู อาหรับและกรีกเข้าด้วยกัน และเป็นพื้นฐานการพัฒนาคณิตศาสตร์ในยุโรปในเวลาต่อมา

ผลงานของอัลควาริชมี (al-Khwarizmi) ได้แก่

1) เขียนตำราชื่อ กิตาบ ซูรอต อัล อัรฎ (Kitab Surat al Aeb) เป็นตำราเกี่ยวกับแผนที่เล่มแรกในคริศตวรรษที่ 9

2) เขียนตำราพีชคณิตที่ชื่อ หิซาบ อัล ญับร วะ อัล มุกอบะละฮ (Hisab al Jabr we al Muqabalah) หรือ (Algebra) ที่หมายถึง การคืนค่า (Restoring) ซึ่งเป็นกระบวนการที่ทำให้ค่าทั้งสองข้างของสมการมีค่าเท่ากัน เป็นต้น

คุณสมบัติของอัลกอริทึม

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

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

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

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

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

5. อัลกอริทึมต้องมีจุดสุดท้ายของการทำงาน : คุณสมบัติอีกข้อหนึ่งที่สำคัญคืออัลกอริทึมต้องมีจุดสุดท้ายของการทำงาน เนื่องจากเครื่องคอมพิวเตอร์ไม่สามารถประมวลผลไปเรื่อย ๆ (infinite) โดยต้องมีจุดสุดท้ายของการทำงานเช่น การบวกเลขจำนวนเต็มครั้งละหนึ่งค่าไปเรื่อย ๆ ในที่นี่จะไม่เป็นอัลกอริทึม เนื่องจากไม่ได้ บอกจุดสุดท้ายของตัวเลขจำนวนเต็ม ดังนั้นจึงเป็นขั้นตอนการทำงานที่ไม่มีจุดสิ้นสุด

จุดประสงค์การเขียนอัลกอริทึม

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

กิจกรรม

ให้นักเรียนวาดรูปในกระดาษตามขั้นตอนวิธี ดังนี้

1. วาดรูปสี่เหลี่ยมมุมฉากให้มีด้านขนาดกับแกน x และ y ให้มีจุดมุมซ้ายล่างที่พิกัด (5,0) มุมขวาบนที่พิกัด (15,10)

2. วาดส่วนของเส้นตรงระหว่างจุดต่อไปนี้

(5,10) และ (10,14)

(10,14) และ (15,10)

(15,0) และ (21,1)

(21,1) และ (21,11)

(21,11) และ (15,10)

(10,14) และ (16,15)

(16,15) และ (21,11)

3. วาดรูปสี่เหลี่ยมมุมฉากให้มีด้านขนาดกับแกน x และ y ให้มีจุดมุมซ้ายล่างที่พิกัด (8,0) มุมขวาบนที่พิกัด (12,5)

เมื่อทำตามขั้นตอนวิธีเสร็จเรียบร้อยแล้ว ให้นักเรียนเปรียบเทียบรูปที่ได้กับเพื่อนว่าเหมือนหรือแตกต่างกันอย่างไร เพราะเหตุใด