Алгоритми Монте-Карло — це рандомізовані алгоритми, які дають неправильний результат із нетривіально обмеженою верхньою ймовірністю. Однак вони часто більш ефективні порівняно з детермінованими алгоритмами. Однак, повторюючи алгоритм з незалежними випадковими числами, ймовірність помилок можна зменшити (збільшення ймовірності, докладніше в статті увипадковлений алгоритм). На відміну від алгоритмів Монте-Карло, алгоритми Лас-Вегаса дозволяють обчислювати лише правильні рішення.
Алгоритм Монте-Карло | |
Названо на честь | Монте-Карло |
---|---|
Протилежне | Лас-Вегас |
Алгоритми Монте-Карло служать основою для моделювання за методом Монте-Карло.
Двома прикладами таких алгоритмів є і .
Література
- Rajeev Motwani, Prabhakar Raghavan: Randomized Algorithms. 1 Auflage. Cambridge University Press, (DOI:10.1017/CBO9780511814075).
- Thomas Müller-Gronbach, Erich Novak, : Monte Carlo-Algorithmen. Springer Berlin Heidelberg, Berlin, Heidelberg, (DOI:10.1007/978-3-540-89141-3).
- Adrian Barbu, Song-Chun Zhu: Monte Carlo Methods. Springer Singapore, Singapore, (DOI:10.1007/978-981-13-2971-5).
- ; (1995). Randomized Algorithms. New York: Cambridge University Press. ISBN .
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 5. Імовірністий аналіз й увипадковлені алгоритми. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
- Berman, Kenneth A.; Paul, Jerome L. (2005). Ch 24. Probabilistic and Randomized Algorithms. Algorithms: Sequential, Parallel, and Distributed. Boston: Course Technology. ISBN .
Примітки
- Karger, David R.; Stein, Clifford (July 1996). A New Approach to the Minimum Cut Problem. J. ACM. 43 (4): 601—640. doi:10.1145/234533.234534. ISSN 0004-5411. S2CID 5385337.
- Kudelić, Robert (1 квітня 2016). Monte-Carlo randomized algorithm for minimal feedback arc set problem. Applied Soft Computing. 41: 235—246. doi:10.1016/j.asoc.2015.12.018.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritmi Monte Karlo ce randomizovani algoritmi yaki dayut nepravilnij rezultat iz netrivialno obmezhenoyu verhnoyu jmovirnistyu Odnak voni chasto bilsh efektivni porivnyano z determinovanimi algoritmami Odnak povtoryuyuchi algoritm z nezalezhnimi vipadkovimi chislami jmovirnist pomilok mozhna zmenshiti zbilshennya jmovirnosti dokladnishe v statti uvipadkovlenij algoritm Na vidminu vid algoritmiv Monte Karlo algoritmi Las Vegasa dozvolyayut obchislyuvati lishe pravilni rishennya Algoritm Monte Karlo Nazvano na chestMonte Karlo ProtilezhneLas Vegas Algoritmi Monte Karlo sluzhat osnovoyu dlya modelyuvannya za metodom Monte Karlo Dvoma prikladami takih algoritmiv ye i Literatura Rajeev Motwani Prabhakar Raghavan Randomized Algorithms 1 Auflage Cambridge University Press ISBN 978 0 521 47465 8 DOI 10 1017 CBO9780511814075 Thomas Muller Gronbach Erich Novak 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 1995 Randomized Algorithms New York Cambridge University Press ISBN 0 521 47465 5 T Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 5 Imovirnistij analiz j uvipadkovleni algoritmi Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4 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 PrimitkiKarger David R Stein Clifford July 1996 A New Approach to the Minimum Cut Problem J ACM 43 4 601 640 doi 10 1145 234533 234534 ISSN 0004 5411 S2CID 5385337 Kudelic Robert 1 kvitnya 2016 Monte Carlo randomized algorithm for minimal feedback arc set problem Applied Soft Computing 41 235 246 doi 10 1016 j asoc 2015 12 018