پاورپوینت طراحی الگوریتم

بخشی از پاورپوینت

اسلاید 1 :

طراحی الگوریتم

اسلاید 3 :

مقدمه

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

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

اسلاید 4 :

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

1) پیچیدگی زمانی الگوریتم در حالت معمول
مانند ضرب ماتریس: Cm×k=Am×n×Bn×k
T(m,n,k)=m×n×k
و یا برای سادگی میگوییم: T(n)=n3

اسلاید 5 :

تحلیل پیچیدگی زمانی و مرتبه اجرایی
2) پیچیدگی زمانی الگوریتم در بدترین حالت
مانند جستجوی ترتیبی
W(n)=n
3) پیچیدگی زمانی الگوریتم در بهترین حالت
مانند جستجوی ترتیبی
B(n)=1

اسلاید 6 :

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

اسلاید 7 :

مرتبه الگوریتم
تعریف O )
برای یک تابع پیچیدگی مفروض f(n) ، مانند n، log n،
مجموعهای از توابع پیچیدگی g(n) است که برای آنها
به ازای یک ثابت حقیقی مثبت c
آنگاه یک عدد صحیح غیر منفی N وجود دارد
به قسمی که به ازای همه n≥N داریم g(n) ≤c×f(n)
روش نمایش: g(n) ϵ O(f(n))

اسلاید 8 :

مرتبه الگوریتم
نمایش به صورت دیاگرام:

اسلاید 9 :

د) مرتبه الگوریتم
در این شکل هرچند n2 + 10n در ابتدا مقادیری بیشتر از 2n2 دارند ولی برای n<=10 روند دیگری شکل میگیرد.

اسلاید 10 :

مرتبه الگوریتم
توابعی با مرتبه O(n^2) می توانند به شرح زیر باشند

اسلاید 11 :

مرتبه الگوریتم
تعریف Ω (Omega)
برای یک تابع پیچیدگی مفروض f(n) ، مانند n، log n
مجموعهای از توابع پیچیدگی g(n) است که برای آنها
به ازای یک ثابت حقیقی مثبت c
آنگاه یک عدد صحیح غیر منفی N وجود دارد
به قسمی که به ازای همه n≥N داریم g(n) ≥c×f(n)
روش نمایش: g(n) ϵ Ω(f(n)

اسلاید 12 :

مرتبه الگوریتم
نمایش به صورت دیاگرام:

اسلاید 13 :

مرتبه الگوریتم

اسلاید 14 :

مرتبه الگوریتم
تعریف Θ (Theta)
برای یک تابع پیچیدگی مفروض f(n) ، مانند n، log n
مجموعهای از توابع پیچیدگی g(n) است که برای آنها
به ازای ثابتهای حقیقی مثبت c و d
آنگاه یک عدد صحیح غیر منفی N وجود دارد
به قسمی که به ازای همه n≥N داریم:
d×f(n) ≥g(n) ≥c×f(n)
روش نمایش: g(n) ϵ Θ(f(n))

اسلاید 15 :

مرتبه الگوریتم
به عبارتی دیگر:
g(n) ϵ O(f(n)) AND Ω(f(n)
یعنی:

اسلاید 16 :

مرتبه الگوریتم
نمایش بهصورت دیاگرام:
نمایش بهصورت مجموعهای:

اسلاید 19 :

ویژگیهای O:
1- اگر g(n) بتواند به صورت مجموع تعداد محدودی از توابع دیگر نوشته شود، در این صورت آن تابعی که بیشترین رشد را دارد، O را مشخص میکند
f(n)=9logn+5(log n)3+3n2+2n3
2n3ϵO(n3)
f(n)ϵO(n3)

اسلاید 20 :

2- ویژگی ضرب
اگر g1ϵO(f1) و g2ϵO(f2) در آن صورت:
g1g2 ϵ ?
O(f1f2)

3- ویژگی جمع
اگر g1ϵO(f1) و g2ϵO(f2) در آن صورت:
g1+g2 ϵ ?
O(f1+f2)

4- ویژگی ضرب در مقدار ثابت
اگر gϵO(f) در آن صورت:
kg ϵ ?
O(f)