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