Algorithms for the Bandwidth Allocation Problem

אלגוריתמים עבור בעיית הקצאת רוחב פס

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

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

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