הסתברות למדעי המחשב 2 – אוניברסיטת אריאל
שם הקורס: הסתברות למדעי המחשב 2
שם הפקולטה: מדעי הטבע
שם המחלקה: מדעי המחשב
מספר הקורס: 7028310
מתכונת הקורס: (הרצאה + תרגולים)
שנת לימודים: ג סמסטר: א היקף שעות: 2 ש"ס נקודות זכות: 2.5
א. מטרות הקורס (מטרות על / מטרות ספציפיות):
היכרות בסיסית עם תורת ההסתברות של מרחבים שאינם בני מנייה והתפלגויות רציפות.
למידה מעמיקה יותר של הסתברות בדידה ושימושיה במדעי המחשב.
ב. תוכן הקורס:
ריכוז מידה, גרפים מקריים והשיטה ההסתברותית, אלגוריתמים הסתברותיים,
התפלגויות רציפות, משפט הגבול המרכזי ונושאים קשורים.
מהלך השיעורים:
תכנית הוראה מפורטת לכל השיעורים:
| יחידת שיעור | נושא השיעור | הערות |
|---|---|---|
| 1. | תזכורת לאי שוויוני מרקוב וצ'בישב, אי שוויוני צ'רנוף-הופדינג. | |
| 2. | החוק החלש והחוק החזק של המספרים הגדולים. | |
| 3. | מבוא לשיטה ההסתברותית, שיטת המומנט הראשון. | |
| 4. | שיטת המומנט השני. | |
| 5. | נושאים בתורת הגרפים המקריים: מודלים וכלים בסיסיים, חסם תחתון על מספרי רמזי, גרפים עם מספר צביעה גדול ומותן גדול. |
|
| 6. | נושאים בתורת הגרפים המקריים: הופעת גרף קבוע, התפלגות הדרגות, קשירות. |
|
| 7. | אלגוריתמים הסתברותיים, זיהוי פולינומים, חתך מינימלי. | |
| 8. | אלגוריתמים הסתברותיים למיון ולמציאת חציון. | |
| 9. | מרחבי הסתברות שאינם בני מנייה, פונקציית הסתברות מצטברת, פונקציית צפיפות. |
|
| 10. | התפלגויות רציפות נפוצות: אחידה, מעריכית, נורמלית ואחרות. | |
| 11. | תוחלת של התפלגויות רציפות נפוצות. | |
| 12. | שונות של התפלגויות רציפות נפוצות. | |
| 13. | משפט הגבול המרכזי. |
ג. חובות הקורס:
- דרישות קדם: הסתברות למדעי המחשב 1.
- חובות / דרישות / מטלות: במהלך הקורס יהיו 5 מטלות. אין חובת הגשה.
- מרכיבי הציון הסופי (ציון מספרי / ציון עובר): 100% בחינה.
ד. ביבליוגרפיה (חובה / רשות) – מסודרת לפי נושאי הקורס:
- Devdatt P. Dubhashi and Alessandro Panconesi, Concentration of measure for the analysis of randomized algorithms, Cambridge University Press, 2009.
- Michael Mitzenmacher and Eli Upfal, Probability and Computing: randomized algorithms and probabilistic analysis, Cambridge University Press, 2005.
- Rajeev Motwani and Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, 1995.
- Noga Alon and Joel H. Spencer, The probabilistic method (fourth edition), John Wiley and Sons, 2016.
- Sheldon Ross, A first course in probability (eighth edition), Pearson Prentice Hall, 2010.