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

שנה"ל תשע"ה

  סיבוכיות
  Computational Complexity  
0368-3168-11
מדעים מדויקים
סמ'  ב'1000-1100222 פיזיקה-שנקרתרגיל מר דורון דין
ש"ס:  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.

 דרישות קדם:

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

 

סילבוס מפורט

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

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

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


אוניברסיטת ת