סיבוכיות

מרצה: פרופ' אמנון תא שמע
מתרגלים: עידו בן אליעזר
אתר הקורס: לחץ עליי!
2010 סמסטר ב'

קצת על הקורס

הקורס הוא המשך ישיר של מודלים חישוביים. החלק הראשון של הקורס הוא חזרה והעמקה של הנושאים הנלמדים במודלים: המחלקות P, NP, coNP, דוגמאות לבעיות NP-Complete, והקשרים בין המחלקות השונות. לאחר מכן מרחיבים את הדיון גם לסיבוכיות מקום, ולמחלקות רחבות יותר. מתעסקים גם בהשפעת היכולת להשתמש בביטים רנדומיים על המחלקות השונות, כמו גם מחלקות של יכולות קירוב.

תרגילים

• ישנה חובת הגשה של 6 מתוך 7 תרגילים, אך הם אינם משפיעים על הציון.

ציונים

• יהיה בוחן במשקל 15% מהציון הסופי ב-27.04.2010.

סיכומים

קישורים

אפשר להיעזר גם באתר של השנה שעברה.

בהצלחה

שיהיה לכולנו בהצלחה!