DTS11 - 15/09/2552

สรุป Sorting (ต่อ)
การเรียงลำดับแบบเร็ว (Quick sort) เป็นการเรียงลำดับที่ใช้วเลาน้อยเหมาะสำรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็วในการทำงาน
การเรียงลำดับแบบแทรก (insertion sort) เป็นวิธีที่ทำการเพิ่มสมาชิกใหม่เข้าไปในเซต ที่มีสมาชิกทุกตัวเรียงลำดับอยู่แล้ว และทำให้เซตใหม่ มีสมาชิกทุกตัวเรียงลำดับด้วย วิธีการเรียงลำดับ
1.เริ่มต้นเปรียบเทียบจากข้อมูลในตำแหน่งที่ 1 กับ 2 หรือข้อมูลในตำแหน่งสุดท้ายและรองสุดท้ายก็ได้
ถ้าเป็นการเรียงลำดับจากน้อยไปมาก
2.จะต้องจัดให้ข้อมูลที่มีค่าน้อยอยู่ในตำแหน่งก่อนข้อมูลที่มีค่ามาก และถ้าเรียงจากมากไปน้อยก็จะจัดให้ข้อมูลที่มีค่ามากอยู่ในตำแหน่งก่อน
การเรียงลำดับแบบฐาน (radix sort)เป็นการเรียงลำดับโดยการพิจารณาข้อมูลทีละหลัก
1.เริ่มพิจารณาจากหลักที่มีค่าน้อยที่สุดก่อน คือ ถ้าเป็นข้อมูลเป็นเลขจำนวนเต็มจะพิจารณาหลักหน่อยก่อน
2.การจัดเรียงจะนำข้อมูลเข้ามาทีละตัว และนำไปเก็บไว้ที่ซึ่งจัดไว้สำหรับค่านั้น เป็นกลุ่มๆ ตามลำดับการเข้ามา
3.ในแต่ละรอบเมื่อจัดกลุ่มเรียบร้อยแล้ว ให้รวบรวมข้อมูลจากทุกกลุ่มเข้าด้วยกัน โดยเริ่มเรียงจากกลุ่มที่มีค่าน้อยที่สุดก่อนแล้วเรียงไปเรื่อยๆ จนหมดทุกกลุ่ม
4.ในรอบต่อไปนำข้อมูลทั้งหมดที่ได้จัดเรียงในหลักหน่วยเรียบร้อยแล้วมาพิจารณาจัดเรียงในหลักสิบต่อไป ทำไปเรื่อยๆ จนครบทุกหลักจะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ
การเรียงลำดับแบบฐานมีวิธีการที่ไม่ซับซ้อนแต่ค่อนข้างใช้เนื้อที่ในหน่วยความจำมาก เนื่องจากการจัดเรียงแต่ละรอบจะต้องเตรียมเนื้อที่สำหรับสร้างที่เก็บข้อมูลในแต่ละกลุ่ม

ตารางแฮช (Hash Table)
ฟังก์ชั่น แฮช จะทำงานแบบสุ่ม การที่แทรกคีย์ในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ที่ถูกสร้างจากฟังก์ชั่น ในช่องเดียวกันตามการเกิดการชนกันก็ยังคงต้องมีอย่างน้อยหนึ่งครั้ง
วิธีการในการรองรับกรชนกันของตารางแฮช คือ
-การทำแบ่งห่วงโซ่ (Chaining)
-แบบการเปิดที่อยู่ (Open Addressing)
การแก้ไขปัญหาชนกันของข้อมูลแบบห่วงโซ่ (Chaining)
1.กรณีที่เลวร้ายที่สุด ในการแทรกข้อมูลคือ o(1)
2.การลบสมาชิก สามารถทำได้ด้วยเวลาที่น้อยที่สุดของ o(1)
ทางปฏิบัติ ใช้เทคนิค ฮิวริสติก (Heuristic) ในการสร้างฟังก์ชั่นแฮช แนวทางหนึ่งที่ดี คือ การแปลงค่าของข้อมูลที่มีอยู่แล้วด้วยข้อมูลที่มีอยู่ (วิธีการหาร : Division method)
วิธีการสร้างฟังก์ชั่นแฮช
1.วิธีการหาร (The Division Method)
2.วิธีการคูณ (The Multiplication Method)
3.วิธีทั่วไป (Universal hsahing)
เทคนิคลำดับการตรวจสอบ
1.การตรวจสอบเชิงเส้น (Linear Probing)
2.การตรวจสอบด้วยสมการกำลังสอง (Quadratic Probing)
3.การสร้างฟังก์ชันแฮชแบบสองเท่า (Double Hashing)

DTS10 - 08/09/2552

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

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

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

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

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

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

DTS09 - 01/09/2552

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

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

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

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

IOSTREAM

#include < iostream.h >
#include < conio.h >
void main()
{
int number1,number2;
float x,y,z;
number1=20;
number2=30;
x=25.25; y=30.05; z=10.75;
clrscr();
cout<< "Program Display Mathmetic calculation"<< endl;
cout<< "number1 = " << number1 << endl;
cout<< "number2 = " << number2 << endl;
cout<< "number1 + number2 = "<< number1+number2 << endl;
cout<< "number1 - number2 = "<< number1-number2 << endl;
cout<< "x+y+z = "<< x+y+z << endl;
cout<< "x*y*z = " << x*y*z << endl;
cout<< "50*25*12.5 = " << 50*25*12.5 << endl;
getch();
}