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

ב. בעיית ההכרעה A מוגדרת כלהלן. קלט : נוסחה בוליאנית φ מצורת CNF שכל משתנה שלה מופיע בה 3 פעמים בדיוק (בצורת ח…

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

נוסח השאלה

ב. בעיית ההכרעה A מוגדרת כלהלן. קלט : נוסחה בוליאנית φφ מצורת CNF שכל משתנה שלה מופיע בה 3 פעמים בדיוק (בצורת חיוב ו/או שלילה). שאלה : האם φφ ספיקה? הוכיחו כי הבעיה A היא NP-קשה. הערות: • בהגדרת הבעיה A אין מגבלה על מספר הליטרלים בהסגרים של נוסחת הקלט. • אפשר להשתמש בסעיף א' גם אם לא השבתם עליו. 5

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

ייחוס מדויק

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

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

בחינה

2024 ב׳ · מועד א׳

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

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

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

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

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

1 עמודים

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

תרגול המשך

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

מטלה1. יהי G=(V,E) גרף שאינו דווקא פשוט - ייתכנו בו קשתות מקבילות ולולאות - ויהי k מספר טבעי. נסמן ב-G' את הגרף הפשוט המתקבל מ-G באמצעות הוספת שני קודקודי…דומה בנושא — לא כפילותמטלהנסמן ב-DHP את בעיית המסלול ההמילטוני בגרפים מכוונים, ב-UHP את הבעיה בגרפים לא מכוונים, ב-DHC את בעיית המעגל ההמילטוני בגרפים מכוונים וב-UHC את הבעיה ב…דומה בנושא — לא כפילותמטלהבכל סעיף מוצגות טענה ואלגוריתם. קבעו אם האלגוריתם מגדיר רדוקציית זמן פולינומי המוכיחה את הטענה, והוכיחו את קביעתכם. נשתמש בהגדרות: - נוסחת CNF ספיקה ב…דומה בנושא — לא כפילותמטלהנקרא לגרף צנוע אם הדרגה המקסימלית שלו היא לכל היותר 1. 1. הוכיחו כי בעיית ההכרעה הבאה היא NP-שלמה: קלט: גרף פשוט לא מכוון G=(V,E) ומספר טבעי k. שאלה:…דומה בנושא — לא כפילותמטלהיהיו k N ו-A \0, ,k\. נגדיר את הבעיה kSAT A: קלט: נוסחה בצורת k-CNF. שאלה: האם קיימת השמה כך שבכל פסוקית מספר הליטרלים המקבלים אמת שייך ל-A? לדוגמה, ב…דומה בנושא — לא כפילותמטלה1. נגדיר אלגוריתם לבעיית BinPacking כלהלן: בהינתן קלט a 1, ,a n, האלגוריתם עובר על כל מספר ברשימה לפי הסדר הנתון; במידת האפשר הוא מכניס אותו לתא האחרו…דומה בנושא — לא כפילות