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

תהא A בעיית ההכרעה הבאה. קלט: גרף לא מכוון G ומספר k. שאלה: האם קיימים ב-G לפחות k קודקודים כך שבין כל שניים מ…

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

נוסח השאלה

תהא AA בעיית ההכרעה הבאה.

קלט: גרף לא מכוון GG ומספר kk.

שאלה: האם קיימים ב-GG לפחות kk קודקודים כך שבין כל שניים מהם אין מסלול.

תהא BB בעיית ההכרעה הבאה.

קלט: גרף לא מכוון GG ומספר kk.

שאלה: האם קיימים ב-GG לפחות kk קודקודים כך שבין כל שניים מהם אין קשת.

נתונות הטענות הבאות:

i. A∈PA\in P

ii. B≤pAB\le_p A

iii. B∈NPB\in NP

אילו מהטענות הנתונות ידועות כנכונות?

  1. אטענות i,iii.
  2. בטענה ii.
  3. גטענות ii,iii.
  4. דטענות i,ii.
  5. הטענה iii.
  6. וטענה i.

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

ייחוס מדויק

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

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

בחינה

2026 ב׳ · מועד א׳

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

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

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

תרגול המשך

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

שיעור5. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה S V בגודל |S| = k עבו…דומה בנושא — לא כפילותמטלה1. יהי G=(V,E) גרף שאינו דווקא פשוט - ייתכנו בו קשתות מקבילות ולולאות - ויהי k מספר טבעי. נסמן ב-G' את הגרף הפשוט המתקבל מ-G באמצעות הוספת שני קודקודי…דומה בנושא — לא כפילותמטלהנקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר 1. 1. הוכיחו כי בעיית ההכרעה הבאה היא NP-שלמה: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה:…דומה בנושא — לא כפילותמטלהנגדיר את בעיית IS: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה: האם קיימת ב-G קבוצה בלתי תלויה בגודל לפחות k? 1. נתונה הרדוקציה הבאה מ-SAT. לכל…דומה בנושא — לא כפילותמטלה1. יהי G=(V,E) גרף שאינו בהכרח פשוט — ייתכנו בו קשתות מקבילות ולולאות — ויהי k מספר טבעי. נסמן ב-G' את הגרף הפשוט המתקבל מ-G באמצעות הוספת שני קודקודי…דומה בנושא — לא כפילותמטלהקליק בגרף לא מכוון הוא קבוצת קודקודים שכל שני קודקודים שונים בה מחוברים בקשת. גרף הוא איחוד זר של קליקים אם ניתן לחלק את קודקודיו לקבוצות שכל אחת מהן…דומה בנושא — לא כפילות

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