فایل ورد کامل مقاله علمی درباره طراحی الگوریتم موازی برای حل مسئله برچسب‌گذاری نقشه‌ها و بهبود کارایی محاسباتی

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

 فایل ورد کامل مقاله علمی درباره طراحی الگوریتم موازی برای حل مسئله برچسب‌گذاری نقشه‌ها و بهبود کارایی محاسباتی دارای ۱۰ صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد فایل ورد کامل مقاله علمی درباره طراحی الگوریتم موازی برای حل مسئله برچسب‌گذاری نقشه‌ها و بهبود کارایی محاسباتی  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی فایل ورد کامل مقاله علمی درباره طراحی الگوریتم موازی برای حل مسئله برچسب‌گذاری نقشه‌ها و بهبود کارایی محاسباتی،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از متن فایل ورد کامل مقاله علمی درباره طراحی الگوریتم موازی برای حل مسئله برچسب‌گذاری نقشه‌ها و بهبود کارایی محاسباتی :

مقدمه
یکی از کارهایی که تهیه کنندگان نقشه بهنگام تهیه نقشه انجام می دهند, برچسب گذاری نقاط نقشه است . بـدین معنی که در کنار هر نقطه اطلاعاتی راجع به آن نقطه می نویسند. اطلاعات باید به گونه ای برروی نقشه قرارگیرند که اطلاعات نقاط مختلف برروی هم قرار نگیرند. انجام خودکار برچسب گذاری نقشه توسط رایانه باعث سهولت و تسریع در انجام اینکار می شود. برای رایانه ای کردن این محاسبه نیاز داریم که برچسب گذاری نقشه را بصورت دقیق تر بیـان کنیم .

تعریف ۱. برچسب گذاری معتبر: در یک صفحه n نقطه جدا از هم داده شده اند. می خواهیم یک مجموعـه n تـایی از مربع ها به طول داشته باشیم بطوریکه هر نقطه کنج یک مربع (و نه بیشتر) قرار گیرد و کلیه مربع ها با یکـدیگر تداخل نداشته باشند(شکل ۱).
تعریف ۲. برچسب گذاری بهینه : در یک صفحه n نقطه جدا از هم داده شده اند. بـه ازای کلیـه اعـداد حقیقـی می خواهیم سوپریمم را بنحوی پیدا کنیم که یک برچسب گذاری معتبر داشته باشیم (شکل ۲).
در سال ۹۲، فورمن و واگنر نشان دادند که مساله برچسب گذاری بهینه NP-hard است [۱]. آنها همچنین الگوریتم تقریبی ارائه دادند که برچسب گذاری معتبری به اندازه حداقل نصف اندازه بهینه می یافت . همچنین آنهـا نشـان دادنـد که اگر آنگاه الگوریتم تقریبی با جواب چندجمله ای وجود ندارد که پاسخ بهتری را تضمین کنـد. پیچیـدگی الگوریتم آنها است . نتیجه مشابهی نیز در [۲] و [۳] گـزارش شـده اسـت . در سـال ۹۵ واگنـر و ولـف الگوریتم جدیدی ارائه دادند که زمان اجرا و کیفیت پاسخ الگوریتم قبلی را تضـمین مـی کـرد[۴]. نقطـه قـوت ایـن الگوریتم نسبت به الگوریتم قبلی این است که الگوریتم [۴] پاسخ های نزدیکتری به اندازه بهینه برچسب گـذاری (در عمل ) می دهد.
در این مقاله ما یک الگوریتم موازی مبتنی بر الگـوریتم [۴]، بـرای افـزایش سـرعت اجـرای برچسـب گـذاری ، ارائـه می دهیم . در بخش ۲ الگوریتم غیرموازی [۴] را بیان می کنیم . در بخـش ۳ الگـوریتم مـوازی را معرفـی مـی کنـیم و پیچیدگی آنرا حساب می کنیم و در بخش ۴ هم نتیجه گیری آمده است . این الگوریتم دارای افزایش سرعت برابـر بـا نسبت به الگوریتم غیر موازی است .
۲- الگوریتم غیرموازی برچسب گذاری نقشه ها
الگوریتمی که شرح آن در ادامه می آید، الگوریتمی است که توسـط واگنـر و ولـف در سـال ۱۹۹۵ معرفـی شـده است [۴]. ابتدا چند تعریف ، که در ادامه از آنها استفاده خواهیم نمود را بیان می کنیم .
تعریف ۳: برای هر نقطه مانند p واقع در نقشه ، بیانگر مربعی به طول است که نقطه p در جنوب غربـی ، جنوب شرقی ، شمال غربی یـا شـمال شـرقی آن قـرار دارد. یـک مقـدار حقیقـی اسـت .
همچنین pi را کاندیدای iام نقطه p می نامیم .
تعریف ۴: برچسب گذاری با اندازه برچسب عبارتست از برچسب گذاری معتبری که در آن کاندیـداها دارای طـول یکسان و برابر باشند.

۲-۱- ساختار الگوریتم غیر موازی
مرحله ۱: پیدا کردن کلیه اندازه های تداخل با ارزش .
مرحله ۲: انجام جستجوی دودویی برروی اندازه های تداخل بدست آمده از مرحله قبل . برای هر اندازه تداخل بررسی می کنیم که آیا پاسخی برای این اندازه برچسب وجود دارد یا خیر. اینکار را با اعمال سه گام زیر انجام می دهیم .
گام الف : پیش پردازش .
گام ب : حذف کاندیداهای غیر ممکن و سپس انجام آزمایش SAT-2 برروی زیر مجموعه باقی مانده .
گام ج : برای نقاطی که بیشتر از دو کاندیدا دارند، دو کاندیـدا را انتخـاب کـرده و سـپس توسـط SAT-2
بررسی می کنیم که آیا پاسخی وجود دارد یا خیر.

۲-۲- پیدا کردن اندازه های تداخل با ارزش
روشی که برای پیدا کردن اندازه های تداخل توسط ولف و واگنر معرفی شده است مبتنی بـر دو قضـیه اسـت کـه آنها را اثبات نموده اند[۴].
قضیه ۱: کلیه اندازه های تداخل با ارزش کوچکتر از اندازه برچسب بهینه هستند. بعبـارت دیگـر انـدازه هـای تداخل بی ارزش بزرگتر از اندازه برچسب بهینه هستند.
قضیه ۲: تنها اندازه های تداخل بین نقطه p و نزدیکترین هشت نقطه همسایه اش در هر یک از چهارسـمت نقطـه pبا ارزش هستند. شکل ۳ نمونه ای از اندازه تداخل بی ارزش را نشان می دهد.
طبق قضیه ۲، برای بدست آوردن اندازه های تداخل نقطه ای مانند p، تنها باید تعداد ثابتی از نزدیکترین همسایه های آن نقطه مورد بررسی قرار گیرند. در [۵] الگوریتمی برای پیدا کردن نزدیکترین k همسایه n نقطه ارائه شـده اسـت که دارای پیچیدگی زمانی است . مرتب سازی اندازه های تداخل نیز n log n زمان نیاز دارد. بنـابراین بدست آوردن اندازه های تداخل و مرتب سازی دارای پیچیدگی زمانی (O(n log n خواهد بود.

۲-۳- بدست آوردن اندازه برچسب بهینه
در این مرحله برای بدست آوردن اندازه برچسب بهینه , در فهرسـت انـدازه هـای تـداخل بـه جسـتجوی دودویـی می پردازیم . به ازای هر اندازه تداخل (که جستجوی دودویی آنرا مشخص می کند) سه گامی کـه در ادامـه مـی آیـد را انجام می دهیم .
۲-۳-۱- گام الف : پیش پردازش
برای کلیه کاندیداهای مانند pi بررسی می کنیم ، اگر حاوی یک نقطه دیگر باشـد، آنگـاه کاندیـدای pi را حذف می کنیم در غیر اینصورت فهرست جدیدی از اطلاعات تداخل بـرای کاندیـدای pi مـی سـازیم . ایـن فهرسـت شامل اندازه های تداخلی خواهد بود که از اندازه برچسب کوچکتر هستند.