20585 מבוא לתורת החישוביות והסיבוכיות

20585 מבוא לתורת החישוביות והסיבוכיות‏1

5 נקודות זכות ברמה מתקדמת ללא אפשרות לכתיבת עבודה סמינריונית

שיוך: מדעים / מדעי המחשב

תנאי קבלה: עמידה בדרישות האנגלית ובדרישות ההדרכה הביבליוגרפית בספרייה. ידע קודם דרוש: הקורסים אלגוריתמים, אוטומטים ושפות פורמליות. ידע קודם מומלץ: הקורסים אלגברה לינארית 1, הסתברות ןמבוא לסטטיסטיקה למדעי המחשב.

פיתוח הקורס: פרופ' זאב נוטוב, פרופ' תמיר טסה

יועצים: ד"ר אלעזר בירנבוים, ד"ר דניאל רייכמן

הקורס עוסק בשאלות הנוגעות ליכולות ולמגבלות החישוב של מחשבים. תחום זה הוא מרכזי בתאוריה של מדעי המחשב ובעל חשיבות מעשית רבה. חלקו הראשון של הקורס עוסק בתורת החישוביות ודן בשאלה "מה ניתן לחשב?". החלק השני של הקורס עוסק בתורת הסיבוכיות ודן בשאלה "מה ניתן לחשב באופן יעיל?".

ספר הקורס

M. Sipser, Introduction to the Theory of Computation, 3rd ed. (‏Cengage Learning, 2013‎)‏

הסטודנטים ילמדו את ספר הקורס באנגלית, בעזרת מדריך למידה בעברית.

נושאי הלימוד

חלק א: תורת החישוביות

• מכונות טיורינג

• בעיות כריעות ובעיות שאינן כריעות,

• אי-כריעותה של בעיית העצירה

• רדוקציות, משפט רייס

• נספח – נושאים מתקדמים בחישוביות: משפט הרקורסיה, כריעות של תורות לוגיות

חלק ב: תורת הסיבוכיות

• סיבוכיות זמן, המחלקות P ו-NP

• שלמות ב-NP, משפט קוק, רדוקציות פולינומיאליות

• סיבוכיות מקום, המחלקה PSPACE, המחלקות L ו-NL, שלמות ב-NL

• משפטי היררכיה

• נושאים מתקדמים בסיבוכיות: אלגוריתמי קירוב לבעיות NP-קשות, אלגוריתמים הסתברותיים, המחלקות BPP, RP, בדיקת ראשוניות

---

1 להשלכות על צבירת נ"ז בשל חפיפה עם קורס(‏ים‎)‏ אחר(‏ים‎)‏, ראו פירוט החפיפה.

עד סמסטר ג2021 (‏כולל‎)‏ הקנה קורס זה 4 נקודות זכות.