بخشی از پاورپوینت
اسلاید 1 :
Fou datio s of algorithms
By: Richard eapolita ; Kumarss aimipour
ترجمه: سید حجت ا... جلیلی
I troductio to algorithms
By:Thomas Corme ; Charles Leiserso ; Ro ald Rivest; Clifford Stei
ترجمه: گروه مهندسی پژوهشی خوارزمی
Computer algorithms
By: Ellis Horowitz; Sartaj Sah i; Sa guthevar Rajasekara
ترجمه: امیر علیخانزاده
طراحی الگوریتم ها
نوشته: دکتر محمود نقیب زاده
اسلاید 2 :
الگوریتم: مجموعه محدودی ازدستورالعملها که اگر دنبال شوند حاصل کار موجب حل مسأله خاصی می شود. شرایط:
¨ورودی
¨خروجی
¨قطعیت
¨محدودیت
¨کارایی
اعتباردهی الگوریتم: لازم است که یک الگوریتم به ازاء تمام مقادیر معتبرورودی تست وجواب صحیح برای آن دریافت شود.
آزمون برنامه:
¨اشکال زدایی: اجرا بر روی مجموعه داده های نمونه و تعیین نادرست بدن برنامه
¨سنجش اجرا (ارزیابی کارایی): اجرای برنامه صحیح برروی مجموعه ای از داده ها و اندازه گیری زمان و حافظه لازم
اسلاید 3 :
مثال: دنباله فیبوناچی 0,1,1,2,3,5,8,13,…
fo=0
f1=1
f =f -1+f -2 , ³2
با روش بازگشتی:
i t fib(i t )
{ if ( <=1)
retur ;
else
retur fib( -1)+fib( -2);
}
اسلاید 4 :
سری فیبوناچی با روش تکرار:
i t fib(i t )
{
i t f1=0 , f2=1;
if ( <=1)
retur ;
else
for (i=2;i<= ;i++) T( ) µ
{ f2=f1+f2;
f1=f2;
}
retur f2;
}
اسلاید 5 :
کارایی الگوریتم به عنوان تابعی از اندازه ورودی با تعیین تعداد دفعات انجام برخی عملیات اصلی تعیین می شود.
عمل مبنایی: دستور یا دستوراتی که کل عملیات انجام شده توسط الگوریتم با تعداد دفعاتی که این دستورات در الگوریتم اجرا می شوند متناسب باشند.
مثال: جمع عناصر آرایه
i t sum(i t , i t s[ ])
{
i t i,r=0;
for(i=1;i<= ;i++)
r+=s[i];
retur r;
}
اسلاید 6 :
1) 3ÎW( 2)
c=1, 0=1, ³ 1 : 3 ³ 1´ 2
2)6´2 + 2ÎO(2 )
c=7, 0=4 , ³ 4 : 6´2 + 2 £ 7´ 2 :
3) Ïq( 2)
برهان خلف: ÎW( 2) Þ ³c 2 , £1/c
بنابراین نامساوی برای همه مقادیر ³ 0 درست نمی باشد.
4)2 22 + lg Îq( 22 )
5) ! ÎO( )
6)6 3/(lg +1) ÎO( 3)
