סילבוס

תוכן הקורס ומטרתו

במסגרת הקורס נעסוק במספר סוגים של משחקים שמשוחקים ע"י שחקן אחד או שני שחקנים על גבי גרף מכוון שלקשתותין מתאימים משקלים, ולפעמים גם הסתברויות. משחקים אלא מהווים גירסא סטוכסטית ותחרותית לבעיית המסלולים הקצרים בגרפים. למשל, Markov Decision Process הוא משחק של שחקן אחד שבו חלק מהמעברים הם הסתברותיים. המשחק Turn-Based Stochastic Game הוא משחק שמשוחק ע"י שני שחקנים שבו חלק מהמעברים הם הסתברותיים.במהלך הקורס נציג אלגוריתמים שונים לפתרון משחקים אלא. זמן הריצה של אלגוריתמים אלה הוא פולינומיאלי רק במקרים מיוחדים מאוד. השאלה האם ניתן לפתור את המשחקים האלה בזמן פולינומיאלי היא השאלה הפתוחה המרכזית בתחום.נדון גם בקשרים בין משחקים אלא לבעיית התכנות הליניארי, ולהכללות קומבינטוריות של תכנות ליניארי.