מודלים חישוביים
קורס 20604 · 5 נ״ז
מועדי בחינות
האוניברסיטה עוד לא פרסמה מועדי בחינות לקורס הזה. נעדכן כאן ברגע שיתפרסמו.
לפי לוח הבחינות של האוניברסיטה הפתוחה; ייתכנו שינויים, והמועד שלכם מופיע בהזמנה לבחינה. כל מועדי הבחינות
פרטי הקורס
- נקודות זכות
- 3 נקודות זכות ברמה רגילה + 2 ברמה מתקדמת
- רמה
- רגילה + 2 ברמה מתקדמת
- שיוך
- מדעים / מדעי המחשב
מתי הקורס נפתח
- 2027סמסטר א – נפתחסמסטר ב – נפתחקיץ – לא מתוכנן
- 2028סמסטר א – נפתחסמסטר ב – נפתחקיץ – לא מתוכנן
לפי תכנון האוניברסיטה; שינויים אפשריים.
קישורים
ידע קודם
מוביל אל
על הקורס
הקורס עוסק בשלוש שאלות בסיסיות הנוגעות ליכולות ולמגבלות החישוב של מחשבים: (א) מהו מחשב? (ב) מה ניתן לחשב? ו- (ג) מה ניתן לחשב באופן יעיל? שאלות אלה הן מרכזיות בתאוריה של מדעי המחשב ובעלות חשיבות מעשית רבה. במסגרת הקורס נכיר מספר מודלים חישוביים יסודיים וננסה להבין את כוח החישוב שלהם.
חלקו הראשון של הקורס עוסק במודלים חישוביים פשוטים יחסית הנקראים "אוטומטים"; למודלים אלה יש זיכרון מוגבל ועל כן גם כוחם החישובי מוגבל. בחלק השני נכיר את "מכונת טיורינג" שהוא מודל חישובי מקובל למחשב של ימינו, ונעסוק בשאלה מה ניתן (ובעיקר מה לא ניתן) לחשב באמצעות מודל חישובי זה. בחלק השלישי של הקורס נדון בשאלה מה ניתן לחשב באופן יעיל.
ספר הקורס
M. Sipser, Introduction to the Theory of Computation, 3rd ed. (Cengage Learning, 2013)
הקורס מבוסס על פרקים 1-5 ו-7 בספר, ועל מדריך למידה בעברית.
נושאי הלימוד
- אוטומטים סופיים ושפות רגולריות.
- דקדוקים, שפות חסרות הקשר, אוטומט מחסנית.
- מכונות טיורינג, שקילות של מודלי חישוב שונים למכונת טיורינג, תזת צ'רץ'-טיורינג.
- כריעות: מכונת טיורינג אוניברסלית, שיטת האלכסון של קנטור, אי-כריעות של בעיית העצירה.
- רדוקציות: בעיות שלא ניתנות להכרעה, רדוקציות מיפוי.
- סיבוכיות זמן: רדוקציות פולינומיאליות, המחלקות P ו-NP, משפט קוק-לוין, בעיות NP-שלמות.
צוות הקורס
- פיתוח הקורס
- פרופ' תמיר טסה, פרופ' זאב נוטוב
- ייעוץ
- ד"ר אלעזר בירנבוים
פרטי הקורס מקטלוג האוניברסיטה הפתוחה, עודכנו ב-4.11.2026.