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

הוכיחו כי TSP, בעיית הסוכן הנוסע שהוגדרה בשיעור, שייכת ל-NP.

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

נוסח השאלה

הוכיחו כי TSPTSP, בעיית הסוכן הנוסע שהוגדרה בשיעור, שייכת ל-NPNP.

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

ייחוס מדויק

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

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

מטלה

2026 א׳

2026א_04_תרגיל_4.md

שאלה 4עמוד 1נבדק אנושית
תרגול המשך

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

בחינהנזכיר את בעיית הסוכן הנוסע. קלט: גרף לא מכוון שלם G = (V,E) עם משקלות w: E ℕ ומספר k ℕ. שאלה: האם קיים מעגל פשוט ב G העובר דרך כל הקודקודים ומשקלו לכל…דומה בנושא — לא כפילותבחינהשמתקיים P=NP. בבעיית הספיקות (3-SAT) מציין n את מספר המשתנים, ו-m את מספר הפסוקיות. בבעיית הסוכן-הנוסע (TSP) ובבעיית הקליקה מציין n את מספר הקדקודים ב…דומה בנושא — לא כפילותבחינהיגרור שמתקיים P=NP . הן בבעיית הסוכן-הנוסע (TSP) והן בבעיית הקליקה n מציין את מספר הקדקודים בגרף. .ד. שלוש התשובות (א-ג) נכונות.דומה בנושא — לא כפילותבחינהאנו מעוניינים להוכיח את הטענה הבאה: טענה: אם קיים קרוב 2000 לבעיית הסוכן הנוסע (TSP) ללא אי שוויון המשולש אז P = NP. ההוכחה תהיה דומה להוכחה שראינו בכ…דומה בנושא — לא כפילותבחינהנזכיר את בעיית האריזה בתאים. קלט: n-ייה של מספרים a 1, ,a n (0,1] ומספר טבעי k . שאלה: האם קיימת חלוקה של a 1,a 2, ,a n ל-k תאים כך שסכום המספרים בכל…דומה בנושא — לא כפילותבחינההיפר-גרף הוא זוג H=(V,E) כאשר V קבוצת קדקודים ו- E אוסף של תת-קבוצות של V. כל תת-קבוצה כזו נקראת קשת היפר- קשת (היפר-קשתות שונות עשויות בעלות מספר קדק…דומה בנושא — לא כפילות