חזרה

סילבוס

מספר קורס 0368-4623-01
שם הקורס התקדמות בניתוח של פונקציות בוליאניות
יחידה אקדמית הפקולטה למדעים מדויקים ע"ש ריימונד ובברלי סאקלר -
מדעי המחשב
מרצה פרופ' שמואל ספראצרו קשר
צור קשר דוא"ל: safra@tauex.tau.ac.il
שעות קבלהשני 17:00 - 16:00
בניין: צ'ק פוינט , חדר: 454
אופן ההוראה שיעור
שעות סמסטריאליות 3
סמסטר ב' תשפ"ב
יום א
שעות 13:00-16:00
בניין אודי.הולצבלט
חדר 007
בבניין פיזיקה שנקר
אין סילבוס

תוכן הקורס ומטרתו

פונקציות בוליאניות


1. מבוא לאנליזת פורייה דיסקרטית
נפתח את הקורס בהצגת הגדרות ורעיונות בסיסיים, כגון התמרת פורייה וinfluence של משתנים. במהלך הקורס נציג כלים בסיסיים ותוצאות בתחום, כמו אי-השוויון ההיפר-קונטרקטיבי, משפט KKL, משפטי החונטה של פרידגוט ובורגיין, sharp thresholds ועקרונן הinvariance.

2. אפליקציות של אנליזת פורייה בתחומים שונים בתיאורייה של מדעי המחשב
נדון בכמה יישומים של אנליזת פורייה בתחומים כמו property testing ולמידה חישובית.

3. אפליקציות של אנליזת פורייה בקושי קירוב
נדון בקצרה בהשערת Unique-Games, השערה מרכזית במדעי המחשב התיאורטיים. נשתמש בתוצאות בסיסיות מאנליזת פורייה כדי להראות כמה מסקנות מהשערה זו, כגון האופטימליות (המותנית) של אלגוריתם Goemans-Williamson עבור בעיית Max-Cut, וקושי (מותנה) של בעיית Vertex-Cover.

4. יישומי ניתוח פורייה קומבינטוריקה אקסטרימאלית.
קומבינטוריקה קיצונית היא התחום השואל, בהכללה, כמה גדול יכול להיות אוסף כלשהו של אובייקטים ספציפיים, תחת תנאים מסוימים. לדוגמא, כמה גדול יכול אוסף של תתי-קבוצות של [n] להיות תחת ההנחה שלכל זוג באוסף יש חיתוך לא טריוויאלי? נראה איך תוצאות מאנליזה ממלאות תפקיד חשוב במתן תשובות מפורטות לחלק משאלות אלו.

5. נושאים מתקדמים.
לקראת סוף הקורס נדון בנושאים מתקדמים יותר ובתוצאות בתחום שהושגו רק לאחרונה. אלה כוללים את הפתרון של השערת הsensitivity, הרחבה של אי-השוויון ההיפר-קונטרקטיבי המכונה בספרות "היפר-קונטרקטיביות גלובלית", והשערת הFourier entropy.



לסילבוס המפורט
מטלות הקורס

עבודת בית

ייתכנו מטלות נוספות
רשימת המטלות המלאה תופיע בסילבוס המפורט של הקורס.



tau logohourglass00:00