|
|
| แถว 78: |
แถว 78: |
| | :<math>E[Y] = E[Y_1 + Y_2] = E[Y_1] + E[Y_2]</math> | | :<math>E[Y] = E[Y_1 + Y_2] = E[Y_1] + E[Y_2]</math> |
| | | | |
| − | ==การกระจายความลับ (Secret Sharing)== | + | ==Linearity of Expectation== |
| − | ถ้า polynomial f มี degree d เราสามารถให้ <math> (x_0,y_0),\ (x_1,y_1),\ ...\ ,\ (x_d,y_d)</math> จะมี polynomial degree d เพียงตัวเดียวที่ผ่าน ทุกจุดดังกล่าว และ polynomial ดังกล่าวหาได้
| + | :สำหรับตัวแปรสุ่ม <math>X, Y</math> |
| | + | :<math>E[X+Y] = E[X]+E[Y]</math> |
| | | | |
| − | ต้องการ key M ให้กลุ่มคน n คน ให้ทุกๆกลุ่มคน < k คน ไม่ทราบข้อมูลเกี่ยวกับ key เลย
| + | :ให้ <math>R.V. X</math> แทนจำนวนถังว่าง |
| − | :กลุ่มคน k คนหา key ได้
| |
| | | | |
| − | หา prime p > key และ p - 1 > n เลือก<math> a_{k-1},a_{k-2},...,a_1</math> จากเซต { 1, 2, ... , p-1}
| + | :<math>E[X] = ?</math> |
| | | | |
| − | ให้ ak-1 ไม่เท่ากับ 0
| + | :ให้ตัวแปรสุ่ม X_i = |
| − | | |
| − | ให้ <math>f(x) = a_{k-1}\,x^{k-1} + a_{k-2}\,x^{k-2} +...+a_2\,x^2+a_1\,x + M</math>
| |
| − | เราจะเลือกจุด <math>\ x_1,\ x_2,\ ...,\ x_n</math> ที่ไม่ซ้ำกัรและไม่เท่ากับ 0 ให้ <math>(\ x_i,\ f(x_i))</math> กับคนที่ i
| |
รุ่นแก้ไขเมื่อ 08:14, 3 กรกฎาคม 2550
ขออภัย
Lecture Note ที่ท่านเรียก ยังไม่เปิดให้ใช้บริการค่ะ
Balls & Bins
- มีถัง
ถัง
- มีบอล ลูก
![{\displaystyle {\rm {Pr[first\ bin\ is\ empty]=}}\left({{\rm {1-}}{\frac {\rm {1}}{\rm {n}}}}\right)^{\rm {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/872ae7759506a112be7071c0d265611466e058b1)
Random Variable
- นิยาม
- สำหรับตัวแปรสุ่ม
![{\displaystyle \sum \limits _{i=-\infty }^{\infty }{i\cdot \Pr[X=i]}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e3c91784fe9c9663e402366d27ca41b9012a195)
- ตัวอย่าง
- มีลูกเต๋า 2 ลูก โยนทีละลูก
- ให้ตัวแปรสุ่ม
แต้มบนลูกเต๋าลูกที่ 1
แต้มบนลูกเต๋าลูกที่ 2
แต้มรวม
![{\displaystyle E[Y_{1}]=(1+2+...+6)\cdot {\frac {1}{6}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eec820ae89a6d4bf954d9ee3c98c67fe1b33ccb3)
![{\displaystyle E[Y_{1}]=3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b1199e48c825805571352c3f049e934f3e8de76)
![{\displaystyle E[Y_{2}]=3.5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c0154a35d2f5f8fff4769051664319f077a66d9)
![{\displaystyle E[Y]=2\cdot {\frac {1}{6}}\cdot {\frac {1}{6}}+3\cdot 2\cdot {\frac {1}{36}}+4\cdot 3\cdot {\frac {1}{36}}+5\cdot .....}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83ae804edf9b3ba8b688ff4361fce99574b70409)
![{\displaystyle E[Y]=7}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fa7fd14e6885678b8a3a3549e0ede2adf577b22b)
![{\displaystyle E[Y]=E[Y_{1}+Y_{2}]=E[Y_{1}]+E[Y_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f15c5939094aa1f677a79890227f372a28677232)
Linearity of Expectation
- สำหรับตัวแปรสุ่ม
![{\displaystyle E[X+Y]=E[X]+E[Y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea2251900ec2b03db1d6f870336155a2a09ff7f1)
- ให้
แทนจำนวนถังว่าง
![{\displaystyle E[X]=?}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fed450511cffa0a2dc75677b3834b8e8eac00989)
- ให้ตัวแปรสุ่ม X_i =
