מודל חישובי

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

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

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

אוטומט סופי[עריכת קוד מקור | עריכה]

דוגמה לאוטומט סופי דטרמיניסטי מעל הא"ב \Sigma=\{0,1\}ששפתו היא כל המילים שמתחילות ונגמרות באותה ספרה
Postscript-viewer-shaded.png ערך מורחב – אוטומט סופי

אוטומט סופי הוא חמישייה <Q,\Sigma,q_0,\delta,F> כאשר:

  • Q היא קבוצת המצבים האפשריים באוטומט.
  • \Sigma היא הא"ב הסופי של השפה שהאוטומט מתאר.
  • q_0 הוא המצב ההתחלתי באוטומט
  • \delta היא פונקציית המעבר, המוגדרת כך
    \delta : Q \times E \rightarrow Q. למעשה, \delta מקבלת מצב ואות קלט, ומחזירה את המצב הבא.
  • F היא קבוצת המצבים המקבלים באוטומט.

האוטומט מקבל מילת קלט w \isin \Sigma^* (נוכל גם לומר כי w=w_0w_1...w_{n-1}, \forall i<n: w_i \isin \Sigma), וקורא את האותיות בה בזו אחר זו. הוא מתחיל את ריצתו על המילה במצב q_0, משם עובר למצב q_1=\delta (q_0,w_0), וכך הלאה (באמצעות הכלל q_i=delta(q_{i-1},w_{i-1}). נאמר כי המילה שייכת לשפת האוטומט, אם"ם הריצה של האוטומט על המילה מסתיימת במצב מקבל, כלומר, q_{|w|} \isin F.

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

מודל חישובי זה הוא פשוט ביותר, והדקדוק השקול לשפת כל השפות שניתן לכתוב אוטומט סופי שמקבל אותן היא השפות הרגולריות.

אוטומט מחסנית[עריכת קוד מקור | עריכה]

דוגמה לאוטומט מחסנית מעל הא"ב \Sigma = \{ a,b \}, המקבלת את השפה L=\{ a^i b^j | i \ge j \}
Postscript-viewer-shaded.png ערך מורחב – אוטומט מחסנית

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

פורמלית, אוטומט מחסנית הוא השישייה <Q,\Sigma,\Gamma,\delta,q_0,F> כאשר:

  • Q היא קבוצת המצבים ההתחלתיים.
  • \Sigma היא הא"ב הסופי שמעליו מוגדרת שפת האוטומט.
  • \Gamma היא הא"ב הסופי של המחסנית (קבוצת האותיות שיכולה להיכתב במחסנית).
  • \delta פונקציית המעבר \delta : Q \times  (\Sigma \cup\{\varepsilon\})  \times \Gamma \rightarrow Q \times \Gamma , המקבלת מצב, אות קלט, ואות מחסנית (לקריאה) ומחזירה את המצב הבא ואות מחסנית (לכתיבה במחסנית).
  • q_0 \isin Q המצב ההתחלתי.
  • F \subseteq F קבוצת המצבים המקבלים.

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

מכונת טיורינג[עריכת קוד מקור | עריכה]

מכונת טיורינג שקוראת מספר בינארי וכותבת את המספר הנגדי לו בשיטת המשלים ל-2.
Postscript-viewer-shaded.png ערך מורחב – מכונת טיורינג

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

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

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

זמן ריצה[עריכת קוד מקור | עריכה]

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

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

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