تحلیل ریاضی دامنه مسئله زمانبندی گرافهای جهتدار به عنوان یک مسئله NP-Hard و ارائه الگوریتمی برای نمونه گیری با توزیع یکنواخت
محل انتشار: هشتمین کنفرانس سالانه انجمن کامپیوتر ایران
سال انتشار: 1381
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 1,942
فایل این مقاله در 6 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ACCSI08_032
تاریخ نمایه سازی: 18 بهمن 1386
چکیده مقاله:
مسئله زمانبندی برنامههای موازی با ساختار گراف جهتدار روی سیستمهای چندپردازنده، یکی از مسایل پیچیده محاسباتی است . در این مسئله یک برنامه موازی با یک گراف جهتدار بیان
میشود و هدف اختصاص مناسب پردازندهها به گرههای گراف است به طوریکه زمان اجرای کل گرهها کمینه شود . یکی از مشکلات مسایل پیچیده محاسباتی، عدم دسترسی به اطلاعات و
شکل دامنهای است که تابع هدف مورد نظر قرار است در آن بهینه شود . این مسئله سبب میشود، در استفاده از الگوریتمهای جستجو مانند الکوریتم ژنتیک که در آن لازم است جمعیت اولیه
دارای توزیعی یکنواخت روی کل دامنه باشد، مشکلاتی بوجود آید، به این ترتیب که با روشهای موجود جمعیت اولیه در گوشهای از دامنه متمرکر شده و امکان و احتمال جستجوی همه
فضای دامنه را به میزان بسیار زیادی کاهش میدهد . در این تحقیق دامنه مسئله زمانبندی گرافهای جهتدار به صورت ریاضی تحلیل شده و بر اساس آن الگوریتمی دقیق برای انتخاب جمعیت
اولیه با توزیع یکنواخت بدست داده میشود . الگوریتم بدست آمده میتواند در همه مسایلی که ورودی آنها به نوعی گرافها هستند مفید باشد .
کلیدواژه ها:
نویسندگان
حسین میارنعیمی
دانشکده برق - دانشگاه علم و صنعت ایران
مجید نادری
دانشکده برق - دانشگاه علم و صنعت ایران
عادل رحمانی
دانشکده کامپیوتر - دانشگاه علم و صنعت ایران
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :