מודל חישובי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ ניסוח וקישורים פנימיים באיורי הצד. |
|||
שורה 1:
[[קובץ:Ejemplo.JPG|ממוזער|[[מכונת טיורינג]], המודל החישובי השקול
ב[[תורת הסיבוכיות]] וב[[תורת הרקורסיה]], '''מודל חישובי''' הוא אוסף של פעולות המותרות בחישוב והעלות שלהן. מודלים אלו משמשים למדידת המורכבות של [[אלגוריתם]] מבחינת [[סיבוכיות זמן|זמן ריצה]] או [[סיבוכיות מקום|זיכרון]], ואף עונים על שאלות מהצורה: "בהינתן מודל חישובי מסוים, האם ניתן להכריע בעיה מסוימת, ובכמה זמן?".
==דוגמות==
===אוטומט סופי===
[[קובץ:UserG48.GIF|ממוזער|דוגמה ל[[אוטומט סופי דטרמיניסטי]] מעל הא"ב <math>\Sigma=\{0,1\}</math>, ששפתו היא כל המילים שמתחילות ונגמרות באותה ספרה.]]
{{ערך מורחב|אוטומט סופי}}
אוטומט סופי הוא חמישייה <math><Q,\Sigma,q_0,\delta,F></math> כאשר:
שורה 21:
===אוטומט מחסנית===
[[קובץ:Automateapile.png
{{ערך מורחב|אוטומט מחסנית}}
אוטומט מחסנית הוא מודל חישובי שמהווה הרחבה ל[[אוטומט סופי דטרמיניסטי]] על ידי הוספת [[מחסנית (מבנה נתונים)|מחסנית]] שבה האוטומט מסוגל לאכסן מידע. הרחבה זו מגדילה את כוחו של האוטומט, כלומר את מחלקת השפות שהוא מסוגל לזהות.
| |||