Алгоритм Монте-Карло

Алгоритми Монте-Карло — це рандомізовані алгоритми, які дають неправильний результат із нетривіально обмеженою верхньою ймовірністю. Однак вони часто більш ефективні порівняно з детермінованими алгоритмами. Однак, повторюючи алгоритм з незалежними випадковими числами, ймовірність помилок можна зменшити (збільшення ймовірності, докладніше в статті увипадковлений алгоритм). На відміну від алгоритмів Монте-Карло, алгоритми Лас-Вегаса дозволяють обчислювати лише правильні рішення.

Алгоритм Монте-Карло
Названо на честь	Монте-Карло
Протилежне	Лас-Вегас

Алгоритми Монте-Карло служать основою для моделювання за методом Монте-Карло.

Двома прикладами таких алгоритмів є алгоритм Каргера-Штейна і алгоритм Монте-Карло для мінімального набору дуг зворотного зв'язку .

Література

• Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms. 1 Auflage. Cambridge University Press, ISBN 978-0-521-47465-8 (DOI:10.1017/CBO9780511814075).

• Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo-Algorithmen. Springer Berlin Heidelberg, Berlin, Heidelberg, ISBN 978-3-540-89140-6 (DOI:10.1007/978-3-540-89141-3).

• Adrian Barbu, Song-Chun Zhu: Monte Carlo Methods. Springer Singapore, Singapore, ISBN 9789811329708 (DOI:10.1007/978-981-13-2971-5).

• Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. New York: Cambridge University Press. ISBN 0-521-47465-5.
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Ch 5. Probabilistic Analysis and Randomized Algorithms. Introduction to Algorithms (вид. 2nd). Boston: MIT Press and McGraw-Hill. ISBN 0-262-53196-8.
• Berman, Kenneth A.; Paul, Jerome L. (2005). Ch 24. Probabilistic and Randomized Algorithms. Algorithms: Sequential, Parallel, and Distributed. Boston: Course Technology. ISBN 0-534-42057-5.