ผลต่างระหว่างรุ่นของ "204512/บรรยาย 4"
ไปยังการนำทาง
ไปยังการค้นหา
แถว 54: | แถว 54: | ||
:มีถัง n ถัง | :มีถัง n ถัง | ||
:มีบอล n ลูก | :มีบอล n ลูก | ||
− | <math>Pr[ | + | <math>\Pr [first\ bin\ is\ empty] = \left( {1 - \frac{1}{n}} \right)^n </math> |
==Random Variable== | ==Random Variable== |
รุ่นแก้ไขเมื่อ 07:40, 3 กรกฎาคม 2550
ขออภัย Lecture Note ที่ท่านเรียก ยังไม่เปิดให้ใช้บริการค่ะ
Balls & Bins
- มีถัง n ถัง
- มีบอล n ลูก
Random Variable
- นิยาม
- สำหรับตัวแปรสุ่ม X
การกระจายความลับ (Secret Sharing)
ถ้า polynomial f มี degree d เราสามารถให้ จะมี polynomial degree d เพียงตัวเดียวที่ผ่าน ทุกจุดดังกล่าว และ polynomial ดังกล่าวหาได้
ต้องการ key M ให้กลุ่มคน n คน ให้ทุกๆกลุ่มคน < k คน ไม่ทราบข้อมูลเกี่ยวกับ key เลย
- กลุ่มคน k คนหา key ได้
หา prime p > key และ p - 1 > n เลือก จากเซต { 1, 2, ... , p-1}
ให้ ak-1 ไม่เท่ากับ 0
ให้ เราจะเลือกจุด ที่ไม่ซ้ำกัรและไม่เท่ากับ 0 ให้ กับคนที่ i