20273 אלגוריתמים בתורת הגרפים
20273 אלגוריתמים בתורת הגרפים1
3 נקודות זכות ברמה רגילה
שיוך: מדעים / מדעי המחשב
ידע קודם דרוש: הקורס מבוא למדעי המחשב.2 ידע קודם מומלץ: הקורסים מתמטיקה דיסקרטית3 (או נושאים במתמטיקה לתלמידי מדעי החברה), הסתברות לתלמידי מדעי המחשב (או מבוא לסטטיסטיקה ולהסתברות לתלמידי מדעים), מבני נתונים ומבוא לאלגוריתמים (או מבני-נתונים).
פיתוח הקורס: פרופ' שמעון אבן (מרצה), תמר וילנר, אלה מטלון
צוות הפקת סרטי ההרצאות: אבי כהן, אלי מדינה, רני גולדמן
מטרת הקורס
הכרת העקרונות והשיטות הבסיסיים לפיתוח אלגוריתמים בתורת הגרפים. יינתנו קריטריונים להערכת היעילות של אלגוריתמים ולבחירת הגישה האלגוריתמית המתאימה לבעיה נתונה.
נושאי הקורס
בין הנושאים הנלמדים: גרפים, מסלולים בגרפים, מעגלי אוילר, בעיית המסלול הקצר ביותר, עץ פורש מינימלי, חיפוש לעומק (DFS), חיפוש לרוחב (BFS), זרימה ברשתות, זיווגים.
הקורס מבוסס על הרצאות פרונטליות של פרופ' שמעון אבן שהוקלטו באוניברסיטה הפתוחה. את ההרצאות ביסס פרופ' אבן על ספרו:
S. Even, Graph Algorithms (Computer Science Press, 1979).
הסטודנטים יקבלו את הקלטות בהשאלה.
1להשלכות על צבירת נ"ז בשל חפיפה עם קורס(ים) אחר(ים), ראו טבלת קורסים חופפים.
2 או אחד מהקורסים מבוא למדעי המחשב ושפת פסקל (20110), מבוא למדעי המחשב ושפת Java (20441).