סילבוס

תוכן הקורס ומטרתו

האם אלגוריתם אופטימיזציה יכול להיות אופטימלי לכשעצמו? הקורס יסקור טכניקות לניתוח הסיבוכיות של אלגוריתמי אופטימיזציה, עם דגש על חסמי סיבוכיות תחתונים שמאפשרים להוכיח כי לא ניתן לשפר באופן מהותי אלגוריתמים מסוימים. נתמקד בשיטות מסדר ראשון, שמתאימות לבעיות בלמידה חישובית מודרנית, ונחקור כיצד תכונות כגון חלקו?ת, קמירו?ת ורעש בגרדיאנט משפיעות על סיבוכיות האופטימיזציה. ההוכחות שלנו ינצלו טכניקות כלליות כגון פולינומי צ'בישב, שיטת לה-קאם ואורקלים מתנגדים.