סיבוכיות
תשע״ז
-
הרצאה 1 ←
סיבוכיות - תיאור כללי ודוגמאות לשאלות מעניינות בתחום
אלגוריתמים באלגברה לינארית
אלוגריתם שטראסן לכפל מטריצות
אלגוריתם קרצובה לכפל פולינומים -
תרגול 1 ←
שדות סופיים
הפיכים מודולו מספר
חבורה אבלית, מרחב ווקטורי
כל שדה סופי הוא בגודל חזקת ראשוני -
הרצאה 2 ←
DFT, FFT
שימוש בקושי חישובי - הצפנה -
תרגול 2 ←
מחלק משותף מקסימלי
אלגוריתם אוקלידס ואלגוריתם אוקלידס המורחב -
הרצאה 3 ←
הצפנה - RSA, פרוטוקול רבין ושקילותו לפירוק לגורמים ראשוניים
סיבוכיות על אמת - מכונות טיורינג, מעגלים בוליאנים -
תרגול 3 ←
אי כריעות בעיית העצירה
הסתברות - אי שוויונות מרקוב וצ'בישב -
הרצאה 4 ←
מעגלים בוליאנים
מכונת טיורינג אוניברסלית
מכונות טיורינג עם אורקל
משפט ההיררכיה בזמן -
תרגול 4 ←
מעגלים בוליאנים
מכונות עם אורקל -
הרצאה 5 ←
סיבוכיות זיכרון, משפט ההיררכייה בזיכרון
הרכבה של מכונות מוגבלות זיכרון
רדוקציות ושלמות -
תרגול 5 ←
מכונות טיורינג מוגבלות זיכרון
-
הרצאה 6 ←
הוכחת שלמות CVAL
הגדרת NCk, ACk
הוכחת שלמות TQBF -
תרגול 6 ←
גרפים
איזון נוסחאות -
הרצאה 7 ←
אי דטרמיניזם
המחלקה NP -
תרגול 7 ←
רדוקציות מחיפוש להכרעה
-
הרצאה 8 ←
אי דטרמיניזם ומחלקות משלימות
אלגוריתמים הסתברותיים -
תרגול 8 ←
תרגילים על גרפים
-
הרצאה 9 ←
אלגוריתמים הסתברותיים
-
תרגול 9 ←
המחלקה RL
-
הרצאה 10 ←
הוכחות אינטראקטיביות
הוכחות אפס-ידע
בעיות אופטימיזציה וקירובים
בעיות פער -
תרגול 10 ←
אלגוריתמים אקראיים
קירובים -
הרצאה 11 ←
בעיות אופטימיזציה
חזרה על סוף השיעור הקודם
בעיות פער
משפט PCP
רדוקציות פער ובעיות פער קשות
בעיית CSG
דוגמאות -
תרגול 11 ←
הוכחות אינטראקטיביות
בעיות פער -
תרגול 12 ←
בעיות פער
משפט ה-PCP
משפט הוסטארד -
הרצאה 12 ←
המשך הוכחה משיעור שעבר
בעיית cubic-solvability
קודים לתיקון שגיאות:
Reed-Solomon
Hadamard -
הרצאה 13 ←
קודים לתיקון שגיאות
חזרה על השיעור הקודם
תיקון טעויות בעזרת קוד ריד-סולומון
מחיקות
החלפות (אלגוריתם וולש-ברלקאמפ)
הרכבת קודים
חלוקת סודות -
תרגול 13 ←
קודים לתיקון שגיאות
חסם סינגלטון
חסם גילברט-ורשמוב