Complexity Atlas
HE
Source-backed question

נגדיר את בעיית האופטימיזציה הבאה, WMAXCUT. קלט: גרף G=(V,E), ופונקציית משקל W המתאימה לכל קשת ב G משקל אי שליל…

1Exams0Assignments0Lessons1Source documents
שאלת רב־ברירהq-bf3c5832c99f

נוסח השאלה

נגדיר את בעיית האופטימיזציה הבאה, WMAXCUT. קלט: גרף G=(V,E), ופונקציית משקל W המתאימה לכל קשת ב G משקל אי שלילי. מטרה: למצוא חתך מושרה בגרף שמשקלו מקסימלי. יהי G,w קלט לבעיית WMAXCUT. נסמן ב W את סך משקלי הקשתות ב G. מהו הערך הגדול ביותר של αα עבור ידוע כי קיים חתך מושרה ב G כך שמשקלו הוא לפחות αWαW ?

  1. אα=1/2.
  2. בα=7/8.
  3. גα=9/10.
  4. דהערך המבוקש תלוי גם במספר הקשתות, לכן לא ניתן לענות על השאלה.
  5. ההערך המבוקש יכול להיות קרוב כרצוננו ל 1.
  6. וα=1/3.

תמלול ראשון מתוך עמוד המקור ב־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.

Exam

2023 B · moed B

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

Question 3Page 2Visual reading

Byte-identical aliases: נושא 131111 קבוצה 13111103 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111104 שנה 2023 סמסטר 2 מועד 2.pdf · נושא 131111 קבוצה 13111105 שנה 2023 סמסטר 2 מועד 2.pdf

View source scan — page 2Source page 2 from נושא 131111 קבוצה 13111102 שנה 2023 סמסטר 2 מועד 2.pdf Open full size
Further practice

These are topic and lesson matches, not identical appearances.

Assignmentנתאר את בעיית האופטימיזציה הבאה: קלט: גרף פשוט מכוון G=(V,E). פלט: קבוצת קשתות E' E גדולה ככל האפשר, כך שהגרף G'=(V,E') חסר מעגלים. 1. נתבונן בקבוצות…Topically related — not a duplicateAssignmentיהא קלט עבור בעיית העץ של שטיינר הכללית, ללא הדרישה שהקלט מקיים את אי-שוויון המשולש: גרף שלם G=(V,E), חלוקה V=R S ופונקציית משקל w:E R + על הקשתות. נג…Topically related — not a duplicateAssignment1. יהי G=(V,E) גרף מכוון, כאשר V=\1,2, ,n\. נסמןTopically related — not a duplicateAssignmentנגדיר אלגוריתם קירוב בשם Next-Fit לבעיית האופטימיזציה של Bin-Packing: קלט: a 1, ,a n , כאשר a 1, ,a n (0,1] ו-n N. לכל i=1, ,n: 1. אם a i יכול להיכנס…Topically related — not a duplicateAssignmentבשיעורים הגדרנו חתך בגרף לא מכוון. באופן דומה, נגדיר חתך בגרף מכוון כחלוקה של קודקודי הגרף לשתי קבוצות זרות (S, S). במקרה של גרף מכוון, קבוצת החתך מוג…Topically related — not a duplicateAssignmentעבור U V בגרף מכוון G=(V,E), החתך המושרה על ידי U, המסומן (U), הוא קבוצת הקשתות היוצאות מ-U: זנבן ב-U וראשן ב- U. בגרף מכוון (U) ו- ( U) אינם בהכרח שו…Topically related — not a duplicate

Near variants — not duplicates