אשנב למתמטיקה Ical Atom רשימת תפוצה

נקודת המוצא שלנו היא בעיית אוסף הקופונים (THE COUPON COLLECTOR‘S PROBLEM, CCP). הבעיה הוזכרה כבר לפני למעלה מ-300 שנה ע״י DE MOIVRE. ניסוח הבעיה הוא כדלקמן: כמה שליפות של קופונים נדרשות בממוצע על מנת להשלים אוסף של $n$ סוגי קופונים, אם בכל שלב נשלף קופון בודד באופן אקראי ובהתפלגות אחידה, כאשר כל השליפות בלתי תלויות.

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

• נתחיל בתיאור מודל רציף לבעיית אוסף הקופונים וכן תוצאה הקשורה למודל זה. השתמשנו במודל הרציף כמה פעמים בעבודתנו.

• טבעי להריץ כמה סימולציות של תהליך ה-CCP כדי לנחש ו/או לאמת את ההתנהגות של משתנים מסויימים. לדוגמה: נסמן ב-$T_{n,m}$ את הזמן עד שהאספן יצליח לאסוף $m$ עותקים מכל אחד מ-$n$ הקופונים ונתבונן בהתפלגות והתוחלת האסימפטוטית שלו כאשר $n$ שואף לאינסוף, ו-$m$ שואף לאינסוף כפונקציה מסויימת של $n$. (בעיה זו נפתרה על ידי ארדש ורניי (1961) עבור $m$ קבוע ונשארה פתוחה עבור $m$ שואף לאינסוף.)

  במהלך המחקר, נתקלנו בקשיים בביצוע סימולציות עבור $T_{n,m}$ ככל ש־n גדל. הבעיה בסימולציה המבוצעת על ידי האלגוריתם הנאיבי והפשוט: כיוון שבכל שלב אנו שולפים קופון בודד, כל ריצה לוקחת זמן של $\Omega(n \log n)$ בהסתברות גבוהה. יתרה מכך, כדי לשמור את הנתונים לגבי מספר הפעמים שראינו כל קופון, אנו זקוקים לשמור $\Theta(n)$ מקום בזיכרון. נוסף על כך, כיוון שידוע כי התכנסות המשתנים ב-CCP היא איטית מאוד, נדרש מספר רב של איטרציות כדי לקבל אומדנים אמינים. לפיכך, עבור $n$-ים גדולים, האלגוריתם הנאיבי הופך לבלתי ישים.

  נציג שני רעיונות הסתברותיים אשר מקצרים באופן משמעותי את זמן הריצה של הסימולציה. בנוסף, נדון בכמה שאלות מעניינות הקשורות לאלגוריתמים שלנו.

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

הרעיון של ”כיוונים שונים ללכת בהם לאינסוף“ במרחבים שונים, גרפים או חבורות נחקר בדרכים רבות. הדבר הוליד מושגים שונים של ”שפה באינסוף“ שניתן להגדיר בכל ההקשרים הללו.

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

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

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

משוואה דיופאנטית היא משוואה פולינומיאלית עבורה אנחנו מחפשים רק את הפתרונות הרציונליים או השלמים. השאלה של פתרונות רציונליים היא משמעותית יותר עדינה מהשאלה של פתרונות ממשיים או מרוכבים: יכול להיות מספר אין-סופי של פתרונות ממשיים בלי שום פתרון רציונלי. אם יש פתרונות רציונליים, אפשר להוכיח זאת פשוט על-ידי כתיבת פתרון. לעומת זאת, כיצד מוכיחים שלמשוואה מסויימת אין פתרון רציונלי? הדרך הכי פשוטה לעשות זאת היא להראות שאין פתרונות ב-$Z/nZ$, או שאין פתרונות ממשיים, ולזה קוראים העקרון הלוקאלי-גלובלי. השיטה הראשונה תוביל אותנו למושג של מספרים $p$-אדיים: השלמה של המספרים הרציונליים כמו המספרים הממשיים, אבל ביחס למטריקה אחרת. אם יישאר זמן, נדבר על מה שאפשר לעשות אם השיטות הללו לא עובדות.

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

בשנות ה-60 של המאה הקודמת, בארי מזור זיהה קשר מעניין ועמוק בין קשרים ומספרים ראשוניים

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