סילבוס

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

בעיית חיפוש מבנים חבויים במידע ממימד גבוה, בו מימד המידע גדול ממספר הדגימות הזמינות, צברה תאוצה בשנים האחרונות. מטרת הקורס היא הקנייה של רקע מתמטי לניתוח בעיות מסוג זה, בעיקר במקרים בהם המידע מיוצג על ידי מטריצה ו/או גרף. בחלק הראשון של הקורס, תוך שימוש בשיטות מתחום תורת-המידע, נפתח חסמים סטטיסטיים, ואלגוריתמים המשיגים את אותם החסמים (תוך התעלמות מהביטים חישוביים), עבור בעיה נתונה עם מבנה חבוי. למרות שבעיות ממימד גבוה עם מבנה מאפשרות פתרון סטטיסטי, האלגוריתמים המשיגים פתרונות אלו הם בעלי סיבוכיות חישובית גבוהה מאוד. מצדו השני של המתרס, אלגוריתמים בעלי סיבוכיות חישובית נמוכה דורשים יותר דגימות באופן משמעותי. בחלק השני של הקורס, נפתח וננתח אלגוריתמים יעלים לאותן בעיות, וכן נסביר את הפערים בין הגבולות הסטטיסטיים לגבולות החישוביים על ידי מיפויים מבעיות קשות מתורת הסיבוכיות. הקורס יכסה חלק מהנושאים הבאים: בעיית הקליקה החבויה, שערוך וקטור דליל ממדידות לינאריות, בעיית גילוי הקהילות, בעיית שערוך תת מטריצה, בעיית ניתוח גורמים ראשיים דלילים, ושערוך מטריצה מדרגה נמוכה.