אתר המרצה ד"ר חוטובלי ראובן

קורסים

  • תכנון וניתוח אלגורי (10120)
  • תקציר הקורס:

    תקציר:

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

    מחצית השניה של הקורס מוקדשת לתורת הגרפים, תוך הצגת גרפים כמודל אוניברסלי לייצוג בעיות ולפתרונן באמצעות כלים אלגוריתמיים. במסגרת זו יילמדו ייצוגים של גרפים, סגור טרנזיטיבי, מסלולי אוילר והמילטון, סריקות BFS ו־DFS, רכיבים קשירים היטב, גרף על ומיון טופולוגי. בהמשך יידונו אלגוריתמים למציאת מסלולים קצרים ביותר, ובהם מסלולים קצרים בגרף DAG, אלגוריתם דייקסטרה, אלגוריתם בלמן-פורד ואלגוריתם פלויד-וורשל. לבסוף, הקורס יעסוק בעצים פורשים מינימליים ובאלגוריתמים הקלאסיים של קרוסקל ופרים.

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