กลับไปหน้าบทความ

อ่าน 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)
  • โปรโตคอลแบบกอสซิป : โปรโตคอลการสื่อสารที่ใช้ในระบบกระจายเพื่อส่งข้อความไปยังคลัสเตอร์ทั้งหมดได้อย่างน่าเชื่อถือ โดยใช้ทรัพยากรเครือข่ายในปริมาณคงที่บนแต่ละโหนด และรับประกันว่าจะไม่มีจุดล้มเหลวเพียงจุดเดียว

ดูเพิ่มเติม

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=With_high_probability&oldid=1304458158 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ด้วยความน่าจะเป็นสูง

ใน ทางคณิตศาสตร์ เหตุการณ์ที่เกิดขึ้น ด้วยความน่าจะเป็นสูง (มักย่อเป็น whp หรือ WHP ) คือเหตุการณ์ที่ ความน่าจะ เป็นขึ้นอยู่กับจำนวน n ค่าหนึ่ง และมีแนวโน้มเข้าใกล้ 1 เมื่อ n...

แอปพลิเคชัน

คำว่า WHP มักใช้กันทั่วไปใน วิทยาศาสตร์คอมพิวเตอร์ โดยเฉพาะ ในการวิเคราะห์ อัลกอริทึมความน่าจะเป็น [ 1 ] ตัวอย่าง เช่น ลองพิจารณาอัลกอริทึมความน่าจะเป็นบนกราฟที่มี โหนด n โหนด...

ดูเพิ่มเติม

อัลกอริทึมแบบสุ่ม เกือบจะแน่นอน ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=With_high_probability&oldid=1304458158 "