אלגוריתמים הסתברותיים לימודי הנדסת תוכנה לתואר ראשון .B.Sc

אלגוריתמים הסתברותיים




Probabilistic Algorithms
קוד הקורס: 12019
3 נ"ז

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

נושאי הקורס
חזרה מהירה על הסתברות. ניתוח תוחלת ושונות לסכומים של משתנים אקראיים מרחק מתוחלת על ידי אי שוויוני מרקוב, צ'בישב וחסמי צ'רנוף.
מיון מהיר בחירת פיבוט אקראית גורמת לזמן ממוצע של O(nlogn).
שימוש בחסמים אלו לבניית אלגוריתם הסתברותי ל-max3sat.
הילוכים מקריים ושימושם לפתרון 2sat ו-3sat.
וריפיקציה של הכפלת מטריצה בוקטור תוך שימוש בפולינומים עם n משתנים מעל שדה סופי.
בנית מרחבי מדגם שהינםk-wise independent . בניות כלליות בעזרת פולינומים ובניות מיוחדות למקרה של בלתי תלויים בזוגות. שימוש במרחבי המדגם כדי לבצע דה-רנדומיזציה לאלגוריתמים הסתברותיים. שימוש במרחבי המדגם לבעיית ה-hashing וכיצד ליצור פונקציות hash טובות.
מציאת שורשים ב- עבור ראשוני, שימוש באלגוריתם זה להחלטה האם מספר n הוא ראשוני.
אלגוריתם הסתברותי למציאת זוג נקודות קרובות ביותר.
ניתוב הודעות על גבי קובייה ממימד n, פער אקספוננציאלי בין אלגוריתם הסתברותי לאלגוריתם דטרמינסטי.

.

דרישות הקדם והדרישות המקבילות הינן:
דרישות קדם: אלגוריתמיקה 2 (10008), הסתברות וסטטיסטיקה 1 (10015).
דרישות מקבילות: אין

לחצו למעבר אל תכנית לימודי הנדסת תוכנה לתואר שני

לייעוץ אקדמי אישי מלאו פרטיכם

צור איתנו קשר »

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

מוזמנים להתייעץ איתנו