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

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

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

נוסח השאלה

תהא A בעיית ההכרעה הבאה. קלט: גרף מכוון G ומספר k. שאלה: האם קיימים ב G k לפחות קודקודים כך שבין כל שניים מהם יש מסלול. תהא B בעיית ההכרעה הבאה. קלט: גרף מכוון G ומספר k. שאלה: האם קיימים ב G k לפחות קודקודים כך שבין כל שניים מהם יש קשת. אילו מהטענות הבאות היא הקזחה החזקה ביותר הידועה כנכונה?
  1. אטענות ב' ג' נכונות.
  2. בA∈coNL וגם B∈NP .
  3. גאם B∈NL אז P=NP .
  4. דאם A∈P אז NP=P .
  5. הA∈NL וגם B∈NL .
  6. ותשובות ב' ד' נכונות.

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

ייחוס מדויק

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

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

בחינה

2025 ג׳ · מועד א׳

shalon_131111_2025_s3_g06_moed1.pdf

שאלה 5עמוד 5קריאה חזותית

עותקים זהים של אותו מסמך: נושא 131111 קבוצה 13111106 שנה 2025 סמסטר 3 מועד 1.pdf

הצגת צילום המקור — עמוד 5עמוד מקור 5 מתוך shalon_131111_2025_s3_g06_moed1.pdf פתיחה בגודל מלא
תרגול המשך

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

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

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