حل تشریحی سوالات طراحی الگوریتم - کنکور دکتری مهندسی کامپیوتر 1399
سوالات طراحی الگوریتم
10 سوالدر درخت میانوندی داده شده، مقدار هر برگ میتواند صفر یا یک باشد. ماکزیمم خروجی این عبارت کدام است؟

2
3
4
6
میدانیم ترتیب شروع و پایان فعالیتهای H و G و F و E و D و C و B و A از چپ به راست بهصورت است. در اینجا زمان شروع و زمان پایان فعالیت X میباشد. میخواهیم این فعالیتها را در تعدادی اتاق که در اختیار داریم انجام دهیم. یک فعالیت در یک اتاق قابل انجام است، اگر در تمام مدت آن فعالیت اتاق بهطور کامل در اختیارش باشد. حداقل تعداد اتاقهای مورد نیاز برای انجام همه فعالیتها کدام است؟
3
4
5
6
اعداد صحیح بین 1 تا 1398 به عنوان ورودی داده شده است. کدام تابع در همساز، اعداد داده شده را بهطور یکنواخت بین 10 خانه جدول درهمسازی توزیع میکند؟(یک توزیع یکنواخت است، اگر تفاضل تعداد اعداد نگاشت شده به هر دو خانه از جدول حداکثر 1 باشد.)
آرایه داده شده است. میتوانیم هر بار دو خانه دلخواه از این آرایه را باهم جابهجا کنیم. با حداقل چند جابهجایی میتوان این آرایه را به یک هرم بیشینه تبدیل کرد؟
0
1
2
3
فرض کنید در گراف وزندار و جهتدار G با n رأس، تنها وزن یالهای خارج شده از رأس s ممکن است منفی باشند. (البته میدانیم گراف دور منفی ندارد.) بزرگترین که به ازای آن الگوریتم دایکسترا روی هر گراف رأسی با فرضهای گفته شده کوتاهترین مسیر از به بقیه رئوس را درست محاسبه میکند، کدام است؟
2
3
4
به ازای هر n همیشه درست کار میکند.
در شبکه داده شده فقط مجاز هستیم ظرفیت یک یال را به هر میزان که بخواهیم افزایش دهیم. با این کار شار بیشینه از s به t را حداکثر چه میزان میتوان افزایش داد؟

5
2
1
اگر مسئله X عضو کلاس NP-Complete به مسئله Y عضو کلاس P در زمان جملهای تبدیل شود، کدام گزینه نادرست است؟
NP=P
NP-Complete=P
NP-Hard=NP
مسئله 3-SAT در زمان چند جملهای حل میشود.
زمان اجرای الگوریتمی بهصورت است. مرتبه زمانی اجرای این الگوریتم کدام است؟
O(n)
O(logn)
O(nlogn)
فرض کنید G یک گراف وزندار و جهتدار با n رأس و m یال است. با فرض اینکه فاصله کوتاهترین مسیر برای هر دو رأس را در یک ماتریس در اختیار داریم، مطلع شدهایم که وزن تنها یک یال تغییر پیدا کرده است. میخواهیم به ازای دو رأس مشخص s و t طول کوتاهترین مسیر بین این دو رأس را به روز کنیم. این کار را در چه زمانی میتوان انجام داد؟
O(n)
O(n+m)
O(1)
O(nlogn+m)
دو هرم کمینه در اختیار داریم که هر یک شامل n عدد است. میخواهیم یک هرم کمینه برای همه این 2n عدد بسازیم. با چه مرتبه زمانی میتوان این کار را انجام داد؟ (فرض کنید هرمهای کمینه با آرایه پیادهسازی شدهاند.)
O(n)
O(nlogn)
O(nloglogn)