سوال ۸۰ کنکور ارشد علوم کامپیوتر ۱۴۰۲

اهمیت

۰/۵

کدام گزاره یا گزاره‌ها، درست است؟

الف ـ مسائل تصمیم‌گیری (یعنی مسائلی که جوابشان بله یا خیر است) دارای الگوریتم تقریبی (تخمینی، approximation) با فاکتور (ضریب تقریب) ۲ نیستند.

ب ـ اگر مسئله‌ای دارای الگوریتم تقریبی با فاکتور ۳ باشد، دارای الگوریتم تقریبی با فاکتور $\frac{۷}{۲}$ نیز هست.

#approximation-algorithms#approximation-ratio#decision-problems#optimization-problems#monotonicity-of-factor