הצגת המקור של הדף "אלגוריתם לאס וגאס"

{{אלגוריתם}}
ב[[מדעי המחשב]], '''אלגוריתם לאס וגאס '''הוא [[אלגוריתם אקראי]] שמחזיר תוצאות נכונות בלבד. אם הוא לא השיג כזו, הוא מודיע על כישלון. במילים אחרות, אלגוריתם לאס וגאס אינו מהמר על נכונות התוצאה, אלא רק על המשאבים המשמשים לצורך החישוב.

דוגמה פשוטה היא [[מיון מהיר]] אקראי, כאשר איבר הציר נבחר באופן אקראי, אבל התוצאה תמיד ממוינת. ההגדרה הרגילה של אלגוריתם לאס וגאס כוללת את ההגבלה שתוחלת [[זמן ריצה (תוכנה)|זמן הריצה]] תמיד תהיה [[סיבוכיות זמן|סופית]], כאשר התוחלת מתבצעת מעל מרחב המידע האקראי, או האנטרופיה, בהם האלגוריתם משתמש. הגדרה חלופית דורשת שאלגוריתם לאס וגאס תמיד יסתיים (יהיה יעיל), אך הוא עשוי לתת כפלט [[פונקציה חלקית|סמל שאינו חלק ממרחב הפתרונות]] כדי לדווח על כשל במציאת פתרון.{{הערה|שם=Galbraith2012|{{Cite book|title=Mathematics of Public Key Cryptography|last=Steven D. Galbraith|publisher=Cambridge University Press|year=2012|isbn=978-1-107-01392-6|page=16}}}}

[[אלגוריתם|אלגוריתמים]] מסוג לאס וגאס הוצגו על ידי [[לסלו בבאי]] ב-1979, בהקשר של בעיית [[איזומורפיות]] [[גרף (תורת הגרפים)|גרפים]], כזוג ל[[אלגוריתם מונטה קרלו]].{{הערה|[[:en:László Babai|László Babai]], [http://people.cs.uchicago.edu/~laci/lasvegas79.pdf Monte-Carlo algorithms in graph isomorphism testing], Université de Montréal, D.M.S. No. 79-10.}} ניתן להשתמש באלגוריתמים מסוג לאס וגאס במצבים בהם מספר הפתרונות האפשריים מוגבל, וכאשר אימות נכונותו של הפתרון המועמד הוא קל יחסית, בעוד חישוב הפתרון הוא מורכב.

מקור השם מהעיר [[לאס וגאס]], אשר ידועה כסמל להימורים.

== מחלקת סיבוכיות ==
[[מחלקת סיבוכיות|מחלקת הסיבוכיות]] של [[בעיית הכרעה|בעיות הכרעה]] להן קיים אלגוריתם לאס וגאס עם [[תוחלת]] זמן ריצה פולינומית, היא [[ZPP]].

מתקיים כי <math> \textrm{ZPP} = \textrm{RP} \cap \,\text{co}\,\textrm{-RP} \!</math>, דבר הקשור באופן הדוק עם הדרך שאלגוריתמים מסוג לאס וגאס נבנים לעיתים. כלומר המחלקה [[RP]] מורכבת מכל בעיות ההכרעה להן קיים אלגוריתם זמן-פולינומי אקראי המחזיר תשובה נכונה, כאשר התשובה הנכונה היא "לא", אבל רשאי לטעות בהסתברות מסוימת הרחוקה מ-1, כאשר התשובה היא "כן". כאשר קיים אלגוריתם כזה עבור בעיה והמשלימה שלה (התשובות "כן" ו "לא" מוחלפות), ניתן להריץ בו זמנית את שני האלגוריתמים ובאופן חוזר ונשנה: להריץ כל אחד מספר קבוע של צעדים, בתורנות, עד שאחד מהם מחזיר תשובה ודאית. זו הדרך הרגילה לבנות אלגוריתם לאס וגאס הפועל בתוחלת זמן פולינומית. שימו לב כי באופן כללי אין [[חסם (מתמטיקה)|חסם עליון]] על זמן הריצה של המקרה הגרוע של אלגוריתם לאס-וגאס.
== הקשר לאלגוריתם מונטה קרלו ==
ב[[אלגוריתם מונטה קרלו]], בדומה ללאס וגאס, המשאבים בשימוש חסומים אבל לא מובטח שהתשובה נכונה. על ידי יישום של [[אי-שוויון מרקוב]], ניתן להמיר אלגוריתם לאס וגאס לאלגוריתם מונטה קרלו באמצעות סיום מוקדם.

== ראו גם ==
* [[אלגוריתם אטלנטיק סיטי]]
* [[אקראיות]]

== קישורים חיצוניים ==
* המדריך לאלגוריתמים ותורת החישוביות, CRC Press LLC, 1999.
* אלגוריתם "לאס וגאס" ב''"מילון של אלגוריתמים ומבני נתונים ''[באינטרנט], פאול א. בלק, ארצות הברית, [[המכון הלאומי לתקנים וטכנולוגיה]]. זמין מ: 17 יולי 2006. (גישה מאי 09, 2009)[https://xlinux.nist.gov/dads/HTML/lasVegas.html]

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}

[[קטגוריה:אלגוריתמים]]