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

پاورپوینت پاورپوینت پیچیدگی الگریتم ها (pptx) 20 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 20 اسلاید

قسمتی از متن PowerPoint (.pptx) :

پیچیدگی الگریتم ها هدف ما در این بحث شناسایی و مقایسه الگریتم های از لحاظ کارایی آنها و شناخت 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 به ترتیب توابع پیچیدگی 2 الگریتم 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 نامیده میشود. مثال: تعیین همیلتونی بودن گراف و دیاگراف مساله فروشنده دوره گرد مکان یابی مکان یابی از جمله مسایلی است که باید در مراحل اولیه طراحی تسهیلات مورد توجه قرار گیرد زیرا مکان مناسب برای یک واحد کارایی و اثربخشی را افزایش داده و منجر به بهبود در کل سیستم می گردد. در این بحث ما مکان یابی را تحت عنوان کلی تری به نام مدیریت لجستیک بررسی می کنیم. مدیریت لجستیک ، مدیریت فعالیت های توزیع و حمل و نقل(از تامین کننده تا مشتریان)در مقیاس بالا با هدف جابجایی مقدار مناسب از مواد مناسب در زمان مناسب و هزینه مناسب با استفاده از بهترین روشهاست.