22921 אופטימיזציה קומבינטורית
22921 אופטימיזציה קומבינטורית
4 נקודות זכות
שיוך: תואר שני / מדעי המחשב
תנאי קבלה: קבלה לתואר שני במדעי המחשב.1
פיתוח הקורס: פרופ' זאב נוטוב, פרופ' גיא קורצרס
הקורס הוא המשכו הטבעי של הקורס אלגוריתמים (20417). הקורס עוסק בעיצוב אלגוריתמים לבעיות יסוד חשובות, למשל: בעיית זיווג המקסימום בגרף כללי, בעיית הזרימה בעלות מינימאלית, בעיית הסוכן הנוסע ובעיות נוספות. כמו כן, נלמדות שיטות כלליות לעיצוב אלגוריתמים לבעיות קומבינטוריות מסוימות (כלומר, שיטות אלו עובדות עבור משפחה רחבה של בעיות).
נושאי הלימוד
-
חתכי מינימום בגרפים לא מכוונים
-
בעיות זרימה בעלות מינימלית
-
אלגוריתמים לבעיות זיווג בגרף כללי
-
בעיית הסוכן הנוסע
ספר הקורס
W.J. Cook, W.H. Cunningham, W.R. Pulleyblank & A Schrijver, Combinatorial Optimization (John Wiley, 1998).
הסטודנטים ילמדו את פרקים 5-1 ואת פרק 7 מספר הקורס באנגלית, בעזרת מדריך למידה מפורט בעברית. המדריך מלווה את פרקי הספר באופן צמוד ומכיל גם פתרונות לשאלות שבספר וחומר נוסף.
1סטודנט שאינו עומד בתנאי הקבלה יכול, במקרים מסוימים, להירשם לקורס. לפרטים נוספים עיינו בסעיף קבלה לקורסים בודדים בתכנית הלימודים לתואר שני במדעי המחשב.