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