חיפוש חדש  חזור
מידע אישי לתלמיד

שנה"ל תש"ף

  סיבוכיות
  Computational Complexity                                                                             
0368-3168-07
מדעים מדויקים
סמ'  ב'1300-1400007תרגיל מר מאיר אורי
סילבוס מקוצר

סילבוס לקורס סיבוכיות 0368-3168-07

(לא בדיוק לפי סדר ההרצאות).

חזרה והרחבה של חומר שנלמד במודלים:

1.      מכונות טיורינג, NP, לכסון, בעיית העצירה, חיפוש לעומת הכרעה.

2.      מ״ט כמודל אוניפורמי (מכונה אחת לכל קלט) לעומת מעגלים כמודל לא אוניפורמי. כל פונקציה סופית ניתן לחשב במעגל. חסם תחתון משיקולי ספירה למעגלים.

3.      היררכיית זמן.

4.      משפט קוק.

סיבוכיות זכרון:

5.      הגדרות, רדוקציות, הרכבות, דוגמאות: כפל מטריצות, קשירות בגרפים.

6.      מחלקות סיבוכיות

7.      stcon היא NL שלמה, NL ב L^2

8.      NL = coNL

9.      זכרון מוכל בזמן אקספוננציאלי

10.  היררכיית זכרון

11.  הגדרת PSPACE

12.  TQBF: הגדרה והוכחת שלמות ב-PSPACE. קשר למשחקים .

נושאים נוספים הקשורים לזמן וזכרון:

13.  Polynomial Hierarchy

14.  מכונות טיורינג בעלות אוב (oracle Turing machines)

15.  משפט Karp Lipton

אקראיות:

16.  הגדרת BPP,RP .  

17.  דוגמאות לאלגוריתמים מטילי מטבעות: האם AB=C עבור מטריצות.
 esting
Polynomial Identity T, Matching בגרף דו-צדדי.

18.  ל־ BPP יש מעגלים בגודל פולינומיאלי.

19.  BPP מוכלת ב 2^.

20.  קושי כמשאב:Hardness vs. randomness   

נושאים מתקדמים:

21.  חסמים תחתונים למעגלים בוליאנים

22.  אלגוריתמי קירוב

23.  פרוטוקולים אינטראקטיבים

סילבוס מפורט

מדעים מדויקים
0368-3168-07 סיבוכיות
Computational Complexity
שנה"ל תש"ף | סמ'  ב' | מר מאיר אורי

666סילבוס מפורט/דף מידע
לצפייה בסילבוס נא ללחוץ כאן

להצהרת הנגישות


אוניברסיטת ת