เกมส์ scratch

คลิกเล่นเกมส์ที่นี่  http://scratch.mit.edu/projects/Moeylee/2804966

อัลกอริทึม ( (Algorithm)

ความหมายของ Algorithm

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

โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (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''

หมายเหตุ:

"←" เป็นเครื่องหมายแทนคำว่า "ให้มีค่าเป็น" เช่น "largest ← the item" หมายความว่า ให้ largest มีค่าเป็น item

"return" เป็นการจบขั้นตอนวิธี และส่งค่าของตัวแปรที่ตามหลัง ออกไปยังขั้นตอนวิธีก่อนหน้าที่เรียกใช้

ประวัติ

 

ผู้ให้กำเนิดขั้นตอนวิธี

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

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

ความรู้เบื้องต้นเกี่ยวกับโครงสร้างข้อมูลและอัลกอริทึม

ความหมายของโครงสร้างข้อมมูล

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

ประเภทของโครงสร้างข้อมูล

          ประเภทของโครงสร้างข้อมูล แบ่งออกเป็น 2 ประเภท คือ

          1) โครงสร้างข้อมูลทางกายภาพ (Physical  Data  Structure)

          เป็นโครงสร้างข้อมูลที่ใช้โดยทั่วไปในภาษาคอมพิวเตอร์  แบ่งเป็น 2 ประเภท ตามลักษณะข้อมูล คือ

          1.1) ข้อมูลเบื้องต้น (Primitive  Data  Types) ได้แก่

                 - จำนวนเต็ม (Integer)

                 - จำนวนทศนิยม (Floatting)

                 - ข้อมูลบูลีน (Boolean)

                 - จำนวนจริง (Real)

                 - ข้อมูลอักขระ (Character)

          1.2) ข้อมูลโครงสร้าง (Structured  Data  Types) ได้แก่

                 - แถวลำดับ (Array)

                 - ระเบียนข้อมูล (Record)

                 - แฟ้มข้อมูล(File)

          2) โครงสร้างข้อมูลทางตรรกะ (Logical  Data  Structure)

          เป็นโครงสร้างข้อมูลที่เกิดจากการจินตนาการของผู้ใช้ แบ่งเป็น 2 ประเภท คือ

          2.1) โครงสร้างข้อมูลแบบเชิงเส้น (Linear  Data  Structures) ความสัมพันธ์ของข้อมูลจะเรียงต่อเนื่องกัน เช่น

                 - ลิสต์ (List)

                 - สแตก (Stack)

                 - คิว (Queue)

                 - สตริง (String)

          2.2) โครงสร้างข้อมูลแบบไม่เชิงเส้น (Non-Linear  Data  Structures) ข้อมูลแต่ละตัวสามารถมีความสัมพันธ์กับข้อมูลอื่นได้หลายตัว ได้แก่

                 - ทรี (Tree)

                 - กราฟ (Graph)

การดำเนินการกับโรงสร้างข้อมูล (Data  Structure  Operation)

          วิธีการดำเนินการกับข้อมูลที่นิยมใช้กันมาก มี 4 แบบ

          1) การเข้าถึงเรคคอร์ด ( Traversing)

          2) การค้นหา (Searching)

          3) การเพิ่ม (Inserting)

          4) การลบ (Deleting)

          ยังมีการจัดการกับข้อมูลอีก 2 อย่าง คือ

          1) การเรียงข้อมูล (Sorting)

          2) การรวมข้อมูล (Merging)

การแทนที่ข้อมูลในหน่วยความจำ

          การแทนที่ข้อมูลในหน่วยความจำหลัก ในการเขียนโปรแกรมคอมพิวเตอร์มี 2 วิธี คือ

          1) การแทนที่ข้อมูลแบบสแตติก (Static  Memory  Representation) เป็นการจองเนื้อที่แบบคงที่แน่นอน

          2) การแทนที่ข้อมูลแบบ (Dynamic Memory Representation) เป็นการแทนที่ข้อมูล  แบบไม่ต้องจองเนื้อที่ ขนาดของเนื้อที่ยืดหยุ่นได้ สามารถส่งคืนเพื่อนำกลับมาใช้ได้อีก

ลักษณะของโปรแกรมแบบมีโครงสร้างที่ดี

          โครงสร้างสำหรับการเขียนโปรแกรมมีดังนี้

          1) โครงสร้างแบบคำสั่งตามลำดับ  จะทำงานตั้งแต่ต้นจนกระทั่งจบโปรแกรมโดยไม่มีการข้ามขั้นตอนการทำงานใด ๆ

          2) โครงสร้างโปรแกรมแบบมีการตัดสินใจ (Decision) มีการตรวจสอบเงื่อนไข เพื่อทำการตัดสินใจว่าจะมีการประมวลผลส่วนใด ซึ่งค่าความเป็นไปได้จะมี จริง และ เท็จ

          3) โครงสร้างโปรแกรมแบบวงจรปิด (Loop) มีลักษณะการทำงานซ้ำ ๆ อยู่ในส่วนหนึ่งส่วนใดของโปรแกรม แบบเป็นวงกลม จนกว่าจะเสร็จขั้นตอน มี 2 ลักษณะ คือ ตรวจสอบเงื่อนไขก่อนทำ และทำก่อนตรวจสอบเงื่อนไข

อัลกอริทึม (Algorithm)

          อัลกอริทึม คือ วิธี หรือ ขั้นตอนการแก้ปัญหาอย่างเป็นขั้นตอน มีระบบ ช่วยให้การแก้ปัญหานั้น ๆ มีประสิทธิภาพ ซึ่งอัลกอริทึมที่นิยมใช้กันมาก ได้แก่

          1) อัลกอริทึมแบบแตกย่อย (Divide-and-conquer) จะนำปัญหาหลักมาทำการแตกย่อยแล้วนำคำตอบที่ได้จากการแตกย่อยมารวมเข้าด้วยกัน

          2) อัลกอริทึมแบบเคลื่อนที่ (Dynamic  Programming) เป็นการหลีกเลี่ยงการคำนวณเพื่อหาคำตอบซ้ำ ๆ ซาก ๆ ซึ่งหากมีการคำนวณซ้ำอีก ก็นำคำตอบที่เก็บไว้มาใช้ได้

          3) อัลกอริทึมแบบทางเลือก (Greedy  Algorithm) จะหาคำตอบโดยเลือกทางเลือกที่ดีที่สุดที่พบได้ในขณะนั้น

ขั้นตอนที่ดีควรมีคุณสมบัติดังนี้

          1) มีความถูกต้อง

          2) ใช้เวลาในการปฏิบัติงานน้อยที่สุด

          3) สั้น กระชับ

          4) ใช้หน่วยความจำน้อยที่สุด

          5) มีความยืดหยุ่นในการใช้งาน

          6) ใช้เวลาในการพัฒนาน้อยที่สุด

          7) ง่ายต่อการทำความเข้าใจ

องค์ประกอบของการจัดทำอัลกอริทึม

          1) การวิเคราะห์ (Analysis)

          - พิจารณาสิ่งที่โจทย์ต้องการ

          - พิจารณารูปแบบของผลลัพธ์ที่โจทย์ต้องการ

          - พิจารณาข้อมูลนำเข้า

          - พิจารษหาวิธีการ หรือสูตรในการแก้ปัญหาที่ต้องการ

          - เลือกโปรแกรมภาษาที่จะใช้เขียนโปรแกรม

          - กำหนดตัวแปรต่าง ๆ ที่ใช้แทนข้อมูลในโปรแกรม

          - จัดลำดับขั้นตอนการดำเนินการเขียนโปรแกรมเพื่อแก้ปัญหาของโจทย์

          2) การออกแบบ (Design)

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

          - รหัสเทียม (Pseudo  Code) เป็นการอธิบายขั้นตอนการประมวลผลโดยใช้วลีภาษาอังกฤษ ใช้คำสั้น ๆ กระทัดรัด ใช้เนื้อที่อธิบายทำงานน้อย แต่อาจเข้าใจยากสำหรับผู้เริ่มเขียนโปรแกรม

          3) การเขียนโปรแกรม (Coding/Programming)        

          พัฒนาการของภาษาโปรแกรม

          - ภาษาเครื่อง เป็นเลขฐานสอง 0 และ 1

          - ภาษาแอสเซมบลี เป็นเลขฐานสิบหก

          - ภาษาระดับสูง ใช้ภาษาอังกฤษในการเขียน เช่น ปาสคาล เป็นต้น

          - ภาษายุคที่ 4 หรือ 4GL เช่น JAVA หรือพวก .net เป็นต้น

          ภาษาสำหรับการเขียนโปรแกรม มีรูปแบบที่สั้น กระชับ รัดกุม และมีข้อกำหนดดังต่อไปนี้

          1. ตัวแปรต้องเขียนด้วยตัวอักษร หรือตัวอักษรปนตัวเลข

          2. การกำหนดค่าตัวแปร ใช้เครื่องหมาย

          3. นิพจน์ที่เป็นการคำนวณจะมีลำดับขั้นตอนของการคำนวณตามลำดับ คือ วงเล็บ ยกกำลัง คูณหรือหาร บวกหรือลบ ถ้าเครื่องหมายระดับความสำคัญเท่ากัน จะคำนวณจากซ้ายไปขวา

          4. ข้อความไปยังขั้นตอน ใช้รูปแบบคือ goto เลขที่ขั้นตอน

          5. การเลือกทำตามเงื่อนไขจ จะต้องทำการตรวจสอบเงื่อนไขก่อนทำ จะมีแบบทางเลือกเดียว คือ ใช้คำสั่ง if และสองทางเลือก คือ ใช้คำสั่ง if...else

          6. การทำงานแบบซ้ำ แบบทดสอบเงื่อนไขก่อนทำ ใช้คำสั่ง while แบบทำก่อนทดสอบเงื่อนไข ใช้คำสั่ง do...while และแบบรู้จำนวนการวนรอบ จะใช้คำสั่ง for

          7. คำอธิบาย เป็นข้อความที่อธิบายรายละเอียดของขั้นตอนการทำงาน หรือ หมายเหตุ (Comment) จะเขียนอยู่ในเครื่องหมาย /และ/

          4) การทดสอบและแก้ไขข้อผิดพลาดของโปรแกรม (Testing  and  Debugging)

          เป็นขั้นตอนการตรวจสอบโปรแกรมที่เขียนว่าทำงานถูกต้องตามความต้องการหรือไม่

          - ข้อผิดพลาดทางไวยกรณ์ (Syntax  Error) เป็นข้อผิดพลาดที่เกิดจากการเขียนคำสั่งที่ผิดไวยกรณ์ของภาษาที่ใช้เขียนโปรแกรมนั้น ๆ

          - ข้อผิดพลาดที่เกิดขึ้นขณะรันโปรแกรม (Run-Time Error) เป็นข้อผิดพลาดที่เกิดขึ้นขณะทำการรันโปรแกรม ส่วนใหญ่เกิดจากการคำนวณตัวเลข

          5) การจัดทำเอกสารและบำรุงรักษา (Documentation  and  Maintenance)

          การจัดทำเอกสาร

          1. คำบรรยายลักษณะของโปรแกรม

          2. คำอธิบายพร้อมผังงานหรือรหัสเทียม

          3. รายการโปรแกรม (Program  Listing)

          4. ผลการทดสอบโปรแกรม

          5. จัดทำเอกสารต่าง ๆ ที่เกี่ยวข้องกับระบบ/โปรแกรม ได้แก่

          - เอกสารแสดงการวิเคราะห์ และออกแบระบบ : System Manual สำหรับผู้พัฒนาระบบโปรแกรม

          - เอกสารอธิบายวิธีการใช้ระบบ/โปรแกรม : User Manual สำหรับผู้ใช้ระบบ/โปรแกรม

          6. สามารถทำควบคู่ไปกับการเขียนโปรแกรม

          7. อาจทำเป็นคู่มือ เอกสารที่อยู่ในโปรแกรม (Online Manual)

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

การวัดประสิทธิภาพของอัลกอริทึม

          สิ่งที่ต้องพิจารณา

          1) โปรแกรมนั้นใช้เนื้อที่ความจำ (Memory) มากน้อยเพียงใด

          2) โปรแกรมนั้นใช้อัลกอริทึม (Algorithm) ที่เร็วเพียงใด

          ในทางทฤษฎี จะระบุความเร็วการทำงานของอัลกอริทึม โดยพิจารณา หรือประมวลผลจำนวนข้อมูลที่อัลกอริทึมนั้นกระทำก่อนที่จะได้ผลลัพธ์ว่ามีการทำงานกี่ครั้ง จำนวนครั้งแทนด้วย N ความเร็วในการทำงานเรียกว่า ฟังก์ชั่น บิ๊กโ-อ (big-oh) : Order of N หรือ O(N)

อัลกอริทึม

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

   รูปแบบการเขียนผังงาน   การเขียนผังงานมี 3 รูปแบบ  คือ

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

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

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

               อุปกรณ์รับข้อมูล (อินพุต)  เช่น เทอร์มินัล คีบอร์ด หรือรับข้อมูลจากการอ่านไฟล์ข้อมูลบนสื่อจัดเก็บข้อมูลได้ เช่น การอ่านข้อมูลจากดิสก์ การอ่านข้อมูลจากเทป หรือการรับข้อมูลจากแป้นคีบอร์ดในการอ่านข้อมูลจากคำกริยา read และ get เพื่อใช้ในเขียนซูโดโค้ด

  Read ใช้เมื่อมีการรับหรืออ่านเรคอร์ดจากไฟล์ข้อมูล

  Get ใช้สำหรับรับข้อมูลจากแป้นคีบอร์ด

               คอมพิวเตอร์ที่สามารถรับข้อมูลได้

               การแสดงผลลัพธ์จะใช้คำกริยา print, write, put output  หรือ display

  Print ใช้สำหรับการส่งผลลัพธ์ออกทางเครื่องพิมพ์

 Write ใช้สำหรับการส่งเอ้าท์พุตเพื่อเก็บบันทึกลงในไฟล์

  put, output หรือ displayจะใช้สำหรับการส่งเอ้าท์พุตออกไปแสดงผลทางหน้าจอ

                                                              สัญลักษณ์ของผังงาน