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

5. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאל…

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

נוסח השאלה

  1. הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה S⊆VS \subseteq V בגודל |S| = k עבורה גודל החתך (S,S̄) הוא 0? הדרכה: היזכרו בבעיה Subset − Sum. [הערה] S מורכבת מרכיבי קשירות בשלמותם נתבונן באלגוריתם הבא: על קלט G=(V,E), k: 1. נמצא את כל הגדלים של רכיבי הקשירות ב-G. נסמן - a_1,a_2,...,a_ℓ. 2. נריץ את האלגוריתם תכנות דינמי של subset-sum על a_1,...,a_ℓ, k ניתוח זמן הרצה: יהי G=(V,E) גרף, יהי k∈INk\in IN. מציאת כל רכיבי הקשירות והגדלים שלהם ניתנת לביצוע בזמן פולינומי ב-|G|. זמן הרצה של האלגוריתם תכנות דינמי של subset−sum−O(ℓ⋅k)subset-sum - O(ℓ\cdot k). הגודל של - a_1,...,a_ℓ,k - Σ_{j=1}^{ℓ} log a_j + log k [הערה] [לא ברור] לא [הערה] שומרים לזמן [הערה] ריצה [לא ברור] [הערה] [לא ברור]! מתק״ם:k,ℓ≤∣V∣: k,ℓ \le|V| לכן, זמן הרצה הוא O(∣V∣2)O(|V|^2). כלומר, פולינומי בגודל G. ניתוח סמנטי: יהי G=(V,E) גרף, יהי k∈INk\in IN. נכונות - [לא ברור]. תרגיל: נתונה הבעיה הבאה: קלט: נוסחה φφ בצורת CNF ורשימת האותיות שלה שאלה: האם φφ ספיקה? לאיזו מחלקה שייכת הבעיה הזו? P ולמעשה L. תרגיל: נתונה הבעיה הבאה: קלט: גרף מכוון G=(V,E),s,t∈VG=(V,E) , s,t\in V. שאלה: האם קיימים בדיוק 2 מסלולים שונים מ-s ל-t. [הערה] לפחות ←\leftarrow כבר פתרנו NL לאיזו מחלקה שייכת הבעיה הזו? נסמן את הבעיה ב-C. נגדיר 2 בעיות חדשות: A : קלט: גרף מכוון G=(V,E),s,t∈V.BG=(V,E) , s,t\in V. B : קלט: גרף מכוון G=(V,E),s,t∈VG=(V,E) , s,t\in V. שאלה: האם קיימים 2 מסלולים שונים מ-s ל-t. שאלה: האם קיימים 3 מסלולים שונים מ-s ל−t.A∈NL-t. A\in NL, משיעורי הבית.B∈NL. B\in NL, בצורה. לכן מאימרמן,Bˉ∈NL, B̄\in NL. לכן −C=A∩Bˉ- C=A\cap B̄ לכן,C∈NL, C\in NL.

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

ייחוס מדויק

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

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

שיעור

שיעור 26-תרגילים.pdf

שיעור 26-תרגילים.pdf

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

העמודים שמהם זה נכתב

1 עמודים

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

תרגול המשך

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

בחינהיהי n N ותהא f:[n] [n] מחזור באורך ℓ ב f הוא סדרה k 1,k 2,...,k ℓ ∈[n] של איברים שונים עבורם f(k j)=k j+1 לכל 1 j ℓ-1 ובנוסף f(k ℓ)=k 1 (תזכורת: [n] =…דומה בנושא — לא כפילותבחינהתהא A בעיית ההכרעה הבאה. קלט: גרף מכוון G ומספר k. שאלה: האם קיימים ב G k לפחות קודקודים כך שבין כל שניים מהם יש מסלול. תהא B בעיית ההכרעה הבאה. קלט:…דומה בנושא — לא כפילותבחינהתהא A בעיית ההכרעה הבאה. קלט: גרף מכוון G ומספר k. שאלה: האם קיים ב-G מעגל באורך לפחות k. תהא B בעיית ההכרעה הבאה. קלט: גרף מכוון G ומספר k. שאלה: האם…דומה בנושא — לא כפילותבחינהענו על שני הסעיפים הנפרדים הבאים. (א1) CIRCUIT-SAT. נתון כי במעגל הפלט שמופק על ידי הרצת רדוקציית Cook-Levin CIRCUIT-SAT P L מופיע תת-המעגל g 18,4,1/4…דומה בנושא — לא כפילותבחינהתהי A שפת השלשות <G1, G2, k> כך ש- G1 הוא גרף לא מכוון שיש בו כיסוי קדקודים בגודל k ו- G2 הוא גרף לא מכוון שכל כיסוי קדקודים בו גדול מ- k. מבין המחלקו…דומה בנושא — לא כפילותבחינהיהיו A ו- B שפות. ידוע ש- A ניתנת לרדוקציית זמן פולינומיאלי ל- B וש- A שלמה ל- EXP (ביחס לרדוקציות זמן פולינומיאלי). נתבונן בטענות הבאות: (i B ∈ NL. (…דומה בנושא — לא כפילות