חיפוש חדש  חזור
מידע אישי לתלמיד

שנה"ל תש"ף

  משחקים על גרפים
  Games On Graphs  
0368-4201
מדעים מדויקים
קבוצה 01
סמ'  א'1600-1900315 בנין רב תחומישיעור פרופ צוויק אורי
דרישות קדם   בחינה   רשימת התפוצה  
ש"ס:  3.0

סילבוס מקוצר

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

להצהרת הנגישות


אוניברסיטת ת 1