204512/บรรยาย 4 - ประวัติรุ่นแก้ไข

124.121.105.111 เมื่อ 15:04, 8 ตุลาคม 2550

2007-10-08T15:04:58Z

124.121.105.111 เมื่อ 15:04, 8 ตุลาคม 2550

2007-10-08T15:04:13Z

Jittat เมื่อ 05:12, 9 สิงหาคม 2550

2007-08-09T05:12:56Z

Jittat เมื่อ 15:56, 19 กรกฎาคม 2550

2007-07-19T15:56:24Z

Jittat: /* Skip List */

2007-07-19T15:54:52Z

Skip List

Jittat: /* 1. ตัวแปรสุ่มแบบ indicator */

2007-07-19T15:23:55Z

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

Jittat: /* 1. ตัวแปรสุ่มแบบ indicator */

2007-07-19T15:23:20Z

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

Jittat: /* 1. ตัวแปรสุ่มแบบ indicator */

2007-07-19T15:22:10Z

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

Jittat: /* 1. ตัวแปรสุ่มแบบ indicator */

2007-07-19T15:21:58Z

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

Jittat: /* 1. Indicator R.V. */

2007-07-19T15:21:35Z

1. Indicator R.V.

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

@@ แถว 1: / แถว 1: @@
 {{หัวคำบรรยาย|204512}}
-'''จดบันทึกคำบรรยายโดย:''' ''(กรุณาใส่ด้วย)''
+'''จดบันทึกคำบรรยายโดย:'''
 บทนี้จะกล่าวถึงทฤษฎีความน่าจะเป็นพื้นฐาน จากนั้นจะพิจารณาโครงสร้างข้อมูลแบบสุ่มสองแบบ คือ skip list และ universal hash

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:12, 9 สิงหาคม 2550
แถว 1:		แถว 1:
	{{หัวคำบรรยาย\|204512}}		{{หัวคำบรรยาย\|204512}}
		+	'''จดบันทึกคำบรรยายโดย:''' ''(กรุณาใส่ด้วย)''
		+
	บทนี้จะกล่าวถึงทฤษฎีความน่าจะเป็นพื้นฐาน จากนั้นจะพิจารณาโครงสร้างข้อมูลแบบสุ่มสองแบบ คือ skip list และ universal hash		บทนี้จะกล่าวถึงทฤษฎีความน่าจะเป็นพื้นฐาน จากนั้นจะพิจารณาโครงสร้างข้อมูลแบบสุ่มสองแบบ คือ skip list และ universal hash

@@ แถว 1: / แถว 1: @@
 {{หัวคำบรรยาย|204512}}
 ==Balls & Bins==
 :มีถัง n ถัง

@@ แถว 178: / แถว 178: @@
 เมื่อกล่าวว่าเหตุการณ์ใดเกิดขึ้นด้วยความน่าจะเป็นสูง จะหมายความว่า เหตุการณ์ดังกล่าวขะไม่เกิดขึ้นด้วยความน่าจะเป็นไม่เกิน <math>\frac{1}{n^c}</math> เมื่อ c>0 และ n คือ parameter ของระบบ
-'''<u>Lemma</u>''': skip list ที่มีข้อมูล n ตัวจะมีความสูง O(log n) ด้วยความน่าจะเป็นสูง
+{{thm-box|'''Lemma:''' skip list ที่มีข้อมูล ''n'' ตัวจะมีความสูง ''O''(log ''n'') ด้วยความน่าจะเป็นสูง}}
+{{begin-pf}}
-'''<u>Proof</u>''' พิจารณาข้อมูล x ใดๆ ความน่าจะเป็นที่ระดับของ x>k
+'''Proof:''' พิจารณาข้อมูล x ใดๆ ความน่าจะเป็นที่ระดับของ x>k
 :'''Pr[ระดับ x>k] =''' <math>\frac{1}{2^k}</math>
 ให้เหตุการณ์ <math>A_i</math> แทนเหตุการณ์ที่ข้อมูลตัวที่ i มีระดับมากกว่า k
@@ แถว 191: / แถว 191: @@
 :'''Pr[ความสูงไม่เกิน k] = 1 - Pr[มีข้อมูลบางตัวมีระดับมากกว่า k]''' <math>\le 1 - \frac{n}{2^k} = 1 - \frac{n}{2^{clogn}} = 1 - \frac{1}{n^{c-1}}</math>
 ถ้า c>2 , เหตุการณ์ดังกล่าวจะเกิดด้วยความน่าจะเป็นสูง
 :'''Pr[เดิน k node] =''' <math>k\cdot\frac{1}{2^k}</math>
 '''<u>Proof</u>'''
 :ให้ H = ความสูง = O(log n)
 :ให้ <math>T_i</math> เป็นเวลาที่ใช้ในชั้นที่ i
 :<math>T = \sum_{i=1}^H T_i</math>
-:<math>E[T] = E[\sum_{i=1}^H T_i] = \sum_{i=1}^H E[T_i] = O(log n)</math>
+:<math>E[T] = E[\sum_{i=1}^H T_i] = \sum_{i=1}^H E[T_i] = O(\log n)</math>
 == Hashing ==

@@ แถว 128: / แถว 128: @@
 <center><math>E[X] = \Pr[X=1]</math></center>}}
 {{begin-pf}}
-จากนิยาม เราได้ว่า <math>E[X] = 0\cdot\Pr[X=0] + 1\cdot\Pr[X=1] = \Pr[X=1]</math>
+'''Proof:''' จากนิยาม เราได้ว่า <math>E[X] = 0\cdot\Pr[X=0] + 1\cdot\Pr[X=1] = \Pr[X=1]</math>
 {{end-pf}}

@@ แถว 127: / แถว 127: @@
 '''Proposition:''' ถ้า X เป็น Indicator R.V.
 <center><math>E[X] = \Pr[X=1]</math></center>}}
 === 2. ตัวแปรสุ่มแบบ binomial ===

@@ แถว 121: / แถว 121: @@
 == ตัวแปรสุ่มที่สำคัญ ==
-=== 1. Indicator R.V. ===
+=== 1. ตัวแปรสุ่มแบบ indicator ===
-:มีค่า 0, 1
+มีตัวแปรสุ่มที่มีค่า 0 หรือ 1  สังเกตว่า
 ถ้า X เป็น Indicator R.V.
-:<math>E[X] = Pr[X=1]</math>
+<center><math>\E[X] = \Pr[X=1]</math></center>}}
 === 2. ตัวแปรสุ่มแบบ binomial ===