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

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

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

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

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

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

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

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

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