יובל רבני

 

234247 אלגוריתמים 1


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


זהו קורס חובה בכל מסלולי הלימוד במדעי המחשב.



ספרות


  1. J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005.

  2. S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill, 2008.

  3. S. Even. Graph Algorithms. Computer Science Press, 1979.

  4. T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms 2nd ed., MIT Press, 2001.


דרישות קדם

234141 קומבינטוריקה למדעי המחשב

234218 מבני נתונים 1


הרצאות

מבוא: חישוב, אלגוריתמים, מודל RAM

אלגוריתמים חמדנים: בעיות ניהול משאבים, קידוד Huffman, עץ פורש מינימום, מטרואידים

סריקה לרוחב

תכנות דינמי: סכום חלקי, מרחק עריכה

מסלולים קלים ביותר: האלגוריתמים של Dijkstra, Bellman-Ford, Floyd-Warshall.

סריקה לעומק: רכיבים קשירים היטב, רכיבים אי-פריקים

הפרד ומשול: קונוולוציות והתמרת Fourier הדיסקרטית, מרחק עריכה

זרימה ברשתות: תכונות, שיטת Ford-Fulkerson, סילום, האלגוריתמים של Edmonds-Karp ו-Dinitz

שימושי זרימה: שידוך מקסימום בגרף דו-צדדי, עיבוד תמונה

בעיית הנישואים היציבים