אלגוריתמים

מרצה: פרופ' מיכה שריר
מתרגל: דני פלדמן
אתר הקורס: http://www.cs.tau.ac.il/~dannyf/alg09/Algorithms09.htm
אתר המתרגל (מכיל עוד חומר "בלתי רשמי" של הקורס): http://www.cs.tau.ac.il/~dannyf
תשס"ט סמסטר א'

קצת על הקורס

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

תרגילים

התרגילים יהוו 10% מהציון בקורס. תרגילים ניתנים באתר הקורס. כל תרגיל ניתן לתקופה של שבועיים.

אז מה היה לנו בשיעורים?

שיעור 1 - 4/11/08

1. עניינים אדמינסטרטיביים
2. הגדרות בתורת הגרפים
3. אלגוריתם BFS
4. התחלנו: הוכחת נכונות של אלגוריתם BFS

סיכום שיעור: קובץ PDF.

שיעור 2 - 11/11/08

1. סיום הוכחת הנכונות של BFS
2. שימושים עבור BFS
3. אלגוריתם DFS
4. תכונות חשובות של DFS: עקרון הקינון, סיווג קשתות הגרף

סיכום השיעור: קובץ PDF.

שיעור 3 - 18/11/08

1. עקרון המסלול הלבן
2. שימושים ל-DFS

סיכום השיעור: אין. מומלץ להשתמש בסיכום מולטינט שהעלה עידן דויטש.

שיעור 4 - 25/11/08

1. עצים פורשים מינימליים - הגדרה ומהות
2. כמה מילים על אלגוריתמים חמדניים
3. אלגוריתם KRUSKAL
4. אלגוריתם PRIM (רק התחלנו)

סיכום השיעור: קובץ PDF.

שיעור 5 - 2/12/08

1. אלגוריתם PRIM
2. מסלולים קצרים ביותר (ממקור יחיד)
3. תכונות מק"בים: תת-מסלול של מק"ב הוא מק"ב, אי-שיווין המשולש, מתי מתקיים שוויון, קשר ל-BFS
3. מטא-אלגוריתם למציאת מק"בים

סיכום השיעור: קובץ PDF.

שיעור 6 - 9/12/08

1. כמה אבחנות על המטא-אלגוריתם
2. אלגוריתם למציאת מק"בים ב-DAG
3. האלגוריתם של פורד
4. האלגוריתם של בלמן-פורד

סיכום השיעור: קובץ PDF.

שיעור 7 - 16/12/08

1. האלגוריתם של דייקסטרה
2. מק"בים בין כל זוגות הצמתים
3. גרסה מטריציאלית של אלגוריתם בלמן-פורד
4. שיפור סדר "הכפלת" המטריצות

סיכום השיעור: קובץ PDF.

שיעור 8 - 23/12/08

1. אלגוריתם פלויד-וורשל
2. אלגוריתם ג'ונסון
3. זרימה ברשתות: הגדרות
4. שיטת פורד-פלקרסון

סיכום השיעור: קובץ PDF.

שיעור 9 - 30/12/08

1. תזכורת: זרימה ברשתות
2. למה שיטת פורד-פלקרסון לא מספיקה?
3. משפט Max Flow - Min Cut

סיכום השיעור: קובץ PDF.

שיעור 10 - 6/1/09

1. אלגוריתם דיניץ
2. רשתות 0/1
3. זיווג מקסימלי
4. משפט הול - בזריזות

סיכום השיעור: קובץ PDF.

שיעור 11 - 13/1/09

1. משפט הול - חזרה בניחותא
2. תכנות דינאמי (דוגמאות: מספרי פיבונאצ'י, כפל מטריצות יעיל, תת-סדרה משותפת מקסימלית, סכום תת-קבוצה)

סיכום השיעור: קובץ PDF.

שיעור 12 - 20/1/09

1. דוגמה נוספת לתכנות דינאמי: טריאנגולציה עם משקל מינימלי
2. התאמת מחרוזות

סיכום השיעור: קובץ PDF (שימו לב: השעה האחרונה טרם הועלתה).

שיעור 13 - 27/1/09

1. חזרה: התאמת מחרוזות באמצעות סימולציה של אוטומט
2. אלגוריתם KMP
3. הערות לגבי במבחן

סיכום השיעור: קובץ PDF.