نوع فایل: پاورپوینت (قابل ویرایش)
قسمتی از متن پاورپوینت :
تعداد اسلاید : 15 صفحه
تحلیل الگوریتم ها مسائل و تمرین ها تحلیل الگوریتم ها 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 a . زمان اجرای مجانبی این قطعه كد برای قانون Horner چیست ؟
b . شبه كدی برای پیاده سازی الگوریتم ارزشیابی ساده چند جمله ای بنویسید
كه هر جمله از چند جمله ای را از ابتدا محاسبه می كند . زمان اجرای این
الگوریتم چیست ؟ در مقایسه با قانون Horner چگونه است ؟
c . ثابت كنید كه ثابت زیر یك ثابت حلقه برای حلقه while در خطوط 3- 5 است .
y = ∑ a x
n-(i+1) k =0 k+i+1 k وارونگی 1 . چه آرایه ای با عناصر مجموعه {1,2,…,n }
بیشترین وارونگی ها را دارد ؟ این آرایه چند وارونگی دارد ؟
2 . چه رابطه ای بین زمان اجرای مرتب سازی درجی و تعداد وارونگی ها درآرایه ورودی وجود دارد ؟
3 . الگوریتمی ارائه دهید كه تعداد وارونگی ها در یك جایگشت روی n عنصر را
در بدترین حالت در زمان Θ(nlgn) تعیین كند . رشد توابع 1 . فرض كنید
f(n) و g(n) بطور مجانبی توابع غیرمنفی باشند . با استفاده از تعریف اصلی
نماد Θ ، ثابت كنید كه max(f(n),g(n)) = Θ(f(n) + g(n))
2 . توضیح دهید چرا عبارت ” زمان اجرای الگوریتم A حداقل O(n ) است ” ، بی معنی است ؟
3 . آیا 2 = O(n ) ؟ آیا 2 = O(2 ) ؟
4 . نشان دهیدهر ثابت حقیقی a وb كه b>0 ،
( n+a ) = Θ(n ) n+1 2n 2 2n 2 b b 5 . آیا 2 = O(n ) ؟ آیا 2 = O(2 ) ؟
توجه: متن بالا
فقط قسمت کوچکی از محتوای فایل پاورپوینت بوده و بدون ظاهر گرافیکی می باشد
و پس از دانلود، فایل کامل آنرا با تمامی اسلایدهای آن دریافت می کنید.
