پاورپوینت پیچیدگی الگریتم ها

توجه : این پروژه به صورت فایل power point (پاور پوینت) ارائه میگردد

  پاورپوینت پیچیدگی الگریتم ها دارای ۲۱ اسلاید می باشد و دارای تنظیمات کامل در Power Point می باشد و آماده پرینت یا چاپ است

فایل پاور پوینت پاورپوینت پیچیدگی الگریتم ها  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

---

لطفا به نکات زیر در هنگام خرید

دانلود پاورپوینت پیچیدگی الگریتم ها

توجه فرمایید.

۱-در این مطلب، متن اسلاید های اولیه 

دانلود پاورپوینت پیچیدگی الگریتم ها

قرار داده شده است

۲-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید

۳-پس از پرداخت هزینه ، حداکثر طی ۱۲ ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد

۴-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد

۵-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار داده نشده است

---

بخشی از متن پاورپوینت پیچیدگی الگریتم ها :

اسلاید ۱ :

• هدف ما در این بحث شناسایی و مقایسه الگریتم های از لحاظ کارایی آنها و شناخت class های مختلف الگریتم ها از لحاظ پیچیدگی است.

تعبیر پیچیدگی

• پیچیدگی(پیچیدگی زمانی)متناسب با کارایی یک الگریتم در حل یک مساله است.
• پیچیدگی یک الگریتم متناسب با ماکزیمم تعداد عملگرهای محاسباتی مقدماتی(+-*/> <) مورد نیاز برای تبدیل ورودی یک الگریتم به خروجی آن با در نظر گرفتن همه حالتهای مساله است.
• پیچیدگی یکی از مفاهیم مهم در حل مسایل است زیرا دانستن محدودیت های یک الگریتم در حل یک مساله در مدت زمان قابل قبول یکی از مسایل مهم در ارزیابی الگریتم ها است.
• الگریتم هایی که کارایی بیشتری در حل مسایل بزرگ دارند مناسبترند.

اسلاید ۲ :

• اگر تعریف کنیم :

:sاندازه مساله – تعداد بیتهای داده های ورودی مساله

     به عنوان مثال در الگریتم های تئوری گراف اندازه مساله تابع تعداد راسها  یا تعداد یالها  یا هر دو است.

:C(s)تابع پیچیدگی

C(s)=4s+6     C(s)=2s2+7s+9 

• رتبه یک الگریتم با تابع پیچیدگی C(s) رفتار C(s) را وقتیs به بینهایت میل میکند بیان میکند.

تعریف:

üالگریتم  cدارای رتبه چند جمله ای است اگر c یک تابع چند جمله ای باشد.

üالگریتم  cدارای رتبه نمایی است اگر c یک تابع نمایی باشد.

üالگریتم  cدارای رتبه فاکتوریل است اگر c یک تابع فاکتوریل باشد.

ü

ü

اسلاید ۳ :

• پیچیدگی در بد ترین حالت(worst-case complexity):

     بر حسب ماکزیمم تعداد محاسبات مورد نیاز برای حل مساله با در نظر گرفتن همه حالت های آن محاسبه میشود.

• پیچیدگی انتظاری(expected time complexity):

     بر حسب میانگین تعداد محاسبات مورد نیاز برای حل مساله با در نظر گرفتن همه حالت های آن محاسبه میشود.

تعریف:

       اگر f و g به ترتیب توابع پیچیدگی ۲ الگریتم a1 و a2 باشند، میگوییم f نسبت به g از رتبه بالاتری برخوردار نیست.

• اگر C1=O(c2), C2=O(c1)باشد رتبه هر دو یکسان خواهد بود.

اسلاید ۴ :

• الگریتم های polynominalمعمولا الگریتم های خوب نامیده میشوند زیرا با افزایش ابعاد مساله ، تعداد محاسبات مورد نیاز برای حل مساله در مقایسه با سایر رتبه ها از رشد کمتری برخوردار است.

          به عبارت دیگر همواره مقداری برای  x0   وجود دارد که به ازای x>x0  الگریتم های polynominal  بهتر از الگریتم های نمایی و فاکتوریل عمل میکنند.

• مسایلی که برای آن هیچ الگریتم چند جمله ای وجود ندارد مساله سخت(intractable) می نامیم.
• Problem P-

  یک مساله Problem P-نامیده می شود اگر حداقل یک الگریتم برای حل آن وجود داشته باشد بگونه ای که کران بالای زمان حل مساله از یک رتبه Polynominal از اندازه ورودی های مساله باشد.

• Problem NP-

یک مساله  را Problem NP-می نامیم اگر اثبات درستی آن (پاسخ مثبت به آن ) به صورت یک مساله P قابل تطبیق باشد.هر p  یک  NP نیز هست.

مثال : تعیین همیلتونی بودن یک گراف

  مساله فروشنده دوره گرد

  مسایل برنامه ریزی خطی

اسلاید ۵ :

• Problem NP Complete-

  مساله ای که الگریتم حل آن قابل انتقال و ترجمه  برای هر مساله NP  دیگری نیز باشدNP hard  نامیده میشود.

  اگر مساله ای  هم NP  و هم NP hard  باشد NP Complete نامیده میشود.

مثال:  تعیین همیلتونی بودن گراف و دیاگراف

       مساله فروشنده دوره گرد

اسلاید ۶ :

• مکان یابی از جمله مسایلی است که باید در مراحل اولیه طراحی تسهیلات مورد توجه قرار گیرد زیرا مکان مناسب برای یک واحد کارایی و اثربخشی را افزایش داده و منجر به بهبود در کل سیستم می گردد.
• در این بحث ما مکان یابی را تحت عنوان کلی تری به نام مدیریت لجستیک بررسی می کنیم.
• مدیریت لجستیک ، مدیریت فعالیت های توزیع و حمل و نقل(از تامین کننده تا مشتریان)در مقیاس بالا با هدف جابجایی مقدار مناسب از مواد مناسب در زمان مناسب و هزینه مناسب با استفاده از بهترین روشهاست.

اسلاید ۷ :

• طبقه بندی مسایل مدیریت لجستیک

  -مساله مکان یابی: تعیین مکان یک یا چند تسهیل در یک یا چند مکان بالقوه

  –مساله تخصیص : فرض بر این است که تعداد تسهیلات و مکان آنها و همچنین مقدار کالای تقاضاشده توسط هر مشتری ،ظرفیت هریک از تسهیلات و هزینه خدمت دهی آنها مفروض است .دراین حالت مساله تعیین مقدار کالایی است که هریک از تسهیلات باید به هر یک از مشتریان ارسال کند.

  -مساله مکانیابی- تخصیص : علاوه بر مقدار کالایی که هر مشتری از هر تسهیل تامین می کند ،محل قرار گیری و ظرفیت آنها را هم مشخص می کند.

• انواع مکانیابی تسهیلات:

     ۱-تک وسیله ای   

     ۲- چند وسیله ای

اسلاید ۸ :

انواع مکانیابی تسهیلات:

• مکانیابی گسسته: مکانهای ممکن برای یک واحد محدود باشد.(اکثر مسایل دنیای واقی )
• مکانیابی پیوسته : مکانهای ممکن برای یک واحد نامحدود باشد.

فاکتورهای موثر در تصمیمات مربوط به مکانیابی

• در عمل فاکتورهای مختلفی با اهمیت های متفاوت در تصمیمات مربوط به مکانیابی موثرند:

.۱نزدیکی به منابع مواد اولیه

.۲هزینه و میزان دسترسی به انرژی و تاسیسات ونیروی انسانی

.۳قوانین دولتی در سطوح مختلفمرکزی ، محلی و منطقه ای

.۴مالیات در سطوح مختلف

.۵بیمه

.۶هزینه های زمین و ساخت

.۷نزدیکی به سیستم حمل ونقل

.۸قوانین زیست محیطی

.۹آب وهوا

.۱۰نزدیکی به مشتریان

اسلاید ۹ :

روشهای حل مسایل مکانیابی در فضای گسسته

  تحلیل های کیفی

روش رتبه بندی موقعیت ها

مراحل رتبه بندی:

.۱لیست نمودن تمامی عوامل موثر در مکانیابی

.۲وزن دهی به هر یک از عوامل

.۳به هر مکان امتیازی بین ۰ تا ۱۰۰ داده شود

.۴امتیاز وزنی هر عامل محاسبه شود

.۵مجموع امتیاز وزنی هر مکان محاسبه و مقایسه شود.

• در این روش ،تصمیم گیری براساس امتیاز وزنی است که این امتیازها به طور Subjective محاسبه شده اند. اما در تصمیم نهایی باید عوامل Objectiveمثل حمل ونقل و هزینه های عملیاتی نیز لحاظ شود.

اسلاید ۱۰ :

تحلیل های کمی

• مدل حمل و نقل

  این مدل معمولابرای تعیین توزیع بهینه کالا بین مجموعه ای از کارخانه های مشخص و مجموعه ای از مشتریان مشخص مورد استفاده قرار می گیرد با هدف مینیمم کردن کل هزینه حمل ونقل کالا بین کارخانه ها و مشتریان .

q  سوال: چگونه می توان با استفاده از مدل حمل ونقل برای انتخاب مکان بهینه بین چند محل استفاده نمود؟

در یک شبکه توزیع که m کارخانه و n مشتری داریم.بدلیل افزایش تقاضا نیاز به تاسیس یک واحد جدید داریم.کارخانه درp محل جدید می تواند قرار گیرد.برای تعیین مکان بهینه از بین این  pمکان می توان:

  Pمدل حمل ونقل تهیه کنیم که هر یک شاملn مشتری و  m+1کارخانه است .از بین آنها بهترین مدل با کمترین هزینه مشخص شده و مکان بهینه و نحوه توزیع بهینه کالاها مشخص می شود.