קורסים שאינם מקנים נקודות זכות
20417 אלגוריתמים
20417 אלגוריתמים1
5 נקודות זכות ברמה רגילה
שיוך: מדעים / מדעי המחשב
ידע קודם דרוש: מתמטיקה בדידה: תורת הקבוצות, קומבינטוריקה ותורת הגרפים, מבני נתונים ומבוא לאלגוריתמים או מבני נתונים, מבוא למדעי המחשב ושפת Java (או יסודות התכנות בשפת Java).
ידע קודם מומלץ: חשבון אינפיניטסימלי 1, אלגברה לינארית 1 (או אלגברה ליניארית לתלמידי מדעים). הסתברות ומבוא לסטטיסטיקה או מבוא לסטטיסטיקה ולהסתברות למדעים.
פיתוח הקורס: מרצים: פרופ' תמיר טסה, פרופ' מנור מנדל, פרופ' זאב נוטוב, ד"ר אסף נוסבוים.
במאי: גיא מאירסון. אולפן: עופר ויינר. פדגוגיה: ד"ר אורלי שטטינר. אסיסטנטים: חן אולמר, איתי פיירוורקר.
מטרות הקורס: הכרות עם אלגוריתמים מרכזיים ועם גישות מרכזיות לפיתוח אלגוריתמים (סריקת גרפים, חמדנות, תכנון דינמי, הפרד ומשול, רשתות זרימה). בסיום הקורס, הלומדים/ות יוכלו:
-
לתרגם בעיות מעשיות משפה יומיומית לשפה מתמטית.
-
להציג ולנתח מספר אלגוריתמים נודעים, תוך יכולת לבצע תיקונים והתאמות במטרה לפתור בעיה נתונה.
-
לפתח אלגוריתם חדש לבעיה נתונה, על בסיס אחת מהגישות: סריקת גרפים, חמדנות, תכנון דינמי, הפרד ומשול, רשתות זרימה.
-
להוכיח/להפריך נכונות, ולנתח זמן ריצה של אלגוריתם נתון.
מתכונת הקורס: הרצאות אולפן מוקלטות.
נושאי הלימוד:
-
מבוא: ניתוח זמני ריצה, תור קדימויות. זיווגים יציבים (Gale–Shapley).
-
גרפים: מבוא. סריקה לרוחב ולעומק (BFS, DFS): רכיבי קשירות חזקה, מיון טופולוגי, דו-צדדיות.
-
חמדנות: מסלולים מזעריים (Dijkstra, Bellman-Ford), עץ פורש מזערי (Jarnik-Prim, Kruskal). דחיסת מחרוזות (Huffman).
-
הפרד ומשול: נוסחאות נסיגה, יישומים אלגבריים: כפל מספרים (Karatsuba), התמרת פורייה וכפל פולינומים (FFT). יישומים נוספים: יישור מחרוזות, נקודות קרובות ביותר במישור.
-
תכנון דינמי: מסלולים מזעריים (Bellman–Ford, Floyd–Warshall), בעיית תרמיל-הגב, מרחק עריכה ויישור מחרוזות, סדר הכפלה של שרשרת מטריצות.
-
רשתות זרימה: אלגוריתמים (Ford–Fulkerson, Edmonds-Karp, Scaling), חתכים מזעריים (MaxFlow = MinCut), פירוק זרימה למסלולים, משפטי Hall, Menger, Kőnig.
1 עד סמסטר ג2021 (כולל) הקנה קורס זה 4 נקודות זכות.
2 בעבר נקרא הקורס אלגברה ליניארית לתלמידי מדעי הטבע.
3 למי שלמדו את הקורס מבני נתונים ולא למדו את הקורס מבני נתונים ומבוא לאלגוריתמים מומלץ להתייעץ עם מרכז/ת הקורס אלגוריתמים לפני ההרשמה אליו.