DTS12/08-09-2009

เรื่อง ตารางแฮช (Hash Table)
ตารางข้อมูลแบบตรง

สมมติว่ามีการกำหนดให้คีย์มาจากเอกภพสัมพัทธ์U={0,1.....,m-1}
การแก้ไขปัญหาคือใช้ตาราง T[0...m-1]การสร้างดัชนีโดยคีย์เพื่อใช้ในการเชื่อมโยงข้อมูล เข้าด้วยกันเพื่อเก็บข้อมูลตำแหน่งที่ถูกต้อง

การชนกันของข้อมูล (Collision)
การแทรกคีย์ในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ที่ถูกสร้างจากฟังก์ชัน ในช่องเดียวกัน

ทางปฏิบัติใช้เทคนิค ฮิวริสติก ในการสร้างฟังก์ชั่นแฮซ แนวทางหนึ่งที่ดีคือ การแปลงค่าของข้อมูลที่มีอยู่แล้วด้วยข้อมูลที่มีอยู่
ฟังก์ชั่นแฮช คือ การกำหนอกค่าคีย์ที่เกิดขึ้นในเอกภพสัมพัทธจากตัวเลขธรรมชาติ


วิธีการสร้างฟังก์ชั่นแฮช
1.วิธีการหาร
2.วิธีการคูณ
3.วิธีทั่วไป

เทคนิคลำดับของการตรวจสอบ
1. การตรวจสอบเชิงเส็น
2.การตรวจสอบด้วยสมการกำลังสอง
3.การสร้างฟังก์ชั่นแฮชแบบสองเท่า

DTS11/08-09-2009

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

การเรียงลำดับแบบเลือก (selection sort)
ทำการเลือกข้อมูลมาเก็บในตำแหน่งที่ ข้อมูลนั้นควรจะอยูที่ละตัว โดยทำการค้นหาข้อมูลนั้นในแต่ละรอบแบบเรียงลำดับ
การเรียงลำดับแบบฟอง(bubble sort)
เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลในตำแหน่งที่อยู่ติดกัน
การเรียงลำดับแบบเร็ว (quick sort)
เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็วในการทำงาน
การเรียงลำดับแบบแทรก(insertion sort)
เป็นวิธีการเรียงลำดับที่ทำการเพิ่มสมาชิกใหม่ไปในเซต ที่มีสมาชิกทุกตัวเรียงลำดับอยู่แล้ว และทำให้เซตใหม่ได้นี้มีสมาชิกทุกตัวเรียงลำดับด้วย
การเรียงลำดับแบบฐาน (radix sort)
เป็นการเรียงลำดับโดยการพิจารณาข้อมูลที่ละหลัก

DTS10/01-09-2009

เรื่อง Graph
กราฟ (Graph) เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น อีกชนิดหนึ่ง กราฟเป็นโครงสร้างข้อมูลที่มีการนำไปใช้ในงาน
ที่เกี่ยวข้องกับการแก้ปัญหาที่ค่อนข้างซับซ้อน
นิยามของกราฟ
กราฟ เป็นโครงสร้างข้อมูลแบบไม่ใช่เชิงเส้นที่ประกอบ ด้วยกลุ่มของสิ่งสองสิ่งคือ
(1) โหนด (Nodes) หรือ เวอร์เทกซ์(Vertexes)
(2) เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
การเขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ ของสิ่งที่เราสนใจแทนโหนดด้วย จุด (pointes) หรือวงกลม (circles)
ที่มีชื่อหรือข้อมูลกำกับ เพื่อบอกความแตกต่างของแต่ละโหนดและเอ็จแทนด้วยเส้นหรือเส้นโค้งเชื่อมต่อระหว่างโหนดสองโหนด
กราฟแบบไม่มีทิศทางเป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (Empty Graph)แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด หรือเชื่อมตัวเอง เอ็จไม่มีทิศทางกำกับ ลำดับของการเชื่อมต่อกันไม่สำคัญ นั่นคือไม่มีโหนดใดเป็นโหนดแรก (First Node) หรือไม่มีโหนดเริ่มต้น และไม่มีโหนดใดเป็นโหนดสิ้นสุด
กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตอาจจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง (Empty Graph) แต่ละเอ็จจะเชื่อมระหว่างโหนดสองโหนด เอ็จมีทิศทางกำกับแสดงลำดับของการเชื่อมต่อกัน โดยมีโหนดเริ่มต้น
(Source Node) และ โหนดสิ้นสุด (Target Node)รูปแบบต่าง ๆ ของกราฟแบบมีทิศทางเหมือนกับ
รูปแบบ ของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟแบบนี้จะมีทิศทางกำกับด้วยเท่านั้น