סיכומים לקורס מודלים חישוביים, שמועבר ע"י פרופסור רונן שאלטיאל. מוזמנים לקרוא, להינות ולהתרגש.
נושאים, ע"פ סדר ההרצאות:
- למה לומדים על מודלים חישוביים?
- אסל"ד
- אס"ד
- שפות רגולריות
- למת הניפוח
- משפט היימיל-נרוד
- אוטומט מחסנית
- שפות חסרות הקשר
- מכונת טיורינג
- שפות כריעות
- שפות מתקבלות
- רדוקציות
- משפט רייס
- הקבוצות P ו-NP
- מסלולים המילטוניים
- משפט קוק-לוין
- בעיות לדוגמה
מצורפים גם שני דפים הכוללים חומר עזר לצורך מבחנים.