Monte Carlo Algorithm
মন্টে কার্লো অ্যালগরিদম
Fixed সময়ে দ্রুত উত্তর দেয়, তবে ছোট probability-তে ভুল হতে পারে এমন randomized algorithm — বারবার চালিয়ে error সূচকীয় হারে কমানো যায়।
also: monte carlo, monte carlo method
guarantee: সময় নির্দিষ্ট ও দ্রুত
variable : উত্তর সঠিক হওয়ার সম্ভাবনা (≥ 1−ε)Independent repetition-এ error ε^k — 5% ভুল algorithm ৩ বার majority vote করলে ~0.125%-এ নামে।
ক্লাসিক: Miller–Rabin primality test (composite-কে কখনো ভুল বলে না; prime-কে ছোট সম্ভাবনায় ভুল হতে পারে), Karger-এর min-cut, Monte Carlo integration।
Exact উত্তর দরকার হলে Las Vegas বা deterministic; approximate উত্তর যথেষ্ট আর সমস্যা বিশাল হলে Monte Carlo প্রায়ই একমাত্র বাস্তবসম্মত পথ।