אתר המרצה ד"ר ארטישצ'ב מריה

קורסים

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

    תקציר:

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

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

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

    תקציר:

    הקורס עוסק בנושאים מתקדמים בתכנון וניתוח אלגוריתמים. במהלך הקורס נלמד אלגוריתמים לזרימה ברשתות ושידוכים, התאמת מחרוזות באמצעות KMP, אלגוריתמים מקוונים ואלגוריתמי קירוב. בנוסף יילמדו נושאים מרכזיים בתורת הסיבוכיות, ובהם המחלקות P, NP, coNP ו-PSPACE, רדוקציות פולינומיות, משפט Cook ובעיות NP-שלמות.