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

שנה"ל תשע"ה

  סיבוכיות
  Computational Complexity  
0368-3168-09
מדעים מדויקים
סמ'  ב'1600-1700204 פיזיקה-שנקרתרגיל מר גלמן אפרים
ש"ס:  1.0

סילבוס מקוצר
 סיבוכיות זמן וזיכרון. המחלקות L,NL,P,NP ו PSPACE. רדוקציות ובעיות שלמות למחלקות הנ"ל. משפט Savitch.  NL=coNL. משפט Cook-Levin. דוגמאות לבעיות NP שלמות. אלגוריתמי קירוב לבעיות NP שלמות. רדוקציות משמרות קירוב. ההיררכיה הפולינומית. חישובים מטילי מטבעות, המחלקה   BPP. המחלקה BPP מוכלת ב S2. משפט ה PCP וקושי של קרוב בעיות NP קשות.

  ספרי לימוד:

 ·      C. Papadimitriou, Computational complexity.

  ·      M. Sipser, Introduction to the theory of computation.

 ·      V. Vazirani, Approximation Algorithms.

 דרישות קדם:

 יעילות של חישובים, מודלים חישוביים

 

 

 

 

 

 

 

 

 

 

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


אוניברסיטת ת