אלגוריתמים

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

• «
• 1
• 2
• »

נתונה הבעיה האלגוריתמית הבאה:

-

1

+

שאלה #105237

		אף תשובה לא נכונה
		הבעיה NPC. ההוכחה באמצעות רדוקציה מבעיית קליק.
		הבעיה NPC כי ניתן לעשות רדוקציה ממנה אל בעיית קליק.
done		הבעיה פולינומית. ניתן לפתור אותה בזמן Theta(V+E).

• gavel
• mood_bad
• share

הגב

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

נתון אלגוריתם A שמכריע את בעיה L בזמן O(n^k) ונתון אלגוריתם B שמכריע את בעיה M בזמן O(m^q) מהו זמן הריצה של הרדוקציה הפולינומית מבעיה A לבעיה B ?

-

1

+

שאלה #105239

		O(min(n^k,m^q))
		אי אפשר לדעת
done		O(n^k)
		O(n^k+m^q)

• gavel
• mood_bad
• share

הגב

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

נתונות הבעיות הבאות: הבעיה A שייכת למחלקה NP. הבעיה B שייכת למחלקה Co-NP: מה מהמשפטים הבאים נכון בהכרח: א. יש רדוקציה פולינומית מ – A ל – B. ב. יש רדוקציה פולינומית מ – B ל – A. ג. קיימת בעיה C כך שמתקיים – יש רדוקציות פולינומיות מ B ל - C ו מ - C ל - A. ד. מכל בעיה ב – NP יש רדוקציה ל – A.

-

1

+

שאלה #105240

		כל המשפטים.
		רק המשפט השלישי.
		רק המשפט הראשון.
done		אף אחד

• gavel
• mood_bad
• share

הגב

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

• «
• 1
• 2
• »