אלגוריתם לאס וגאס

{{#invoke:ParamValidator|validateparams|module_options=יחידה:PV-options}} {{#invoke:תבנית מידע|מידע| | טבלה-עיצוב = width: 22em; font-size: 95%; | כותרת תבנית-עיצוב =background: #B2C6FF; border:1px solid #aaaaaa; border-bottom:0px; | כותרת-עיצוב = background: #B2C6FF; | תמונה = | כיתוב= | תווית-מידע10=מחלקה | תווית-מידע20=סוג | תווית-מידע30=מבנה נתונים | תווית-מידע40=סיבוכיות זמן |סיבוכיות זמן-ויקינתונים=P3752 | תווית-מידע50=סיבוכיות מקום |סיבוכיות מקום-ויקינתונים=P3755 | תווית-מידע60=ממציא |ממציא-ויקינתונים-מרובה=P61 |ממציא-ויקינתונים-פרטים=P577 | תווית-מידע70=נקרא על שם |נקרא על שם-ויקינתונים-מרובה=P138 | תווית-מידע80=הומצא |הומצא-ויקינתונים=P575

}}

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

דוגמה פשוטה היא מיון מהיר אקראי, כאשר איבר הציר נבחר באופן אקראי, אבל התוצאה תמיד ממוינת. ההגדרה הרגילה של אלגוריתם לאס וגאס כוללת את ההגבלה שתוחלת זמן הריצה תמיד תהיה סופית, כאשר התוחלת מתבצעת מעל מרחב המידע האקראי, או האנטרופיה, בהם האלגוריתם משתמש. הגדרה חלופית דורשת שאלגוריתם לאס וגאס תמיד יסתיים (יהיה יעיל), אך הוא עשוי לתת כפלט סמל שאינו חלק ממרחב הפתרונות כדי לדווח על כשל במציאת פתרון.תבנית:הערה

אלגוריתמים מסוג לאס וגאס הוצגו על ידי לסלו בבאי ב-1979, בהקשר של בעיית איזומורפיות גרפים, כזוג לאלגוריתם מונטה קרלו.תבנית:הערה ניתן להשתמש באלגוריתמים מסוג לאס וגאס במצבים בהם מספר הפתרונות האפשריים מוגבל, וכאשר אימות נכונותו של הפתרון המועמד הוא קל יחסית, בעוד חישוב הפתרון הוא מורכב.

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

מחלקת סיבוכיות

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

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

הקשר לאלגוריתם מונטה קרלו

באלגוריתם מונטה קרלו, בדומה ללאס וגאס, המשאבים בשימוש חסומים אבל לא מובטח שהתשובה נכונה. על ידי יישום של אי-שוויון מרקוב, ניתן להמיר אלגוריתם לאס וגאס לאלגוריתם מונטה קרלו באמצעות סיום מוקדם.

ראו גם

• אלגוריתם אטלנטיק סיטי
• אקראיות

קישורים חיצוניים

• המדריך לאלגוריתמים ותורת החישוביות, CRC Press LLC, 1999.
• אלגוריתם "לאס וגאס" ב"מילון של אלגוריתמים ומבני נתונים [באינטרנט], פאול א. בלק, ארצות הברית, המכון הלאומי לתקנים וטכנולוגיה. זמין מ: 17 יולי 2006. (גישה מאי 09, 2009)[1]