אוטומטים ומשחקים

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