אלגוריתם מקוון

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

ניתוח התחרותיות (competitive analysis) של האלגוריתם הוא חקר איכות החלטות של אלגוריתמים מקוונים. זהו ניתוח של החרטה של אלגוריתם מקוון.

דוגמאות[עריכת קוד מקור | עריכה]

ניהול זיכרון מטמון[עריכת קוד מקור | עריכה]

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

משחק בעל יותר משחקן יחיד[עריכת קוד מקור | עריכה]

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

בעיית k-השרתים[עריכת קוד מקור | עריכה]

בעיית k השרתים (K-Server problem) היא אחת מהבעיות הידועות באלגוריתמים מקוונים. בבעייה זו ישנם k שרתים מפוזרים במרחב מטרי סופי (מעין "חדר"). מקובל לדרוש שהשטח יהיה מלבני. הבעייה מוגדרת כך: בהינתן k שרתים המיוצגים על ידי נקודות במישור, ובקשות שמגיעות מנקודות שונות, כיצד השרתים יוכלו לטפל בכל הבקשות כאשר המרחק הכולל של תנועת השרתים הוא מינימלי? שרת מטפל בבקשה על ידי הגעה אליה. הנחה רווחת במדעי המחשב [דרוש מקור] טוענת כי לבעיית k-השרתים יש אלגוריתם k-תחרותי. לבעיית 2 השרתים ידוע אלגוריתם 2-תחרותי. האלגוריתם הוא מכוון מכיוון שהשרתים אינם יודעים איפה הבקשות תופענה.