دسته: پاورپوینت
بازدید: 35 بار
فرمت فایل: ppt
حجم فایل: 15 کیلوبایت
تعداد صفحات فایل: 15
نوع فایل: پاورپوینت (قابل ویرایش)
قسمتی از متن پاورپوینت :
تعداد اسلاید : 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 ) ؟
توجه: متن بالا فقط قسمت کوچکی از محتوای فایل پاورپوینت بوده و بدون ظاهر گرافیکی می باشد و پس از دانلود، فایل کامل آنرا با تمامی اسلایدهای آن دریافت می کنید.