סדרות דה ברויין ומשחקים קומבינטוריים

סדרת דה ברויין מסדר $n$ מעל אלפבית $[k]$ היא סדרה באורך $k^n$ אשר מכילה כל מחרוזת באורך $n$ מהאלפבית כתת-מילה בדיוק פעם אחת.

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

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

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