لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : .ppt ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : 15 اسلاید
قسمتی از متن .ppt :
تحلیل الگوریتم ها
مسائل و تمرین ها
تحلیل الگوریتم ها
1 . با استفاده ازاستقرای ریاضی نشان دهید زمانی که n توان صحیحی از 2 است جواب رابطه بازگشتی زیربرابرچیست ؟
اگر n = 2 2
اگربرای k>1 ، n = 2 T(n) = 2T(n/2) + n
2 . مرتب سازی درجی می تواند به صورت یک روال بازگشتی بشرح زیر بیان شود . به منظور مرتب کردن A[1..n] ، آرایه A[1...n-1] را بطور بازگشتی مرتب کرده و سپس A(n) را درآرایه مرتب شده A[1..n-1] درج می کنیم . یک رابطه بازگشتی برای زمان اجرای این نسخه بازگشتی از مرتب سازی درجی بنویسید .
k
مرتب سازی درجی روی آرایه های کوچک در مرتب سازی ادغام
1 . یک تغییر در مرتب سازی ادغام را در نظر بگیرید که درآن n/k زیر لیست با طول k با استفاده از مرتب سازی درجی ، مرتب شده و سپس با استفاده از فرایند ادغام استاندارد ادغام می شوند و k مقداری است که باید مشخص شود .
a . نشان دهید که n/k زیر لیست هر یک با طول k می توانند بوسیله مرتب سازی درجی در بدترین حالت در زمان Θ(n/k) مرتب شوند.
b . نشان دهید که زیر لیست ها می توانند دربدترین حالت درزمان Θ(nlg(n/k)) ادغام شوند .
درستی قانون Horner
قطعه کد زیر قانون horner را برای ارزشیابی چند جمله ای
P(x) = ∑ a x
= a + x(a + x(a +…+x(a + xa )…)),
با ضرایب داده شده a ,a ,…, a و یک مقدار برای x پیاده سازی می کند :
1 y ← 0
2 i ← n
3 While i ≥ 0
4 do y ← a + x . y
5 i ← i -1
n
k =0
k
k
0
1
n-1
n
i
0
1
n
2
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : .ppt ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : 20 اسلاید
قسمتی از متن .ppt :
1
طراحی الگوریتمها
میان ترم 8
پایان ترم 9
تمرین 3
حضور 1
2
منابع
Foundations of algorithms
By: Richard Neapolitan; Kumarss Naimipour
ترجمه: سید حجت ا... جلیلی
Introduction to algorithms
By:Thomas Cormen; Charles Leiserson; Ronald Rivest; Clifford Stein
ترجمه: گروه مهندسی پژوهشی خوارزمی
Computer algorithms
By: Ellis Horowitz; Sartaj Sahni; Sanguthevar Rajasekaran
ترجمه: امیر علیخانزاده
طراحی الگوریتم ها
نوشته: دکتر محمود نقیب زاده
3
مقدمه
الگوریتم: مجموعه محدودی ازدستورالعملها که اگر دنبال شوند حاصل کار موجب حل مسأله خاصی می شود. شرایط:
ورودی
خروجی
قطعیت
محدودیت
کارایی
اعتباردهی الگوریتم: لازم است که یک الگوریتم به ازاء تمام مقادیر معتبرورودی تست وجواب صحیح برای آن دریافت شود.
آزمون برنامه:
اشکال زدایی: اجرا بر روی مجموعه داده های نمونه و تعیین نادرست بدن برنامه
سنجش اجرا (ارزیابی کارایی): اجرای برنامه صحیح برروی مجموعه ای از داده ها و اندازه گیری زمان و حافظه لازم
4
اهمیت توسعه کارایی
مثال: دنباله فیبوناچی 0,1,1,2,3,5,8,13,…
fo=0
f1=1
fn=fn-1+fn-2 , n2
با روش بازگشتی:
int fib(int n)
{ if (n<=1)
return n;
else
return fib(n-1)+fib(n-2);
}
f(5)
f(3)
f(4)
f(1)
f(2)
f(0)
f(1)
f(3)
f(1)
f(2)
f(0)
f(1)
f(2)
f(0)
f(1)
لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : .ppt ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : 20 اسلاید
قسمتی از متن .ppt :
1
طراحی الگوریتمها
میان ترم 8
پایان ترم 9
تمرین 3
حضور 1
2
منابع
Foundations of algorithms
By: Richard Neapolitan; Kumarss Naimipour
ترجمه: سید حجت ا... جلیلی
Introduction to algorithms
By:Thomas Cormen; Charles Leiserson; Ronald Rivest; Clifford Stein
ترجمه: گروه مهندسی پژوهشی خوارزمی
Computer algorithms
By: Ellis Horowitz; Sartaj Sahni; Sanguthevar Rajasekaran
ترجمه: امیر علیخانزاده
طراحی الگوریتم ها
نوشته: دکتر محمود نقیب زاده
3
مقدمه
الگوریتم: مجموعه محدودی ازدستورالعملها که اگر دنبال شوند حاصل کار موجب حل مسأله خاصی می شود. شرایط:
ورودی
خروجی
قطعیت
محدودیت
کارایی
اعتباردهی الگوریتم: لازم است که یک الگوریتم به ازاء تمام مقادیر معتبرورودی تست وجواب صحیح برای آن دریافت شود.
آزمون برنامه:
اشکال زدایی: اجرا بر روی مجموعه داده های نمونه و تعیین نادرست بدن برنامه
سنجش اجرا (ارزیابی کارایی): اجرای برنامه صحیح برروی مجموعه ای از داده ها و اندازه گیری زمان و حافظه لازم
4
اهمیت توسعه کارایی
مثال: دنباله فیبوناچی 0,1,1,2,3,5,8,13,…
fo=0
f1=1
fn=fn-1+fn-2 , n2
با روش بازگشتی:
int fib(int n)
{ if (n<=1)
return n;
else
return fib(n-1)+fib(n-2);
}
f(5)
f(3)
f(4)
f(1)
f(2)
f(0)
f(1)
f(3)
f(1)
f(2)
f(0)
f(1)
f(2)
f(0)
f(1)