חיפוש חדש  חזור
מידע אישי לתלמיד

שנה"ל תש"ף

  אלגוריתמים תת-לינאריים ויעילי זכרון
  Sublinear and Streaming Algorithms  
0368-4204
מדעים מדויקים
קבוצה 01
סמ'  ב'1100-1400006 שרייבר מתמטישיעור פרופ אושמן רותם
דרישות קדם   רשימת התפוצה  
ש"ס:  3.0

סילבוס מקוצר

בקורס זה נדבר על מס' מודלים לאלגוריתמים יעילים בזמן ובזכרון. הקורס יתחלק ל- 3 חלקים:

1. אלגוריתמי streaming: במודל חישוב זה יש לנו רצף (stream) ארוך של קלט, והאלגוריתם סורק את הקלט פעם אחת ומחשב פונקציה כלשהי שלו. לרשותנו זכרון מוגבל, ואיננו יכולים להחזיק בזכרון את כל הקלט שראינו -- כיצד ניתן לחשב או לקרב פונקציות כגון מס' האיברים השונים בקלט (distinct elements), האיברים הנפוצים ביותר בקלט (heavy hitters), וכיוב'?

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

3. אלגוריתמים מבוזרים: בשנים האחרונות אנו רואים שימושים מעניינים של אלגוריתמי streaing ואלגוריתמים תת-לינאריים בחישוב מבוזר. בחלק האחרון של הקורס נסקור כמה משימושים אלו.

סילבוס מפורט

מדעים מדויקים
0368-4204-01 אלגוריתמים תת-לינאריים ויעילי זכרון
Sublinear and Streaming Algorithms
שנה"ל תש"ף | סמ'  ב' | פרופ אושמן רותם

סילבוס מפורט/דף מידע
לצפייה בסילבוס נא ללחוץ כאן

להצהרת הנגישות


אוניברסיטת ת