האוניברסיטה הפתוחה

תיאורי הקורסים

20417 אלגוריתמים

20417 אלגוריתמים‏

4 נקודות זכות ברמה רגילה

שיוך: מדעים / מדעי המחשב

ידע קודם דרוש: הקורסים אלגברה לינארית 1 (‏או אלגברה ליניארית לתלמידי מדעי הטבע‎)‏, מבני נתונים ומבוא לאלגוריתמים.1

פיתוח הקורס: פרופ' זאב נוטוב, פרופ' מנור מנדל; תמר אלמוג (‏תרגום‎)‏, אילנה גולן (‏עריכה‎)‏

מטרות הקורס

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

  • יישום שיטות אלו בבעיות אלגוריתמיות.

  • העמקת הלימוד של שיטות ניתוח אלגוריתמים.

ספר הקורס

הקורס מבוסס על הספר פיתוח אלגוריתמים, שהינו תרגום לעברית של פרקים 7-1 של הספר:

J. Kleinberg & E. Tardos, Algorithm Design (‏Addison Wesley, 2006‎)‏

נושאי הלימוד

  • חזרה: ניתוח זמן ריצה, תור קדימויות.

  • אלגוריתמים בגרפים: סריקה לרוחב ולעומק בגרפים מכוונים ולא מכוונים; יישומים – דו-קשירות ומיון טופולוגי, אלגוריתם גייל-שאפלי לזיווג יציב.

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

  • הפרד ומשול: ספירת היפוכים, מציאת זוג נקודות קרובות ביותר במישור, כפל מספרים, קונוולוציה והתמרת פורייה.

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

  • זרימה ברשתות: אלגוריתם פורד-פולקרסון, חתכים מינימליים, אלגוריתמי זרימה יעילים (‏דיניץ, אדמונדס-קרפ, דחיפת קדם זרימה‎)‏, פירוק זרימה למסלולים, הרחבות של בעיות זרימה, יישומים.


1 למי שלמדו את הקורס מבני נתונים ולא למדו את הקורס מבני נתונים ומבוא לאלגוריתמים מומלץ להתייעץ עם מרכז/ת הקורס אלגוריתמים לפני ההרשמה אליו.