مساله سیستم عامل

[tiberium]

این مساله مربوط به NP هست که ایجا توضیح دادم
http://www.sampadia.com/forum/index.php/topic,97353.0.html
اما چون حلش صرفا ایده هست و تقریبا دانش خاصی نمی خواد اینجا مطرح کردم.

فرض کنید یه سیستم عامل دارید .ما به این سیستم عامل یه سری task میدیم.برای هر task سه تا مولفه تعریف شده
یکی اینکه از چه زمانی به بعد میتونه شروع بشه...قبل از چه زمانی باید تموم شده باشه....و اینکه چقدر طول میکشه
مثلا یه taski از 5 به بعد میتونه شروع بشه....قبل 20 هم باید تموم شده باشه.3 ثانیه هم طول میکشه
این کار رو هم میشه از 5 تا 8 انجام داد..هم از 6 تا 9 و حالت های دیگه.
n تا task به این سیستم عامل داده میشه.میخوایم بدونیم آیا میتونیم یه الگوریتمی طراحی کنیم که تو زمان چند جمله ای بگه آیا میشه تمامی این کار ها رو طبق شرایطی که گفته انجام بدیم یا نه. البته این جوابش نه هست و می خوایم NP بودنشو ثابت کنیم.
و از مساله subset sum هم استفاده کنید. ( توضیح این مساله تو همون تاپیکی که بالا دادم هست.) بعنی باید یه روشی ارائه بدین که اگر این مساله رو بتونیم حل کنیم subset sum هم میتونیم با همین راه حل کنیم

 

[tiberium]

پاسخ : مساله سیستم عامل

فکر کنید یکم
یه ایده ای چیزی.... حتما که نباید درست باشه! هرچی به ذهنتون میاد بگید

 

[Parham MLK]

پاسخ : مساله سیستم عامل

من خیلی دیر سر میزنم ببخشید!

مث دفه‌ی قبل، فرض میکنیم الگوریتم خفنی پیدا شده که این مسئله رو با اُردر چندجمله‌ای حل میکنه!
حالا subset sum رو در نظر بگیرید:

n تا عدد داریم. می خوایم بدونیم آیا میشه یه عده از اینا رو انتخاب کرد که جمعشون دقیقا بشه K یا نه.

این مسئله یه K داره و یه n.
ما میایم تو مسئله‌ی سیستم عامل، زمان شروع همه‌ی n تا taskمون رو میدیم 0 و زمان پایانشون رو میدیم K.
حالا به مدت زمان انجام هر کدوم از taskها یکی از n تا عدد مسئله‌ی subset sum رو میدیم!!

خب دیگه واضحه. نه!؟

با تشکر از وقتی که در اختیار من قرار دادید!

 

[tiberium]

پاسخ : مساله سیستم عامل

من خیلی دیر سر میزنم ببخشید!

مث دفه‌ی قبل، فرض میکنیم الگوریتم خفنی پیدا شده که این مسئله رو با اُردر چندجمله‌ای حل میکنه!
حالا subset sum رو در نظر بگیرید:این مسئله یه K داره و یه n.
ما میایم تو مسئله‌ی سیستم عامل، زمان شروع همه‌ی n تا taskمون رو میدیم 0 و زمان پایانشون رو میدیم K.
حالا به مدت زمان انجام هر کدوم از taskها یکی از n تا عدد مسئله‌ی subset sum رو میدیم!!

خب دیگه واضحه. نه!؟

با تشکر از وقتی که در اختیار من قرار دادید!

مشکل اینجاست که برنامه ای که داریم میگه آیا می تونه همه ی این task هارو طبق شرایط انجام بده یا نه.
الان طبق چیزی که میگی اگر همه ی task ها رو بگیم از 0 تا k قطعا یه سری از task ها رو نمیتونه انجام بده. چون جمع وقت این کارها میتونه از k بیشتر باشه

ممنون از این که وقت گذاشته حدود راه حل رو گرفتی.باید بازم روش ایده بزنی