دانلود نمونه سوال امتحان درس تحلیل و طراحی الگوریتم های پیشرفته – دکتر ابریشمی – دی ماه 1394 – دانشگاه امام رضا (ع)

درس تحلیل و طراحی الگوریتم های پیشرفته یکی از درس های بسیار مهم و در عین حال سخت مقطع کارشناسی ارشد رشته نرم افزار کامپیوتر می باشد. این درس با مطرح کردن مسائل مختلف و ارائه راه کارهای مختلف برای آنها دانشجو را با مباحث پیشرفته طراحی الگوریتم ها آشنا می کند. در زیر نمونه سوالات امتحانی برای درس تحلیل و طراحی الگوریتم های پیشرفته ارائه شده است که مطالعه آنها برای دوستانی که امتحان این درس را در پیش دارند خالی از لطف نخواهد بود.

1. مسائل NP-Complete را تعریف کرده و ثابت کنید مسئله تصمیم گیری Clique یک مسئله NP-Complete است.
2. الگوریتم Relabel to Front را تشریح کنید (کلیه مفاهیم بکار رفته در الگوریتم را تشریح کنید).
3. فرض کنید از الگوریتم Rabin-Karp برای یافتن عدد 26 در رشته T = 3141592653589793 با پیمانه q = 11 استفاده کرده ایم، نحوه کار الگوریتم بر روی این رشته را توضیح داده و بیان کنید چندبار برخورد جعلی رخ می دهد؟
4. مسئله برنامه ریزی خطی زیر را به روش سیمپلکس حل کنید:

Maximize:

\[ x_{1} + 2 x_{2} – x_{3} \]

Subject To:

\[ 2x_{1}+x_{2}+x_{3} \leq 14 \]

\[ 4x_{1}+2x_{2}+2x_{3} \leq 28 \]

\[ 2x_{1}+5x_{2}+5x_{3} \leq 30 \]

\[ x_{1}, x_{2}, x_{3} \geq 0 \]

5. مشکل اصلی در مرتبه زمانی بالای الگوریتم تصادفی برای حل مسئله Min Cut در چیست؟ الگوریتم Fast Cut برای حل این مشکل را توضیح دهید. احتمال رسیدن به جواب در این الگوریتم چقدر است؟
6. یک الگوریتم تقریبی برای حل مسئله فروشنده دوره گرد در شرایطی که نامساوی مثلث برقرار باشد نوشته و درجه تقریب آن را ثابت کنید.