อ่าน 1 นาที
ด้วยความน่าจะเป็นสูง
ใน ทางคณิตศาสตร์ เหตุการณ์ที่เกิดขึ้น ด้วยความน่าจะเป็นสูง (มักย่อเป็น whp หรือ WHP ) คือเหตุการณ์ที่ ความน่าจะ เป็นขึ้นอยู่กับจำนวน n ค่าหนึ่ง และมีแนวโน้มเข้าใกล้ 1 เมื่อ n...
ด้วยความน่าจะเป็นสูง
ในทางคณิตศาสตร์เหตุการณ์ที่เกิดขึ้นด้วยความน่าจะเป็นสูง (มักย่อเป็นwhpหรือWHP ) คือเหตุการณ์ที่ความน่าจะเป็นขึ้นอยู่กับจำนวนn ค่าหนึ่ง และมีแนวโน้มเข้าใกล้ 1 เมื่อnเข้าสู่ค่าอนันต์ กล่าวคือ ความน่าจะเป็นของ การเกิด เหตุการณ์สามารถทำให้เข้าใกล้ 1 ได้มากเท่าที่ต้องการโดยการทำให้nมีค่ามากพอ
แอปพลิเคชัน
คำว่า WHP มักใช้กันทั่วไปในวิทยาศาสตร์คอมพิวเตอร์ โดยเฉพาะ ในการวิเคราะห์อัลกอริทึมความน่าจะเป็น [ 1 ] ตัวอย่างเช่น ลองพิจารณาอัลกอริทึมความน่าจะเป็นบนกราฟที่มี โหนด nโหนด หากความน่าจะเป็นที่อัลกอริทึมจะส่งคืนคำตอบที่ถูกต้องคือแล้วเมื่อจำนวนโหนดมีขนาดใหญ่มาก อัลกอริทึมก็จะถูกต้องด้วยความน่าจะเป็นที่ใกล้เคียงกับ 1 มาก ข้อเท็จจริงนี้แสดงออกมาสั้นๆ โดยการกล่าวว่าอัลกอริทึมนั้นถูกต้องแบบ WHP
ตัวอย่างการใช้คำนี้ ได้แก่:
- การทดสอบความเป็นจำนวนเฉพาะของมิลเลอร์-ราบิน : อัลกอริทึมเชิงความน่าจะเป็นสำหรับการทดสอบว่าจำนวนn ที่กำหนดให้ เป็นจำนวนเฉพาะหรือจำนวนประกอบหรือไม่ ถ้าnเป็นจำนวนประกอบ การทดสอบจะตรวจพบ ว่า nเป็นจำนวนประกอบแบบ WHP (Willing One Priority) มีโอกาสเล็กน้อยที่เราจะโชคร้ายและผลการทดสอบจะคิดว่าnเป็นจำนวนเฉพาะ แต่ความน่าจะเป็นของความผิดพลาดสามารถลดลงได้เรื่อยๆ โดยการทำการทดสอบหลายๆ ครั้งด้วยการสุ่มค่าที่แตกต่างกัน
- อัลกอริทึมของ Freivald : อัลกอริทึมแบบสุ่มสำหรับการตรวจสอบการคูณเมทริกซ์ ทำงานได้เร็วกว่าอัลกอริทึมแบบกำหนดตายตัว WHP
- Treap : ต้นไม้ค้นหาแบบไบนารีแบบสุ่ม ความสูงของมันคือ WHP แบบลอการิทึมFusion treeเป็นโครงสร้างข้อมูลที่เกี่ยวข้อง
- รหัสออนไลน์ : รหัสแบบสุ่มที่ช่วยให้ผู้ใช้สามารถกู้คืนข้อความ WHP ต้นฉบับได้
- BQP : กลุ่มความซับซ้อนของปัญหาที่มีอัลกอริธึมควอนตัมแบบใช้เวลาในการคำนวณพหุนามซึ่งถูกต้องตามหลัก WHP (Whole Handly Problem)
- การเรียนรู้ที่ถูกต้องโดยประมาณ : กระบวนการเรียนรู้ของเครื่องจักรที่ฟังก์ชันที่เรียนรู้มีข้อผิดพลาดในการวางนัยทั่วไปต่ำ (WHP)
- โปรโตคอลแบบกอสซิป : โปรโตคอลการสื่อสารที่ใช้ในระบบกระจายเพื่อส่งข้อความไปยังคลัสเตอร์ทั้งหมดได้อย่างน่าเชื่อถือ โดยใช้ทรัพยากรเครือข่ายในปริมาณคงที่บนแต่ละโหนด และรับประกันว่าจะไม่มีจุดล้มเหลวเพียงจุดเดียว
ดูเพิ่มเติม
สรุปเนื้อหา
ข้อมูลสำคัญจากบทความ
ข้อมูลสำคัญเกี่ยวกับ ด้วยความน่าจะเป็นสูง
ใน ทางคณิตศาสตร์ เหตุการณ์ที่เกิดขึ้น ด้วยความน่าจะเป็นสูง (มักย่อเป็น whp หรือ WHP ) คือเหตุการณ์ที่ ความน่าจะ เป็นขึ้นอยู่กับจำนวน n ค่าหนึ่ง และมีแนวโน้มเข้าใกล้ 1 เมื่อ n...
แอปพลิเคชัน
คำว่า WHP มักใช้กันทั่วไปใน วิทยาศาสตร์คอมพิวเตอร์ โดยเฉพาะ ในการวิเคราะห์ อัลกอริทึมความน่าจะเป็น [ 1 ] ตัวอย่าง เช่น ลองพิจารณาอัลกอริทึมความน่าจะเป็นบนกราฟที่มี โหนด n โหนด...
ดูเพิ่มเติม
อัลกอริทึมแบบสุ่ม เกือบจะแน่นอน ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=With_high_probability&oldid=1304458158 "