שיעור 1 - 22/2/11

• תזכורת - מכונת טיורינג
• משפט על זמני ריצה
• מכונת אורקל

תרגול 1 - 22/2/11

• השוואה בין מכונת טיורינג חד סרטית ומכונת טיורינג k סרטית

שיעור 2 - 1/3/11

• רדוקציות Karp
• רדוקציות Cook
• חיפוש לעומת הכרעה

תרגול 2 - 1/3/11

• קבוצה ב"ת מקסימלית כבעיה ב-NP

שיעור 3 - 8/3/11

• כיצד להפוך מכונת טיורינג למעגל
• כיצד להפוך מעגל למכונת טיורינג
• חישוב מוגבל זכרון

תרגול 3 - 8/3/11

• מחלקות זמן אקספוננציאלי

שיעור 4 - 15/3/11

• סיבוכיות מקום
• stCON
• NL ו- coNL

תרגול 4 - 15/3/11

• סיבוכיות מקום לוגריתמית

שיעור 5 - 22/3/11

• ההיררכיה הפולינומיאלית

תרגול 5 - 22/3/11

• 2SAT

שיעור 6 - 29/3/11

• TQBF
• מכונת טיורינג הסתברותית
• אמפליפיקציה לשגיאה של מכונות עם שגיאה דו צדדית

תרגול 6 - 29/3/11

• ההיררכיה הפולינומיאלית

שיעור 7 - 5/4/11

• זיווג מושלם
• המחלקה Psize

תרגול 7 - 5/4/11

• מחלקות סיבוכיות הסתברותיות

שיעור 8 - 12/4/11

• משפט סיפסר
• GNI
• שיחה אינטרקטיבית

תרגול 8 - 12/4/11

• חישוב הסתברותי - וידוא כפל מטריצות

שיעור 9 - 3/5/11

• IP חלקית ל PSpace
• MIP, PCP

תרגול 9 - 3/5/11

• אלגוריתמי קירוב
• הוכחות אינטרקטיביות

שיעור 10 - 17/5/11

• אלגוריתמי קירוב

תרגול 10 - 17/5/11

• בעיית הסוכן הנוסע

שיעור 11 - 24/5/11

• Gap ו- PCP

תרגול - 24/5/11

שיעור 12 - 31/5/11

• אלגוריתם אל-גמל
• אלגוריתם חלוקת מכונית
• פרוטוקול 3 צביעה עם 0 מידע
• סיכום הקורס

תרגול 11 - 31/5/11

• בעיות הבטחה

תרגול חזרה