יובל רבני

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

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

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

ספרות

•J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley, 2005.
•S. Dasgupta, C. Papadimitriou, and U. Vazirani. Algorithms. McGraw-Hill, 2008.
•S. Even. Graph Algorithms. Computer Science Press, 1979.
•T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms 2nd ed., MIT Press, 2001.