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