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

שאלה פתוחהq-15389eda30ab

נוסח השאלה

הוכיחו כי בעיית ההכרעה שמוגדרת להלן שייכת למחלקת הסיבוכיות P. קלט: גרף לא מכוון G = (V, E) ומספר טבעי k שאלה: האם קיימת קבוצה $S \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\in IN$ . מציאת כל רכיבי הקשירות והגדלים שלהם ניתנת לביצוע בזמן פולינומי ב-|G|. זמן הרצה של האלגוריתם תכנות דינמי של $subset-sum - O(ℓ\cdot k)$ . הגודל של - a_1,...,a_ℓ,k - Σ_{j=1}^{ℓ} log a_j + log k [הערה] [לא ברור] לא [הערה] שומרים לזמן [הערה] ריצה [לא ברור] [הערה] [לא ברור]! מתק״ם $: k,ℓ \le|V|$ לכן, זמן הרצה הוא $O(|V|^2)$ . כלומר, פולינומי בגודל G. ניתוח סמנטי: יהי G=(V,E) גרף, יהי $k\in IN$ . נכונות - [לא ברור]. תרגיל: נתונה הבעיה הבאה: קלט: נוסחה $φ$ בצורת CNF ורשימת האותיות שלה שאלה: האם $φ$ ספיקה? לאיזו מחלקה שייכת הבעיה הזו? P ולמעשה L. תרגיל: נתונה הבעיה הבאה: קלט: גרף מכוון $G=(V,E) , s,t\in V$ . שאלה: האם קיימים בדיוק 2 מסלולים שונים מ-s ל-t. [הערה] לפחות $\leftarrow$ כבר פתרנו NL לאיזו מחלקה שייכת הבעיה הזו? נסמן את הבעיה ב-C. נגדיר 2 בעיות חדשות: A : קלט: גרף מכוון $G=(V,E) , s,t\in V. B$ : קלט: גרף מכוון $G=(V,E) , s,t\in V$ . שאלה: האם קיימים 2 מסלולים שונים מ-s ל-t. שאלה: האם קיימים 3 מסלולים שונים מ-s ל $-t. A\in NL$ , משיעורי הבית $. B\in NL$ , בצורה. לכן מאימרמן $, B̄\in NL$ . לכן $- C=A\cap B̄$ לכן $, C\in NL$ .

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

Exact provenance

Appearances by source document

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Lesson

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

Question 5Page 4Visual reading

The pages this was written from

1 page

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Lecture 26 · page 4תרגילים
Shared wordsשמוגדרת · היזכרו · מורכבת · מרכיבי · בשלמותם · הגדלים

נוסח השאלה

Appearances by source document

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

The pages this was written from

Related questions from another source type