אלגוריתמים מקוונים לקלטים סטוכסטיים
תאור נושא הסמינר:
נניח ויש ברשותנו מוצר שברצוננו למכור, וקונים חסרי סבלנות מתגלים אחד אחרי השני. עם הגעת קונה נקבל הצעת מחיר שעלינו או לקבל או לדחות מיידית. מטרתנו למקסם את הרווח. לו היינו יודעים את העתיד (ובפרט את סדרת ההצעות), מטרה זו הייתה טריוויאלית: נמכור למרבה במחיר! לצערנו, העתיד לא ידוע, ובמקרה הגרוע אפילו לא ניתן להשיג קירוב כלשהו של הרווח הרב ביותר בדיעבד. למרות זאת, זו בעיה בסיסית בכלכלה, אותה היינו רוצים לפתור. כדי להתגבר על תוצאות קושי פתולוגיות, כלכלנים (מדעני מחשב, ואנשי חקר ביצועים) חוקרים בעיות כנ״ל תחת מודלים סטוכסטיים, כדוגמת:
- בעיות עם סדר אקראי:
הקלט שרירותי (ואף אדברסריאלי), אך סדר ההגעה אקראי.
- בעיות עם קלט אקראי:
הקלט נבחר מהתפלגות כלשהי (ידועה במדויק, בקירוב, או בכלל לא).
הקורס יעסוק בתיאוריה של אלגוריתמים לבעיות כמו הנ״ל, ויענה על שאלות כגון:
- איך מפתחים אלגוריתמים שמשיגים קירוב של אלגוריתם שיודע את העתיד?
- איך מפתחים אלגוריתמים כאלו שגם מהירים?
- איך מראים תוצאות אי-אפשרות לבעיות כאלו?
- מה הקשר בין שאלות אלו לתחומים אחרים, כגון תורת המשחקים האלגוריתמית?
קדמים ורקע קודם
הקורס בעל אופי תיאורטי ודורש בגרות מתמטית. מאופיו הסמינר דורש נינוחות עם אלגוריתמים והסתברות. קורסים בנושאים אלו (למשל, 234247 ו-094412) הם קדמים לקורס, וחזרה על נושאים אלו לפני הסמינר תועיל לכלל המשתתפים.
מספר ההרצאות הראשונות יינתנו על ידי המרצה, שייתן רקע על התחום ועל אופן קריאת מאמר ובניית הרצאה אפקטיביים. (ראו גם לשונית עצות באתר הבית של המרצה).
דרישות הקורס
הציון הסופי ייקבע על סמך קריאת מאמר והצגתו (ביחידים), והשתתפות בהרצאות.
הרישום ידני: יש לשלוח דוא"ל למרצה wajc@technion.ac.il עם פרטים אישיים, כולל גיליון ציונים, ומידע על ניסיון קודם בעמידה מול קהל (למשל, תרגול), אם יש.
רשימת ספרות: תפורסם בהמשך, תחת לשונית ״חומר המקצוע״.
תוצאות למידה
בסיום הקורס הסטודנטים.ות ידעו כיצד:
- לפתח ולנתח אלגוריתמים מקוונים יעילים למודלים סטוכסטיים.
- להוכיח תוצאות קושי לאלגוריתמים כאלו.
- לקרוא ולהציג מאמרים בתחום.