20545 סיבוכיות חישובית
20545 סיבוכיות חישובית1
4 נקודות זכות ברמה מתקדמת
שיוך: מדעים / מדעי המחשב
תנאי קבלה: עמידה בדרישות האנגלית ובדרישות ההדרכה הביבליוגרפית בספרייה. ידע קודם דרוש: הקורסים אלגוריתמים, מתמטיקה דיסקרטית,2 הסתברות לתלמידי מדעי המחשב (או מבוא לסטטיסטיקה ולהסתברות לתלמידי מדעים), אלגברה לינארית 1. ידע קודם מומלץ: הקורס אוטומטים ושפות פורמליות.
פיתוח הקורס: פרופ' דוד הראל, פרופ' גיא קורצרס; תלמה מוקדי (עריכה)
מטרת הקורס לערוך היכרות מעמיקה עם נושאים תאורטיים בסיסיים כמו, למשל, מכונות טיורינג ושלמות ב-NP.
ספר הקורס
C. H. Papadimitriou, Computational Complexity (Addison Wesley, 1994).
הסטודנטים ילמדו את ספר הקורס באנגלית בעזרת מדריך למידה בעברית.
הקורס מיועד לסטודנטים בשלבים המאוחרים בלימודיהם.
נושאי הקורס
|
• |
מכונות טיורינג: מכונות טיורינג בסיסיות, מודל ה-RAM והשקילות למכונות טיורינג. |
|
• |
אי כריעות: מכונות טיורינג אוניברסליות, |
|
• |
יחסים בין מחלקות: מחלקות סיבוכיות בסיסיות, שלמות, משפטי היררכיה, משפטי הכלה בסיסיים. |
|
• |
רדוקציות ושלמות: שלמות ב-NP, שלמות |
|
• |
מבחר בעיות שלמות ב-NP: ספיקות, בעיות בגרפים, בעיות במספרים, בעיות בקבוצות, אלגוריתמים פסבדו- פולינומיים, שלמות חזקה ב-NP. |
|
• |
המחלקה CO-NP: CO-NP בעיית הראשוניות, בעיות חישוב, פונקציות מלאות. |
|
• |
אלגוריתמים הסתברותיים: חישובים סימבוליים, הילוכים אקראיים ו- 2-SAT, אלגוריתמים לראשוניות, RP, PP, BPP, מודל המעגלים. |
|
• |
הצפנה: מפתחות פומביים ו- RSA. |
|
• |
קירובים: כיסוי בצמתים וספיקות. |
|
• |
מקביליות: חישוב מקבילי, NC. |
1הקורס נלמד בפעם האחרונה בסמסטר א2008.
להשלכות על צבירת נ"ז בשל חפיפה עם קורס(ים) אחר(ים), ראו טבלת קורסים חופפים.