วันพฤหัสบดีที่ 15 ตุลาคม พ.ศ. 2552

ลูกแรดเตรียมพร้อมล่าเหยื่อ

จากการที่ได้เรียนวิชาเตรียมฝึกประสบการณวิชาชีพ 3
คิดว่าได้ประสบการณ์มากในการเตรียมพร้อมที่จะออกฝึกงาน ไม่ว่าจะเป็นใน
1.เรื่องคุณธรรมและจริยธรรมในการทำงานและการปฏิบัติงานกับเพื่อนร่วมงาน ความรับผิดชอบในหน้าที่
2.เรื่องการเงินส่วนบุคคล ทำให้รู้จักการออมเงินว่าจะบริหารเงินอย่างไร
3.การพัฒนาบุคลิกภาพ เช่น การแต่งหน้า การทำผม การแต่งตัวและการวางตัวให้อยู่ในสังคมได้โดยเหมาะสม
4.มีการทดสอบภาษาอังกฤษ เพื่อจะทราบถึงว่าเรามีความสามารถภาษาอังกฤษมากน้อยเพียงใด
5.กิจกรรมการคัดไทย ทำให้เราฝึกการเขียน เพื่อที่จะได้นำไปปฏิบัติการทำงาน
6.ได้ประสบการณ์ในการคุมสอบ IT เพราะการคุมสอบ IT ครั้งนี้มีปัญหาและอุปสรรคว่าเราควรจะแก้ไขอย่างไร
7.ได้รู้จักแนวคิดและวิธีที่จะประสบความสำเร็จในชิวีต
8.ได้รู้ถึงวัฒนธรรมของต่างชาติ ทำให้ทราบว่าการทำธุรกิจกับชาวต่างชาติและการติดต่อสื่อสารกับชาวต่างชาติ
9.มีความรู้ในด้านซอฟต์แวร์ต่าง ๆ มากขึ้น เพื่อที่เราจะได้นำไปพัฒนาและศึกษา
10.ได้รับฟังข้อคิดดี ๆ จากพระอาจารย์ที่มาเทศนาให้ฟัง

วันพุธที่ 14 ตุลาคม พ.ศ. 2552

DTS12-29-09-2552

Sorting และSearching
Sorting การเรียงลำดับแบบเร็ว
การเรียงลำดับแบบเร็ว (quick sort) เป็นวิธีการเรียงลำดับที่ใช้เวลาน้อยเหมาะสำหรับข้อมูลที่มีจำนวนมากที่ต้องการความรวดเร็วในการทำงาน วิธีนี้จะเลือกข้อมูลจากกลุ่มข้อมูลขึ้นมาหนึ่งค่าเป็นค่าหลัก แล้วหาตำแหน่งที่ถูกต้องให้กับค่าหลักนี้ เมื่อได้ตำแหน่งที่ถูกต้องแล้วใช้ค่าหลักนี้เป็นหลักในการแบ่งข้อมูลออกเป็น สองส่วน ถ้าเป็นการเรียงลำดับจากน้อยไปมาก ส่วนแรกอยู่ในตอนหน้าข้อมูลทั้งหมดจะมีค่าน้อยกว่าค่าหลักที่เป็นตัวแบ่งส่วน และอีกส่วนหนึ่งจะอยู่ในตำแหน่งตอนหลังข้อมูลทั้งหมดจะมีค่ามากกว่าค่าหลัก แล้วนำแต่ละส่วนย่อยไปแบ่งย่อยในลักษณะเดียวกันต่อไป จนกระทั่งแต่ละส่วนไม่สามารถแบ่งย่อยได้อีกต่อไปจะได้ข้อมูลที่มีการเรียงลำดับตามที่ต้องการ
กรณีที่แย่ที่สุด คือ กรณีที่ข้อมูลมีการเรียงลำดับอยู่แล้ว อาจจะเรียงจากน้อยไปหามากหรือจากมากไปน้อยที่สุดหรือมากที่สุด จำนวนครั้งของการเปรียบเทียบจะมากที่สุดดังนี้
กรณีที่ดีที่สุด คือ กรณีที่ค่าหลักที่เลือกแบ่งข้อมูลอยู่ตรงกลางกลุ่มพอดี และในแต่ละส่วนย่อยก็เช่นเดียวกันจำนวนครั้งของการเปรียบเทียบเป็นดังนี้
จำนวนครั้งของการเปรียบเทียบ = n log2n คร้ง

Searching การค้นหาข้อมูล
การค้นหา แบ่งออกเป็น 2ประเภท ตามแหล่งที่จัดเก็บข้อมูลเช่นเดียวกับการเรียงลำดับ
1. การค้นหาข้อมูลแบบภายใน
2. การค้นหาข้อมูลแบบภายนอก
การค้นหาแบบเชิงเส้นหรือการค้นหาตามลำดับ (Linear)
เป็นวิธีที่ใช้กับข้อมูลที่ยังไม่ได้เรียงลำดับ
หลักการคือ ให้นำข้อมุลที่จะหามาเปรียบเทียบกับข้อมูลตัวแรกในแถวลำดับ
1. ถ้าไม่เท่ากันให้เปรียบเทียบกับข้อมูลตัวถัดไป
2. ถ้าเท่ากันให้หยุดการค้นหา หรือการค้นหาจะหยุดเมื่อพบข้อมูลที่ต้องการหรือหาข้อมูลทุกจำนวนในแถวลำดับแล้วไม่พบ
การค้นหาแบบเซนทินัล (sentinel)
เป็นวิธีการค้นหาแบบเดียวกับวิธีการค้นหาแบบเชิงเส้นแต่ประสิทธิภาพดีกว่าตรงที่เปรียบเทียบน้อยครั้งกว่า พัฒนามาจากอัลกอริทึ่มแบบเชิงเส้น
หลักการ
1.เพิ่มขนาดของแถวลำดับ ที่ใช้เก็บข้อมูลอีกหนึ่งที่
2. นำข้อมูลที่จะใช้ค้นหาข้อมูลใน array ไปฝากที่ต้นหรือ ท้าย array
3. ตรวจสอบผลลัพธ์จากการหา
การค้นหาแบบไบนารี (Binary Search)
การค้นหาแบบไบนารีทรีใช้กับข้อมูลที่ ถูกจัดเรียงแล้วเท่านั้น
1. หาตัวแทนข้อมูลเพื่อนำมาเปรียบเทียบกับค้าที่ต้องการค้นหาตำแหน่งตัวแทนข้อมูลหาได้ขากสูตร
mid =(low+hing)/2
mid คือ ตำแหน่งกลาง,low คือ ตำแหน่งต้นแถวลำดับ
hing คือ ตำแหน่งท้ายของข้อมูล
2. การค้นหาแบบไบนารี (Binary Search)
การค้นหาแบบไบนารีใช้กับข้อมูลที่ถูกจัดเรียงแล้วเท่านั้น หลักการของการค้นหาคือ ข้อมูลถูกแบ่งออกเป็นสองส่วน แล้วนำค่ากลางข้อมูลมาเปรียบเทียบกับคีย์ที่ต้องการหา ถ้าข้อมูลมีการเรียงจากน้อยไปหามาก เมื่อเปรียบเทียบแล้วคีย์มีค่ามากกว่าค่ากลาง แสดงว่าต้องทำการค้นหาข้อมูลในครึ่งหลังต่อไป จากนั้นนำข้อมูลครึ่งหลังมาหาค่ากลางต่อ ทำอย่างนี้ไปเรื่อย ๆ จนกว่าจะได้ข้อมูลที่ต้องการ เช่นต้องการหาว่า 12 อยู่ในลิสต์ (1 4 6 8 10 12 18 19) หรือไม่ เริ่มการค้นหาแบบไบนารีด้วยการเปรียบเทียบกับค่ากลางในลิสต์ คือค่า a[4] ซึ่งเก็บค่า 8 ซึ่ง 12 > a[4] หมายความว่าค่า 12 ควรจะอยู่ในข้อมูลด้านขวาของ a[4] คือ ช่วง a[5] …a[8] โดยไม่สนใจช่วงข้อมูล a[1] …a[3] และใช้วิธีการค้นหาแบบไบนารีเช่นเดิมอีกกับชุดข้อมูลครึ่งหลัง คือ a[5] …a[8] นั่นคือ เปรียบเทียบกับค่ากลางของชุดข้อมูลครึ่งหลัง (a[5] …a[8] ) คือค่า a[6] ซึ่งเก็บค่า 12 ซึ่ง 12 = a[6]
จะได้ว่าค่า 12 อยู่ในตำแหน่งที่ 6 ในลิสต์

DTS11-22-09-2552

ตารางแฮช (Hash Table)
ตารางข้อมูลแบบตรง (Direct-address table)สมมติว่ามีการกำหนดให้คีย์มาจากเอกภพสัมพัทธ์ U = {0,1,…,m-1} การแก้ไขปัญหาคือใช้ตาราง T[0..m-1] การสร้างดัชนีโดยคีย์ เพื่อใช้ในการ เชื่อมโยงข้อมูล เข้าด้วยกันเพื่อเก็บข้อมูลเข้าในตำแหน่งที่ถูกต้อง
เมื่อขนาดของเอกภพสัมพัทธ์เพิ่มมากขึ้น ตามหลักการยังคง สามารถทำงานได้ แต่ขนาดของตาราง T จะมีผลกระทบทางแก้ปัญหาคือต้องหาวิธีการจับคู่คีย์ให้มีช่วงกว้างที่เล็กลงโดยเรียกวิธีการนี้ว่าฟังก์ชันแฮช (Hash Function)ผลลัพธ์ที่ได้เรียกว่าตารางแฮช (Hash Table)
การเข้าถึงข้อมูลโดยตรง กำหนด ให้ k เป็นคีย์ ถูกจัดเก็บอยู่ใน ช่อง k ด้วยการทำแฮชด้วยพื้นฐาน การจัดเก็บในช่องที่ h(k) โดยใช้ฟังก์ชัน h เพื่อคำนวณหาช่องของคีย์โดยการจับคู่กับเอกภพสัมพัทธ์U ในตาราง T h: U 􀃆 {0,1,…,m-1}
ฟังก์ชัน แฮช จะทำงานแบบสุ่ม ตัวอย่างเช่น h(k) = k mod m เมื่อ m เป็นค่าหลัก (prime number) จำนวนช่อง (Slot)แนวคิดการจัดเก็บ ค่าคีย์ของ k ในตำแหน่ง ที่ T[h(k)] เมื่อ k ∈ U , h(k) ∈ [0..m-1] แนวคิดหลัก คือ ลด ขนาดอะเรย์ของดัชนีการที่แทรกคีย์ในตาราง ที่จัดเก็บนั้นมีโอกาสที่คีย์ที่ถูกสร้างจากฟังก์ชัน ในช่องเดียวกันอย่างไรก็ตามการเกิดการชนกันก็ยังคงต้องมีอย่างน้อยหนึ่งครั้ง
การแก้ไขปัญหาชนกันของข้อมูล แบบห่วงโซ่(Chaining)
1. กรณีที่เลวร้ายที่สุด ในการแทรกข้อมูลคือ o(1)
2. การลบสมาชิก สามารถทำได้ด้วยเวลาที่น้อยที่สุดของ o(1)ทางปฏิบัติ ใช้เทคนิค ฮิวริสติก (Heuristic) ในการสร้างฟังก์ชันแฮช แนวทางหนึ่งที่ดีคือ การแปลงค่าของข้อมูลที่มีอยู่แล้วด้วยข้อมูลที่มีอยู่ (วิธีการหาร:Division method) ฟังก์ชันแฮช คือการกำหนดค่าคีย์ที่เกิดขึ้นในเอกภพสัมพัทธ์จากตัวเลขธรรมชาติ
วิธีการสร้างฟังก์ชันแฮช (Method for Creating Function)
1.วิธีการหาร (The Division Method)
2.วิธีการคูณ(The Multiplication Method)
3.วิธีทั่วไป (Universal hashing)
วิธีการหาร (The Division Method)Open Addressingฟังก์ชันแฮช คือh: ν{0, 1, . . . m -1 }--> {0, 1, . . . , m-1}ลำดับในการตรวจสอบ(probe sequence) คือ<>
เทคนิคลำดับของการตรวจสอบ
1. การตรวจสอบเชิงเส้น (Linear Probing)
2.การตรวจสอบด้วยสมการกำลังสอง(Quadratic Probing)
3. การสร้างฟังก์ชันแฮชแบบสองเท่า(Double Hashing)
เทคนิคลำดับของการตรวจสอบ
1.การตรวจสอบเชิงเส้น (Linear Probing)รูปแบบของ ฟังก์ชันคือh(k, i) = (h` (k) + i) mod m เมื่อ i = 0, 1, 2, . . . , m-1 h` คือ auxiliary ของฟังก์ชันแฮช
2. การตรวจสอบด้วยสมการกำลังสอง(Quadratic Probing)รูปแบบของ ฟังก์ชันคือh(k, i) = (h` (k) + c1i + c2i2) mod m เมื่อ i = 0, 1, 2, . . . , m-1h`คือ auxiliary ของฟังก์ชันแฮช c1 + c2 ≠ 0 เป็นค่าคงที่แบบ auxiliary
3. การสร้างฟังก์ชันแฮชแบบสองเท่า (Double Hashing)รูปแบบของ ฟังก์ชันคือh(k, i) = (h1, 9k) + ih2 (k)) mod m เมื่อ h1 และ h2 เป็น auxiliary ของฟังก์ชันค่า k เป็นค่าเริ่มต้นของ ตำแหน่งการตรวจสอบ และค่า offset