אלגוריתמי קירוב Flashcards
1
Q
הגדירו:
אלגוריתם c-מקרב.
A
2
Q
מהי בעיית MAX-3SAT?
A
3
Q
הציעו פתרון 2-מקרב לבעיית התרמיל השלם.
A
ההוכחה בתמונה.
נשים לב שהטריק שנעשה כאן (החזרת המקסימום בין שתי אפשרויות, והשימוש בmax בהוכחה כפי שנעשה) חשוב ונפוץ.
4
Q
מהו חתך מקסימלי בגרף?
A
5
Q
מהו האלגוריתם שפותר את בעיית החתך המקסימלי?
A
זהו פתרון 2 מקרב.
6
Q
מהו זמן הריצה של האלגוריתם שפותר את בעיית החתך המקסימלי?
A
7
Q
יהי אלגוריתם 2.5 מקרב לבעיית מקסימיזציה או מינימיזציה.
האם האלגוריתם הוא בהכרח גם 3 מקרב?
האם האלגוריתם הוא בהכרח גם 2 מקרב?
A
בלי קשר להיותו של הבעיה בעיית מקסימיזציה או מינימיזציה,
אלגוריתם שהוא 2.5 מקרב הוא בהכרח 3 מקרב.
אלגוריתם שהוא 2.5-מקרב אינו בהכרח 2 מקרב.
8
Q
הציעו אלגוריתם 2 מקרב לבעיית MAX-3SAT.
A
9
Q
הוכיחו את נכונות האלגוריתם הנאיבי ה2 מקרב לבעייתMAX-3SAT.
A
