شما اینجایید
خانه > دانشگاه > نمونه سوال امتحانی درس طراحی الگوریتم های پیشرفته

نمونه سوال امتحانی درس طراحی الگوریتم های پیشرفته

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

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

  1. مسائل NP-Complete را تعریف کرده و ثابت کنید مسئله تصمیم گیری Clique یک مسئله NP-Complete است.
  2. الگوریتم Relabel to Front را تشریح کنید (کلیه مفاهیم بکار رفته در الگوریتم را تشریح کنید).
  3. فرض کنید از الگوریتم Rabin-Karp برای یافتن عدد ۲۶ در رشته 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 \]

  1. مشکل اصلی در مرتبه زمانی بالای الگوریتم تصادفی برای حل مسئله Min Cut در چیست؟ الگوریتم Fast Cut برای حل این مشکل را توضیح دهید. احتمال رسیدن به جواب در این الگوریتم چقدر است؟
  2. یک الگوریتم تقریبی برای حل مسئله فروشنده دوره گرد در شرایطی که نامساوی مثلث برقرار باشد نوشته و درجه تقریب آن را ثابت کنید.
نوتیف
امیدوارم مطالب نوتیف برایتان مفید واقع شده باشد. با عضویت در خبرنامه نوتیف مطالب تازه ما را در اینباکس خود داشته باشید. کانال ما در تلگرام هم راه سریع و مطمئنی برای آگاهی از مطالب ماست. *** من رضا حیدری مدیر وب سایت نوتیف هستم. همکنون مشغول به تحصیل در رشته کارشناسی ارشد نرم افزار بوده و به دنیای فناوری علاقه مندم به همین دلیل در نوتیف به دنبال نشر و ترویج موضوعات روز دنیای فناوری بخصوص موضوعات مرتبط با دنیای موبایل، اینترنت، کامپیوتر هستم. در کنار اینها گاهی هم گریزی به دیگر موضوعات مهم خواهیم زد که خالی از لطف نخواهد بود. با نوتیف همراه باشید بودن با شما افتخار بزرگی برای ماست.

پاسخ دهید

3 × سه =

Top