קורסים שאינם מקנים נקודות זכות
20417 אלגוריתמים
20417 אלגוריתמים1
5 נקודות זכות ברמה רגילה
שיוך: מדעים / מדעי המחשב
ידע קודם דרוש: מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים.
מבני נתונים ומבוא לאלגוריתמים או מבני נתונים (20433). מבוא למדעי המחשב ושפת Java (או יסודות התכנות בשפת Java).
ידע קודם מומלץ:
אלגברה לינארית 1 (או אלגברה ליניארית לתלמידי מדעים ).
הסתברות ומבוא לסטטיסטיקה או מבוא לסטטיסטיקה ולהסתברות למדעים
פיתוח הקורס: פרופ' זאב נוטוב, פרופ' מנור מנדל; תמר אלמוג (תרגום), אילנה גולן (עריכה)
מטרות הקורס
-
הכרת השיטות והעקרונות הבסיסיים בפיתוח אלגוריתמים: סריקת גרפים, השיטה החמדנית, תכנון דינמי, הפרד-ומשול, זרימות וחתכים.
-
יישום שיטות אלו בבעיות אלגוריתמיות.
-
העמקת הלימוד של שיטות ניתוח אלגוריתמים.
ספר הקורס
הקורס מבוסס על הספר פיתוח אלגוריתמים, שהינו תרגום לעברית של פרקים 7-1 של הספר:
J. Kleinberg & E. Tardos, Algorithm Design (Addison Wesley, 2006)
נושאי הלימוד
-
חזרה: ניתוח זמן ריצה, תור קדימויות.
-
אלגוריתמים בגרפים: סריקה לרוחב ולעומק בגרפים מכוונים ולא מכוונים; יישומים – דו-קשירות ומיון טופולוגי, אלגוריתם גייל-שאפלי לזיווג יציב.
-
אלגוריתמים חמדניים: בעיות תזמון, מסלולים קצרים ביותר, עץ פורש מינימלי בגרפים מכוונים ולא מכוונים, הצברה, קודי הופמן.
-
הפרד ומשול: ספירת היפוכים, מציאת זוג נקודות קרובות ביותר במישור, כפל מספרים, קונוולוציה והתמרת פורייה.
-
תכנון דינמי: תזמון מקטעים, בעיית תרמיל הגב, יישור סדרות, מסלולים קצרים ביותר בגרפים ממושקלים ממקור יחיד ובין כל הזוגות.
-
זרימה ברשתות: אלגוריתם פורד-פולקרסון, חתכים מינימליים, אלגוריתמי זרימה יעילים (דיניץ, אדמונדס-קרפ, דחיפת קדם זרימה), פירוק זרימה למסלולים, הרחבות של בעיות זרימה, יישומים.
1 עד סמסטר ג2021 (כולל) הקנה קורס זה 4 נקודות זכות.
2 בעבר נקרא הקורס אלגברה ליניארית לתלמידי מדעי הטבע.
3 למי שלמדו את הקורס מבני נתונים ולא למדו את הקורס מבני נתונים ומבוא לאלגוריתמים מומלץ להתייעץ עם מרכז/ת הקורס אלגוריתמים לפני ההרשמה אליו.