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