מרצה/ים:
פרופסור אמיר שפילקה
מתרגל/ים:
מר בן לי וולק
סיכומים:
Tuesday, March 14, 2017
נושאי השיעור:
- סיבוכיות - תיאור כללי ודוגמאות לשאלות מעניינות בתחום
- אלגוריתמים באלגברה לינארית
- אלוגריתם שטראסן לכפל מטריצות
- אלגוריתם קרצובה לכפל פולינומים
Tuesday, March 14, 2017
נושאי השיעור:
- שדות סופיים
- הפיכים מודולו מספר
- חבורה אבלית, מרחב ווקטורי
- כל שדה סופי הוא בגודל חזקת ראשוני
Tuesday, March 21, 2017
נושאי השיעור:
- מחלק משותף מקסימלי
- אלגוריתם אוקלידס ואלגוריתם אוקלידס המורחב
Tuesday, March 28, 2017
נושאי השיעור:
- הצפנה - RSA, פרוטוקול רבין ושקילותו לפירוק לגורמים ראשוניים
- סיבוכיות "על אמת" - מכונות טיורינג, מעגלים בוליאנים
Tuesday, March 28, 2017
נושאי השיעור:
- אי כריעות בעיית העצירה
- הסתברות - אי שוויונות מרקוב וצ'בישב
Tuesday, April 4, 2017
נושאי השיעור:
- מעגלים בוליאנים
- מכונת טיורינג אוניברסלית
- מכונות טיורינג עם אורקל
- משפט ההיררכיה בזמן
Wednesday, April 5, 2017
נושאי השיעור:
- סיבוכיות זיכרון, משפט ההיררכייה בזיכרון
- הרכבה של מכונות מוגבלות זיכרון
- רדוקציות ושלמות
Tuesday, June 6, 2017
נושאי השיעור:
- הוכחות אינטראקטיביות
- הוכחות אפס-ידע
- בעיות אופטימיזציה וקירובים
- בעיות פער
Tuesday, June 13, 2017
נושאי השיעור:
- בעיות אופטימיזציה
- חזרה על סוף השיעור הקודם
- בעיות פער
- משפט PCP
- רדוקציות פער ובעיות פער קשות
- בעיית CSG
- דוגמאות
Tuesday, June 20, 2017
נושאי השיעור:
- המשך הוכחה משיעור שעבר
- בעיית cubic-solvability
- קודים לתיקון שגיאות:
- Reed-Solomon
- Hadamard
Tuesday, June 27, 2017
נושאי השיעור:
- קודים לתיקון שגיאות
- חזרה על השיעור הקודם
- תיקון טעויות בעזרת קוד ריד-סולומון
- "מחיקות"
- "החלפות" (אלגוריתם וולש-ברלקאמפ)
- הרכבת קודים
- חלוקת סודות