חישוביות וסיבוכיות – אוניברסיטת אריאל
שם הקורס: חישוביות וסיבוכיות סמסטר: א תשפ"ב
שם הפקולטה: מדעי הטבע שם המחלקה: מדעי המחשב
מספר הקורס: 7035910
מטרת הקורס: לימוד מעמיק של נושאים תיאורטיים במדעי המחשב.
מבנה הקורס: הרצאה 3 ש"ש, תרגול 1 ש"ש.
חובות / דרישות / מטלות: במהלך הקורס תהיינה 3 מטלות חובה.
מרכיבי הציון הסופי (ציון מספרי / ציון עובר): 85% בחינה ו-15% ציון מטלות (מגן). כדי לעבור את הקורס יש לקבל 60 לפחות בבחינה.
מהלך השיעורים:
תכנית הוראה מפורטת לכל השיעורים:
| שיעור 1 | הכרת המודל של מכונת טיורינג דטרמיניסטית. שקילות מודלים. מכונת טיורינג אוניברסלית. |
| שיעור 2 | מכונת טיורינג לקבלת שפות. קבלת שפות למול הכרעת שפות. המחלקות R ו-RE. |
| שיעור 3 | הוכחת אי כריעות של השפה HP (Halting Problem) ושפות דומות. |
| שיעור 4 | רדוקציות. הגדרה, ושימוש לצורך הוכחת אי כריעות של שפות. שפות שלמות. |
| שיעור 5 | משפט Rice |
| שיעור 6 | הוכחת כריעות של השפה BHP (bounded halting problem) |
| שיעור 7 | מכונת טיורינג אי דטרמיניסטית |
| שיעור 8 | סיבוכיות – הגדרת המחלקות P,NP,coNP. היכרות עם השאלה הפתוחה P=NP ? |
| שיעור 9 | רדוקציה פולינומית. שפות שלמות ב-NP. |
| שיעור 10 | השפה SAT. היכרות עם מבחר שפות NP-שלמות. |
| שיעור 11 | משפט Cook-Levin. |
| שיעור 12 | בעיות חיפוש למול בעיות הכרעה. |
| שיעור 13 | היכרות עם מחלקות סיבוכיות נוספות. |
מקורות:
- Introduction to the Theory of Computing. International Thomson Publishing, 2013, M Sipser.
- Computers and Intractability : A Guide to the Theory of NP- Completeness/ M. R. Garey, D. S. Johnson
- Introduction to Automata Theory, Languages, and Computation (2nd Edition)/ John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman