Algoritmus typu Monte Carlo

Algoritmus typu Monte Carlo je v teoretické informatice označení pro takový pravděpodobnostní algoritmus, který může s malou pravděpodobností vrátit špatný výsledek. Tím se na první pohled liší od algoritmů typu Las Vegas, které vždy na konci vrátí správný výsledek, ovšem s malou pravděpodobností mohou běžet velmi dlouho, než skončí. Na algoritmus typu Las Vegas lze algoritmus typu Monte Carlo do jisté míry převést, pokud máme způsob, jak určit, zda je výsledek správný. V takovém případě lze algoritmus Monte Carlo pouštět opakovaně, dokud nevrátí správný výsledek.

Jméno Monte Carlo dal tomuto typu algoritmů v roce 1947 řecký fyzik Nicholas Metropolis, a to podle Monte Carla v Monaku, kde je slavné kasíno.

Příkladem algoritmu typu Monte Carlo je Millerův–Rabinův test prvočíselnosti.^[1]