Algoritmus typu Monte Carlo

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

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é 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 CarlaMonaku, kde je slavné kasíno.

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

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Monte Carlo algorithm na anglické Wikipedii.

  1. KOUBKOVÁ, Alena; PAVELKA, Jan. Úvod do teoretické informatiky. Praha: Matfyzpress, 1998. ISBN 80-85863-33-2. Kapitola Pravděpodobnost a algoritmy, s. 122.