שיעור 1 - 3/3/09

• עניינים אדמיניסטרטיביים
• מבוא לחישוביות וסקירה הסטורית
• הגדרת חישוביות, תזת צ'רץ'-טיורינג, בעיית העצירה
• הגדרת P, NP, coNP

תרגול 1 - 3/3/09

• הגדרת המחלקות P, NP, coNP
• הגדרת פעולת הכוכב
• הוכחת סגירות כלפי כוכב של שלושת המחלקות

שיעור 2 - 10/3/09 לא התקיים (חופשת פורים)

תרגול 2 - 10/3/09 לא התקיים (חופשת פורים)

שיעור 3 - 17/3/09

• דוגמאות לבעיות ב-P ו-NP
• הוכחת P מוכל ב-NP מוכל ב-EXP
• הגדרה חלופית ל-NP
• רדוקציות פולינומיאליות ובעיות NP-שלמות

תרגול 3 - 17/3/09

• רדוקציית Karp
• סגירות NP תחת רדוקציית Karp פולי'
• רדוקציית Cook
• שקילות הסגירות של NP לרדוקציות Cook לשאלה NP = coNP

שיעור 4 - 24/3/09

• הוכחת NP-שלמות של TMSAT
• משפט Cook-Levin
• בעיות NP-שלמות אחרות
• שקילות בעיות החלטה וחיפוש בבעיות NP-שלמות
• מחלקות סיבוכיות נוספות

תרגול 4 - 24/3/09

• חיפוש לעומת החלטה - בעיית 3col כדוגמה
• הקשר בין שפות אונריות ו-NP-שלמות

שיעור 5 - 31/3/09

• הוכחת EXP != NEXP => P != NP
• המחלקות סיגמא-2-P ופאי-2-P
• משפט היררכיית הזמן
• אורקלים

שיעור 6 - 21/4/09

• חזרה פורמלית על מכונות טיורינג
• סיבוכיות מקום
• רדוקציות log-space
• בעיית CONN

תרגול 6 - 21/4/09

• הוכחה שהמשלימה של 2SAT היא coNL-שלמה
• תמונת מצב לגבי שאלות פתוחות בסיבוכיות מקום

שיעור 7 - 28/4/09 לא התקיים (יום הזיכרון)

תרגול 7 - 28/4/09 לא התקיים (יום הזיכרון)

שיעור 8 - 5/5/09

• חזרה על חומר קודם
• משפט Savitch
• משפט Immerman

תרגול 8 - 5/5/09

• משפט Savitch
• משפט Immerman
• תרגילים בנושא

שיעור 9 - 12/5/09

• בעיות PSPACE-שלמות (TQBF)
• אלגוריתמי קירוב
• Vertex Cover
• שימוש ב-Linear Programming

תרגול 9 - 12/5/09

• הגדרת סדר קירוב
• קירוב בעיית TSP המקיימת את אי שיוון המשולש

שיעור 10 - 19/5/09

• אלגוריתמי קירוב
• בעיית Set Cover
• הוכחת יחס קירוב
• קושי בקירוב בעיות ובעיות Gap

תרגול 10 - 19/5/09

• בעיות Gap
• בעיית Max-2SAT

שיעור 11 - 26/5/09

• משפט ה-PCP
• רדוקציות שומרות Gap
• בעיות Constraint Graph
• קושי בקירוב IS

תרגול 11 - 26/5/09

• בעיות Gap - המשך
• השיטה ההסתברותית
• בעיות Constraint Graph - CSG

שיעור 12 - 2/6/09

• בעיית צביעה מינימילת
• גרפי אילוצים "סימטריים להסטה" - qCSG
• רדוקציה מגרף אילוצים כללי לגרף אילוצים "סימטרי" kCSG < qCSG
• מסקנה: קיורב צביעה מינימלית בכל קבוע סופי הוא NP-קשה
• הוכחת עדות ללא מסירת מידע (סיפור פקיד הבנק)

תרגול 12 - 2/6/09

• חזרה על קושי בקירוב IS:

משפט ה-PCP
gap-kCSG[a,1] < gap-IS[a/k,1/k]
gap-kCSG[a,1] < gap-k^lCSG[a^l,1]

• שאלה ממבחן בנושא אמפליפיקציה

שיעור 13 - 9/6/09

• חזרה על ההירארכיה הפולינומיאלית
• הגדרת מכונת טיורינג רנדומית והמחלקה BPP
• BPP מוכל בסיגמא-2-P
• הליכה רנדומית

תרגול 13 - 9/6/09

• חזרה על קושי בקירוב המספר הכרומטי:

רדוקציה מ-qCSG לצביעה מינימלית
רדוקציה מ-kCSG ל-qCSG

• (דה-רנדומיזציה של אלגוריתם רנדומי)

שיעור 14 - 16/6/09

• חסם צ'רנוף
• שתי דוגמאות לאלגוריתמים רנדומיים:

קירוב SetCover באמצעות LP
קירוב MaxCut באמצעות SDP

תרגול 14 - 16/6/09

• דה-רנדומיזציה של בעיית Max-Cut
• דה-רנדומיזציה של בעיית Min-Cut