מקצוע מידע על מקצוע : אלגוריתמים בתרחישי אי-וודאות - 097280

097280 - אלגוריתמים בתרחישי אי-וודאות
נקודות
זיכוי
3.0
 
ניתן
בסמסטר
ב
 
עבודת
בית
פרויקט
או סמינר
מעבדה תרגול הרצאה  
3       3 שעות
שבועיות

קביעת הציון עפ"י הגשת עבודת גמר.


  094223 מבני נתונים ואלגוריתמים   (   מקצועות קדם
) 094411 הסתברות ת' ו -    
  094412 הסתברות מ   ( או
) 234247 אלגוריתמים 1 ו -    


אלגוריתמים שפועלים במודל החישוב הסטנדרטי(mar) מתבססים על ההנחה היסודית שהקלט במלואו נגיש במהלך כל הריצה. במציאות, מאידך, חלק מהקלט נחשף לעיתים רק בשלב מתקדם של ריצת האלגוריתם, ולפיכך נדרשים מודלים אלגוריתמיים אלטרנטיביים שמתאימים לתרחישי אי-וודאות. מטרת הקורס הינה להציג מודלים אלגוריתמיים כאלה ולחקור אותם באמצעות מגוון בעיות אופטימיזציה קומבינטורית. בסיום הקורס הסטודנט יהיה מסוגל: 1.לתכנן אלגוריתמים לבעיות בסיסיות במודל החישוב המקוון ולנתח את יחס התחרותיות שלהם. בעיות אלו כוללות: ואריאציות של בעיית ה paging, מקרים מוגבלים של בעיית ה- metrical task system, בעיות שמבוססות על עיקרון ה- rent-or-buy 2.לתכנן אלגוריתמים לבעיות אופטימיזציה קומבינטורית בסיסיות במודל ערוץ המידע ולנתח את יחס הקירוב שלהם. בעיות אלו כוללות: ואריאציות של מציאת עץ פורש מינימום בגרפים, ואריאציות של בניית spanners בגרפים, מקרים מוגבלים של כיסוי בצמתים/קשתות בגרפים והייפרגרפים.
3. ליישם עקרונות יסודיים בתכנון וניתוח של אלגוריתמים קומבינטוריים לבעיות אופטימיזציה סטוכסטית. עקרונות אלו כוללים: דגימה לצורך בניית פתרון, ושימוש בתכנות ליניארי.4. ליישם עקרונות יסודיים בתכנון וניתוח של אלגוריתמים מבוזרים במודל העברת ההודעות, עקרונות אלו כוללים: שימוש שימוש באקראיות לצורך שבירת סימטריה, תלות בגודל הרשת אל מול תלות בדרגה המקסימלית בחישוב מקומי.




ספרי לימוד
שנת הוצאה מוציא לאור מחברים ספר
2000 siam david peleg distributed computing: a locality-sensitive approach
1998 cambridge university press allan borodin and ran el-yaniv online computation and competitive analysis

נערך בתאריך 25/07/2021 בשעה 17:42:17