קורסים שאינם מקנים נקודות זכות
22902 אלגוריתמים אקראיים
22902 אלגוריתמים אקראיים
4 נקודות זכות
שיוך: תואר שני / מדעי המחשב
שיוך נוסף: מדעים / מדעי המחשב
תנאי קבלה: קבלה לתואר שני במדעי המחשב.1 ידע קודם דרוש: הקורס חישוביות ומבוא לסיבוכיות (או קורס אחר בסיבוכיות).
פיתוח הקורס: פרופ' מיכאל לנגברג, פרופ' ספי נאור
הקורס דן באלגוריתמים המבצעים בחירות אקראיות במהלך ריצתם.
הקורס מקנה כלים הסתברותיים חיוניים בעולם האלגוריתמים, והקומבינטוריקה:
(א) ניתוח מאורעות, הערכות זנב (מרקוב ,צ'בישב, צ'רנוף), הוכחות קיום הסתברותיות.
(ב) דה-רנדומיזציה (תוחלות מותנות, k-wise-independence).
(ג) שרשראות מרקוב.
הקורס מציג יישומים נודעים לחשיבה הסתברותית במגוון ענפים: גרפים אקראיים, מבני נתונים, קרוב בעיות NP-קשות, סיבוכיות תקשורת, הוכחות אינטראקטיביות.
חומר הלימוד
-
הספר:
M. Mitzenmacher & E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Cambridge University Press, 2005)
-
מדריך למידה
1 סטודנט שאינו עומד בתנאי הקבלה יכול, במקרים מסוימים, להירשם לקורס. לפרטים נוספים עיינו בסעיף קבלה לקורסים בודדים בתכנית הלימודים לתואר שני במדעי המחשב.