סילבוס

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

מתמטיקה של חישוביות על פי אלגברה לינארית

בקורס זה נציג נושאים עקרוניים בחישוביות, בכללם אלגוריתמים כגון SEMIDEFINITE PROGRAMING, קרוב לבעיות מעל סריגים (LLL), כפל מטריצות, ניתוח גורמים ראשיים (PCA).
כמו כן, נתון בהנחות קשיות המאפשרות קריפטוגרפיה (הנחת קשיות של LEARNING WITH ERRORS כדי לאפשר ONE WAY FUNCTIONS הצפנת מפתח ציבורי), וכן נדון אלו בעיות ניתן לפתור על מחשבים קוונטים.
בנוסף, נכיר את האובייקט המתמטי של סריגים, שהפך בעשורים האחרונים לאבן יסוד בקריפטוגרפיה ובמדעי המחשב.

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

נושאי הקורס:
משוואות לינאריות - מזווית אחרת: קודים, בעיות חישוביות על משוואות לינאריות.
קודים לתיקון שגיאות: קודים לינאריים, קוד ריד סלומון וריד מולר, קוד הדמרד, בדיקות לוקליות.
סיבוכיות חישובית באמצעות משוואות לינאריות: CVP היא קשה.
סריגים: הגדרות ותכונות בסיסיות, משפטי מינקובסקי, התמרת פורייה על גבי סריגים, אלגוריתם LLL.
סיבוכיות בממוצע: בעיית Shortest Integer Solution, סיבוכיות במקרה הגרוע של SVP ל SIS, קשיות למידה עם טעויות (LWE) ושימושים בקריפטוגרפיה.
קריפטוגרפיה: הצפנת מפתח ציבורית, פונקציות חד כיווניות (ONE WAY FUNCTIONS), פונקציות HASH מונעות התנגשויות (CRH).
אופטימיזציה ולמידת מכונה: SEMIDEFINITE PROGRAMING, ניתוח גורמים ראשוניים (PCA).
אלגוריתמים לכפל מטריצות, מבוא למחשוב קוונטי ועוד...

הערה: ייתכנו שינויים בסילבוס בהתאם לקצב ולוח הזמנים של הסמסטר.

דרישות קדם: אלגברה לינארית 1א, מודלים חישוביים (במקביל).
בנוסף, הקורס ידרוש בגרות מתמטית ויכלול שימוש נרחב בנושאים שונים מקורסי שנה א' במתמטיקה (הסתברות, אינטגרלים, מטריצות אוניטריות וכדומה)