วันศุกร์ที่ 26 ตุลาคม พ.ศ. 2555

แบบทดสอบ


แบบทดสอบ

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

2.  อธิบายลักษณะสำคัญของ ข้อมูลคอมพิวเตอร์
ตอบ  ลักษณะที่สำคัญของคอมพิวเตอร์สามารถแบ่งออกได้ 6 ประเภท คือ
1. ความรวดเร็ว    2.หน่วยความจำ 3.การทำงานอัตโนมัติ
4.การเก็บรักษาข้อมูลหรือโปรแกรม 5.ความถูกต้องและความเชื่อถือได้ 6.การใช้งานด้หลายๆด้าน

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

4.  อธิบายลักษณะสำคัญของโครงสร้างข้อมูลทางกายภาพ
ตอบ    โครงสร้างข้อมูลทางกายภาพ เป็นโครงสร้างข้อมูลที่ใช้โดยทั่วไปในภาษาคอมพิวเตอร์แบ่ง
            ออกเป็น 2ประเภท
            1 ข้อมูลเบื้องต้น ได้แก่1.จำนวน  2.จำนวนทศนิยม  3.ข้อมูลบูลีน 4.จำนวนจริง 5.ข้อมูลอักขระ
            2 ข้อมูลโครงสร้าง ได้แก่     1.แถวลำดับ   2.ระเบียนข้อมูล   3.แฟ้มข้อมูล

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


6. อธิบายลักษณะสำคัญของ Pimitive Data Types
ตอบ  คือชนิดข้อมูลที่ใช้ในการเขียนโปรแกรมสำหรับเก็บข้อมูลชนิดต่างๆ ได้แก่ จำนวนเต็ม(Integer) จำนวนทศนิยม(Floating Point) ข้อมูลอักขระ(Character) และข้อมูลตรรกะ (Logical Data)


7. อธิบายลักษณะสำคัญของ Structure Data Types
ตอบ  คือกลุ่มของข้อมูลที่มีความสัมพันธ์กัน โดยข้อมูลเหล่านี้อาจมีชนิดข้อมูลที่แตกต่างกัน มีชื่อที่ใช้อ้างถึงข้อมูลแต่ละตัวต่างกัน แต่ข้อมูลกลุ่มนี้จะอยู่ภายใต้ชื่อกลุ่มข้อมูลเดียวกัน จะมีลักษณะเป็น เขตข้อมูล(Field), แถวลำดับ(Array), ระเบียน(Record)ตัวอย่างเช่น ต้องการเก็บข้อมูลของนักเรียนแต่ละคนซึ่งประกอบด้วย รหัส ชื่อ นามสกุล อายุ เกรดเฉลี่ย จำนวน 10 คน

8.  อธิบายลักษณะสำคัญของโครงสร้างข้อมูลแบบเชิงเส้น พร้อมยกตัวอย่าง
ตอบ   โครงสร้างที่มีการจัดเก็บข้อมูลในลักษณะต่อเนื่องกัน ถ้าทราบตำแหน่งแรกของข้อมูลก็สามารถทราบตำแหน่งข้อมูลตัวถัดไปหรือข้อมูลตัวอื่นได้ ทางคณิตศาสตร์จะเรียกว่า เวกเตอร์ (Vector) ข้อมูลมีลักษณะเป็น 1 มิติ ยกตัวอย่างเช่น อาเรย์, สแตก, คิว, ลิสต์




 9.  อธิบายลักษณะสำคัญของโครงสร้างข้อมูลแบบไม่เป็นเชิงเส้น พร้อมยกตัวอย่าง
ตอบ   โครงสร้างข้อมูลแบบไม่เชิงเส้น (Non-Linear Structure) โครงสร้างที่ไม่มีคุณสมบัติของเชิงเส้น สามารถใช้แสดงความสัมพันธ์ของข้อมูลที่ซับซ้อนได้มากกว่าโครงสร้างข้อมูลแบบเชิงเส้นเช่น ทรี, กราฟ




10.      เขียนผังแสดงการจัดหมวดหมู่โครงสร้างข้อมูลคอมพิวเตอร์ พร้อมอธิบาย
ตอบ 

 1. โครงสร้างข้อมูลเบื้องต้น (Primitive Data Structure) เป็นชนิดข้อมูลที่ไม่มีโครงสร้างข้อมูลอื่นมาเป็นส่วนประกอย เมื่อต้องการเก็บค่าสามารถเรียกใช้งานได้ทันที บางครั้งเรียกว่าชนิดข้อมูลพื้นฐาน (Base Type) หรือสร้างมาให้ใช้ด้วยภาษานั้น ๆ  ส่วนโครงสร้างข้อมูลแบบอื่น ๆ จะมีโครงสร้างข้อมูลอื่นเป็นส่วนประกอบ เมื่อต้องการใช้จะต้องกำหนดรูปแบบรายละเอียดโครงสร้างขึ้นมาก่อนเรียกว่าข้อมูลชนิดผู้ใช้กำหนด
(Uses-defined Type) ดังนี้
        2. โครงสร้างข้อมูลแบบเรียบง่าย (Simple Data Structure) จะมีสมาชิกที่เป็นโครงสร้างข้อมูลอื่นเป็นส่วนประกอบ มีรูปแบบง่าย ๆ ไม่ซับซ้อน สามารถทำความเข้าใจและสร้างขึ้นมาใช้งานได้ง่าย
                3. โครงสร้างข้อมูลเชิงเส้น (Linear Data Structure) เป็นโครงสร้างที่ความซับซ้อนมากขึ้น ประกอบด้วยสมาชิกที่เป็นโครงสร้างข้อมูลอื่นจัดเรียงต่อกันเป็นแนวเส้น
               4. โครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) เป็นโครงสร้างที่มีความซับซ้อนเช่นกัน ประกอบด้วยสมาชิกที่เป็นโครงสร้างข้อมูลอื่นจัดเรียงกันในรูปแบบไบนารี่ ที่จัดเรียงสมาชิกมีการแยกออกเป็นสองทาง และแบบ N- อาร์เรย์ ที่จัดเรียงสมาชิกมีการแยกออกได้หลายทางหลายรูปแบบไม่แน่นอน
5. โครงสร้างการจัดการแฟ้มข้อมูล (File Organization) เป็นโครงสร้างสำหรับนำข้อมูลเก็บไว้ในหน่วยความจำสำรอง โดยข้อมูลจะอยู่ในรูปแบบโครงสร้างข้อมูลอื่น และมีวิธีการจัดการโดยการนำโครงสร้างข้อมูลอื่น ๆ มาช่วย
โครงสร้างข้อมูลต่าง ๆที่กล่าวมาอาจต้องมีการควบคุมการทำงานที่เกี่ยวข้องกับข้อมูลและส่วนที่มาเกี่ยวข้องให้เป็นไปตามที่ต้องการเรียกว่า โครงสร้างข้อมูลนามธรรม ลักษณะโครงสร้างจะแบ่งออกเป็น 2 ส่วน คือ ส่วนข้อมูลและส่วนปฏิบัติการ โดนภายในจะมีรายลเอียดการทำงานต่าง ๆ ประกอบด้วยโครงสร้างการจัดเก็บข้อมูลและอัลกอริทึม เมื่อใดที่เรียกใช้งานโครงสร้างนามธรรมในส่วนรายละเอียดการทำงานจะไม่ถูกเกี่ยวข้องหรือมีผลกระทบโดยถูกปิดบังไว้ จะเห็นว่าโครงสร้างข้อมูลซับซ้อนจะเป็นโครงสร้างข้อมูลนามธรรมที่ต้องมีส่วนการจัดเก็บข้อมูลและส่วนปฏิบัติการ



11.      ยกตัวอย่างที่แสดงให้เห็นถึงความสำคัญของการศึกษาโครงสร้างข้อมูล และการนำโครงสร้างข้อมูลไปใช้งาน พร้อมอธิบายโดยละเอียด
ตอบ    1. อธิบายลักษณะจัดเก็บข้อมูล ด้วยโครงสร้างข้อมูลที่เหมาะสมได้
2. สามารถเขียนโปรแกรมจัดการโครงสร้างข้อมูลได้3. สามารถออกแบบโครงสร้างข้อมูลเพื่อใช้งานได้อย่างมีประสิทธิภาพ 





วันศุกร์ที่ 19 ตุลาคม พ.ศ. 2555

วิชาโครงสร้างข้อมูลและอัลกอริทึม



พื้นฐานโครงสร้างข้อมูล 

            คอมพิวเตอร์เป็นอุปกรณ์ที่สร้างขึ้นมาเพื่อใช้จัดการและเปลี่ยนแปลงข้อมูลข่าวสาร (Information) ดังนั้น จึงต้องมีการศึกษาถึงการควบคุมดูแลการทำงานของคอมพิวเตอร์ที่ยุ่งเกี่ยวกับข้อมูลข่าวสาร เมื่อมีการเปลี่ยนแปลงแก้ไขหรือเพื่ออำนวยประโยชน์ที่ต้องการการทำงานเพื่อนแก้ไขปัญหาต่าง ๆ ด้วยระบบคอมพิวเตอร์จะประกอบด้วยส่วนต่าง ๆ ทางด้านฮาร์ดแวร์ (Hardware) เช่น ซีพียู (CPU) หน่วยความจำ (Memory) อุปกรณ์รับส่งข้อมูล(Input/Output Device)และซอฟแวร์(Software)ที่นำมาใช้ควบคุมการทำงานของฮาร์ดแวร์ เพื่อแก้ไขปัญหานั้น ๆ ในการแก้ไขปัญหาจึงต้องมีกระบวนการพัฒนาซอฟต์แวร์ (Software Development) ที่เป็นขั้นตอนมาใช้ดังนี้
ขั้นตอนการพัฒนาซอฟแวร์
การแยกแยะและวิเคราะห์ปัญหา
        ในขั้นตอนแรกเป็นการแก้ไขปัญหาโดยการวิเคราะห์และแยกแยะ สิ่งแรกที่ต้องพิจารณา คือ เอาต์พุต ที่ต้องการและมีข้อมูลข่าวสารอะไรบ้างที่ทำที่ทำให้สามารถแก้ไขปัญหาได้หลังจากพิจารณาเอ้าท์พุตก็คือพิจารณาอินพุต และมีข้อมูลข่าวสารอะไรบ้างที่ทำให้สามารถแกไขปัญหาได้ หลังจากแยกแยะเอ้าท์พุตและอินพุต รวมถึงข้อมูลข่าวสารที่ต้องการเสร็จสิ้นลงก้เป็นการพัฒนาเขียนอัลกอรึทึมและโปรแกรม
การออกแบบระบบ
        เนื่องจากระบบคอมพิวเตอร์ไม่สามารถที่จะเข้าใจและแกไขปัญหาบางอย่างได้ จึงต้องมีวิธีการที่จะแก้ไขปัญหาโดยการออกแบบระบบ ซึ่งเป็นการวางแผนออกแบบที่แยกแยะออกเป็นปัญหาย่อย และพิจารณาสร้างชุดคำสั่งเพื่อแก้ไขปัญหาย่อยนั้น จากนั้นมารวมกันเป็นระบบที่สามารถแก้ไขปัญหาทั้งหมด มีลักษณะการวางแผนออกแบบจากบนลงล่าง (Top-down Design) ซึ่งประกอบด้วย 2 ส่วนหลัก ๆ คือ
        1. โครงสร้างข้อมูล (Data Strutcure) ใช้ควบคุมและจัดการกับข้อมูลของปัญหานั้น ๆ หรือที่เรียกว่าชนิดข้อมูลมีโครงสร้าง เรียกสั้น ๆ ว่าชนิดข้อมูล เช่น ชนิดข้อมูลอาร์เรย์ ชนิดข้อมูลสแตก และชนิดข้อมูลลิ้งค์ ลิสต์ การออกแบบระบบต้องเลือกใช้โครงสร้างข้อมูลอย่างเหมาะสมเพื่อจัดการกับข้อมูลที่ใช้ในระบบ
        2. การออกแบชุดคำสั่ง (Module Design) ในการแก้ไขปัญหาจะต้องมีกระบวนการทำงานเพื่อให้ได้มาซึ่งข้อมูลข่าวสารหรือเอ้าท์พุต ที่ต้องการโดยชุดคำสั่งเป็นส่วนประกอบของระบบ จึงต้องมีการออกแบบการทำงานที่เป็นชุดคำสั่งหรือโมดุลนั้นๆ และเรียกว่า อัลกอรึทึม ได้เป็น
โครงสร้างข้อมูล + อัลกอริทึม = โปรแกรม


โครงสร้างข้อมูลอาร์เรย์


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


โครงสร้างข้อมูลสตริง และเรคคอร์ด

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




โครงสร้างข้อมูลสแตก 

        โครงสร้างข้อมูลที่รู้จักและนำมาใช้งานมากชนิดหนึ่งก็คือ  สแตก  ( Stack ) มีลักษณะเป็นรายการในแนวเชิงเส้น   ( Linear  List )  รูปแบบหนึ่ง  และมีข้อกำหนด ให้ชุดปฏิบัติการ  สามารถเพิ่มและลบรายการเพียงด้านเดียว   ซึ่งเป็นด้านบนสุดของสแตก   ( Top of  Stack )  เรียกว่าตัวชี้สแตก (  Stack  Pointer )  มีรูปแบบเป็น Top ( S )   โดยสแตกมีการกำหนดเป็นรูปแบบ  ดังนี้
        S = [  S 1 , S 2  , . . . , S T  ]
           
        ด้านบนสุดของสแตกจะอยู่ที่  Top ( S )  = S T   และมีจำนวนสมาชิกในสแตกเท่ากับ  T  ดังในรูปที่  4.1

            รูปที่  4.1  ตัวอย่างลักษณะสแตกที่มีสมาชิกเท่ากับ  T  มีตัวชี้สแตก Top



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

   
คิว (Queue) เป็นโครงสร้างข้อมูลที่รู้จักและนำมาใช้งานมากเช่นเดียวกับสแตก (Stack) และมีลักษณะเป็นรายการในแนวเชิงเส้น (Linear List) เช่นกัน มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าเข้าไปในตอนท้ายของรายการเพียงด้านเดียว เรียกว่า ส่วนหลัง (Rear) และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่าส่วนหน้า (Front) ซึ่งกำหนดคิวเป็นรูปแบบดังนี้
    Q = [Q1, Q2, . . .  , QT]
            โดย Front (Q) คือ Q1 และ Rear (Q) คือ QT มีจำนานสมาชิกในคิวเท่ากับ T ดังในรูปที่ 5.1 โดยลักษณะมีตัวชี้ส่วนหน้าอยู่ด้านซ้ายและตัวชี้ด้านท้ายอยู่ด้านขวา และอาจกลับด้านกันก็ได้ให้ตัวชี้ส่วนหน้าอยู่ด้านขวาและตัวชี้ส่วนท้ายอยู่ด้านซ้าย


โครงสร้างข้อมูลลิ้งค์ลิสต์



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


โครงสร้างข้อมูลลิ้งค์ลิสต์

วิธีแก้ปัญหาในการย้ายข้อมูลที่พบในการจัดเก็บที่มีรูปแบบเรียงตามลำดับ(Sequential)เปลี่ยนมาใช้รูปแบบไม่เรียงตามลำดับ(Non-sequential)ซึ่งรูปแบบการเรียงตามลำดับจะมีสมาชิกเรียงต่อเนื่องติดกันในทางตรรกะ (Logical) และทางกายภาพ(Physical) เป็นแบบเดียวกัน แต่รูปแบบไม่เรียงตามลำดับสมาชิกต่อเนื่องติดกันในทางตรรกะ ส่วนทางกายภาพไม่จำเป็นต้องเหมือนกัน โดยในทางตรรกะจะแสดงด้วยแต่ละสมาชิกมีการชี้ (Point) ต้อไปยังสมาชิกตัวถัดไป สมาชิกทุกตัวในรายการจึงถูกเชื่อมต่อ (Link) เข้าด้วยกัน ดังรูปที่ 6.1 เป็นรายการเชื่อมต่อหรือเรียกว่าลิงค์ลิสต์ (Linked List) มีสมาชิก N ตัว แต่ละสมาชิกเรียกว่าโหนด (Node)


รีเคอร์ซิฟ

        ในระหว่างการออกแบบเขียนโปรแกรมแบบบนลงล่าง (Top-down Design)  จะมีงานย่อย (Subtask)  เพื่อแก้ปัญหาในแต่ละเรื่อง และผู้เขียนโปรแกรมต้องการใช้งานย่อยที่เรียบง่าย และสามารถแก้ไขปัญหาที่มีขนาดใหญ่ได้ จึงมีการใช้งานย่อยในลักษณะที่เรียกตัวเองขึ้นมาทำงาน เรียกว่า รีเคอร์ซีฟ (Recursive)  เป็นเทคนิคที่ส่วนใหญ่ใช้กับโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้น อย่างเช่น ทรี (Tree)  และกราฟ (Graph)  เพื่อให้การใช้งานมีความสะดวกและง่าย
ฟังก์ชันรีเคอร์ซีฟ
        โดยส่วนใหญ่การเขียนโปรแกรมจะใช้ฟังก์ชันเรียกฟังก์ชันอื่นขึ้นมาทำงาน บางครั้งอาจต้องมีการให้ฟังก์ชันเรียกตัวเองขึ้นมาทำงานเรียกว่าฟังก์ชันรีเคอร์ซีฟ  (Recursive Function)  ซึ่งใช้ในบางภาษา เช่น ภาษาซี ปาสคาล จาวา ปกติแล้วการเขียนอัลกอริทึมที่มีการทำงานซ้ำแบบเดิมจะใช้การวนลูปแบบต่าง ๆ แต่ใช้เป็นฟังก์ชันรีเคอร์ซีฟแทนได้ในลักษณะทำซ้ำอัตโนมัติ บางครั้งจึงเรียกว่า ลูปเสมือน  (Virtual Loop)


อัลกอริทึม


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

การตรวจสอบความถูกต้องของอัลกอริทึม

การเรียกให้โปรแกรมหรือระบบทำงานแบบเบื้องต้นเพื่อทดสอบกับข้อมูลที่หลากหลายยังไม่มีประสิทธิภาพเพียงพอเนื่องจากการทดสอบแสดงให้ทราบถึงข้อผิดพลาดที่ปรากฏอยู่เท่านั้น แต่ข้อผิดพลาดที่ไม่ปรากฏจะไม่สามารถทราบได้ จึงนำการตรวจสอบแบบการอนุมาน (Deductive) มาใช้เพื่อรับประกันว่าผลลัพธ์มีความถูกต้อง
การตรวจสอบอัลกอริทึมเพื่อใช้แก้ไขปัญหาว่ามีความถูกต้องจึงใช้การอนุมานซึ่งแสดงขั้นตอนการประมวลผลของอัลกอริทึมถูกต้องหรือไม่ตั้งแต่มีการรับข้อมูลเข้ามาและแก้ปัญหาจนถึงผลลัพธ์ที่ได้ออกมา ดังนั้น การตรวจสอบความถูกต้องของอัลกอริทึม A เริ่มต้นด้วยการ
วินิจฉัย I เป็นการสมมุติข้อมูลที่จะรับเข้ามาใช้งาน (Input Assertion) เรียกว่าเงื่อนไขตอนต้นเรียกว่าเงื่อนไขตอนท้าย (Post ondition) ได้เป็นข้อพิสูจน์ทางตรรกะแสดงให้ทราบวา O จะเกิดขึ้นตาม I และได้เป็น


ได้หลักเกณฑ์ คือ เมื่อกำหนดเงื่อนไขตอนต้น I หลังจากอัลกอริทึม A ทำงานจนถึงจุดสิ้นสุด (Terminate) จะต้องได้เงื่อนไขตอนท้าย O โดยพิจารณาจากตัวอย่างอัลกอริทึมหาค่าเฉลี่ยของค่าทั้งหมดที่เก็บไว้ในอาร์เรย์ดังในตารางที่ 8.1

ตารางที่ 8.1 อัลกอริทึมคำนวณหาค่าเฉลี่ย
1.กำหนดค่าเริ่มต้นให้ตัวแปร sum = 0
2.กำหนดค่าเริ่มต้นให้ตัวแปรดัชนี i = 0
3.วนลูป while i < n ให้ทำดังนี้
  a. นำค่าของอาร์เรย์ X[i] บวกกับตัวแปร sum
  b. เพิ่มค่าให้กับตัวแปร i หนึ่งค่า
4. คำนวณหาค่าเฉลี่ย sum/n และส่งคืนกลับ
เมื่อวินิจฉัยการรับค่า I จะได้คำอธิบายดังนี้
I: ค่าที่รับเข้ามาประกอบด้วยตัวเลข n > 1 และอาร์เรย์ X ที่เก็บค่าเลขทศนิยม
เมื่อวินิจฉัยผลลัพธ์ O ออกมาจะได้คำอธิบาย
O: อัลกอริทึมทำงานเสร็จ ค่าที่ส่งคืนกลับมาให้เป็นค่าเฉลี่ยของ X[0],…,X[n-1]

การแสดงผลการทำงานได้ว่าเงื่อนไขตอนท้าย O จะเกิดขึ้นมาได้ตามเงื่อนไขตอนต้น I และมีหลายช่วงของอัลกอริทึมซึ่งเป็นการวินิจฉัยตอนกลาง (Intermediate Assertion) โดยเกี่ยวกับสถานะของการประมวลผลเมื่อทำงานถึงในช่วงนั้น ๆ จากตัวอย่างอัลกอริทึมที่ผ่านมามีการวินิจฉัยตอนกลาง L ในส่วนท้ายของการวนลูป while ซึ่งจะเป็นจริงทุกครั้งเมื่อการทำงานมาถึงช่วงนี้และการวินิจฉัยตอนกลางนี้เรียกว่าการวนลูปสม่ำเสมอ (Loop Invariant) จะได้ว่า

I: ค่าที่เข้ามาประกอบด้วยตัวเลข n > 1 และอาร์เรย์ X ที่เก็บค่าเลขทศนิยม
1. กำหนดค่าเริ่มต้นให้ตัวแปร sum = 0
2. กำหนดค่าเริ่มต้นให้ตัวแปรดัชนี i = 0
3. วนลูป while i < n ให้ทำดังนี้
a. นำค่าของอาร์เรย์ X[i] บวกให้ตัวแปร Sum
b. เพิ่มค่าให้กับตัวแปร i หนึ่งค่า
L: ค่าของตัวแปร i เป็นจำนวนครั้งในการทำงานที่ถึงในแต่ละช่วง และตัวแปร sum เป็นผลรวมค่าของแต่ละสมาชิก i ในอาร์เรย์ X
4. คำนวณค่าเปลี่ยน sum/n และส่วนคืนกลับ
O: อัลกอริทึมทำงานเสร็จ ค่าที่ส่งคืนกลับมาให้เป็นค่าเฉลี่ยของ X[i],…,X[n-1]

การตรวจสอบจึงประกอบด้วยการแสดงคำอธิบายให้ทราบว่าการวินิจฉัย L จะเกิดขึ้นตาม
การรับค่าเข้ามาของการวินิจฉัย I และแสดงให้ทราบว่าการวินิจฉัย O จะเกิดขึ้นตามการวินิจฉัย L
การอนุมานทางคณิตศาสตร์สามารถนำมาใช้กับการวนลูปสม่ำเสมอ I ได้โดยสมมุติให้ k เป็นจำนวนครั้งในการทำงานที่ไปถึงส่วนล่างของการวนลูป ให้ ik และ sumk เป็นค่าของตัวแปร i และ sum ตามลำดับของแต่ละครั้งที่ทำงานมาถึง เมื่อ k = 1 เป็นการผ่านรอบแรกในลูป ค่าของ i มีค่าเป็น 0 จากค่าเริ่มต้นเท่ากับ 0 (บรรทัด 2) ตัวแปร sum มีค่าเท่ากับ X[0] (บรรทัด 3) ดังนั้นจะได้ว่าตัวแปร i และ sum มีค่าที่ถูกวินิจฉัยของ L เมื่อ k = 1 หากสมมุติให้การทำงานเมื่อไปถึงส่วนล่างของการวนลูปสำหรับครั้งที่ k การวนลูปสม่ำเสมอของ L ได้เป็น ดังนี้

ik = k และ sumk = X[0] + . . . + X[k]

ซึ่งสามารถตรวจสอบได้ว่า L เป็นจริงเช่นกันเมื่อการทำงานต่อไปผ่านไปถึงการวนลูปในครั้งที่ k + 1 ซึ่งได้เป็น

ik+1 = k + 1 และ sumk+1 = X[0] +. . . + X[k]

ในรอบที่ k + 1 เมื่อผ่านการวนลูปค่าของ i มีความถูกต้องเพื่อใช้งานดังนี้

sumk+1 = sumk + X[k] (บรรทัด 3a)
= X[0] +. . . + X[k] (การอนุมานสมมุติ)

และค่าของ i จะเพิ่มขึ้นหนึ่งค่าดังนี้

ik+1 = ik + 1 (บรรทัด 3b)
= k + 1 (การอนุมานสมมุติ)

จากนี้เมื่อทำต่อเนื่องโดยการอนุมานในแต่ละครั้งการทำงานไปถึงส่วนล่างของการวนลูปค่าของตัวแปร i และ sum จะถูกวินิจฉัยในการวนลูปสม่ำเสมอ หลังจากการวนลูปทำงานผ่านรอบที่ n ค่าของ sum = X[0] + ... + X[n-1] และค่าของ i = n เมื่อค่าของ i เท่ากับค่า n นิพจน์ i < n ซึ่งควบคุมการทำงานซ้ำในลูปเป็นเท็จ ลูป while จึงหยุดการทำงานและทำต่อที่บรรทัด 4 เป็นการคำนวณหาค่าของสมาชิกในอาร์เรย์ จากนั้นการทำงานถึงจุดสิ้นสุดของอัลกอริทึมและนำการวินิจฉับผลลัพธ์มาใช้ ดังนั้น การตรวจสอบความถูกต้องของอัลกอริทึมจึงเสร็จสมบูรณ์




โครงสร้างข้อมูลทรี

                โครงสร้างข้อมูลในบทต่าง ๆ ที่ได้กล่าวผ่านมาเป็นโครงสร้างเชิงเส้น  (Linear  Data  Structure)  แต่ละสมาชิกจะมีสมาชิกตัวถัดไปเพียงตัวเดียว  สำหรับในบททนี้จะกล่าวถึงโครงสร้างข้อมูลไม่เป็นเชิงเส้น  (Nonlinear  Data  Structure)  ซึ่งแต่ละสมาชิกสามารถมีสมาชิกตัวถัดไปได้หลายตัว  โดยมีแนวความคิดของโครงสร้างแตกสาขา  (Branching  Structure)  และเป็นที่รู้จักคือ  โครงสร้างข้อมูลทรี  (Tree)  ซึ่งกล่าวถึงในบทนี้กับโครงสร้างข้อมูลกราฟ  (Graph)  จะกล่าวถึงในบทหน้าถัดไป
ทรีทั่วไป
            จากลักษณะพิเศษของทรีทั่วไป  (General  Tree)  มีการกำหนดเป็นระดับซึ่งมีตัวแรก  คือ  รูททรี  (Rooted  Tree)  ซึ่งมีเพียงโหนดเดียวทำหน้าที่เป็นรูท  (Root)  และมีความแตกต่างจากโหนดอื่น ๆ รูทของทรี  T  จะกำหนดเป็น  Root(T)  โดยทรี  T  เป็นเช็ตจำนวนที่แน่นอน  (Finite  Set)  ตั้งแต่  0  หรือมากกว่าของโหนด  (v1, v2, . . . , vn)  ดังนั้น
                1.  จะมีเพียงโหนดเดียว  (v1)  ที่ออกแบบเป็นพิเศษ  เรียกว่า  Root  (T)
                2.  โหนดที่เหลือ  (v2, . . . , vn)  จะถูกแบ่งออกเป็นส่วน ๆ เท่ากับ  m http://itd.htc.ac.th/st_it50/it5027/image/DSA/Unit9_files/image003.gif 0 ที่ต่อกันเป็นเช็ตชื่อ  T1, T2, . . ., Tm  จะได้ว่าแต่ละ  Ti  คือ  ทรีและเป็นทรีย่อย  (Subtree)  ของรูททรีหรือ  Root(T)
                3.  หากทรีใด ๆ ไม่มีโหนดเลยเรียกว่านัลทรี  (Null  Tree)

โครงสร้างข้อมูลกราฟ


   กราฟ  (Graph)  เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น  (Nonlinear  Data  Structure)  มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา  แต่เป็นลักษณะพิเศษแบบหนึ่งของกราฟ  โดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ  เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด
        กราฟมีลักษณะเป็นเซ็ตของจุด  (Point)  และเซ็ตของเส้น  (Line)  ซึ่งแต่ละเส้นทำหน้าที่เชื่อมจุดเข้าด้วยกัน  แต่ละจุดเรียกว่าโหนด  (Node)  ของกราฟและเส้นเรียกว่าเอจ  (Edge)  บางครั้งเอจจะเรียกว่าอาร์ค  (Arc)  และโหนดเรียกว่าเวอร์ทิค  (Vertice)  โดยกำหนดให้กราฟ  G  มีเซ็ตของโหนดเป็น  VG  และเซ็ตของเอจเป็น  EG  เช่น  ในรูปที่ 10.1  VG  =  {a, b, c, d}  และ  EG  =  {1, 2, 3, 4, 5, 6, 7, 8,}  จำนวนสมาชิกที่มีใน  VG  เรียกว่าออเดอร์  (Order)  ของกราฟ  ถ้าออเดอร์เท่ากับ  0  คือ  กราฟไม่มีสมาชิกเรียกว่านัลกราฟ  (Null  Graph)

การจัดเรียงลำดับข้อมูล

            สำหรับบทนี้เป็นการกล่าวถึงเทคนิคในการจัดเรียงลำดับค่าของข้อมูล ( Sorting )  ซึ่งเป็นกระบวนการที่คล้ายกับเทคนิคในการค้นหาค่าของข้อมูล ( Searching )  ที่จะกล่าวในบทถัดไปเป็นการจัดเรียงลำดับค่าของข้อมูลหรือการเรียงลำดับข้อมูลจะพิจารณาจากการรวบรวมเรคคอร์ดหรือระเบียน  ( Record )  โดยมีคีย์ที่นำมาใช้พิจารณาถึงลำดับก่อนหน้าและหลังของแต่ละเรคคอร์ดเพื่อประสิทธิภาพการทำงานและง่ายต่อการเรียกใช้งาน  การเรียงลำดับข้อมูลจึงเป็นกระบวนการเพื่อจัดการเรคคอร์ดให้จัดเรียงลำดับตามค่าของคีย์  เป็นเทคนิคที่ช่วยให้การค้นหาข้อมูลมีประสิทธิภาพมากขึ้น  โดยมีการแบ่งออกเป็น 2 ประเภทหลัก ๆ คือ
การเรียงลำดับภายใน
        การเรียงลำดับภายใน ( Internal Sorting )  เป็นหลักการที่นำมาใช้เมื่อข้อมูลทั้งหมดที่รวบรวมไว้มีขนาดเล็กเพียงพอที่จะเก็บไว้           และทำการเรียงลำดับภายในหน่วยความจำหลัก     ( Memory )  เวลาที่ใช้ในการอ่านและเขียนเรคคอร์ดจะไม่นำมาใช้พิจารณาถึงประสิทธิภาพการเรียงลำดับข้อมูล  แต่จะใช้เวลาในการเปรียบเทียบค่าของคีย์มาพิจารณา  นอกจากนี้การเรียงลำดับภายในยังแบ่งออกเป็น  2  ลักษณะ คือ การเรียงลำดับข้อมูลที่ใช้เฉพาะพื้นที่หน่วยความจำของตนเอง ( Inplace Sort )  และการเรียงลำดับข้อมูลที่ต้องใช้พื้นที่หน่วยความจำเพิ่มเติมเข้ามาช่วยจัดเรียง
การเรียงลำดับภายนอก
        การเรียงลำดับภายนอก ( External Sorting )  เป็นหลักการที่นำมาใช้กับข้อมูลที่รวบรวมไว้เป็นจำนวนมาก ๆ ไม่สามารถเก็บไว้ในหน่วยความจำหลักได้หมดในคราวเดียวกัน   แต่ต้องเก็บไว้ในหน่วยความจำสำรอง  เช่น  เทปแม่เหล็กหรือจานแม่เหล็ก  การเรียงลำดับข้อมูลจะกระทำได้เพียงบางส่วน  ในแต่ละครั้ง   ประสิทธิภาพการเรียงลำดับแบบนี้จึงพิจารณาจากเวลาที่ใช้อ่านและเขียน  เพื่อถ่ายโอนข้อมูลระหว่างหน่วยความจำหลักกับหน่วยความจำสำรอง
        บางครั้งการเรียงลำดับใช้กับเรคคอร์ดที่มีค่าของคีย์ซ้ำกันได้  ทำให้อัลกอริทึมการเรียงลำดับเรียกว่า สเตเบิ้ล  ( Stable Sort )  เมื่อลำดับของเรคคอร์ดที่มีค่าของคีย์ที่ซ้ำกันยังคงมีลำดับเหมือนเดิมหลังจากมีการเรียงลำดับ  เช่น  เรคคอร์ดที่ 5  และ 8  มีค่าของคีย์เท่ากัน  หลังจากที่เรียงลำดับแล้วเรคคอร์ดที่ 5  ยังคงมาก่อนเรคคอร์ดที่ 8  เหมือนเดิม  จึงเรียกว่า  การเรียงลำดับแบบสเตเบิ้ล  แต่ถ้าหากเรคคอร์ดที่ 5  ไปอยู่หลังเรคคอร์ดที่ 8  ไม่ว่าจะเป็นสเตเบิ้ล  การเรียงลำดับแบบสเตเบิ้ลนำมาใช้เมื่อลำดับเดิมยังมีความสำคัญหรือมีความหมายบางอย่างในการใช้งาน  เช่น  การเรียงลำดับเรคคอร์ดตามค่าของคีย์แต่คำนึงถึงเวลาของแต่ละเรคคอร์ดที่บันทึกเก็บไว้


การค้นหาข้อมูล


                           ในบทนี้เป็นการกล่าวถึงเทคนิคในการค้นหาค่าของข้อมูล  (Searching)  ที่เป็นโครงสร้างซึ่งเป็นเทคนิคที่นำมาใช้กับแฟ้มข้อมูล  และเมื่อพิจารณาถึงการรวบรวมเรคคอร์ด  แต่ละเรคคอร์ดจะมีคีย์ที่นำมาใช้แยกแยะความแตกต่างจากเรคคอร์ดอื่น ๆ คีย์อาจประกอบด้วยฟิลด์เดียวหรือหลายฟิลด์  ค่าของคีย์อาจจะสร้างความเป็นหนึ่งเดียวให้กับเรคคอร์ดหรือเป็นแบบให้มีค่าซ้ำกันได้หลายเรคคอร์ด  แต่คำนึงถึงลำดับก่อนหลังเมื่อถูกเพิ่มเข้ามา  การค้นหาข้อมูลจึงเป็นกระบวนการหาตำแหน่งของเรคคอร์ดที่ต้องการตามค่าของคีย์  โดยมีอัลกอริทึมการค้นหาเป็นเทคนิคในการค้นหาเรคคอร์ดตามค่าของคีย์ซึ่งเป็นค่าที่ได้รับเข้ามาเพื่อค้นหา  ในการค้นหาจะสิ้นสุดลงเมื่อพบเรคคอร์ดที่มีค่าคีย์ตรงกันหรือไม่พบ  อัลกอริทึมที่นำมาใช้มีหลายแบบแต่ที่กล่าวถึง  คือ
1.   การค้นหาแบบลำดับ  (Sequential Search)
2.   การค้นหาแบบแบ่งครึ่ง  (Binary Search)
3.   การค้นหาแบบสอดแทรก  (Interpolation Search)
4.   การค้นหาข้อความ  (Text Searching)

อ้างอิง                             

http://itd.htc.ac.th