อัลกอริทึมเบื้องต้น
อัลกอริทึม มีที่มาจากชื่อของนักคณิตศาสตร์ชาวเปอร์เซียในยุคศตวรรษที่ 9 ชื่ออะบู อับดิลลาห์ มูฮัมหมัด บิน มูซา อัลคอวาริซมีย์ (Abu Abdillah Muhammad binMusa al-Khawarizmi) คำว่าอัลคอวาริซมีย์ (al-Khawarizmi)ได้เพี้ยนเป็นอัลกอริทมี (Algoritmi)เมื่องานเขียนของเขาได้รับการแปลเป็นภาษาละติน แล้วกลายเป็นอัลกอริทึม(Algorithm) ซึ่งหมายถึงกฎที่ใช้ในการคิดคำนวณเลขคณิตในช่วงศตวรรษที่ 18 ในปัจจุบันคำนี้ได้มีความหมายที่กว้างขึ้นโดยหมายรวมถึงขั้นตอนวิธีการในการแก้ปัญหาต่าง ๆ มีนักการศึกษา นักวิชาการ ให้ความหมายของคำว่า อัลกอริทึม (Algorithm) ไว้หลายท่าน ดังนี้
ราชบัณฑิตยสถานได้บัญญัติศัพท์คำว่า “Algorithm” ใช้คำว่า “ขั้นตอนวิธี” หมายถึง ขั้นตอนวิธีการแก้ปัญหาเชิงคำนวณด้วยคอมพิวเตอร์
อัลกอริทึม (Algorithm) หมายถึง ขั้นตอนหรือลำดับการประมวลผลในการแก้ปัญหาใดปัญหาหนึ่งซึ่งจะช่วยให้ผู้พัฒนาโปรแกรมเห็นขั้นตอนการเขียนโปรแกรมอย่างง่ายขึ้น
อัลกอริทึม (Algorithm) หมายถึง แนวคิดอย่างมีเหตุผลที่ผู้เขียนโปรแกรมใช้ในการอธิบายวิธีการอย่างเป็นขั้นตอนตามลำดับในการที่จะพัฒนาโปรแกรมนั้น ๆ เพื่อตรวจสอบขั้นตอนต่าง ๆ ในการทำงานและความถูกต้องในแต่ละขั้นตอน
อัลกอริทึม (Algorithm) คือ กระบวนการแก้ปัญหาที่สามารถอธิบายออกมาเป็นขั้นตอนที่ชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร กระบวนการนี้ประกอบด้วยจะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำอีก จนกระทั่งเสร็จสิ้นการทำงาน (http://mindphp.com)
ภาพที่ 1 บทเรียนอัลกอริทึมเบื้องต้น
ที่มา : วัชรพัฒน์ ศรีคำเวียง
จากที่กล่าวมาข้างต้น สรุปได้ว่า อัลกอริทึม (Algorithm) หมายถึง กระบวนการทำงานอย่างใดอย่างหนึ่ง ที่มีลำดับการทำงานเป็นขั้นเป็นตอนชัดเจน และปฏิบัติตามขั้นตอนแล้วได้ผลลัพธ์ที่ถูกต้อง
ซึ่งในการเริ่มต้นในการเขียนโปรแกรมอัลกอริทึมมีความสำคัญเป็นอย่างมากเพราะ เป็นการจัดลำดับขั้นตอนวิธีการแก้ปัญหาหรือจัดการความคิดให้เป็นขั้นตอนต่าง ๆ เพื่อแก้ไขปัญหาในขั้นตอนการเขียนโปรแกรมที่สอดคล้องกรรมวิธีแก้ปัญหาที่กำหนดไว้ การเขียนอัลกอริทึมจึงเป็นการแสดงลำดับการทำงานตามคุณสมบัติด้านการประมวลผลของคอมพิวเตอร์ ที่พร้อมจะนำไปแปลงเป็นลำดับคำสั่งให้คอมพิวเตอร์ทำงาน การเขียนโปรแกรมคอมพิวเตอร์ด้วยภาษาที่เหมาะสม เพื่อสั่งให้คอมพิวเตอร์ทำงานตามอัลกอริทึมที่กำหนดไว้ และการเขียนอัลกอริทึมออกมาให้ตรวจสอบความถูกต้องได้ครบถ้วนขึ้น
หลักการเขียนอัลกอริทึม
กระบวนการสำคัญเริ่มต้นที่จุดจุดเดียวในการมีจุดเริ่มต้นหลายที่จะทำให้กระบวนการวิธีสับสน จนในที่สุดอาจทำให้ผลลัพธ์ที่ได้ไม่ตรงกับความต้องการ หรืออาจทำให้อัลกอริทึมนั้นไม่สามารถทำงานได้เลย
กำหนดการทำงานเป็นขั้นเป็นตอนอย่างชัดเจน การกำหนดอัลกอริทึมที่ดีควรมีขั้นตอนที่ชัดเจนไม่คลุมเครือ เสร็จจากขั้นตอนหนึ่ง ไปยังขั้นตอนที่สองมีเงื่อนไขการทำงานอย่างไร ควรกำหนดให้ชัดเจน
การทำงานแต่ละขั้นตอนควรสั้นกระชับ เพราะการกำหนดขั้นตอนการทำงานให้สั้นกระชับนอกจากจะทำให้โปรแกรมทำงานได้รวดเร็วแล้ว ยังเป็นประโยชน์ต่อผู้อื่นที่มาพัฒนาโปรแกรมต่อด้วยเพราะสามารถศึกษาอัลกอริทึมจากโปรแกรมที่เขียนไว้ได้ง่าย
ผลลัพธ์ในแต่ละขั้นตอนควรต่อเนื่องกัน การออกแบบขั้นตอนที่ดีนั้นผลลัพธ์จากขั้นตอนแรกควรเป็นข้อมูลสำหรับนำเข้า ให้กับข้อมูลในขั้นต่อไป ต่อเนื่องกันไปจนกระทั่งได้ผลลัพธ์ตามที่ต้องการ
การออกแบบอัลกอริทึมที่ดี ควรออกแบบให้ครอบคลุมการทำงานในหลายรูปแบบ เช่น การออกแบบโดยคิดไว้ล่วงหน้าว่าหากผู้ใช้โปรแกรมป้อนข้อมูลเข้าผิดประเภท โปรแกรมจะมีการเตือนว่าผู้ใช้งานมีการใส่ข้อมูลที่ผิดประเภทโดยโปรแกรมจะไม่รับข้อมูลนั้น เพื่อให้ใส่ข้อมูลใหม่อีกครั้ง เพื่อป้องกันการเกิดจุดบกพร่องของโปรแกรมได้
ประโยชน์ของอัลกอริทึม
ประโยชน์ของอัลกอริทึม (Algorithm) คือ ทำให้ไม่สับสนกับวิธีดำเนินงาน เพราะทุกอย่างจะถูกจัดเรียงเป็นขั้นตอนมีวิธีการและทางเลือกไว้ให้ เมื่อนำมาใช้จะทำให้การทำงานสำเร็จอย่างรวดเร็ว ทำให้ปัญหาลดลงหรือสามารถค้นหาต้นเหตุของปัญหาได้อย่างรวดเร็ว เนื่องจากกระบวนการถูกแยกแยะกิจกรรม ขั้นตอน และความสัมพันธ์ ออกมาให้เห็นอย่างชัดเจน
รูปแบบการเขียนอัลกอริทึม
การเขียนอัลกอริทึมมีหลายรูปแบบ โดยผู้เขียนสามารถใช้อัลกอริทึมหลายรูปแบบประกอบกันในการออกแบบอัลกอริทึมนั้นเพื่อใช้ในการแก้ปัญหาการเขียนโปรแกรมได้
1.แบบลำดับ (Sequential) มีลักษณะการทำงานจะเป็นไปตามขั้นตอน ก่อน-หลัง ต่อเนื่องกันไปเป็นลำดับ โดยการทำงานแต่ละขั้นตอนต้องทำให้เสร็จก่อน แล้วจึงไปทำขั้นตอนต่อไป
ตัวอย่างเช่น อัลกอริทึมแบบลำดับ การทอดไข่เจียว
เริ่มต้น
หยิบไข่ไก่
ตอกไข่ไก่ใส่ภาชนะ
ปรุงรส ด้วยเครื่องปรุง
ตีไข่ด้วยช้อนส้อม
ตั้งกระทะบนเตา
เปิดแก๊ส และติดไฟ
ใส่น้ำมันพืช
นำไข่ที่ปรุงรสแล้วใส่ลงในกระทะที่ร้อน
ทอดจนสุก
ตักขั้นใส่จานที่เตรียมไว้
จบการทำงาน
2.แบบทางเลือก (Decision) อัลกอริทึมรูปแบบนี้ มีเงื่อนไขเป็นตัวกำหนดเส้นทางการทำงานของกระบวนการแก้ปัญหา โดยตัวเลือกนั้นอาจจะมีตั้งแต่ 2 ตัวขึ้นไป เช่น สอบข้อเขียน คะแนนเต็ม 50 ได้คะแนน 30 สอบผ่าน ถ้าต่ำกว่า 30 สอบไม่ผ่าน
ตัวอย่างการเขียนอัลกอริทึมแบบทางเลือก อัลกอริทึมตัดเกรดวิชาคอมพิวเตอร์
เริ่มต้น
คะแนนสอบของนักเรียน
ตรวจสอบคะแนน (คะแนนที่สอบผ่าน 50 คะแนน)
ถ้ามากกว่า 50 คะแนน สอบผ่าน
ถ้าน้อยกว่า 50 คะแนน สอบตก
ประกาศผล
จบการทำงาน
3.แบบทำซ้ำ (Repetition) อัลกอริทึมแบบนี้คล้ายกับแบบทางเลือก คือ มีการตรวจสอบเงื่อนไข แต่แตกต่างกันตรงที่เมื่อการทำงานตรงตามเงื่อนไขที่กำหนด โปรแกรมจะกลับไปทำงานอีกครั้งวนการทำงานแบบนี้เรื่อย ๆ จนกระทั่งไม่ตรงกับเงื่อนไขที่กำหนดไว้จึงหยุดการทำงานหรือทำงานในขั้นต่อไป
ตัวอย่างการเขียนอัลกอริทึมแบบทำซ้ำ อัลกอริทึมการซื้อมังคุด 1 กิโลกรัม
เริ่มต้น
หยิบถุงพลาสติก
หยิบมังคุดมาเลือก โดยกดที่เปลือกที่นิ่มๆ
ตรวจสอบเงื่อนไข (น้อยกว่า 1 กิโลกรัม)
ถ้าจริง เลือกมังคุดต่อ
ถ้าเท็จ หยุดเลือก
จ่ายเงินให้กับผู้ที่ขาย
จบการทำงาน
คุณลักษณะการเขียนอัลกอริทึม
ในการแก้ปัญหาแต่ละปัญหามหลายวิธี ดังนั้นการเขียนอัลกอริทึมเพื่อแก้ปัญหาแต่ละปัญหาก็มีหลายวิธีด้วย แต่ละวิธีมีทั้งข้อเด่นข้อด้อย ดังนั้นต้องเลือกให้เหมาะสมกับงานและสภาพแวดบ้อมในขณะนั้น โดยทั่วไปอัลกอริทึมที่ดี ต้องคุณลักษณะดังต่อไปนี้
มีความถูกต้อง ความถูกต้องเป็นคุณสมบัติข้อแรกที่จะต้องพิจารณา นั่นคือเมื่อทำงานตามอัลกอริทึม แล้วจะต้องได้ผลลัพธ์ที่ถูกต้อง ซึ่งถ้าผลลัพธ์ที่ได้จากอัลกอริทึมไม่ถูกต้อง จะถือว่าไม่ใช่อัลกอริทึมที่ดี โดยที่ไม่จำเป็นต้องพิจารณาคุณสมบัติข้ออื่น ๆ
ใช้เวลาในการปฏิบัติงานน้อยที่สุด
สั้น กระชับ มีเฉพาะขั้นตอนที่จำเป็นเท่านั้น
ใช้เนื้อที่ในหน่วยความจำน้อยที่สุด เนื้อที่ในหน่วยความจำจะถูกใช้สำหรับเก็บค่าของตัวแปร และเก็บคำสั่งที่ใช้ในการทำงาน ดังนั้น ถ้าอัลกอริทึมยาวเกินความจำเป็น จะทำให้ใช้เนื้อที่มาก และ ถ้ามีตัวแปรมากเกินความจำเป็น ก็จะทำให้เสียเนื้อที่ในหน่วยความจำไปด้วย
มีความยืดหยุ่นในการใช้งาน
ใช้เวลาในการพัฒนาน้อยที่สุด เมื่อนำอัลกอริทึมไปแปลงเป็นโปรแกรมภาษาคอมพิวเตอร์แล้วจะต้องใช้เวลาน้อยที่สุด
ง่ายต่อการทำความเข้าใจ
การวิเคราะห์อัลกอรึทึม
การวิเคราะห์ขั้นตอนวิธีการ ต้องทำการแยกแยะระบบว่าเป็นข้อมูลเข้า หรือออกดังนี้
อะไรเป็นข้อมูลเข้า (Input)
วิธีการประมวลผลที่จะนามาซึ่งคาตอบ (Process)
อะไรเป็นข้อมูลออก (Output)
ตัวอย่างที่ 1 ต้องการหาค่าเฉลี่ยของคะแนนวิชา Fundamental of Computer ของนักศึกษาจานวน 50 คน
วิเคราะห์อัลกอริทึม
ข้อมูลเข้า : คะแนนของนักศึกษาแต่ละคน (Score)
ประมวลผล : ผลรวมของคะแนนนักศึกษาทุกคน ¸ 50 (Average)
ข้อมูลออก : พิมพ์ผลลัพธ์
ตัวอย่างที่ 2 จงคำนวณหาพื้นที่สามเหลี่ยม โดยให้ผู้ใช้สามารถ Input ข้อมูลความสูงและความยาวฐานได้
วิเคราะห์อัลกอริทึม
ข้อมูลเข้า : ความสูง (H) , ความยาวฐาน (B)
ประมวลผล : คำนวณ Area = ½ * B*H
ข้อมูลออก : แสดงค่าพื้นที่สามเหลี่ยมที่หน้าจอ
เครื่องมือช่วยในการเขียนอัลกอริทึม
การเขียนอัลกอริทึม เป็นการวางแผนเกี่ยวกับการแก้ปัญหา โดยจะอธิบายการทำงานที่ชัดเจนเพื่อเป็นแนวทางในการเขียนโปรแกรม ช่วยให้การเขียนโปรแกรมทำได้ง่ายขึ้น ช่วยให้โปรแกรมมีข้อผิดพลาดน้อยลง นอกจากนี้ยังช่วยตรวจสอบการทำงานของโปรแกรม ทำให้ทราบขั้นตอนการทำงานของโปรแกรมได้อย่างรวดเร็ว โดยไม่ต้องดูจากโปรแกรมจริง
ในการเขียนอัลกอริทึม มีเครื่องมือช่วยในการเขียนที่นิยมใช้ 3 แบบ คือ
1. บรรยาย (narrative description)
2. ผังงาน (flowchart)
3. รหัสลำลอง (pseudo code)
1. การเขียนอัลกอริทึมแบบบรรยาย เป็นการแสดงขั้นตอนการทำงานในลักษณะการบรรยายเป็นข้อความด้วยภาษาพูดใด ๆ เช่น ภาษาไทย ภาษาอังกฤษ ภาษาเกาหลี ภาษาญี่ปุ่น หรือ ภาษาจีน เป็นต้น ขึ้นอยู่กับความถนัดของผู้เขียนอัลกอริทึม มักเขียนบรรยายขั้นตอนการทำงานเป็นข้อๆ เช่น
ตัวอย่าง การปลูกต้นไม้ แสดงขั้นตอนการทำงานด้วยอัลกอริทึมแบบบรรยายได้ดังนี้
เริ่มต้น
ขุดหลุม
ใส่ปุ๋ย
นำต้นไม้ลงหลุม
กลบดิน
ปักหลักยึดต้นไม้
รดน้ำ
จบการทำงาน
ข้อดีของการเขียนอัลกอริทึมแบบบรรยาย
การเขียนอัลกอริทึมแบบบรรยาย มีข้อดี คือ ง่านในการเขียนบรรยาย เนื่องจากใช้ภาษาพูดที่ผู้เขียนอัลกอริทึมคุ้นเคยอยู่แล้ว ดังนั้นจึงง่ายในการเขียนบรรยาย
ข้อเสียของการเขียนอัลกอริทึมแบบบรรยาย เนื่องจากการเขียนมีลักษณะบรรยาย มีรายละเอียดดังนี้
ขอบเขตของการบรรยายกว้างเกินไปยืดเยื้อเกินไป
ยากต่อความเข้าใจ
ยากในตรวจสอบความถูกต้อง
ยากในการแปลงเป็นโปรแกรม
2. การเขียนอัลกอริทึมแบบผังงาน การเขียนอัลกอริทึมแบบผังงานจะแสดงขั้นตอนการทำงานในลักษณะของรูปภาพหรือสัญลักษณ์ ซึ่งเป็นสัญลักษณ์ที่เป็นมาตรฐาน ไม่อ้างอิงภาษาใดภาษาหนึ่ง ทำให้เห็นลำดับการทำงานก่อนหลังได้ชัดเจน เช่น
ตัวอย่าง การปลูกต้นไม้ แสดงขั้นตอนการปลูกต้นไม้ด้วยผังงาน ดังภาพต่อไปนี้
ภาพที่ 2 ผังงานแสดงขั้นตอนการปลูกต้นไม้
ที่มา : http://algorithm-elearning.esy.es/
ข้อดีของการเขียนอัลกอรทึมแบบผังงาน
1. ทำความเข้าใจได้ง่าย
2. ตรวจสอบความถูกต้องได้ง่าย
3. พัฒนาโปรแกรมได้ง่าย
4. ง่ายต่อการบำรุงรักษาโปรแกรม
วิธีการเขียนผังงานที่ดี
1. ใช้สัญลักษณ์ตามที่กำหนดไว้ ขนาดแตกต่างกันได้
2. ใช้ลูกศรแสดงทิศทางการไหลของข้อมูลจากล่างขึ้นบนหรือซ้ายไปขวา
3. คำอธิบายในภาพควรสั้นกระทัดรัด และเข้าใจได้ง่าย
4. มีความเป็นระเบียบเรียบร้อย สะอาด
5. ทุกแผนภาพต้องมีลูกศรแสดงทิศทางเข้า – ออก
6. ผังงานควรสมดุลระหว่างซ้ายและขวา
7. ไม่ควรโยงเส้นเชื่อมผังงานี่อยู่ไกลมาก ๆ ควรใช้สัญลักษณ์จุดเชื่อมต่อแทน
8. ผังงานควรทดสอบความถูกต้องของการทำงานก่อนนำไปเขียนโปรแกรม
3. การเขียนอัลกอริทึมโดยใช้รหัสลำลอง เป็นการเขียนขั้นตอนการทำงานในลักษณะของคำอธิบายที่มีรูปแบบโครงสร้างชัดเจน ไม่ขึ้นกับภาษาใดภาษาหนึ่ง แต่สามารถเปลี่ยนเป็นภาษาคอมพิวเตอร์ได้ง่าย ดังนั้นโครงสร้างส่วนใหญ่จึงนิยมใช้คำสั่งเฉพาะที่มีอยู่ในคอมพิวเตอร์เพื่อแทนการทำงานต่าง ๆ เช่น Read if Case หรือ While/Do เป็นต้น การเขียนอัลกอริทึมมีลักษณะดังต่อไปนี้
1. รูปแบบเป็นภาษพูดง่าย ๆ ภาษอังกฤษ หรือภาษาไทยก็ได้
2. ไม่มีกฎที่แน่นอนตายตัว แต่ลักษณะคล้ายกับภาษาคอมพิวเตอร์
3. ไม่เจาะจงภาษาคอมพิวเตอร์ใดภาษาหนึ่ง
4. ใช้คำเฉพาะ (Keyword)
5. เริ่มต้น คือคำสั่งที่อยู่บรรทัดแรก และ สิ้นสุด คือ คำสั่งที่อยู่บรรทัดสุดท้าย
6. ใช่ย่อหน้าในการเขียนการทำงานย่อยที่อยู่ภายใน
7. ไม่ระบุอุปกรณ์ในการรับข้อมูลหรือแสดงผลข้อมูล
8. ข้อมูลต่าง ๆที่ใช้ควรจะอยู่ในรูปของตัวแปร
ลักษณะที่ดีของรหัสเทียม การเขียนรหัสเทียมที่ดี จะต้องมีลักษณะดังนี้
1. ชัดเจน
2. สั้น กระชับและได้ใจความ
3. รูปแบบแน่นอนกะทัดรัด และมองคล้ายภาษาคอมพิวเตอร์ระดับสูง
4. แปลเป็นภาษาคอมพิวเตอร์ได้เร็ว
รูปแบบ Algorithm แบบรหัสเทียม
<ชื่อของอัลกอริทึม>
START
1……………………………….
2……………………………….
3…………………………………
END
ตัวอย่างโจทย์
จงเขียนโปรแกรมคำนวณหาพื้นที่ สามเหลี่ยมทั่วไป โดยให้โปรแกรมมีการรับค่า ฐาน และ สูงจากทาง Keyboard จากนั้นแสดงผลลัพธ์ของพื้นที่ออกทางจอภาพ
วิเคราะห์โจทย์
แบ่งออกเป็นสองส่วนคือ ส่วนในการรับค่า คือรับค่า ฐาน และ สูงจากผู้ใช้มาเก็บไว้ในตัวแปร และส่วนในการคำนวณ สูตรในการหาพื้นที่สามเหลี่ยมคือ (1/2) * ฐาน * สูง
ตัวอย่าง การเขียนอัลกอริทึม คำนวณหาพื้นที่สามเหลี่ยมอัลกอริทึม (Algorithm) การหาพื้นที่สามเหลี่ยม
เริ่มต้น
รับค่าความยาวของฐานมาเก็บในตัวแปร BASE
รับค่าความยาวของสูงมาเก็บในตัวแปร HEIGHT
คำนวณหาพื้นที่ AREA = 0.5 * BASE*HEIGHT
แสดงผลพื้นที่
จบ
ซูโดโค้ด (Pseudo codes) Algorithm Triangle
START
READ BASE
READ HEIGHT
AREA = 0.5 * BASE * HEIGHT
PRINT AREA
END
จากที่กล่าวมาทั้งหมดสรุปได้ว่า อันกอริทึม (Algorithm) เป็นวิธีการในการทำงานอย่างใดอย่างหนึ่ง ที่มีลำดับการทำงานเป็นขั้นตอนชัดเจน และปฏิบัติตามขั้นตอนแล้วได้ผลลัพธ์ที่ถูกต้อง อัลกอริทึมที่ดีจะต้องมีความถูกต้อง ทำงานได้เร็ว สั้น กระชับ ใช้เนื้อที่ในหน่วยความจะน้อย มีความยืดหยุ่นเขียนโปรแกรมได้เร็ว และง่ายต่อการทำความเข้าใจ การเขียนอัลกอริทึมเป็นการวางแผนเกี่ยวกับการแก้ปัญหา โดยจะอธิบายการทำงานที่ชัดเจนเพื่อเป็นแนวทางในการเขียนโปรแกรม ช่วยให้การเขียนโปรแกรมทำได้ง่ายขึ้น ลดข้อผิดพลาดของโปรแกรม และช่วยตรวจสอบการทำงานของโปแกรม การเขียนอัลกอริทึมมีเครื่องมือช่วยในการเขียน คือ การบรรยาย ผังงาน และ ซูโดโค๊ด การเขียนแบบบรรยายจะเขียนบรรยายด้วยภาษาพูดใด ๆ ทำให้แปลงเป็นโปแกรมได้ยาก การเขียนแบบผังงานจะเขียนเป็นรูปภาพโดยใช้สัญลักษณ์แทนความหมายต่าง ๆ ทำให้มองเห็นลพดับการทำงานของอัลกอริทึมได้ชัดเจน แปลงเป็นโปรแกรมก็ทำได้ง่ายและเร็ว การเขียนแบบรหัสเทียมจะกึ่งบรรยายร่วมกับคำเฉพาะซึ่งจะใกล้เคียงกับภาษาคอมพิวเตอร์ทำให้แปลงเป็นโปรแกรมภาษา คอมพิวเตอร์ก็ทำได้ง่ายและเร็วกว่าการเขียนแบบผังงาน