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

נזכיר את בעיית הסוכן הנוסע. קלט: גרף לא מכוון שלם G = (V,E) עם משקלות w: E ℕ ומספר k ℕ. שאלה: האם קיים מעגל פש…

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

נוסח השאלה

נזכיר את בעיית הסוכן הנוסע. קלט: גרף לא מכוון שלם G = (V,E) עם משקלות w:E→Nw: E \to ℕ ומספר k∈Nk \in ℕ. שאלה: האם קיים מעגל פשוט ב G העובר דרך כל הקודקודים ומשקלו לכל היותר k. א. הוכיחו כי בעיית הסוכן הנוסע היא NP קשה. ב. נסחו את בעיית האופטימיזציה המתאימה לבעיית הסוכן הנוסע, והוכיחו כי אם קיים אלגוריתם קירוב לבעיה עבור גרפים עם משקלים כלליים עם יחס קירוב 2 אז P = NP.

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

ייחוס מדויק

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

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

תרגול המשך

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

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