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