נקודות זכות באוניברסיטה העברית: 3

תואר: מוסמך

היחידה האקדמית שאחראית על הקורס: מדעי המחשב

סמסטר: סמסטר ב'

שפת ההוראה: אנגלית ועברית

קמפוס: קרית א"י ספרא

מורה אחראי על הקורס (רכז): עמרי וינשטין

דוא"ל של המורה האחראי על הקורס: Omri.weins@gmail.com

שעות קבלה של רכז הקורס:

מורי הקורס:
פרופ עמרי וינשטין

תאור כללי של הקורס:
קורס זה יכסה אלגוריתמים מתקדמים לפתרון תכניות לינאריות (LPs), משיטות קלאסיות (אלגוריתם הסימפלקס והאליפסואיד) ועד שיטות נקודות-פנים (Interior-Point Methods) ,פונקציות מחסום (Self-Concordant Barrier functions) ושיטות ניתוח על בסיס פוטנציאל אנרגטי של המסלול המרכזי (Energy Potential function).

בחלק השני של הקורס נחקור פתרונות מקורבים מהירים לבעיות תכנות לינארי באמצעות גרסאות של שיטת עדכוני המשקל הכפלי (Multiplicative-Weight Updates, MwU), כולל אלגוריתם פרנק-וולף (Frank-Wolfe algorithm), האלגוריתם של קלרקסון (Clarkson’s algorithm), זרימת מקסימום (MaxFlow, CKMST).

מטרות הקורס:

תוצרי למידה :
בסיומו של קורס זה, סטודנטים יהיו מסוגלים:
עבודת בית + פרזנטציה של נושא מחקרי בפורמט סמינריוני

דרישות נוכחות (%):
70

שיטת ההוראה בקורס:

רשימת נושאים / תכנית הלימודים בקורס:
• עיגול תכנות לינארי (LP Rounding) + יישומים
• דואליות קמורה + דואל פרנשל (Convex Duality + Frenchel Dual) • שיטת הסימפלקס (Simplex Method)
• אליפסואיד (Ellipsoid)
• שיטת ניוטון לפונקציות מחסום תואמות עצמית (Newton’s Method for SC Barrier Functions)
• שיטות הנקודות הפנימיות (Interior-Point Methods)
• ניתוח מבוסס אנרגיה (Energy-based Analysis)
• שיטת המשקלים המכפילים (Multiplicative Weights Method) (PST/Clarkson/Frank-Wolfe)
• האצה באמצעות צימוד לינארי (Acceleration via Linear Coupling

חומר חובה לקריאה:
Convex Optimization,
S. Boyd

חומר לקריאה נוספת:
Yin-Tat Lee’s course “Optimization and Geometry” in UW

מרכיבי הציון הסופי :
הגשת עבודה מסכמת / פרויקט גמר / מטלת סיכום / מבחן בית / רפרט % 70
מצגת / הצגת פוסטר / הרצאה / סמינר / פרוסמינר / הצעת מחקר % 30

מידע נוסף / הערות: