אלגוריתמים

Discuss, Learn and be Happy דיון בשאלות

• «
• 1
• 2
• »

מה ניתן לומר על בעיית המינימיזציה של הכיסוי על ידי קודקודים Cover Vertex?

-

1

+

שאלה #105194

		ניתן להוכיח שבעיה זו היא NPHard באמצעות רדוקציה ממנה לבעיית קליק.
		קיים אלגוריתם קירוב פולינומי לבעיה עם חסם יחס 2 ,בתנאי שהיא מקיימת את אי שוויון המשולש.
done		אף תשובה לא נכונה.
		הבעיה היא פולינומית כי קיים לה אלגוריתם עם חסם יחס 2 .

• gavel
• mood_bad
• share

הגב

מיין לפי דירוג חדש ישן

שאלה מספר 9, נתונה הנוסחה תראה את המשך השאלה?

-

1

+

שאלה #105195

		גם ב וג נכונות
done		נוכל להציע אלגוריתם תכנון דינמי שימלא את האלכסון הראשי ויתקדם לכיוון הקצה הימני למעלה.
		נוכל להציע אלגוריתם תכנון דינמי שימלא את שורה 0 ויתקדם שורה אחר שורה.
		נוכל להציע אלגוריתם תכנון דינמי שימלא את עמודה 0 ויתקדם עמודה אחר עמודה.

• gavel
• mood_bad
• share

הגב

מיין לפי דירוג חדש ישן

נתונות שתי בעיות- B,A .ידוע ש- AeP וש- BeNPC .איזו מהטענות ודאי נכונה?

-

1

+

שאלה #105196

		גם A וגם B שייכות ל- NPHard.
done		A ניתנת לרדוקציה פולינומית ל-B .
		B ניתנת לרדוקציה פולינומית ל-A.
		אם נמצא רדוקציה פולינומית מ-A ל-B ,אזי יש גם רדוקציה פולינומית מ-B ל-A .

• gavel
• mood_bad
• share

הגב

מיין לפי דירוג חדש ישן

אלו מהטענות הבאות נכונה עבור אלגוריתם הקירוב של בעיית הסוכן הנוסע?

-

1

+

שאלה #105197

done		האלגוריתם מוצא עץ פורש מינימלי וסורק את קודקודי העץ בסדר תחילי.
		האלגוריתם מוצא עץ פורש מינימלי וסורק את קודקודי העץ בסדר תוכי.
		עבור כל גרף, האלגוריתם יחזיר פתרון עם חסם יחס 2 .
		אם לא מתקיים אי שוויון המשולש, חסם היחס של הפתרון שיחזיר האלגוריתם יהיה בהכרח גדול מ-2 .

• gavel
• mood_bad
• share

הגב

מיין לפי דירוג חדש ישן

בהינתן גרף מכוון וחסר מעגלים, (E,V=(G וקבוצת קודקודים, V'V. איזה מהאלגוריתם הבאים מהווה אלגוריתם פולינומי שימצא האם קיים בגרף G מסלול מכוון המבקר בכל צמתי 'V( ויכול לבקר גם בצמתים נוספים(.

-

1

+

שאלה #105198

		לא קיים אלגוריתם פולינומי לפתרון בעיה זו.
done		נבצע מיון טופולוגי על הגרף, ולכל קודקוד בסדר המלא שנקבל, אם הוא שייך ל-'V ,נבדוק באמצעות BFS האם קיים מסלול בינו לבין הקודקוד הבא אחריו בסדר המלא, ושייך ל-'V .
		נפעיל את האלגוריתם של Warshall Floid על הגרף ונבדוק האם בין כל 2 קודקודים v,u השייכים ל -'V גם אורך המסלול המינימלי בין u ל - v קטן מאינסוף, וגם אורך המסלול המינימלי בין v ל - u קטן מאינסוף.
		נבצע מיון טופולוגי על הגרף, ולכל קודקוד בסדר המלא שנקבל, אם הוא שייך ל-'V ,נבדוק באמצעות BFS האם קיים מסלול בינו לבין הקודקוד הבא אחריו בסדר המלא, ושייך ל-'V .

• gavel
• mood_bad
• share

הגב

מיין לפי דירוג חדש ישן

נתונה הבעיה האלגוריתמית הבאה: בתור לבנק עומדים n לקוחות, אך יכולים להיכנס אליו רק 10 לקוחות בו זמנית. לכל לקוח יש זמן שירות שלו, וכאשר הוא מסיים, יכול להיכנס לקוח אחר כדי להחליפו. ברצוננו להביא למינימום אז סכום זמני ההמתנה של כלל הלקוחות בהנחה שלא מגיעים לקוחות חדשים במהלך ההמתנה. מה ניתן לומר על בעיה זו?

-

1

+

שאלה #105199

		הבעיה היא NPHard אך אינה שייכת ל-NP כיוון שאין לה אלגוריתם אימות פולינומי.
		אף תשובה לא נכונה.
		הבעיה היא NPC :רדוקציה מבעיית packing bin.
done		הבעיה היא פולינומית: ניתן לפתור אותה באמצעות אלגוריתם חמדני.

• gavel
• mood_bad
• share

הגב

מיין לפי דירוג חדש ישן

נתונה רשת זרימה (E,V=(G וזרימה f ברשת זו. בנינו עבורה רשת שיורית. איזו מהתשובות הבאות נכונה?

-

1

+

שאלה #105200

		מספר הקשתות ברשת השיורית יהיה שווה למספר הקשתות ברשת המקורית.
		מספר הקשתות ברשת השיורית יכול להיות קטן או שווה למספר הקשתות ברשת המקורית.
done		מספר הקשתות ברשת השיורית יכול להיות גדול או שווה למספר הקשתות ברשת המקורית.
		מספר הקשתות ברשת השיורית לעולם לא יהיה שווה למספר הקשתות ברשת המקורית.

נערך לפני שנה אורלי סלם

• gavel
• mood_bad
• share

הגב

מיין לפי דירוג חדש ישן

תהא N רשת זרימה כך שכל הקיבולים )capacity )על הקשתות שלה זוגיים מלבד קשת אחת e שהקיבול שלה (e(c הוא ערך אי-זוגי. תהא f זרימה מקסימלית ברשת N .איזו מהטענות הבאות נכונה?

-

1

+

שאלה #105201

		|f |בהכרח אי זוגי.
		|f |בהכרח זוגי.
done		אם |f |אי זוגי, אזי בהכרח (e(c)=e(f.
		אם |f |זוגי, אזי בהכרח e חוצה את החתך המינימלי ברשת הזרימה.

• gavel
• mood_bad
• share

הגב

מיין לפי דירוג חדש ישן

נתון גרף קשיר לא מכוון (E,V=(G עם משקולות, ונתונים שני עצים פורשים מינימליים שונים T2,T1 לגרף זה, כאשר העצים האלו שונים זה מזה לפחות בקשת אחת. איזו מהטענות הבאות לא יכולה להיות נכונה?

-

1

+

שאלה #105202

done		לכל קשת בגרף G יש משקל שונה.
		לכל חתך בגרף G יש לפחות 2 קשתות שחוצות את החתך.
		אין אף קשת משותפת בין T1 ו-T2.
		יש עץ פורש מינימלי שלישי, שונה מ- T1 ומ-T2 ,עבור הגרף G.

• gavel
• mood_bad
• share

הגב

מיין לפי דירוג חדש ישן

מה את חושבת שהתשובה?

-

1

+

שאלה #105203

done		אם נמצא קליק בגודל 4 ,אזי הנוסחה ספיקה.
		הנוסחה הנתונה אינה ספיקה כיוון שיש בה 4 פסוקיות אך רק שלושה משתנים.
		אפשרות לקליק מקסימלי: הקודקוד של b מפסוקית 1 ,הקודקוד של b מפסוקית 2 ,הקודקוד של b מפסוקית 3 ,הקדקוד של b מפסוקית 4 .
		הנוסחה הנתונה ספיקה, הואיל ואחרי הפעלת הרדוקציה, נמצא בגרף שנקבל קליק בגודל 3 .

• gavel
• mood_bad
• share

הגב

מיין לפי דירוג חדש ישן

• «
• 1
• 2
• »