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

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

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

נוסח השאלה

עבור k≥3k\ge3 נגדיר את בעיית האופטימיזציה הבאה, kMaxCutkMaxCut.

קלט: גרף לא מכוון G=(V,E)G=(V,E).

מטרה: למצוא פירוק של VV ל-kk קבוצות זרות V1,…,VkV_1,\ldots,V_k כך שמספר הקשתות שכל אחד מהקצוות שלהן בקבוצה אחרת מקסימלי.

נסמן ב-mm את מספר הקשתות בגרף. מהו הערך הגדול ביותר של ℓ\ell עבורו ידוע כי קיים פירוק של VV ל-kk קבוצות זרות V1,…,VkV_1,\ldots,V_k כך שמספר הקשתות שכל אחד מהקצוות שלהן בקבוצה אחרת הוא לפחות ℓ\ell?

  1. א

    ℓ=kmk+1\ell=\frac{km}{k+1}

  2. ב

    ℓ=3m4\ell=\frac{3m}{4}

  3. ג

    ℓ=m2k\ell=\frac{m}{2^k}

  4. ד

    ℓ=(2k−1)m2k\ell=\frac{(2^k-1)m}{2^k}

  5. ה

    ℓ=(k−1)mk\ell=\frac{(k-1)m}{k}

  6. ו

    ℓ=m2\ell=\frac{m}{2}

נוסח מטלה שנבדק אנושית.

ייחוס מדויק

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

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

בחינה

2026 ב׳ · מועד א׳

מ-2026 סמסטר ב מועד א (טופס נבחן)

שאלה 7עמוד 1נבדק אנושית

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

תרגול המשך

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

מטלהקלט: קבוצה U, אוסף \F 1, ,F m\ של m תתי-קבוצות של U, שכל אחת מהן בגודל 3, ומספר טבעי k. שאלה: האם קיימת קבוצה S U, בגודל |S|=k, המקיימתדומה בנושא — לא כפילותמטלהנקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר 1. 1. הוכיחו כי בעיית ההכרעה הבאה היא NP-שלמה: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה:…דומה בנושא — לא כפילותמטלהנתאר את בעיית האופטימיזציה הבאה: קלט: גרף פשוט מכוון G=(V,E). פלט: קבוצת קשתות E' E גדולה ככל האפשר, כך שהגרף G'=(V,E') חסר מעגלים. 1. נתבונן בקבוצות…דומה בנושא — לא כפילותמטלהיהא קלט עבור בעיית העץ של שטיינר הכללית, ללא הדרישה שהקלט מקיים את אי-שוויון המשולש: גרף שלם G=(V,E), חלוקה V=R S ופונקציית משקל w:E R + על הקשתות. נג…דומה בנושא — לא כפילותמטלה1. נגדיר אלגוריתם לבעיית BinPacking כלהלן: בהינתן קלט a 1, ,a n, האלגוריתם עובר על כל מספר ברשימה לפי הסדר הנתון; במידת האפשר הוא מכניס אותו לתא האחרו…דומה בנושא — לא כפילותמטלה1. יהי G=(V,E) גרף מכוון, כאשר V=\1,2, ,n\. נסמןדומה בנושא — לא כפילות