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