20395 סיבוכיות אלגוריתמים
20395 סיבוכיות אלגוריתמים
4 נקודות זכות ברמה מתקדמת
שיוך: מדעים / מדעי המחשב
תנאי קבלה: עמידה בדרישות האנגלית ובדרישות ההדרכה הביבליוגרפית בספרייה. ידע קודם דרוש: הקורסים חשבון אינפיניטסימלי 1, אלגברה לינארית 1, מתמטיקה דיסקרטית,1 מבני נתונים ומבוא לאלגוריתמים (או מבני נתונים). ידע קודם מומלץ: הקורס אלגוריתמים.
פיתוח הקורס: פרופ' אברהם גינזבורג, ד"ר יהודית בר אילן; יהודית גוגנהיימר (עריכה)
הקורס דן באלגוריתמים לפתרון בעיות שונות ובניתוח סיבוכיותם. כאשר מוצג אלגוריתם לפתרון בעיה מסוימת, אחת השאלות החשובות ביותר היא מהו זמן הריצה של האלגוריתם. הקורס דן במושג זמן הריצה ועוסק בפיתוח כלים מתמטיים לניתוחו. כלים אלה מיושמים בניתוח אלגוריתמים אחדים.
ספר הקורס
H. S. Wilf, Algorithms and Complexity (Prentice Hall, 1986).
הסטודנטים ילמדו את כל ספר הקורס באנגלית, חוץ מפרק 3, בעזרת מדריך למידה מפורט בעברית. המדריך מלווה את פרקי הספר באופן צמוד ומכיל גם פתרונות לשאלות שבספר וחומר נוסף.
נושאי הקורס (בהתאמה לפרקי הספר)
|
פרק 1 |
הקדמה מתמטית |
|
פרק 2 |
אלגוריתמים רקורסיביים |
|
פרק 4 |
אלגוריתמים בתורת המספרים |
|
פרק 5 |
שלמות ב-NP (NP – Completeness) |
1