אביב 2017

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