วันเสาร์ที่ 18 มีนาคม พ.ศ. 2560

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

ความหมายของโครงสร้างข้อมูล
โครงสร้างข้อมูล (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 เลขที่ขั้นตอน

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

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

อ้างอิงจากเว็บ : https://piyamasprajong.wordpress.com/%E0%B9%80%E0%B8%99%E0%B8%B7%E0%B9%89%E0%B8%AD%E0%B8%AB%E0%B8%B2/%E0%B8%84%E0%B8%A7%E0%B8%B2%E0%B8%A1%E0%B8%A3%E0%B8%B9%E0%B9%89%E0%B9%80%E0%B8%9A%E0%B8%B7%E0%B9%89%E0%B8%AD%E0%B8%87%E0%B8%95%E0%B9%89%E0%B8%99%E0%B9%80%E0%B8%81%E0%B8%B5%E0%B9%88%E0%B8%A2%E0%B8%A7/

1 ความคิดเห็น:

  1. The Best Casino Games of 2020 | Dr.MD
    The best casinos games of 2020. 대전광역 출장안마 Best casino games of 2020. 광주광역 출장샵 Best Casino 김해 출장마사지 Games of 2020. Best casino games of 2020. Best casino games of 2020. Best casino games of 2020. The Best casino games of 2020. The Best casino games of 2020. Best 서산 출장샵 casino games of 2020. 용인 출장마사지 The Best casino games of 2020.

    ตอบลบ