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