אלגוריתם מקוון
במדעי המחשב, אלגוריתם מקוון (online algorithm) הוא אלגוריתם אשר מאולץ לפלוט החלטות לפני השלמת קבלת כל הקלט. מאידך גיסא, אלגוריתם שאינו מקוון (offline algorithm) מורשה לעבור על כל הקלט בטרם ייאלץ לפלוט את החלטתו הראשונה. מסיבה זו, אלגוריתם מקוון עשוי להגיע להחלטות שאינן אופטימאליות יחסית לאלגוריתם שאינו מקוון.
ניתוח התחרותיות (competitive analysis) של האלגוריתם הוא חקר איכות החלטות של אלגוריתמים מקוונים. זהו ניתוח של החרטה של אלגוריתם מקוון.
דוגמאות
ניהול זיכרון מטמון
בין שאר תפקידיה, מערכת הפעלה של מחשב מתפעלת מידע המחולק פנימית לדפים. המשתמש מבצע פעולות המתרגמות לבקשות גישה לדפים. רק לחלק מדפים אלה יש מקום בזיכרון המטמון של המחשב, ורובם נשמרים בדיסק הקשיח שלו. זמן הטעינה של דפים מהדיסק הקשיח לזיכרון הוא ארוך מאד בהשוואה לרוב פעולותיו האחרות של המחשב. מסיבה זו, כשהמשתמש מבצע פעולה המתרגמת לצורך לטעון דף לזיכרון, ויש צורך לפנות דף אחר מהזיכרון לצורך כך, אידיאלית היה כדאי לפנות את הדף שיבוקש האחרון בעתיד. דא עקא, שהמחשב אינו יודע בשלב זה את כל סדרת הבקשות בעתיד, ולכן זו בעיה מקוונת.
משחק בעל יותר משחקן יחיד
רוב המשחקים בעלי יותר משחקן יחיד (לדוגמה שחמט או דמקה) הם, לפי ההגדרה, מקוונים. אי אפשר לקבל מראש את סדרת ההחלטות של היריב, מפני שפעולותיו של כל צד נקבעות בין היתר על פי פעולת הצד השני.
בעיית k-השרתים
בעיית k השרתים (K-Server problem) היא אחת מהבעיות הידועות באלגוריתמים מקוונים והוצגה לראשונה ב-1988[1]. בבעיה זו ישנם k שרתים מפוזרים במרחב מטרי סופי (מעין "חדר"). הבעיה מוגדרת כך: בהינתן k שרתים הנמצאים בנקודות במישור, ובקשות שמגיעות מנקודות שונות באופן מקוון, צריך להחליט לכל בקשה איזה שרת להזיז לנקודה שלה כדי לטפל בה. המטרה היא להזיז את השרתים במרחק הכולל (על פי המרחב המטרי) הקטן ביותר האפשרי.
השערה רווחת היא כי יחס התחרותיות של בעיית k-השרתים הוא k. ידוע כי k הוא הערך הטוב ביותר האפשרי וכי לבעיית 2 השרתים ידוע אלגוריתם 2-תחרותי. לערכים גדולים יותר היחס הטוב ביותר הידוע הוא 2k-1[2].
הערות שוליים
22372918אלגוריתם מקוון