28 خرداد 1392, 11:27 ب.ظ
سلام
در این پست قصد دارم پاسخ تشریحی سوالات درس طراحی الگوریتم مربوط به آزمون دکتری ۹۲ رو قرار بدم.
از دوستانی که تو آزمون شرکت کرده بودن و یا دوستانی که امسال میخوان شرکت کنن، دعوت میشه که مشارکت داشته باشن و نظراتشونو راجع به سوالات بیان کنن.
مرسی
سوالات رو از اینجا دانلود کنید :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
*******************************************************************************************************
۳۱- گزینه ۲ صحیح است.
گزاره الف صحیح است زیرابا استفاده از الگوریتم زیر می توان زیردنباله مذکور را بدست آورد. بدیهی است که تعداد گامهای اجرای حلقه for برابر n بوده و هر گام در زمان [tex]O(1)[/tex] انجام می شود، بنابراین زمان اجرای کلی الگوریتم برابر [tex]O(n)[/tex]
است.
توضیح الگوریتم: در این الگوریتم اندیس های ابتدا و انتهای زیر دنباله ی جاری به ترتیب در seq_start و seq_end ذخیره می شوند و متغیرهای max_sec_start و نیز max_sec_end به ترتیب اندیس های ابتدا و انتهای زیر دنباله ای هستند که حاصلضرب عناصر آن ماکزیمم است. حاصلضرب عناصر زیردنباله جاری در متغیر this_prod ذخیره می شود و max_prod بزرگترین حاصلضرب زیردنباله های مشاهده شده را در خود نگه می دارد.
گزاره ب صحیح نیست.
*******************************************************************************************************
۳۲- گزینهی ۱ صحیح میباشد.
مسئلهی A بیانی دیگر از مسئلهی فروشندهی دورهگرد میباشد، میدانیم که این مسئله انپی-سخت میباشد.
مسئلهی B حالت تصمیمگیری مسئلهی فروشندهی دورهگرد بوده و مسئلهای انپی-کامل میباشد.
مسئلهی A را به دو صورت میتوان توسط مسئلهی B حل نمود:
۱-با محاسبهی جایگشت رئوس و وزن دور مربوطه و بررسی آن توسط ماشینی که مسئلهی B را حل میکند.
۲-با انجام جستجو در میان اعداد [M-0]، این روش ممکن است بسیار به پاسخ نزدیک شود ولی با توجه به حقیقی بودن وزنها ممکن است هرگز به جواب نرسد.
گزینهی ۴ نادرست میباشد، زیرا گرچه به کمک ماشین مربوطه نمیتوان مسئلهی A را در زمان چندجملهای حل نمود، ولی این امر توسط روش ۱ در زمان [tex]O(n!)[/tex] ممکن میباشد.
گزینههای ۲و۳ نیز با توجه به انپی سخت بودن مسئلهی A امکان پذیر نمیباشند.
گرچه گزینهی ۱ نیز چندان صحیح نیست ولی بهترین گزینهی ممکن میباشد، زیرا در صورت استفاده از روش ۲ تعداد حالات پیش رو ناشمارا میباشد.
*******************************************************************************************************
۳۳- گزینهی ۲ صحیح میباشد.
یک روش برای حل این مسئله در زمان خطی با استفاده از روش حریصانه و به صورت زیر میباشد:
در ابتدا قبل از اجرای الگوریتم در زمان [tex]O(V E)[/tex] لیستی L از برگهای درخت را تهیه نموده و بیت مربوط به انتخاب آنها را صفر مینماییم.
حال با داشتن لیست برگهای موجود در درخت به صورت زیر عمل مینماییم:
while L is not empty
f ← remove first leaf from L
if mark[f]==FALSE and parent[f]==NIL
mark[f]=TRUE
else if mark[f]==FALSE and parent[f]≠NIL
mark[parent[f]]=TRUE
remove f from T
if parent[f]≠NIL and parent[f]≠root[T] and children[parent[f]]==NIL
append parent[f] to L
البته برای حل این مسئله میتوان از الگوریتم خطی برنامهنویسی پویا برای محاسبهی پوشش رأسی نیز استفاده نمود.
*******************************************************************************************************
ادامه دارد...
در این پست قصد دارم پاسخ تشریحی سوالات درس طراحی الگوریتم مربوط به آزمون دکتری ۹۲ رو قرار بدم.
از دوستانی که تو آزمون شرکت کرده بودن و یا دوستانی که امسال میخوان شرکت کنن، دعوت میشه که مشارکت داشته باشن و نظراتشونو راجع به سوالات بیان کنن.
مرسی
سوالات رو از اینجا دانلود کنید :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
*******************************************************************************************************
۳۱- گزینه ۲ صحیح است.
گزاره الف صحیح است زیرابا استفاده از الگوریتم زیر می توان زیردنباله مذکور را بدست آورد. بدیهی است که تعداد گامهای اجرای حلقه for برابر n بوده و هر گام در زمان [tex]O(1)[/tex] انجام می شود، بنابراین زمان اجرای کلی الگوریتم برابر [tex]O(n)[/tex]
است.
توضیح الگوریتم: در این الگوریتم اندیس های ابتدا و انتهای زیر دنباله ی جاری به ترتیب در seq_start و seq_end ذخیره می شوند و متغیرهای max_sec_start و نیز max_sec_end به ترتیب اندیس های ابتدا و انتهای زیر دنباله ای هستند که حاصلضرب عناصر آن ماکزیمم است. حاصلضرب عناصر زیردنباله جاری در متغیر this_prod ذخیره می شود و max_prod بزرگترین حاصلضرب زیردنباله های مشاهده شده را در خود نگه می دارد.
گزاره ب صحیح نیست.
*******************************************************************************************************
۳۲- گزینهی ۱ صحیح میباشد.
مسئلهی A بیانی دیگر از مسئلهی فروشندهی دورهگرد میباشد، میدانیم که این مسئله انپی-سخت میباشد.
مسئلهی B حالت تصمیمگیری مسئلهی فروشندهی دورهگرد بوده و مسئلهای انپی-کامل میباشد.
مسئلهی A را به دو صورت میتوان توسط مسئلهی B حل نمود:
۱-با محاسبهی جایگشت رئوس و وزن دور مربوطه و بررسی آن توسط ماشینی که مسئلهی B را حل میکند.
۲-با انجام جستجو در میان اعداد [M-0]، این روش ممکن است بسیار به پاسخ نزدیک شود ولی با توجه به حقیقی بودن وزنها ممکن است هرگز به جواب نرسد.
گزینهی ۴ نادرست میباشد، زیرا گرچه به کمک ماشین مربوطه نمیتوان مسئلهی A را در زمان چندجملهای حل نمود، ولی این امر توسط روش ۱ در زمان [tex]O(n!)[/tex] ممکن میباشد.
گزینههای ۲و۳ نیز با توجه به انپی سخت بودن مسئلهی A امکان پذیر نمیباشند.
گرچه گزینهی ۱ نیز چندان صحیح نیست ولی بهترین گزینهی ممکن میباشد، زیرا در صورت استفاده از روش ۲ تعداد حالات پیش رو ناشمارا میباشد.
*******************************************************************************************************
۳۳- گزینهی ۲ صحیح میباشد.
یک روش برای حل این مسئله در زمان خطی با استفاده از روش حریصانه و به صورت زیر میباشد:
در ابتدا قبل از اجرای الگوریتم در زمان [tex]O(V E)[/tex] لیستی L از برگهای درخت را تهیه نموده و بیت مربوط به انتخاب آنها را صفر مینماییم.
حال با داشتن لیست برگهای موجود در درخت به صورت زیر عمل مینماییم:
while L is not empty
f ← remove first leaf from L
if mark[f]==FALSE and parent[f]==NIL
mark[f]=TRUE
else if mark[f]==FALSE and parent[f]≠NIL
mark[parent[f]]=TRUE
remove f from T
if parent[f]≠NIL and parent[f]≠root[T] and children[parent[f]]==NIL
append parent[f] to L
البته برای حل این مسئله میتوان از الگوریتم خطی برنامهنویسی پویا برای محاسبهی پوشش رأسی نیز استفاده نمود.
*******************************************************************************************************
ادامه دارد...