מפת הסיבוכיות
EN
שאלה מבוססת מקור

נגדיר את בעיית האופטימיזציה הבאה, WMAXCUT. קלט: גרף G=(V,E), ופונקציית משקל W המתאימה לכל קשת ב G משקל אי שליל…

1בחינות0מטלות0שיעורים1מסמכי מקור
שאלת רב־ברירהq-bf3c5832c99f

נוסח השאלה

נגדיר את בעיית האופטימיזציה הבאה, WMAXCUT. קלט: גרף G=(V,E), ופונקציית משקל W המתאימה לכל קשת ב G משקל אי שלילי. מטרה: למצוא חתך מושרה בגרף שמשקלו מקסימלי. יהי G,w קלט לבעיית WMAXCUT. נסמן ב W את סך משקלי הקשתות ב G. מהו הערך הגדול ביותר של αα עבור ידוע כי קיים חתך מושרה ב G כך שמשקלו הוא לפחות αWαW ?

  1. אα=1/2.
  2. בα=7/8.
  3. גα=9/10.
  4. דהערך המבוקש תלוי גם במספר הקשתות, לכן לא ניתן לענות על השאלה.
  5. ההערך המבוקש יכול להיות קרוב כרצוננו ל 1.
  6. וα=1/3.

תמלול ראשון מתוך עמוד המקור ב־tools/summary/.work. צילום העמוד מצורף למטה כדי שאפשר יהיה לאמת סימון מתמטי וניסוח.

ייחוס מדויק

מופעים לפי מסמך מקור

כל כרטיס הוא קובץ שונה באמת. גרסאות או שאלונים כפולים באותו PDF מוצגים בתוך אותו כרטיס ואינם מגדילים את מספר המועדים.

בחינה

2023 ב׳ · מועד ב׳

נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf

שאלה 3עמוד 2קריאה חזותית

עותקים זהים של אותו מסמך: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 2.pdf

הצגת צילום המקור — עמוד 2עמוד מקור 2 מתוך נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf פתיחה בגודל מלא
תרגול המשך

אלו התאמות לפי נושא ושיעור — לא מופעים זהים של אותה שאלה.

מטלהנתאר את בעיית האופטימיזציה הבאה: קלט: גרף פשוט מכוון G=(V,E). פלט: קבוצת קשתות E' E גדולה ככל האפשר, כך שהגרף G'=(V,E') חסר מעגלים. 1. נתבונן בקבוצות…דומה בנושא — לא כפילותמטלהיהא קלט עבור בעיית העץ של שטיינר הכללית, ללא הדרישה שהקלט מקיים את אי-שוויון המשולש: גרף שלם G=(V,E), חלוקה V=R S ופונקציית משקל w:E R + על הקשתות. נג…דומה בנושא — לא כפילותמטלה1. יהי G=(V,E) גרף מכוון, כאשר V=\1,2, ,n\. נסמןדומה בנושא — לא כפילותמטלהנגדיר אלגוריתם קירוב בשם Next-Fit לבעיית האופטימיזציה של Bin-Packing: קלט: a 1, ,a n , כאשר a 1, ,a n (0,1] ו-n N. לכל i=1, ,n: 1. אם a i יכול להיכנס…דומה בנושא — לא כפילותמטלהבשיעורים הגדרנו חתך בגרף לא מכוון. באופן דומה, נגדיר חתך בגרף מכוון כחלוקה של קודקודי הגרף לשתי קבוצות זרות (S, S). במקרה של גרף מכוון, קבוצת החתך מוג…דומה בנושא — לא כפילותמטלהעבור U V בגרף מכוון G=(V,E), החתך המושרה על ידי U, המסומן (U), הוא קבוצת הקשתות היוצאות מ-U: זנבן ב-U וראשן ב- U. בגרף מכוון (U) ו- ( U) אינם בהכרח שו…דומה בנושא — לא כפילות

וריאציות קרובות — לא כפילויות