الگوریتم لاس وگاس
در محاسبات، الگوریتم لاس وگاس، یک الگوریتم تصادفی است که همیشه پاسخ صحیح را می‌دهد. که یعنی همیشه منجر به تولید پاسخ صحیح است یا ما را از خطا آگاه می‌کند. به عبارت دیگر, الگوریتم لاس وگاس, با صحت نتایج، بازی یا قمار نمی‌کند، بلکه با منابعی که برای محاسبه استفاده می‌شوند بازی (قمار) می‌کند یک مثال ساده مرتب‌سازی سریع تصادفی است. که در آن محور یا عضو مؤثر در مرتب‌سازی به صورت تصادفی انتخاب شده اما نتیجه این است که همیشه پاسخ مرتب شده داریم. الگوریتم لاس وگاس یک محدودیت دارد و آن این است که باید همیشه زمان اجرا متناهی باشد.
الگوریتم لاس وگاس توسط László Babai در سال 1979 در زمینه مشکل گراف ایزومورفیسم (هم‌ریخت) به عنوان یک دوگانه به مونت کارلو و الگوریتم معرفی شد. الگوریتم لاس وگاس را می توان در موقعیت های که در آن‌ها تعداد راه حل ها ممکن است نسبتاً کم باشد و در آن تایید صحت یک کاندیدا راه حل نسبتاً آسانی است استفاده کرد در حالی که در واقع راه‌حل محاسبات واقعاً پیچیده است.
نام الگوریتم اشاره به نام شهر لاس وگاس نوادا است که به خوبی در ایالات متحده به عنوان یک نماد از قمار شناخته شده است.
پانویس
- ↑ Steven D. Galbraith (2012). Mathematics of Public Key Cryptography. Cambridge University Press. p. 16. ISBN 978-1-107-01392-6.
- ↑ László Babai, Monte-Carlo algorithms in graph isomorphism testing, Université de Montréal, D.M.S. No. 79-10.
- ↑ Leonid Levin, The Tale of One-way Functions, Problems of Information Transmission, vol. 39 (2003), 92-103.
- ↑ Dan Grundy, Concepts and Calculation in Cryptography بایگانی‌شده در ۱۲ آوریل ۲۰۱۶ توسط Wayback Machine, University of Kent, Ph.D. thesis, 2008