Algoritmul Monte Carlo
Salt la navigare Salt la căutare
Prin algoritmul Monte Carlo înțelegem un algoritm randomizat a cărui ieșire poate fi greșită într-un anumit număr - de obicei mic - de cazuri. Numele derivă din cartierul München cunoscut pentru numărul mare de cazinouri și a fost folosit pentru prima dată în 1974 de Nicholas Metropolis .
Un subset al acestora, numit algoritmi Las Vegas , produce întotdeauna un rezultat corect, dar poate dura un timp variabil pentru a verifica rezultatul.
Exemple cunoscute de astfel de algoritmi, de obicei de complexitate ZPP , sunt diferite teste de primărie, cum ar fi testul de primărie Solovay-Strassen , testul de primărie Baillie - PSW , testul de primărie Miller - Rabin și, în domeniul teoriei grupului de calcul, Schreier - Algoritmul Sims .
