חישוביות וסיבוכיות
קוד קורס: 10076
2.5 נ"ז
נושאי הקורס:
- מכונות טורינג.
- רדוקציות פשוטות.
- NP ו-P.
- משפט cook.
- בעיות NP קשות ושלמות שונות והרדוקציות המוכיחות זאת.
- מחלקת הסיבוכיות PSPACE.
- אי כריעות בעיית העצירה.
- בעיות לא כריעות אחרות כמו ריצוף המישור.
דרישות הקדם והדרישות המקבילות בקורס חישוביות וסיבוכיות הינן:
דרישות קדם: אוטומטים ושפות פורמליות (10087).
דרישות מקבילות: אין.