קוד קורס: 10076
2.5 נ"ז

נושאי הקורס:

  • מכונות טורינג.
  • רדוקציות פשוטות.
  • NP ו-P.
  • משפט cook.
  • בעיות NP קשות ושלמות שונות והרדוקציות המוכיחות זאת.
  • מחלקת הסיבוכיות PSPACE.
  • אי כריעות בעיית העצירה.
  • בעיות לא כריעות אחרות כמו ריצוף המישור.

דרישות הקדם והדרישות המקבילות בקורס חישוביות וסיבוכיות הינן:
דרישות קדם: אוטומטים ושפות פורמליות (10087).
דרישות מקבילות: אין.

קרא עוד