Please enable JavaScript.
Coggle requires JavaScript to display documents.
การคิดเชิงคำนวณ - Coggle Diagram
การคิดเชิงคำนวณ
บทที่ 1 แนวคิดเชิงคำนวณ
1.การแบ่งปัญหาใหญ่เป็นปัญหาย่อย (Decomposition)
แนวคิดเชิงคำนวณ ที่เกี่ยวข้องกับการแบ่งปัญหาใหญ่เป็นปัญหาย่อย (Decomposition) นั้นเป็นการแตกปัญหาที่ซับซ้อนให้เป็นปัญหาย่อยที่มีขนาดเล็กลงและซับซ้อนน้อยลง เพื่อช่วยให้การวิเคราะห์และออกแบบวิธีการแก้ปัญหาทำได้ง่ายขึ้นทำให้คิดอย่างเป็นระบบมากยิ่งขึ้น โดยผ่านการแยกย่อยปัญหาต่าง ๆ เนื่องด้วยกระบวนงานบางกระบวนงาน มีวิธีการที่ทำงานอย่างเป็นขั้นตอน และมีระบบย่อย จึงมีความจำเป็นที่ต้องแยกปัญหานั้นออกมาเป็นส่วนย่อย ๆ เพื่อสามารถศึกษาปัญหาของกระบวนการได้ชัดเจนยิ่งขึ้น
2.การพิจารณารูปแบบ (Pattern Recognition)
ดังนั้นการพิจารณารูปแบบ เป็นการหารูปแบบซึ่งเป็นทักษะการหาความสัมพันธ์ที่เกี่ยวข้อง แนวโน้ม และลักษณะ ทั่วไปของสิ่งต่าง ๆ การหารูปแบบเพื่อสร้างความเข้าใจระหว่างองค์ประกอบเหล่านั้น
การจัดหมวดหมู่สัตว์ที่คล้ายคลึงกัน ให้อยู่ในสปีชีส์เดียวกัน เพื่อให้ง่ายต่อการศึกษา
การหาพฤติกรรมการบริโภคของคน ว่านิยมซื้ออะไร ช่วงเวลาไหน มีรูปแบบพฤติกรรมซ้ำ ๆ อะไรบ้าง
ความสัมพันธ์ของเฟืองหน้า และเฟืองหลัง ของรถจักรยานที่เชื่อมกันด้วยโซ่จักรยานมีลักษณะเหมือนระบบรอก
สิ่งของ เช่นมาส์นั้น มีรูปลักษณ์ภายนอกที่แตกต่างกันออกไปแต่สังเกตได้ว่ารูปแบบการใช้งานนั้นเหมือนกัน
การเขียนโปรแกรมที่ทำซ้ำ ๆ กันหลาย ๆ ครั้ง จะมีลักษณะรูปแบบที่เหมือนกัน รูปแบบของปัญหาที่คล้ายกันสามารถนำวิธีการแก้ปัญหามาประยุกต์ใช้ เพื่อใช้วิธีการแก้ปัญหาเดียวกันได้
3.การคิดเชิงนามธรรม (Abstraction)
แนวคิดนามธรรมจึงเป็นองค์ประกอบหนึ่งของแนวคิดเชิงคำนวณ ซึ่งใช้กระบวนการคัดแยกคุณลักษณะที่สำคัญออกจากรายละเอียดปลีกย่อย ในปัญหาหรืองานที่กำลังพิจารณา เพื่อให้ได้ข้อมูลที่จำเป็นและเพียงพอในการแก้ปัญหา แนวคิดนามธรรมบางอย่างอาจจะอยู่ในรูปแบบของรูปร่างหรือรูปทรง ความแตกต่าง ความเหมือนรูปแบบอักขระ การแทนสัญลักษณ์ต่าง ๆ เช่น การแทน 0 1 ของเลขฐานสอง การคัดแยกรายละเอียดปลีกย่อยที่ไม่จำเป็นต่อการตัดสินใจหรือการใช้งาน เช่น การใช้แผนที่ การคำนวณระยะทาง การวาดแผนทีการเดินทางไป ณ จุดหมายใดจุดหมายหนึ่ง การเดินทางด้วยรถไฟฟ้า หรือแม้แต่การอธิบายปัญหาโดยใช้รายละเอียดและแบบซ่อนรายละเอียด ล้วนเป็นแนวคิดเชิงนามธรรมที่อยู่ในชีวิตประจำวันทั้งสิ้น
1.การคิดเชิงนามธรรมที่เกี่ยวข้องกับรูปทรง
2.การคิดเชิงนามธรรมที่เกี่ยวข้องกับตัวอักษร
3.การคิดเชิงนามธรรมจากเกมเลขฐานสอง
4.การคัดแยกรายละเอียดปลีกย่อย
5.การอธิบายปัญหาโดยใช้รายละเอียด และแบบซ่อนรายละเอียด
4.การออกแบบอัลกอริทึม (Algorithm)
การออกแบบอัลกอริทึม ในแนวคิดเชิงคำนวณจึงเป็นการพัฒนากระบวนการหาคำตอบให้เป็นขั้นตอนที่บุคคลหรือคอมพิวเตอร์สามารถนำไปปฏิบัติตามเพื่อแก้ปัญหาได้ อัลกอริทึมที่ดี จะต้องมีความถูกต้อง ต้องมีลำดับขั้นตอนที่ชัดเจน มีความยืดหยุ่นในการใช้งาน ใช้เวลาในการพัฒนาน้อย และง่ายต่อการทำความเข้าใจ เครื่องมือที่จะช่วยให้การเขียนอัลกอริทึมของโปรแกรมทำได้ง่ายขึ้น ช่วยให้โปรแกรมมีข้อผิดพลาดน้อยลง เช่น การเขียนบรรยาย การเขียนผังงาน หรือรหัสเทียม จะช่วยให้อัลกอริทึมมีความถูกต้องแม่นยำ และมีข้อผิดพลาดน้อยลง
คุณสมบัติของอัลกอริทึม
1.มีความถูกต้อง (correctness) ความถูกต้องเป็นคุณสมบัติข้อแรกที่สำคัญจะต้องพิจารณา ต้องได้ผลลัพธ์ที่ถูกต้อง ซึ่งถ้าผลลัพธ์ที่ได้จากอัลกอริทึมไม่ถูกต้อง จะถือว่าไม่ใช่อัลกอริทึมที่ดี
2.ใช้เวลาในการปฏิบัติงานน้อยที่สุด (efficiency) อัลกอริทึมที่ดีต้องใช้เวลาในการปฏิบัติงานน้อย มีขั้นตอนในการปฏิบัติงานที่ถูกต้อง
3.ต้องมีลำดับขั้นตอนที่ชัดเจน ในการประมวลผลชุดคำสั่งต่าง ๆ ที่ถูกกำหนดด้วยกฎเกณฑ์ในการแก้ปัญหาของ อัลกอริทึม จะต้องประมวลผลเป็นลำดับตามขั้นตอน เพราะการแก้ปัญหาด้วยคอมพิวเตอร์จะต้อง มีลำดับขั้นตอนที่แน่นอน ซึ่งแต่ละขั้นตอนของอัลกอริทึมจะต้องทำหน้าที่อย่างชัดเจนและต่อเนื่องโดยการเริ่มต้นทำงานแต่ละขั้นตอนมีการรับและส่งข้อมูลต่อเนื่องกันไปจนสิ้นสุดการทำงาน ถ้าลำดับไม่ดีอาจจะทำให้การประมวลผลผิดพลาดได้
4.ใช้เนื้อที่ในหน่วยความจำน้อยที่สุด เนื้อที่ในหน่วยความจำจะถูกใช้สำหรับเก็บค่าของตัวแปร และเก็บคำสั่งที่ใช้ในการทำงาน ดังนั้น ถ้าอัลกอริทึมยาวเกินความจำเป็น จะทำให้ใช้เนื้อที่มาก และ ถ้ามีตัวแปรมากเกินความจำเป็น ก็จะทำให้เสียเนื้อที่ในหน่วยความจำไปด้วย
5.มีความยืดหยุ่นในการใช้งาน
6.ใช้เวลาในการพัฒนาน้อยที่สุด เมื่อนำอัลกอริทึมไปแปลงเป็นโปรแกรมภาษาคอมพิวเตอร์แล้วจะต้องใช้เวลาน้อยที่สุด
7.ง่ายต่อการทำความเข้าใจ (readability) อ่านง่ายเข้าใจลำดับขั้นตอนได้ง่าย มีความชัดเจนของขั้นตอน
บทที่ 2 การแก้ปัญหาและขั้นตอนวิธี
1.การแก้ปัญหาด้วยคอมพิวเตอร์
ปัญหาที่สามารถแก้ได้ด้วยคอมพิวเตอร์ ไม่จำเป็นต้องเป็นปัญหาทางคณิตศาสตร์เสมอไปซึ่งก่อนจะแก้ปัญหาต้องเข้าใจปัญหาและความต้องการให้ชัดเจนแล้วค่อยพัฒนาขั้นตอนวิธีที่สามารถใช้งานได้
1.นิยามปัญหา (Problem Definition)
2.การวิเคราะห์ปัญหา (Problem Analysis)
3.การออกแบบอัลกอริทึม (Algorithm Design)
4.การพัฒนาโปรแกรม (Program Development)
5.การทดสอบความถูกต้อง (Program Testing)
6.การจัดทำเอกสาร (Documentation)
7.การบำรุงรักษา (Maintenance)
2.การระบุข้อมูลเข้า ข้อมูลออกและเงื่อนไขของปัญหา
2.1 ข้อมูลเข้า ( input) เป็นข้อมูลที่ใช้เพื่อประมวลผล
2.2 ข้อมูลออก ( Output) เป็นข้อมูลที่แสดงผลลัพธ์
2.3 การระบุข้อมูลเข้า และข้อมูลออกอาจจะไม่สามารถทำได้อย่างชัดเจน จึงต้องทำความเข้าใจกับปัญหามากขึ้น
การออกแบบขั้นตอนวิธี
การออกแบบขั้นตอนวิธี คือ ขั้นตอนการแก้ปัญหาอย่างเป็นลำดับ โดยประกอบด้วยชุดคำสั่งการทำงานอย่างเป็นลำดับและชัดเจน เครื่องมือในการออกแบบขั้นตอนวิธี ประกอบด้วย
การบรรยาย
การออกแบบขั้นตอนวิธีด้วยการบรรยาย เป็นการเขียนบรรยายวิธีการแก้ปัญหาอย่างเป็นลำดับโดยใช้ภาษาธรรมชาติ
รหัสเทียม(Pseudo Code)
เป็นการเขียนโปรแกรมในรูปแบบภาษาอังกฤษที่มีขั้นตอนและรูปแบบแน่นอนกะทัดรัด
ประโยชน์ของรหัสเทียม(Pseudo Code)
เป็นเครื่องมือในการกำหนดโครงร่างกระบวนการทำงานของการเขียนโปรแกรมและใช้เป็นต้นแบบในการทบทวน ปรับปรุงแก้ไขและพัฒนาโปรแกรมของโปรแกรมเมอร์และนักวิเคราะห์ระบบ
3.ผังงาน
ผังงาน (Flowchart) เป็นรูปภาพ หรือ สัญลักษณ์ ที่ใช้เขียนแทนขั้นตอนของงานหรือสิ่งที่กำลังอธิบาย ที่อาจประกอบไปด้วยคำอธิบาย ข้อความ หรือคำพูด แบบย่อ ของงานหนึ่งๆ โดยใช้สัญลักษณ์ที่เป็นมาตรฐานเดียวกัน เพราะการนำเสนอขั้นตอนของงานให้เข้าใจตรงกันระหว่างผู้เกี่ยวข้อง ด้วยคำพูด หรือ ข้อความทำได้ยากกว่า
ลักษณะของผังงานที่ดี
1.ใช้สัญลักษณ์ตามที่กำหนดไว้
2.ใช้ลูกศรแสดงทิศทางการไหลของข้อมูลจากบนลงล่าง หรือ จากซ้ายไปขวา
คำอธิบายในภาพควรสั้นกะทัดรัด และ เข้าใจง่าย
ทุกแผนภาพต้องมีลูกศรแสดงทิศทางเข้า – ออก
5.ไม่ควรโยงเส้นเชื่อมผังงานที่อยู่ไกลมาก ๆ ควรใช้สัญลักษณ์จุดเชื่อมต่อแทน
รูปแบบของผังงาน
ผังงานแบบเรียงลำดับ
เป็นรูปแบบผังงานที่ง่ายที่สุด ไม่ซับซ้อน และไม่มีการเปรียบเทียบเงื่อนไขใด ๆ โดยแสดงขั้นการทำงานไปตามลำดับตั้งแต่ต้นจนสิ้นสุดการบวนการ
ผังงานแบบมีเงื่อนไข
เป็นรูปแบบที่มีการสร้างเงื่อนไขเพื่อเลือกทำงานในขั้นต่อไป
โดยใช้เงื่อนไขการตัดสินใจเพียง 2 ทางเลือก เช่น
จริง หรือ เท็จ
ใช่ หรือ ไม่ใช้
ถูก หรือ ผิด
ผังงานแบบทำซ้ำ
เป็นรูปแบบที่มีการกระทำกระบวนการหนึ่งหลายครั้ง โดยมีเงื่อนไขในการควบคุมจะแตกต่างกับรูปแบบมีเงื่อนไขตรงที่เงื่อนไขจะถูกทดสอบจนกว่าจะเป็นเท็จถึงจะหยุดการทำซ้ำ
ลักษณะขั้นตอนวิธี
แก้ปัญหาได้อย่างมีประสิทธิภาพ
ให้คำตอบที่ถูกต้อง
ใช้เวลาในการปฏิบัติการน้อย
ชัดเจนและกระทัดรัด
4.การจัดเรียงและค้นหาข้อมูล
การจัดเรียงข้อมูลเป็นสิ่งที่พบอยู่เสมอ เมื่อต้องการประมวลผลข้อมูลจำนวนมาก การเรียงลำดับข้อมูลด้วยเงื่อนไขที่เหมาะสม จะทำให้การค้นหาข้อมูลทำได้อย่างมีประสิทธิภาพ เช่น การทำข้อมูลนักศึกษามาจัดเลียงลำดับรหัสนักศึกษา เพื่อนำไปใช้ในการพิมพ์ใบเซ็นชื่อเข้าสอบหรือการเรียงข้อมูลพนักงานตามรหัสพนักงานเพื่อใช้การพิมพ์สลิปเงินเดือน
1.แบบเลือก ( Selection Sort)
การเลือกข้อมูลที่น้อยที่สุดมาไว้เป็นลำดับแรก
จากนั้นในรายการข้อมูลที่เหลืออยู่จะเลือกข้อมูลที่มีค่าน้อยที่สุดมาเป็นข้อมูลในรายการคำตอบ ลำดับที่ 2 ทำไปเรื่อยๆ จนครบทุกจำนวน
แบบแทรก ( Insertion Sort)
เป็นการนำข้อมูลที่ยังไม่ถูกพิจารณามาแทรกในตำแหน่งที่ถูกต้องโดยค่าของข้อมูลที่กำลังพิจารณาต้องมีค่ามากกว่าหรือเท่ากับ ค่าของข้อมูลตัวหน้า หรือ น้อยกว่าหรือเท่ากับ ค่าของข้อมูลตัวหลัง ในรายการที่เรียงลำดับไว้แล้ว
การค้นหาข้อมูล
เป็นกระบวนการหาตำแหน่งของข้อมูลตามค่าของคีย์ โดยมีอัลกอริทึมการค้นหา เป็นเทคนิคการค้นหาข้อมูลตามค่าของคีย์ที่เป็นค่าที่รับเข้ามาเพื่อค้นหาการค้นหาจะสิ้นสุดลงเมื่อพบข้อมูลที่มีค่าคีย์ตรงกันหรือไม่พบข้อมูล
รูปแบบการค้นหาข้อมูล มี ดังนี้
1.การค้นหาแบบตามลำดับ (Sequence Search)
การหาข้อมูลแบบเป็นลำดับขั้นตอน โดยจะค้นหาตั้งแต่ตัวแรกเรียงลำดับไปทีละตัวจนกว่าจะพบข้อมูลที่ต้องการ หรือเปรียบเทียบไปจนถึงตัวสุดท้าย การค้นหาวิธีนี้เป็นวิธีที่ง่ายที่สุด อัลกอริทึมในการค้นหาไม่ซับซ้อนสามารถใช้กับข้อมูลที่เรียงลำดับแล้วหรือข้อมูลที่ยังไม่ได้เรียงลำดับก็ได้
การค้นหาแบบทวิภาคหรือแบบแบ่งครึ่ง (Binary Search)
วิธีการค้นหาโดยใช้ระบบแบ่งครึ่งข้อมูลทั้งหมดออกเป็นสองส่วน การค้นหาตัวที่ต้องการจะต้องเลือกหาจากข้อมูลทีละส่วน คือแบ่งเป็นสองส่วนย่อย หากพบในส่วนที่หนึ่ง ก็ไม่ต้องเสียเวลาหาในอีกส่วนหนึ่งอีกต่อไป
เป็นขั้นตอนวิธีเพื่อหาตำแหน่งของค่าที่ต้องการ
(ข้อมูลนำเข้า หรือ "key") ที่ใช้ในแถวลำดับที่ได้มีการเรียงลำดับข้อมูลแล้ว ขั้นตอนวิธีจะเริ่มจากเปรียบเทียบข้อมูลที่นำเข้ากับข้อมูลที่อยู่ตรงกลางของแถวลำดับถ้าข้อมูลมีค่าเท่ากันแสดงว่าพบ "คีย์" ที่ต้องการ
การค้นหาข้อมูลแบบทวิภาค เหมาะสำหรับค้นหาข้อมูลที่มีการเรียงลำดับอยู่แล้ว