אלגוריתם דטרמיניסטי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

על אף שהשימוש במונח אלגוריתם בכלל, ואלגוריתם דטרמיניסטי בפרט, נפוץ במדעי המחשב, השניים משמשים בכל צורות החיים. דוגמה לאלגוריתם דטרמינסטי היא החילוק הארוך.

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

הגדרה פורמלית[עריכת קוד מקור | עריכה]

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

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

בעיות באלגוריתמים דטרמינסטיים[עריכת קוד מקור | עריכה]

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

אף על פי שכל בעיה אלגוריתמית פתירה, ניתנת לפתרון באמצעות אלגוריתם דטרמינסטי, בעבור חלק גדול מהבעיות האלגוריתמים הדטרמניסטיים הידועים איטיים יותר (במונחי סיבוכיות) ממשפחות אלגוריתמיות אחרות‏‏‏[1]. בתורת הסיבוכיות המחלקה המכילה את הבעיות שקיים אלגוריתם דטרמיניסטי הרץ בזמן סביר (פורמלית, זמן הריצה שלו הוא פולינום של גודל הקלט) מכונה P. עם זאת, מכיוון שמחשבים מסוגלים להשתמש בפועל באקראיות בחישובים (באמצעות מחולל פסאודו אקראי), המושג של אלגוריתם דטרמיניסטי יעיל אינו מייצג את כלל השיטות היעילות לפתרון בעיות; המחלקה BPP המייצגת את כל הבעיות הניתנות לפתרון בידי אלגוריתם אקראי יעיל בעל הסתברות "טובה" להצלחה נחשבת על פי רוב למחלקה הסטנדרטית של "כל הבעיות הניתנות לפתרון יעיל במחשבים".

השלכות שליליות לאי היכולת לפתור בעיות בזמן סביר[עריכת קוד מקור | עריכה]

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

השלכות חיוביות לאי היכולת לפתור בעיות בזמן סביר[עריכת קוד מקור | עריכה]

כיום ידועות מספר בעיות שלא מוכר אלגוריתם יעיל הפותר אותן, אך בהינתן מידע נוסף הן ניתנות לפתרון יעיל, מה שפותח פתח לשימוש בבעיות אלו כבסיס למערכות הצפנה. הדוגמה הקלאסית היא של מערכת ההצפנה RSA, שבה כדי לפענח הודעה יש לבצע חישוב התלוי במספר שהוא מכפלת שני ראשוניים גדולים. אם שני הראשוניים הללו ידועים קל לבצע את החישוב שמפענח הודעה; אך לא ידועה שום דרך לבצע חישוב זה ביעילות אם הם אינם ידועים, כך שקשה לתוקף לפצח את ההודעה (המתקפה הישירה ביותר דורשת לפרק לגורמים את המכפלה, אך גם זוהי בעיה שנחשבת כיום לקשה). באופן כללי פונקציות שקל לחשב אך קשה להפוך מבלי שיהיה נתון מידע נוסף נקראות "פונקציות מלכודת" (Trapdoor functions).

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ להרחבה בנושא זה ע"ע P=NP