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