היפר-גרף הוא זוג H=(V,E) כאשר V קבוצת קדקודים ו- E אוסף של תת-קבוצות של V. כל תת-קבוצה כזו…

שאלת רב־ברירהq-b931626bd806

נוסח השאלה

היפר-גרף הוא זוג H=(V,E) כאשר V קבוצת קדקודים ו- E אוסף של תת-קבוצות של V. כל תת-קבוצה כזו נקראת קשת היפר- קשת (היפר-קשתות שונות עשויות בעלות מספר קדקודים שונה). כיסוי קדקודים של H הוא קבוצה $S\subseteq V$ המקיימת שבכל היפר-קשת E יש קדקוד שייך ל- S. מה הטענה (הנכונה) החזקה ביותר שניתן לטעון לגבי הבעיה של מציאת כיסוי קדקודים מינימלי בהיפר-גרף?

אקיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב O(lg n) .
בקיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב 2.
גקיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב 3.
דקיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב O(√n).
האם קיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב O(lg n) אז P=NP.
ואם קיים אלגוריתם לבעיה הרץ בזמן פולינומי באורך הקלט ומשיג יחס קירוב O(√n) אז NP=coNP.

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

ייחוס מדויק

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

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

בחינה

2023 ב׳ · מועד א׳

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

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

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

הצגת צילום המקור — עמוד 9

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

פתיחה בגודל מלא

נוסח השאלה

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

2023 ב׳ · מועד א׳

שאלות קשורות ממקור מסוג אחר