سال انتشار: ۱۳۸۴

محل انتشار: یازدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۸

نویسنده(ها):

سیدعبدالرضا طاهایی –
امیرحسین جهانگیر –

چکیده:

افراز سیستم به سخت افزار و نرم افزار یکی از مراحل اساسی در طراحی توأمان سیستمها می باشد . افراز به معنای تعیین سخت افزاری بودن یا نرم افزاری بودن اجزای سیستم است به گونه ای که بعضی شرایط بهینه یا برآورده شوند . مسئله افراز در بعضی توصیفا ت یک مسئلهNP-Hard و در یک توصیف با نگاشت آن به مسئله حداکثر شارش در تئوری گراف ، یک مسئلهP شمرده می شود و الگوریتمهایی که برای حل آن به کار می روند دارای پیچیدگی بالاتر از O(n3 می باشند . این مقاله در صدد است تا با پیش بینی پاسخ سراسری با استفاده از اطلاعات محلی(تمایل پاسخهای منفرد به چگونگی پیاده سازی )، نقطه آغازین مناسبی جهت شتاب بخشیدن به روشهای متداول مکاشفه ای ارایه نماید . با توجه به کاهش کیفیت جواب در قبال افزایش فضای مسئله در الگوریتمهای مکاشفه ای، تعیین نقطه آغاز می تواند تاثیر چشمگیری در تو انمندی روش داشته باشد . میزان توانمندی الگوریتم مکاشفه ای پس از تعین نقطه شروع نسبت به روشهای متداول مسئله افراز در مجموعه ای گسترده از گرافهای تصادفی ارایه شده است