Randomized algorithms
อัลกอริธึมแบบสุ่ม
อ่าน 1 นาทีหลักฐานที่ตรวจสอบได้ทางความน่าจะเป็น
Mathematical proofsในทฤษฎีความซับซ้อนของการ คำนวณ การพิสูจน์ที่ตรวจสอบได้ด้วยความน่าจะเป็น ( PCP ) คือ การพิสูจน์ประเภทหนึ่งที่สามารถตรวจสอบได้ด้วยอัลกอริทึมแบบสุ่มโดยใช้ปริมาณความสุ่มที่จำกัด...
อ่าน 1 นาทีหลักการตัดสินใจแบบเลื่อนออกไป
Algorithms and data structures stubsอัลกอริทึมแบบสุ่มจะทำการเลือกแบบสุ่มเป็นชุดๆ การเลือก แบบสุ่ม เหล่านี้ อาจมีความสัมพันธ์กันอย่างซับซ้อน ทำให้ยากต่อการวิเคราะห์ ในหลายกรณีจึง ใช้ หลักการตัดสินใจแบบเลื่อนออกไป...
อ่าน 1 นาทีการทดสอบทรัพย์สิน
Approximation algorithmsการทดสอบคุณสมบัติเป็นสาขาหนึ่งของวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีซึ่งเกี่ยวข้องกับการออกแบบอัลกอริธึมที่รวดเร็วเป็นพิเศษสำหรับการตัดสินใจโดยประมาณ...
อ่าน 1 นาทีอัลกอริทึมแบบสุ่ม
Printworthy redirectsอัลกอริทึมแบบสุ่มคืออัลกอริทึม ที่ใช้ ความสุ่มในระดับหนึ่งเป็นส่วนหนึ่งของตรรกะหรือกระบวนการทำงาน โดยทั่วไปแล้ว อัลกอริทึมจะใช้ บิต...
อ่าน 1 นาทีอัลกอริทึมแอตแลนติกซิตี้
Randomized algorithmsในด้านการคำนวณอัลกอริทึมแอตแลนติกซิตี้เป็นอัลกอริทึมแบบสุ่มที่ตอบได้อย่างถูกต้องอย่างน้อย 75% ของเวลาในบางคำจำกัดความที่แตกต่างกัน เกณฑ์ความถูกต้องอาจเป็นค่าใดๆ ที่มากกว่า 50%...
อ่าน 1 นาทีโปรโตคอลอาร์เธอร์-เมอร์ลิน
Randomized algorithmsในทฤษฎีความซับซ้อนของการคำนวณ โปรโตคอล Arthur –Merlinซึ่งแนะนำโดยBabai (1985)เป็นระบบพิสูจน์แบบโต้ตอบที่การโยนเหรียญ ของผู้ตรวจสอบ ถูกจำกัดให้เป็นสาธารณะ (กล่าวคือ...
อ่าน 1 นาทีวิธีโมเมนต์ลำดับที่หนึ่งและลำดับที่สอง
Probabilistic modelsในทฤษฎีความน่าจะ เป็น วิธีโมเมนต์ลำดับ ที่หนึ่งลำดับที่สอง (FOSM)หรือเรียกอีกอย่างว่าวิธีโมเมนต์ลำดับที่หนึ่งลำดับที่สองค่าเฉลี่ย...
อ่าน 1 นาทีอัลกอริทึมการสุ่มตัวอย่างแบบซ้อนกัน
Bayesian statisticsอัลกอริทึมการสุ่มตัวอย่างแบบซ้อนกันเป็น วิธี การคำนวณสำหรับ ปัญหา ทางสถิติแบบเบย์เซียนในการเปรียบเทียบแบบจำลองและสร้างตัวอย่างจากการกระจายความน่าจะเป็นภายหลัง...
อ่าน 1 นาทีอัลกอริทึมแบบสุ่ม
Analysis of algorithmsอัลกอริทึมแบบสุ่มคืออัลกอริทึม ที่ใช้ ความสุ่มในระดับหนึ่งเป็นส่วนหนึ่งของตรรกะหรือกระบวนการทำงาน โดยทั่วไปแล้ว อัลกอริทึมจะใช้ บิต...
อ่าน 1 นาทีทฤษฎีสารสนเทศเชิงอัลกอริทึม
Algorithmic information theoryทฤษฎีสารสนเทศเชิงอัลกอริทึม ( AIT ) เป็นสาขาหนึ่งของวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีที่เกี่ยวข้องกับความสัมพันธ์ระหว่างการคำนวณและสารสนเทศของวัตถุที่สร้างขึ้นโดยการคำนวณ...
อ่าน 1 นาทีการเรียงสับเปลี่ยนแบบสุ่ม
Permutationsการเรียงสับเปลี่ยนแบบสุ่มคือลำดับที่การเรียงลำดับของสิ่งต่างๆ ในลำดับใดๆ ก็ตาม มีโอกาสเกิดขึ้นเท่ากันโดยสุ่มกล่าวคือ เป็น ตัวแปรสุ่ม ที่มีค่าเป็นการเรียงสับเปลี่ยนของชุดวัตถุ
อ่าน 1 นาทีอัลกอริทึมการนับโดยประมาณ
CS1 errors: missing periodicalอัลกอริทึมการนับโดยประมาณช่วยให้สามารถนับเหตุการณ์จำนวนมากโดยใช้หน่วยความจำเพียงเล็กน้อย คิดค้นขึ้นในปี 1977 โดยRobert MorrisจากBell
อ่าน 1 นาทีอัลกอริทึม MST ที่ใช้เวลาเชิงเส้นที่คาดหวัง
Randomized algorithmsอัลกอริทึม MST ที่คาดหวังเวลาเชิงเส้นเป็นอัลกอริทึมแบบสุ่มสำหรับการคำนวณป่าแผ่คลุมขั้นต่ำของกราฟถ่วงน้ำหนักที่ไม่มีจุดยอดโดดเดี่ยวพัฒนาโดยDavid Karger , Philip Klein และRobert...
อ่าน 1 นาทีอัลกอริทึม Baum–Welch
Bioinformatics algorithmsในวิศวกรรมไฟฟ้าการคำนวณทางสถิติและชีวสารสนเทศอัลกอริทึม Baum–Welchเป็นกรณีพิเศษของอัลกอริทึมการคาดการณ์-การเพิ่มค่าสูงสุดที่ใช้ในการค้นหาพารามิเตอร์ที่ไม่ทราบค่าของแบบจำลองมาร์คอฟท...
อ่าน 1 นาทีการเก็บตัวอย่างอ่างเก็บน้ำ
Algorithmsการสุ่มตัวอย่างแบบอ่างเก็บน้ำ (Reservoir sampling)เป็นกลุ่มของอัลกอริทึมแบบสุ่มสำหรับการเลือกตัวอย่างแบบสุ่มอย่างง่ายโดยไม่ใส่คืน จำนวน kรายการ...
อ่าน 1 นาทีวิธีมอนเตคาร์โลทางชีววิทยา
Computational physicsวิธีการ Biology Monte Carlo (BioMOCA)ได้รับการพัฒนาขึ้นที่มหาวิทยาลัยอิลลินอยส์ เออร์บานา-แชมเปญเพื่อจำลองการขนส่งไอออนในสภาพแวดล้อมอิเล็กโทรไลต์ผ่านช่องไอออนหรือรูพรุนนาโนที่ฝังอย...
อ่าน 1 นาทีความซับซ้อนในกรณีเฉลี่ย
Analysis of algorithmsในทฤษฎีความซับซ้อนของการคำนวณความซับซ้อนในกรณีเฉลี่ยของอัลกอริทึมคือปริมาณทรัพยากรการคำนวณ บางอย่าง (โดยทั่วไปคือเวลา) ที่อัลกอริทึมใช้ โดยเฉลี่ยจากอินพุตที่เป็นไปได้ทั้งหมด
อ่าน 1 นาทีการลดตัวเองแบบสุ่ม
Randomized algorithmsหลักการลดรูปตัวเองแบบสุ่ม ( RSR ) คือกฎที่ว่าอัลกอริทึมที่ดีสำหรับกรณีเฉลี่ยจะหมายถึงอัลกอริทึมที่ดีสำหรับกรณีที่เลวร้ายที่สุด RSR...
อ่าน 1 นาทีเครื่องจักรทัวริงเชิงความน่าจะเป็น
Models of computationในวิทยาการคอมพิวเตอร์เชิง ทฤษฎี เครื่องจักรทัวริงเชิงความน่าจะเป็นคือเครื่องจักรทัวริงแบบไม่กำหนดที่เลือกการเปลี่ยนสถานะ ที่มี อยู่ ณ แต่ละจุดตามการกระจายความน่า จะเป็นบาง อย่าง...
อ่าน 1 นาทีการทดสอบความเป็นเอกของโซโลเวย์–สตราสเซน
Modular arithmeticการทดสอบความเป็นจำนวนเฉพาะของ Solovay–Strassenซึ่งพัฒนาโดยRobert M.
อ่าน 1 นาทีการรบกวนพร้อมกัน การประมาณค่าแบบสุ่ม
Numerical climate and weather modelsการประมาณค่าแบบสุ่มที่มีการรบกวนพร้อมกัน ( Simultaneous perturbation stochastic approximation : SPSA) เป็น วิธีการเชิงอัลกอริ ทึมสำหรับการปรับระบบที่มีพารามิเตอร์...
อ่าน 1 นาทีด้วยความน่าจะเป็นสูง
Computer science stubsในทางคณิตศาสตร์เหตุการณ์ที่เกิดขึ้นด้วยความน่าจะเป็นสูง (มักย่อเป็นwhpหรือWHP ) คือเหตุการณ์ที่ความน่าจะเป็นขึ้นอยู่กับจำนวนn ค่าหนึ่ง และมีแนวโน้มเข้าใกล้ 1...
อ่าน 1 นาทีอัลกอริทึมการหมุน
Applied mathematics stubsอัลกอริทึม Pivotเป็นรูปแบบหนึ่งของอัลกอริทึม Monte Carloที่ใช้ในการสร้างการกำหนดค่าของการเดินที่หลีกเลี่ยงตัวเองโดยทั่วไปบนแลตทิซ...
อ่าน 1 นาทีหลักการของเหยา
CS1 maint: ignored ISBN errorsในทฤษฎีความซับซ้อนของการคำนวณหลักการของเหยา (หรือเรียกว่าหลักการมินิแม็กซ์ของเหยาหรือเลมมาของเหยา ) เชื่อมโยงประสิทธิภาพของอัลกอริทึมแบบสุ่มกับอัลกอริทึมแบบกำหนด (ไม่ใช่แบบสุ่ม)...