DTS11-15/09/2009

SUMMARY B4 FINAL

สรุป TREE

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

โหนดแต่ละโหนดจะต้องประกอบไปด้วยโหนดแม่

โหนดที่ต่ำกว่าโหนดแม่จะเรียกว่าโหนดลูก

โหนดที่สูงสุดและไม่มีโหนดแม่จะเรียกว่า โหนดราก

โหนดที่มีโหนดแม่เป็นโหนดเดียวกันเรียกว่า โหนดพี่น้อง

โหนดที่ไม่มีโหนดลูฏจะเรียกว่า โหนดใบ

เส้นเชื่อมแสดงความสัมพันธ์ระหว่างโหนดสองโหนดเรียกว่า กิ่ง

นิยามของทรี

1. นิยามทรีด้วยนิยามของกราฟ คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด ในโครงสร้าง การเขียนรูปแบบทรีเขียนได้ 4 แบบ
1) แบบที่มีรากอยู่ด้านบน
2) แบบที่มีรากอยู่ด้านล่าง
3) แบบที่มีรากอยู่ด้านซ้าย
4) แบบที่มีรากอยู่ด้านขวา
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟหรือการเวียนเกิด คือ ทรีที่ประกอบไปด้วยสมาชิกที่เรียกว่าโหนด โดยที่ถ้าว่าง ไม่มีโหนดใดๆ จะเรียกว่า Null Tree ถ้ามีโหนดหนึ่งเป็นโหนดราหอีกโหนดจะเป็นทรีย่อย
----------------------------------------------------------------------------
สรุป GRAPE

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

นิยมนำไปใช้แก้ปัญหาหลัก ๆ 2 ปัญหา คือ
1. การสร้างต้นไม้ทอดข้ามน้อยที่สุด(Minimum Spanning Trees :MST)
1. เรียงลำดับเอดจ์ ตามน้ำหนัก
2. สร้างป่าที่ประกอบด้วยต้นไม้ว่างที่มีแต่โหนด และไม่มีเส้นเชื่อม
3. เลือกเอดจ์ที่มีน้ำหนักน้อยที่สุดและยังไม่เคยถูกเลือกเลย ถ้ามีน้ำหนักซ้ำกันหลายค่าให้สุ่มมา 1 เส้น
4. พิจารณาเอดจ์ที่จะเลือก ถ้านำมาประกอบในต้นไม้ทอดข้ามน้อยที่สุดแล้วเกิด วงรอบ ให้ตัดทิ้งนอกนั้นให้นำมาประกอบเป็นเอดจ์ในต้นไม้ทอดข้ามน้อยที่สุด
5. ตรวจสอบเอดจ์ที่ต้องอ่านในกราฟ ถ้ายังอ่านไม่หมดให้ไปทำข้อ 3
6. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา
7. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (5,7) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
8. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุด ตามตัวอย่าง คือ edges (1,4) จากนั้นให้ตัดทิ้งไม่นำมาเชื่อมต่อต้นไม้ในป่า เนื่องจากทำให้เกิดวงรอบ
9. เลือกเอดจ์ที่เหลือและมีน้ำหนักน้อยที่สุดมา ตามตัวอย่าง คือ edges(3,5) นำมาเชื่อมต่อต้นไม่ในป่า เนื่องจากเป็นเอดจ์สุดท้าย
2. การหาเส้นทางที่สั้นที่สุด(Shortest path)
2.1 เริ่มต้นให้เซต S มีเพียงโหนดเดียว คือโหนดที่เป็นจุดเริ่มต้น
2.2 คำนวณหาระยะทางจาก โหนดที่เป็นจุดเริ่มต้น ไปยังโหนดทุกโหนดในกราฟ โดยยอมให้ใช้โหนด
ในเซต S เป็นทางผ่านได้ ถ้ามีมากกว่า 1 ทาง ให้เลือกทางที่สั้นที่สุด นำไปใส่ใน D ของแต่ละโหนด
2.3 เลือกโหนด W ที่ห่างจากโหนดเริ่มต้นน้อยที่สุดไปไว้ใน S การคำนวณหาระยะทางสั้นที่สุด จาก โหนดต้นทางคือโหนด 1 ไปยังโหนดใด ๆ
------------------------------------------------------------------------
สรุปเรื่อง sorting

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

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

การเรียงลำดับแบบฟอง เป็นการเปรียบเทียบข้อมูลที่ในตำแหน่งอยู่ติดกัน ถ้าข้อมูลทั้งสองไม่อยู่ในตำแหน่งที่ถูกต้องให้สลับตำแหน่ง ข้อมูลมีการเรียงลำดับจากน้อยไปมาก

การเรียงลำดับแบบเร็ว ใช้เวลาน้อย เหมาะกับข้อมูลที่มีจำนวนมากต้องการความรวดเร็วในการทำงาน และกำหนดค่าหนึ่งเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ โดยแบ่งข้อมูลออกเป็นสองส่วน ส่วนแรกอยู่ตอนหน้าของข้อมูล ทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่ง

การเรียงลำดับแบบแทรก เป็นการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัวเรียงกันอยู่แล้ว ทำให้เซตใหม่ได้มีสมาชิกทุกตัวเรียงลำดับด้วย

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

การเรียงลำดับแบบฐาน เป็นการพิจารณาข้อมูลทีละหลัก โดยเริ่มจากข้อมูลที่มีค่าน้อยที่สุดก่อน นั้นคือข้อมูลที่เป็นจำนวนเต็มในหลักหน่วยก่อน และจัดเรียงเข้ามาทีละตัวแล้วนำไปเก็บไว้เป็นกลุ่ม ในรอบต่อไปนำข้อมูลทั้งหมดมาจัดเรียงในหลักหน่วยก่อนแล้วจึงไปทำหลักสิบตอไป
-------------------------------------------------------------------
สรุป searching

การค้นหาข้อมูล คือ การใช้วิธีการค้นหาโครงสร้างข้อมูล เพื่อดุซ่าข้อมูลตัวที่ต้องการถูฏเก็บอยู่ในโครงสร้างแล้วหรือยัง

การค้นหา สามารถแบ่งได้ 2 ประเภท ตามแหล่งที่จัดเก็บข้อมูลเช่นเดียวกับกสนเรียงลำดับ
การค้นหาข้อมูลภายนอก(INTERNAL SEARCHING)
การค้นหาข้อมูลภายใน(EXTERNAL SEARCHING)

1. การค้นหาเชิงเส้นหรือการค้นหาแบบลำดับ(LINEAR)เป็นวิธีที่ใช้กับข้อมูลที่ไม่เรียงลำดับ
2. การค้นหาแบบเซนทินัล (SENTINEL) เป็นวิธิที่การค้นหาแบบเดียวกับการค้นหาแบบเชิงเส้นแต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า พัฒนามาจากอัลกอริทึ่มแบบเชิงเส้น
3. การค้นหาแบบไบนารี(BINARY SEARCH) ใช้กับข้อมูลที่จัดเรียงแล้วเท่านั้น หลักการต้องมีการแบ่งข้อมูลออกเป็น 2 ส่วน แล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา