DTS 11/08-09-2552

สรุป กราฟ ต่อ

การท่องไปในกราฟ คือ การเข้าไปเยือนโหนดในกราฟ
หลักการทำงาน คือ แต่ละโหนดจะถูกเยือนเพียงครั้งเดียว

เทคนิคการท่องไปในกราฟมี 2 แบบ
1.การท่องแบบกว้าง โดยเลือกโหนดที่เป็นจุดเริ่มต้น ต่อมาให้เยือนโหนดอื่นที่ใกล้กันกับโหนดเริ่มต้นที่ละระดับ
จนเยือนหมดทุกโหนดในกราฟ (แบบคิว)

2.การท่องแบบลึก คล้ายกับการท่องทีละระดับของทรี กำหนดเริ่มต้นที่โหนดแรกและเยือนโหนดถัดไปตามแนววิถีจน
ไปสู่ปลายวิถี จากนั้นย้อนกลับตามแนววิถีเดิม จนสามารถดำเนินการต่อเนื่องเข้าสู่แนววิถีอื่นๆ เพื่อเยือนโหนดอื่นๆ
ต่อไปจนครบทุกโหนด (แบบสแตก)

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

การเรียงลำดับอย่างมีประสิทธิภาพ
หลักเกณฑ์ในการพิจารณาเพื่อเลือกวิธีการเรียงลำดับที่ดีและเหมาะสมกับระบบงาน

1.เวลาและแรงงานที่ต้องใช้ในการเขียนโปรแกรม

2.เวลาที่เครื่องคอมพิวเตอร์ต้องใช้ในการทำงานตามโปรแกรมที่เขียน

3.จำนวนเนื้อที่ในหน่วยความจำหลักมีเพียงพอหรือไม่
วิธีการเรียงลำดับ มีหลายวิธีที่สามารถใช้ในการเรียงลำดับข้อมูลได้

วิธีการเรียงลำดับแบ่งออกเป็น 2 ประเภท
1.การเรียงลำดับภายใน (internal sorting) เป็นการเรียงลำดับที่ข้อมูลทั้งหมดต้องอยู่ในหน่วยความจำหลัก
2.การเรียงลำดับแบบภายนอก (external sorting) เป็นการเรียนลำดับข้อมูลที่เก็บอยู่ในหน่วยความจำสำรอง
เป็นการเรียงลำดับข้อมูลในแฟ้มข้อมูล

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

การเรียงลำดับแบบ Bubble Sort
เป็นวิธีการเรียงลำดับที่มีการเปรียบเทียบข้อมูลในตำแหน่งที่อยู่ติดกัน
1.ถ้าข้อมูลทั้งสองไม่อยู่ในลำดับที่ถูกต้องให้สลับตำแหน่งที่อยู่กัน
2.ถ้าเป็นการเรียงลำดับจากน้อยไปมากให้นำข้อมูลตัวที่มีค่าน้อยกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก ถ้าเป็นการเรียงลำดับจากมากไปน้อยให้นำข้อมูล ตัวที่มีค่ามากกว่าอยู่ในตำแหน่งก่อนข้อมูลที่มีค่าน้อย
การจัดเรียงลำดับแบบฟองเป็นวิธีที่ไม่ซับซ้อนมาก เป็นวิธีการเรียงลำดับที่นิยมใช้กันมากเพราะมีรูปแบบที่เข้าใจง่าย

DTS 10/01-09-2552

สรุป Tree(ต่อ)เอ็กซ์เพรสชันทรี การนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์
ลำดับขั้นตอนการคำนวณความสำคัญของเครื่องหมายมีดังนี้
-ฟังก์ชัน
-วงเล็บ
-ยกกำลัง
-เครื่องหมายหน้าเลขจำนวน-คูณ หรือ หาร
-บวก หรือลบ
-ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา

สรุป กราฟ (Graph)
กราฟ เป็น โครงสร้างข้อมูลแบบไม่ใช่เชิงเส้น นำไปใช้แก้ปัญหาที่ค่อนข้างซับซ้อน

นิยามของกราฟ
กราฟ เป็นโครสร้างข้อมูลแบบไม่ใช่เชิงเส้น ที่ประกอบ
1.โหนด หรือเวอร์เทกซ์
2.เส้นเชื่อมระหว่างโหนด เรียก เอ็จ (Edges)
-กราฟที่มีเอ็จเชื่อมระหว่างโหนดสองโหนด ถ้าเอ็จไม่มีลำดับ ความสัมพันธ์เรียกกราฟว่า กราฟแบบไม่มีทิศทาง
-ถ้ากราฟมีเอ็จที่มีลำดับความสัมพันธ์หรือมีทิศทางกำกับด้วยเรียกกราฟว่า กราฟแบบมีทิศทาง -การเขียนกราฟแสดงโหนดและเส้นเชื่อมความสัมพันธ์ระหว่างโหนดไม่มีรูปแบบที่ตายตัว
-เขียนกราฟเพื่อแสดงให้เห็นความสัมพันธ์ของสิ่งที่สนใจแทนโหนดด้วยจุด หรือวงกลม ที่มีชื่อหรือข้อมูลกำกับ

ลักษณะของกราฟ
-กราฟที่มีลักษณะต่อเนื่อง เป็นกราฟที่มีเส้นทางเชื่อมจากโหนดใดๆ ไปยังโหนดอื่นเสมอ
-กราฟที่มีลักษณะเป็นวิถี มีเส้นเชื่อมไปยังโหนดต่างๆ อย่างเป็นลำดับ โดยแต่ละโหนดจะเป็นโหนดที่ใกล้กันกับโหนดที่อยู่ถัดไป
-กราฟที่เป็นวัฎจักร ต้องมีอย่างน้อย 3 โหนด ที่โหนดสุดท้ายต้องเชื่อมกับโหนดแรก
-กราฟที่มีลักษณะไม่ต่อเนื่อง ไม่มีเส้นทางเชื่อมจากโหนด 3 ไปยังโหนดอื่นเลย
-กราฟแบบมีทิศทาง เป็นเซตแบบจำกัดของโหนดและเอ็จ โดยเซตจะว่างไม่มีโหนดหรือเอ็จเลยเป็นกราฟว่าง รูปแบบของกราฟแบบมีทิศทางเหมือนกับรูปแบบของกราฟไม่มีทิศทาง ต่างกันตรงที่กราฟแบนี้จะทิศทางกำกับด้วยเท่านั้น

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