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

תהא A בעיית ההכרעה הבאה. קלט: גרף מכוון G=(V,E) וקודקוד v V. שאלה: האם קיימים ב-G לפחות 3 מעגלים (מכוונים) העו…

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

נוסח השאלה

תהא A בעיית ההכרעה הבאה. קלט: גרף מכוון G=(V,E) וקודקוד v∈Vv\in V. שאלה: האם קיימים ב-G לפחות 3 מעגלים (מכוונים) העוברים דרך v. תהא B בעיית ההכרעה הבאה. קלט: גרף מכוון G=(V,E) וקודקוד v∈Vv\in V. שאלה: האם קיימים ב-G בדיוק 3 מעגלים העוברים דרך v. אילו מהטענות הבאות היא החזקה ביותר הידועה כנכונה?

  1. אA∈NL וגם B∈NL.
  2. בA∈coNL וגם B∈P.
  3. גA∈P וגם B∈P.
  4. דA∈DSpace(log^2n) וגם B∈NL.
  5. הA∈L וגם B∈NL.
  6. וA∈NL וגם B∈DSpace(log^2n).

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

ייחוס מדויק

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

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

בחינה

2023 ב׳ · מועד א׳

נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 1.pdf

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

עותקים זהים של אותו מסמך: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 1.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 1.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 1.pdf

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

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

מטלה1. הוכיחו כי בעיות ההכרעה שלהלן שייכות למחלקת הסיבוכיות L. 1. קלט: גרף לא מכוון G=(V,E) וקבוצת קודקודים S V. שאלה: האם הקבוצה S היא כיסוי קודקודים ב-G…דומה בנושא — לא כפילותשיעורii. קלט: גרף מכוון G = (V,E) ושני קודקודים s,t V. שאלה: האם קיים בגרף G מסלול מ-s ל-t ש-3 מחלק את מספר קשתותיו? נסמן את השפה ב-A. נוכיח כי A NL. נתבונ…דומה בנושא — לא כפילותמטלה1. בסעיף זה נרצה להוכיח את משפט היררכיית הזמן. תהא f פונקציה ישימה בזמן. נגדיר:דומה בנושא — לא כפילותשיעור5. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה S V בגודל |S| = k עבו…דומה בנושא — לא כפילותמטלהחזרו על הוכחת משפט היררכיית המקום שהוצגה בהרצאה, וודאו שההוכחה מובנת לכם במלואה. השתמשו בכך כדי להוכיח באופן מלא את משפט היררכיית הזמן. **משפט:** תהיי…דומה בנושא — לא כפילותמטלהנסתכל על בעיית כיסוי הקודקודים VC: קלט: גרף לא מכוון G=(V,E) ומספר טבעי k. שאלה: האם קיים בגרף G כיסוי קודקודים בגודל k? 1. הוכיחו כי קיים אלגוריתם לב…דומה בנושא — לא כפילות

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