אלגוריתם דטרמיניסטי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ←בעיות באלגוריתמים דטרמינסטיים: - עריכה על פי דף השיחה |
מ בוט החלפות: מסוים; |
||
שורה 11:
==בעיות באלגוריתמים דטרמינסטיים==
קיימים יישומים בהם לא רוצים שהמצבים הבאים יהיו צפויים (כמתחייב מההגדרה). משחקי קלפים למשל הם דוגמה ליישום בו לא ניתן לתת את האפשרות לחזות את הקלפים הבאים בחפיסה. מכיוון שהאקראיות שבה המחשב משתמש אינה אקראיות "אמיתית" אלא ניפוח דטרמיניסטי של Seed שעשוי להגיע ממקור בעל חוקיות
אף על פי שכל בעיה אלגוריתמית פתירה, ניתנת לפתרון באמצעות אלגוריתם דטרמינסטי, בעבור חלק גדול מהבעיות האלגוריתמים הדטרמניסטיים הידועים איטיים יותר (במונחי [[סיבוכיות]]) ממשפחות אלגוריתמיות אחרות<ref>להרחבה בנושא זה ע"ע [[P=NP]]</ref>. ב[[תורת הסיבוכיות]] המחלקה המכילה את הבעיות שקיים אלגוריתם דטרמיניסטי הרץ בזמן סביר (פורמלית, זמן הריצה שלו הוא [[פולינום]] של גודל הקלט) מכונה [[P (סיבוכיות)|P]]. עם זאת, מכיוון שמחשבים מסוגלים להשתמש בפועל באקראיות בחישובים (באמצעות מחולל פסאודו אקראי), המושג של אלגוריתם דטרמיניסטי יעיל אינו מייצג את כלל השיטות היעילות לפתרון בעיות; המחלקה [[BPP]] המייצגת את כל הבעיות הניתנות לפתרון בידי אלגוריתם אקראי יעיל בעל הסתברות "טובה" להצלחה נחשבת על פי רוב למחלקה הסטנדרטית של "כל הבעיות הניתנות לפתרון יעיל במחשבים".
| |||