دانلود فایل پاورپوینت نقد و بررسی پیچیدگی محاسباتی

PowerPoint قابل ویرایش
33 صفحه
8900 تومان

لطفا به نکات زیر در هنگام خرید دانلود فایل پاورپوینت نقد و بررسی پیچیدگی محاسباتی توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود فایل پاورپوینت نقد و بررسی پیچیدگی محاسباتی قرار داده شده است

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

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

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

اسلاید ۱ :

در مطالعه ی الگوریتم ها و محاسبت بحثی راجع به اینکه وقتی مه این الگوریتم ها عملا بر روی کامپیوتر انجام می شوند نکرده ایم

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

در این فصل ما به زبان ساده نظریه پیچیدگی محاسبات را تشریح می کنیم.بحث ما محدود به پیچیدگی زمانی خواهد بود اگرچه نتایج مشابهی در خصوص پیچیدگی فضا وجود دارد.

اسلاید ۲ :

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

ااما تاکید بر روی مسائل اساسی باید باشد و از مسائل جنبی باید صرف نظر کرد.

اسلاید ۳ :

برای بحث در خصوص پیچیدگی محاسباتی  فرضیات زیر را در نظر می گیریم:

مدل مورد مطالعه ی ما ماشین تورینگ خواهد بود که در زیر آنرا توضیح می دهیم.

اندازه ی مساله را با nنشان می دهیم بنابراین در مسئله مرتب سازیn,تعداد عناصر لیست است اگر چه اندازه ی مساله همیشه به این آسانی قابل لمس نیست اما همواره آنرا مرتبط با یک عدد صحیح می کنیم.

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

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

اسلاید ۴ :

ابتدا به مفهوم زمان در ماشین تورینگ می پردازیم.هر حرکت ماشین تورینگ را یک واحد زمانی در نظر می گیریم و لذا زمان یک محاسبه ,تعداد حرکاتی است که انجام می شود.همانگونه که گفته شد می خواهیم ببینیم که نیازهای محاسباتی با افزایش اندازه ی مساله چگونه رشد می کند.البته معمولا بدترین حالت را در نظر می کیریم.وقتی که می گوئیم  که محاسبه ای دارای پیچیدگی زمانی T(n) است منظور ما اینست که محاسبه هر مسئلا ای با اندازه nبا انجام T(n)حرکت  توسط یک ماشین تورینگ به انجام می رسد.

اسلاید ۵ :

نکته ی دیگر که باید قبل از بدست آوردن نتایج بیشتر مطرح شود اینست که به محاسبه بر روی مسائل بزرگ با نیازهای محاسباتی بالا علاقه مندیم.در نتیجه ما nرا بسیار بزرگ در نظر میئ گیریم .

بنابراین ماشینی که یک محاسبه را درمدت n² انجام می دهد خیلی کاراتر از ماشینی کهn²+nزمان  می برد نیست و وقتی که n بزرگ باشد فقط عوامل موثرتر در نظر گرفته می شوند.هم چنین مفهوم واحد زمانی تعریف شده نیست بنابراین می تواند یک میلی ثانیه,یک ثانیه و یا یک سال باشد.

اسلاید ۶ :

می گوئیم که تابع f(n) از نوع g(n) است اگر مقدار ثابت c به طوری که

 c                  f(n) / g (n)

برای  تمامی n ها صحت اشته باشد.برای اینکه بگوئیم f از رده g(order) است می نویسیم

f ( n) =O(g(n))                  

این نماد مناسب و سنتی است ولی غیرمحکم و خطرناک است.

اسلاید ۷ :

علامت = در اینجا نباید به عنوان تساوی تفسیر شود. و محاسباتی مانند

O(n)+O(n)=2 O(n)        

درست نیست و ممکن است که منجر به نتایج غیرصحیح شود.گرچه نماد O به درستی استفاده شود می تواند در سنجش پیچیدگی مفید واقع شود.

اسلاید ۸ :

۱انتخاب الگوریتم چه تاثیری بر کارایی مرتب سازی دارد؟

نشان دهید که نتایج زیر درست است

 )n²+۵ log n = O(n²)                  الف

=O(n!)                             ب

) n!=O(n)                             ج

اثبات منید که اگر f(n)=O(g(n))وg(n)=O(h(n))باشد آنوقت f(n)=O(h(n)) است.

نشان دهید که اگرf (n)=O(n²) وg (n)=O(n³)باشد آنوقت

f ( n)+g(n)=O(n³)                      و

f ( n)g(n)=O(n^6)                       است.

در تمرین ۴ آیا درست است که g(n)/f(n)=O(n)باشد؟

فرض کنید که f ( n)=2n²+nوg (n)=O(n²)باشد.درد بحث زیر چه اشکالی وجود دارد.

nf (n)=O(n²)+O(n)

nبه طوریکه

nf (n)-g(n)=O(n²)+O(n)-O(n²)

nو بنابراین

nf ( n)-g( n)=O(n)

اسلاید ۹ :

زمانی که صحبت از پیچیدگی می شود دیگر تساوی بین انواع ماشینهای تورینگ قابل طرح نیست.

اسلاید ۱۰ :

 درمثال ۹-۴یک ماشین تورینگ یک نواره برای زبان

L = {a b : n ۱}ساخته شد.با نکاهی به الگوریتم .ورد استفاده در می یابیم که برای W= a bتقریبا ۲nقدم برای تطبیق هر aباbمربوط لازم است.

بنابراین کل محاسبه,زمانی معادل با O (n²)می برد.

ااما با یک ماشین دو نواره می توانیم الگوریتم دیگری را استفاده نمائیم.ابتدا همه aها را روی نوار دوم کپی می کنیم سپس آنها  را با bروی نوار اول تطبیق می دهی.هر دو عمل کپی و تطبیق می تواند در زمان O(n)انجام شود.بنابراین,ماشین دو نواره دارای پیچیدگی زمانی n است.

مطالب فوق فقط متون اسلاید های ابتدایی پاورپوینت بوده اند . جهت دریافت کل ان ، لطفا خریداری نمایید .
PowerPointقابل ویرایش - قیمت 8900 تومان در 33 صفحه
سایر مقالات موجود در این موضوع
دیدگاه خود را مطرح فرمایید . وظیفه ماست که به سوالات شما پاسخ دهیم

پاسخ دیدگاه شما ایمیل خواهد شد