پاورپوینت تحلیل الگوریتمها (pptx) 17 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 17 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
تحليل الگوريتم ها
مسائل و تمرين ها
تحليل الگوريتم ها
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 ) ؟
6 . ثابت كنيد زمان اجراي يك الگوريتم Θ(g(n)) است اگر و فقط اگر زمان اجراي آن در بدترين حالت O(g(n)) و زمان اجراي آن در بهترين حالت Ω(g(n)) باشد .
2n
2n
n+1
2
