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é 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 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.