22927 סמינר: אלגוריתמים מקוונים

22927 סמינר: אלגוריתמים מקוונים

3 נקודות זכות

שיוך: תואר שני / מדעי המחשב

 תנאי קבלה: 12 נקודות זכות בלימודי התואר השני בממוצע של לפחות 80. ידע קודם דרוש: הקורס אלגוריתמים.

פיתוח הקורס: ד"ר לאה אפשטיין

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

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

נושאי הלימוד

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

מטרות הסמינר

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

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