התמודדות עם בעיות NP-קשות לימודי הנדסת תוכנה לתואר ראשון .B.Sc

התמודדות עם בעיות NP-קשות




Coping with NP-hardness
קוד הקורס: 12016
3 נ"ז

מטרות הקורס
הכרת בעיות NP-קשות לעומק, למידת דרכים שונות לפתירתן למרות הקושי התיאורטי.

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

כל הטכניקות ילמדו כשיטה כללית, ועם אפליקציה לבעיות מוכרות.

דרישות הקדם והדרישות המקבילות הינן:
דרישות קדם: חישוביות וסיבוכיות (10076), אלגוריתמיקה 1 (10007), הסתברות וסטטיסטיקה 2 (10016).
דרישות מקבילות: אין

לחצו למעבר אל תכנית לימודי הנדסת תוכנה לתואר שני

לייעוץ אקדמי אישי מלאו פרטיכם

צור איתנו קשר »

אני מאשר/ת קבלת מידע פרסומי מהמכללה

מוזמנים להתייעץ איתנו