hoco.hc

New Member
ارسال ها
388
لایک ها
267
امتیاز
0
#1
2- می خواهیم n کار
را بر روی یک پردازنده انجام دهیم. زمان لازم برای انجام هر کار یک واحد است. برای هر کار تعدادی بازه داریم که باید آن کار را در یکی از آن بازه ها انجام دهیم. طول تما این بازه ها و زمان شروع و پایان آن ها عددی صحیح است. می توانیم انتخاب کنیم که یک کار را در چه زمانی انجام دهیم، ولی بایستی زمان انجام یک کار در یکی از بازه های مربوط به آن قرار گیرد.
می دانیم که پردازنده نمی تواند دو کار را به صورت همزمان انجام دهد. هنگامی که پردازنده می خواهد کاری انجام دهد باید روشن شود. هنگامی که پردازنده کاری را به پایان رساند، اگر کاری دیگری باید در همان لحظه شروع شود، اجرای آن را شروع می کند. در غیر این صورت پردازنده به طور خودکار خاموش می شود.
هدف ما در این مسئله این است که همه کار ها را انجام دهیم به طوری که تعداد دفعانی که مجبور می شویم پردازنده را روشن کنیم کمینه شود.

مسئله Aمی دانیم که تعداد بازه های مربوط به هر کار حداکثر 2 است.
مسئله Bمسئله در حالت کلی. ( هیچ محدودیتی روی تعداد بازه ها وجود ندارد. )
حالا ثابت کنید که اگر الگوریتمی با زمان چند جمله ای وجود داشته باشد که مسئله ی A را حل کند، الگوریتمی با زمان چند جمله ای برای مسئله B وجود دارد.

منبع: دوره تابستانه المپیاد کامپیوتر 1385
 
آخرین ویرایش توسط مدیر
بالا