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

שנה"ל תש"ף

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

סילבוס מקוצר

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

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

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

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

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


אוניברסיטת ת 1