קורסים שאינם מקנים נקודות זכות
22922 אלגוריתמי קירוב
4 נקודות זכות
שיוך: תואר שני / מדעי המחשב
שיוך נוסף: מדעים / מדעי המחשב
תנאי קבלה: קבלה לתואר שני במדעי המחשב.1 ידע קודם מומלץ: הקורס נושאים מתקדמים באלגוריתמים.
פיתוח הקורס: פרופ' זאב נוטוב, פרופ' ניב בוכבינדר
רבות מבעיות היסוד שייכות לקטגוריה של בעיות NP שלמות. מציאת אלגוריתם הרץ בזמן סביר (כלומר, בזמן הפולינומיאלי בגדל הקלט) עבור אחת מבעיות אלה, יגרור אלגוריתם פולינומיאלי לכל בעיה NP שלמה. למרות מאמצים רבים בשלושים השנים האחרונות, לא נמצא אלגוריתם פולינומיאלי לאף בעיה NP שלמה. הקורס עוסק באלגוריתמים למציאת פתרון מקורב בזמן פולינומיאלי לבעיות NP שלמות. המדד המקובל לטיב הקירוב הוא המנה בין ערך הפתרון שהאלגוריתם מניב לבין הערך האופטימלי, עבור הקלט הגרוע ביותר. בקורס יוצגו אלגוריתמי קירוב לבעיות בסיסיות וחשובות, ביניהן: בעיית הסוכן הנוסע (TSP), בעיות תזמון, ובעיות בתכנון רשתות (הכללות של חתכים, עצים פורשים וכו'), וכן יוצגו שיטות כלליות לתכנון אלגוריתמי קירוב (כלומר, שיטות העובדות על משפחה של בעיות).
נושאי הלימוד
-
מבוא
-
אלגוריתמים חמדניים ואלגוריתמי חיפוש מקומי
-
אלגוריתמים המבוססים על תכנות דינמי
-
אלגוריתמים אקראיים המבוססים על עיגול של תכניות לינאריות
-
אלגוריתמים המבוססים על עיגול של תכניות חיוביות
-
השיטה הפרימאלית-דואלית
-
בעיות חתכים ושיטות עיגול המבוססות על מרחבים מטריים
-
עיגול סדרתי של תכניות לינאריות
ספר הקורס
David B. Shmoys & David P. Williamson, The Design of Approximation Algorithms (Cambridge University Press, 2011)
הסטודנטים ילמדו חלק מספר הקורס באנגלית בעזרת מדריך למידה בעברית.
1 סטודנט שאינו עומד בתנאי הקבלה יכול, במקרים מסוימים, להירשם לקורס. לפרטים נוספים עיינו בסעיף קבלה לקורסים בודדים בתכנית הלימודים לתואר שני במדעי המחשב.