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

אנו מעוניינים להוכיח את הטענה הבאה: טענה: אם קיים קרוב 2000 לבעיית הסוכן הנוסע (TSP) ללא אי שוויון המשולש אז P…

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

נוסח השאלה

אנו מעוניינים להוכיח את הטענה הבאה: טענה: אם קיים קרוב 2000 לבעיית הסוכן הנוסע (TSP) ללא אי שוויון המשולש אז P = NP. ההוכחה תהיה דומה להוכחה שראינו בכיתה (עבור קרוב 2024) אך כשנבנה את הגרף השלם מגרף הקלט ניתן לכל קשת בגרף השלם שלא קיימת בגרף הקלט משקל αα במקום המשקל שנתנו בכיתה (כאשר αα עשוי להיות תלוי במספר קדקודי גרף הקלט שנסמנו ב- N). מבין הערכים הבאים, מה ערך αα המינימלי שיאפשר להוכיח את הטענה?

  1. אα = 1999N + 2.
  2. בα = 1999N.
  3. גα = 1999N + 1.
  4. דα = 2000N.
  5. הα = 2000N + 1.
  6. וα = 2000N + 2.

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

ייחוס מדויק

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

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

בחינה

2024 א׳ · מועד א׳

נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf

שאלה 1עמוד 3קריאה חזותית
הצגת צילום המקור — עמוד 3עמוד מקור 3 מתוך נושא 131111 קבוצה 13111101 שנה 2024 סמסטר 1 מועד 1.pdf פתיחה בגודל מלא
תרגול המשך

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

מטלההיפרגרף 3-אחיד הוא זוג H=(V,E), כאשר V קבוצת קודקודים ו-E אוסף תת־קבוצות של V, כל אחת בגודל 3. כל קבוצה כזו היא היפר־קשת. כיסוי קודקודים של H הוא S V…דומה בנושא — לא כפילותמטלהנסמן ב-TSP-TI את תת־הקבוצה של TSP, גרסת ההכרעה של בעיית הסוכן הנוסע, שמכילה אך ורק גרפים המקיימים את אי־שוויון המשולש (*Triangle Inequality*). הוכיחו…דומה בנושא — לא כפילותמטלההוכיחו כי TSP, בעיית הסוכן הנוסע שהוגדרה בשיעור, שייכת ל-NP.דומה בנושא — לא כפילותמטלהנקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר 1. 1. הוכיחו כי בעיית ההכרעה הבאה היא NP-שלמה: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה:…דומה בנושא — לא כפילותמטלהקליק בגרף לא מכוון הוא קבוצת קודקודים שכל שני קודקודים שונים בה מחוברים בקשת. גרף הוא איחוד זר של קליקים אם ניתן לחלק את קודקודיו לקבוצות שכל אחת מהן…דומה בנושא — לא כפילותמטלהקלט: קבוצה U, אוסף \F 1, ,F m\ של m תתי-קבוצות של U, שכל אחת מהן בגודל 3, ומספר טבעי k. שאלה: האם קיימת קבוצה S U, בגודל |S|=k, המקיימתדומה בנושא — לא כפילות