อัลริทึม
คืออะไร
Algorithm คือ กระบวนการแก้ปัญหาที่สามารถอธิบายออกมาเป็นขั้นตอนที่ชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร กระบวนการนี้ประกอบด้วยจะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซำอีก จนกระทั่งเสร็จสิ้นการทำงาน Algorithm ไม่ใช่คำตอบแต่เป็นชุดคำสั่งที่ทำให้ได้คำตอบ วิธีการในการอธิบาย Algorithm ได้แก่ 1. Natural Language อธิบายแบบใช้ภาษาที่เราสื่อสารกันทั่วไป 2.Pseudocode อธิบายด้วยรหัสจำลองหรือรหัสเทียม 3.Flowchart อธิบายด้วยแผนผัง การนำขั้นตอนวิธีไปใช้แก้ปัญหา ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่นเดียวกัน ตัวอย่างเช่น ในการวางแผนการใช้ทรัพยากรทางธุรกิจขององค์กร หรือ Enterprise Resource Planning ( ERP ) เพื่อให้เกิดการใช้ทรัพยากรอย่างมีประโยชน์สูงสุด ซึ่งจำเป็นต้องวางแผนอย่างเป็นระบบ เป็นขั้นตอน จึงจำเป็นต้องอาศัย Algorithm ด้วย เพื่อให้ทราบถึงขั้นตอนต่างๆ และสามารถตัดทอนขั้นตอนที่เกินความจำเป็น อีกทั้งยังสามารถปรับปรุง และเพิ่มเติมขั้นตอนใหม่ เข้าไปได้ ช่วยลดความสับสนขณะทำงานด้วย
ขั้นตอนวิธี หรือ algorithm (ภาษาไทย : อัลกอริทึม) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic)
โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน
ในการทำงานอย่างเดียวกัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time) , และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน
การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมล
โครงสร้างข้อมูล (Data Structure) คืออะไร โอภาส เอี่ยมสิริวงศ์, "โครงสร้างข้อมูล (Data Structures)" บริษัท ซีเอ็ดยูเคชั่น จำกัด., กรุงเทพฯ, 2549. โครงสร้างข้อมูล (Data Structure) - บิท (Bit) คือ ข้อมูลที่มีขนาดเล็กที่สุด เป็นข้อมูลที่เครื่องคอมพิวเตอร์เข้าใจ และใช้งานได้ ได้แก่ 0 หรือ 1 - ไบท์ (Byte) หรือ อักขระ (Character) คือ ตัวเลข หรือ ตัวอักษร หรือ สัญลักษณ์พิเศษ จำนวน 1 ตัว - ฟิลด์ (Field) หรือ เขตข้อมูล คือ ไบท์ หรือ อักขระตั้งแต่ 1 ตัวขึ้นไปรวมกันเป็นฟิลด์ เช่น เลขประจำตัว หรือ ชื่อพนักงาน - เรคคอร์ด (Record) หรือระเบียน คือ ฟิลด์ตั้งแต่ 1 ฟิลด์ขึ้นไป ที่มีความสัมพันธ์เกี่ยวข้องกันมารวมกัน - ไฟล์ (File) หรือ แฟ้มข้อมูล คือ หลายเรคคอร์ดมารวมกัน เช่น ข้อมูลที่อยู่นักเรียนมารวมกัน - ฐานข้อมูล (Database) คือ หลายไฟล์ข้อมูลมารวมกัน เช่น ไฟล์ข้อมูลนักเรียนมารวมกันในงานทะเบียน แล้วรวมกับไฟล์การเงิน | เว็บเพจที่เกี่ยวข้อง + แนะนำหนังสือ + ซูโดโค้ด (Pseudocode) + การเขียนโปรแกรม เรียงเลข 3 ตัว ตัวอย่างข้อมูล ภาษาปาสคาล ภาษาซี ภาษาจาวา ภาษาวีบี |
ศัพท์เทคนิค (Technical Terms) |
|
ความรู้เบื้องต้นเกี่ยวกับการพัฒนาระบบ |
การพัฒนาโปรแกรมประกอบด้วยขั้นตอนพื้นฐาน 7 ขั้นตอน [3]p.19 1. กำหนดปัญหา (Define the Problem) 2. ร่างรายละเอียดแนวทางแการแก้ไขปัญหา (Outline the Solution) 3. พัฒนาอัลกอริทึม (Develop Algorithm) อาจนำเสนอด้วย Flowchart, DFD, ER หรือ UML 4. ตรวจสอบความถูกต้องของอัลกอริทึม (Test the Algorithm for Correctness) 5. เขียนโปรแกรม (Programming) 6. ทดสอบโปรแกรม (Testing) 7. จัดทำเอกสารและบำรุงรักษาโปรแกรม (Document and Maintain the Program)
|
อัลกอริทึม (Algorithm) http://www.thaiall.com/datastructure/pseudocode.htm |
ต.ย. อัลกอริทึมที่ 1 : ต้มมาม่า [3]p.25 1. หามาม่าไว้ 1 ซอง 2. ฉีกซองมาม่าและเทลงถ้วยเปล่า 3. ฉีกซองเครื่องปรุง แล้วเทลงถ้วยเดิม 4. ต้มน้ำให้ร้อนได้ที่ แล้วเทลงถ้วย 5. ปิดฝาไว้ 3 นาที 6. เปิดฝา แล้วรับประทาน | คำถาม : ต้มมาม่า 1. มีขั้นตอนใดสลับกันได้ 2. ถ้าเปลี่ยนข้อความ จะเปลี่ยนอย่างไร 3. ถ้าทำหลายถ้วยจะทำอย่างไร ? คน 3 คนใครอายุมากที่สุด และเป็นเท่าใด |
ต.ย. อัลกอริทึมที่ 2 : หาค่าเฉลี่ย ใช้ Pseudo Code 1. set variable 2. loop | คำถาม : หาค่าเฉลี่ย 1. เขียนเป็นภาษาไทยอย่างไร 2. แต่ละบรรทัดในจาวาคืออะไร 3. สลับบรรทัดใดในจาวาได้บ้าง 4. ไม่มีตัวแปร avg จะได้หรือไม่ | 1. 2. 3. 4. 5. | ภาษาจาวา byte x; int i = 0; int total = 0; while (i < 5) { x = System.in.read(); total = total + x; i++; } double avg = total/i; System.out.println(avg); |
ปฏิบัติการพื้นฐานของเครื่องคอมพิวเตอร์ [3]p.37 |
1. รับข้อมูล (input device) 2. แสดงผล (output device) 3. คำนวณ (limit and sequence) 4. กำหนดค่าตัวแปร (storage) 5. เปรียบเทียบ หรือเลือกทำงาน (compare or decision) 6. ทำซ้ำ (repeation or loop) |
หน่วยความจำ (Memory) |
ชนิดข้อมูลนามธรรม (Abstract Data Type : ADT) |
ชนิดข้อมูลนามธรรม (Abstract Data Type) คือ เครื่องมือกำหนดโครงสร้างข้อมูลที่ประกอบด้วยชนิดของโครงสร้างข้อมูล รูปแบบการดำเนินการ หรือแยกได้ 3 ส่วนคือ รูปแบบข้อมูล (Element) โครงสร้าง (Structure) และ การดำเนินการ (Operations) [4]p.25
|
ประสิทธิภาพของอัลกอริทึม (Algorithm Efficiency) |
ประเด็นที่ใช้วัดประสิทธิภาพ [3]p.58 1. เวลาที่ใช้ประมวลผล (Running Time) 2. หน่วยความจำที่ใช้ (Memory Requirement) 3. เวลาที่ใช้แปลโปรแกรม (Compile Time) 4. เวลาที่ใช้ติดต่อสื่อสาร (Communication Time) | ปัจจัยที่ส่งผลต่อความเร็วในการประมวลผล 1. ความเร็วของเครื่องคอมพิวเตอร์ (CPU, Main Board) 2. อัลกอริทึมที่ออกแบบเพื่อใช้งาน 3. ประสิทธิภาพของตัวแปลภาษา 4. ชุดคำสั่งที่สั่งประมวลผลเครื่องคอมพิวเตอร์ 5. ขนาดของหน่วยความจำในเครื่องคอมพิวเตอร์ 6. ขนาดของข้อมูลนำเข้า และผลลัพธ์จากการประมวลผล |
- การวัดประสิทธิภาพของอัลกอริทึม (Efficiency Algorihm) - การวิเคราะห์บิ๊กโอ (Big-O Analysis) - ขั้นตอนการเปลี่ยน f() เป็น Big-O Notation [4]p.23 | ความหมายของลอการิทึม - ลอการิทึม (อังกฤษ: logarithm) เป็นการดำเนินการทางคณิตศาสตร์ที่เป็นฟังก์ชันผกผันของฟังก์ชันเลขชี้กำลัง - ค่าลอการิทึมของจำนวนหนึ่งโดยกำหนดฐานไว้ให้ จะมีค่าเทียบเท่ากับ การเอาฐานมายกกำลังค่าลอการิทึม ซึ่งจะให้คำตอบเป็นจำนวนนั้น ลูปแบบเพิ่ม 2 เท่า for(i=1;i<1000;i*=2){ echo i; } เช่น 1 2 4 8 16 32 64 ลูปแบบลด 2 เท่า for(i=1;i<1000;i/=2){ echo i; } เช่น 1000 500 250 125 62.5 31.25 |
- ต.ย.1 จงหาผลบวกของการบวกจำนวนที่เริ่มต้นตั้งแต่ 1 - 10 ดร.บุญญฤทธิ์ อุยยานนวาระ เปรียบเทียมประสิทธิภาพของ Big-O กับความเร็วของยวดยาน ดังนี้ + O(1) เหมือนเครื่องว๊าบ หรือเครื่องย้ายมวลสาร คือ ไกลแค่ไหนไม่เกี่ยว + O(log n) เหมือนเครื่องบินโดยสาร + O(n) - เหมือนรถฟอร์มูล่าวัน ระยะทางไกลขึ้น ก็ขับนานขึ้น + O(n log n) - เหมือนรถยนตทั่วไป ยิ่งไกลยิ่งช้า + O(n^2) - เหมือนมอร์เตอร์ไซด์ + O(n^3) - เหมือนจักรยาน + O(2^n) - เหมือนคนเดิน | การทำซ้ำ หรือลูป มีหลายแบบ - ลูปแบบเชิงเส้น (Linear Loops) - ลูปแบบลอการิธมิค (Logarithmic Loops) - ลูปแบบซ้อน (Nested Loops) |
อาร์เรย์ (Array) |
- อาร์เรย์หนึ่งมิติ (One Dimension Array) | http://msdn.microsoft.com |
เรคอร์ด (Record) |
ลิงค์ลิสต์ (Linked List) [3]p.101 |
การดำเนินงานพื้นฐานของลิสต์ (Basic Operations of List) 1. การแทรก (Insertion) 2. การลบ (Deletion) 3. การปรับปรุง (Updation) 4. การท่องเข้าไปในลิสต์ (Traversal) |
ตัวชี้ข้อมูลด้วยภาษาปาสคาล [2]p.220 Binary Tree type nodeptr = ^trnode; trnode = record end; | ตัวชี้ข้อมูลด้วยภาษาซี [3]p.193 Abstract Data Type ของ คิว typedef struct node { } QUEUE_NODE; typedef struct { } QUEUE; QUEUE* createQueue (void); bool enqueue (QUEUE* q, void* itemptr); |
สร้างคิว [2]p.221 var root : nodeptr; begin maket(root); procedure maket(var t:nodeptr); begin end; | สร้างคิว QUEUE* createQueue (void) { } |
เพิ่มข้อมูลในคิว [2]p.224 new(n); inserted := false; o := t; while not inserted do begin if num <= o^.data then else end; n^.data := num; n^.leftptr := nil; n^.rightptr := nil; | เพิ่มข้อมูลในคิว bool enqueue (QUEUE* q, void* itemptr) { } |