ผลต่างระหว่างรุ่นของ "204512/บรรยาย 4"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
แถว 1: แถว 1:
 
{{หัวคำบรรยาย|204512}}
 
{{หัวคำบรรยาย|204512}}
 
'''จดบันทึกคำบรรยายโดย:'''
 
'''จดบันทึกคำบรรยายโดย:'''
:นายมนชัย สารทอง
+
:นายมนต์ชัย สารทอง
 
:นายอุกฤษณ์ กุลดิลก 50653971
 
:นายอุกฤษณ์ กุลดิลก 50653971
  

รุ่นแก้ไขปัจจุบันเมื่อ 15:04, 8 ตุลาคม 2550

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

จดบันทึกคำบรรยายโดย:

นายมนต์ชัย สารทอง
นายอุกฤษณ์ กุลดิลก 50653971

บทนี้จะกล่าวถึงทฤษฎีความน่าจะเป็นพื้นฐาน จากนั้นจะพิจารณาโครงสร้างข้อมูลแบบสุ่มสองแบบ คือ skip list และ universal hash

Balls & Bins

มีถัง n ถัง
มีบอล n ลูก

Random Variable

นิยาม
สำหรับตัวแปรสุ่ม X




Ex.1 มีลูกเต๋า 2 ลูก โยนทีละลูก

ให้ตัวแปรสุ่ม

แต้มบนลูกเต๋าลูกที่ 1
แต้มบนลูกเต๋าลูกที่ 2
แต้มรวม

Linearity of Expectation

สำหรับตัวแปรสุ่ม X, Y

จาก Ex.1 ให้ตัวแปรสุ่ม X แทนจำนวนถังว่าง

ให้ตัวแปรสุ่ม

ถ้าถังที่ i ว่าง
กรณีอื่นๆ

สังเกตว่า

ดังนั้น

โดย Linearity of Expectation











มีบอล m ลูก มีถัง n ถัง

ให้ จำนวนถังว่าง

หา E[X]


ต้องโยนบอลกี่ลูก X จะเข้าใกล้ 0



ให้




Thm
สำหรับตัวแปรสุ่ม X, Y
Proof
ให้
ตามต้องการ

ตัวแปรสุ่มที่สำคัญ

1. ตัวแปรสุ่มแบบ indicator

มีตัวแปรสุ่มที่มีค่า 0 หรือ 1 สังเกตว่า

Proposition: ถ้า X เป็น Indicator R.V.


Proof: จากนิยาม เราได้ว่า

Littlebox.png

2. ตัวแปรสุ่มแบบ binomial

มีการทดลองสำเร็จด้วยความน่าจะเป็น p
ทดลอง n ครั้ง แบบไม่ขึ้นต่อกัน
จำนวนครั้งของการทดลองที่สำเร็จ จะเป็นตัวแปรสุ่มแบบ
binomial => มี พารามิเตอร์ (n, p)

สำหรับตัวแปรสุ่ม X แบบ binomial ที่มี parameter (n, p)

ให้

ถ้าการทดลองครั้งที่ i สำเร็จ
กรณีอื่นๆ

ดังนั้น

เมื่อ แทนสัมประสิทธิ์ทวินาม ที่มีค่าเท่ากับ

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

3. Geometric R.V.

มีเหรียญที่ออกหัวด้วยความน่าจะเป็น p
จำนวนครั้งที่โยนจนได้หัว เป็นตัวแปรสุ่มแบบ geometric [พารามิเตอร์ p]
ให้ r.v. X เป็นตัวแปรสุ่มแบบ geometric ที่มี parameter p

Skip List

#---------------->O---------->#
                  |
#---->O---------->O------->O->#
      |           |        |
#---->O------->O->O---->O->O->#
      |        |  |     |  |
#->O->O->O->O->O->O->O->O->O->#

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

เมื่อกล่าวว่าเหตุการณ์ใดเกิดขึ้นด้วยความน่าจะเป็นสูง จะหมายความว่า เหตุการณ์ดังกล่าวขะไม่เกิดขึ้นด้วยความน่าจะเป็นไม่เกิน เมื่อ c>0 และ n คือ parameter ของระบบ

Lemma: skip list ที่มีข้อมูล n ตัวจะมีความสูง O(log n) ด้วยความน่าจะเป็นสูง


Proof: พิจารณาข้อมูล x ใดๆ ความน่าจะเป็นที่ระดับของ x>k

Pr[ระดับ x>k] =

ให้เหตุการณ์ แทนเหตุการณ์ที่ข้อมูลตัวที่ i มีระดับมากกว่า k

Pr[] =

ให้เหตุการณ์ A แทนเหตุการณ์ที่มีข้อมูลบางตัวมีระดับมากกว่า k

ดังนั้น

ให้ K = c log n = O(log n) จะได้ว่า

Pr[ความสูงไม่เกิน k] = 1 - Pr[มีข้อมูลบางตัวมีระดับมากกว่า k]

ถ้า c>2 , เหตุการณ์ดังกล่าวจะเกิดด้วยความน่าจะเป็นสูง

Littlebox.png

Pr[เดิน k node] =

Theorem: Expected search time ของ skip list ที่มีข้อมูล n ตัว คือ O(log n)


Proof

ให้ H = ความสูง = O(log n)
ให้ เป็นเวลาที่ใช้ในชั้นที่ i
Littlebox.png

Hashing

ในส่วนนี้ จะให้ แทนเซตของคีย์ และ แืทนเซตของดัชนีในตาราง

hash function จะส่งคีย์ไปยังตำแหน่งในตาราง

นิยาม: Family of hash function เป็น 2-universal ถ้า สำหรับทุก ๆ สมาชิก ที่ ,


เลือกจำนวนเฉพาะ p > M
ให้ สำหรับ และ


Lemma
สำหรับ x, y ที่
จำนวน ที่
ไม่เกิน ตัว


Proof
ให้
(1) ถ้า
พิสูจน์ด้วยข้อขัดแย้ง
assume
x = y
(2) ถ้า แล้ว
จำนวนคู่ r, s ที่สอดคล้อง
(3) พิจารณา คู่ r, s คู่หนึ่ง ที่
จะหาค่า a, b ที่
แต่ละคู่ r, s จะมี a, b คู่เดียว

จาก (1), (2), (3), มี a, b ไม่เกิน คู่