بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

تحليل الگوريتم ها

 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] درج مي كنيم . يك رابطه بازگشتي براي زمان اجراي اين نسخه بازگشتي از مرتب سازي درجي بنويسيد .

اسلاید 2 :

مرتب سازي درجي روي آرايه هاي كوچك در مرتب سازي ادغام

1 . يك تغيير در مرتب سازي ادغام را در نظر بگيريد كه درآن n/k زير ليست با طول k با استفاده از مرتب سازي درجي ، مرتب شده و سپس با استفاده از فرايند ادغام استاندارد ادغام مي شوند و k مقداري است كه بايد مشخص شود .

 a . نشان دهيد كه n/k زير ليست هر يك با طول k مي توانند بوسيله مرتب سازي درجي در بدترين حالت در زمان Θ(n/k)  مرتب شوند.

 b . نشان دهيد كه زير ليست ها مي توانند دربدترين حالت درزمان Θ(nlg(n/k)) ادغام شوند . 

اسلاید 3 :

 درستي قانون 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  

اسلاید 4 :

 a . زمان اجراي مجانبي اين قطعه كد براي قانون Horner چيست ؟

 b . شبه كدي براي پياده سازي الگوريتم ارزشيابي ساده چند جمله اي بنويسيد كه هر جمله از چند جمله اي را از ابتدا محاسبه مي كند . زمان اجراي اين الگوريتم چيست ؟ در مقايسه با قانون Horner چگونه است ؟

 c . ثابت كنيد كه ثابت زير يك ثابت حلقه براي حلقه while در خطوط 3- 5 است .

y = ∑ a        x

اسلاید 5 :

وارونگي

 1 . چه آرايه اي با عناصر مجموعه {1,2,…,n }  بيشترين وارونگي ها را دارد ؟ اين آرايه چند وارونگي دارد ؟

 2 . چه رابطه اي بين زمان اجراي مرتب سازي درجي و تعداد وارونگي ها درآرايه ورودي  وجود دارد ؟

 3 . الگوريتمي ارائه دهيد كه تعداد وارونگي ها در يك جايگشت روي n عنصر را در بدترين حالت در زمان Θ(nlgn)  تعيين كند . 

اسلاید 6 :

رشد توابع

 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  )

اسلاید 7 :

 5 . آيا 2    = O(n  )  ؟ آيا 2   = O(2   ) ؟

 6 . ثابت كنيد زمان اجراي يك الگوريتم  Θ(g(n))  است اگر و فقط اگر زمان اجراي آن در بدترين حالت O(g(n))  و زمان اجراي آن در بهترين حالت Ω(g(n))  باشد .

 

اسلاید 8 :

نمادهاي استاندارد و توابع عمومي

 1 . نشان دهيد اگر f(n) و g(n) توابع صعودي يكنواخت باشند ، آنگاه توابع f(n) + g(n) وf(g(n)) نيز صعودي يكنواخت هستند ، و اگر علاوه بر آن f(n) و g(n) غير منفي نيز باشند ، آنگاه f(n). g(n)  صعودي يكنواخت است .

 2 . آيا تابع ┌ lg n ┐!  بطور چند جمله اي محدود است ؟ آيا تابع ┌ lg lgn ┐!  بطور چند جمله اي محدود مي شود ؟

 3 . كدام يك بطور مجانبي بزرگتر است :

                                                               lg *(lgn)   يا lg(lg*n)

 

اسلاید 9 :

 a . توابع زير را برحسب مرتبه رشد رتبه بندي كنيد .

Lg(lg*n)     2        (√2 )           n           n!         (lg n)!

(3/2)          n         lg  n        lg(n!)        2            n

Ln ln n       lg*n     n. 2         n             ln n        1

 2              (lg n)       e            4          (n+1)!       √ lg n              

اسلاید 10 :

براي دو تابع f(n)  و g(n)  داريم f(n) = Θ(g(n))  اگروفقط اگر f(n) = O(g(n))  و f(n) = Ω(g(n))  .

اكثر ويژگي هاي رابطه اي اعداد حقيقي در مقايسه هاي مجانبي نيز به كار ميروند .

 تعدي :

 f(n) = Θ(g(n))  و g(n) = Θ(h(n)) دلالت مي كنند براينكه f(n) = Θ(h(n))  

 f(n) = O(g(n))  و g(n) = O(h(n)) دلالت مي كنند براينكه f(n) = O(h(n))  

 f(n) = Ω(g(n))  و g(n) = Ω(h(n)) دلالت مي كنند براينكه f(n) = Ω(h(n))  

 f(n) = o(g(n))  و g(n) = o(h(n))  دلالت مي كنند براينكه f(n) = o(h(n))  

 f(n) = ω(g(n))  و g(n) = ω(h(n)) دلالت مي كنند براينكه f(n) = ω(h(n))   

در متن اصلی پاورپوینت به هم ریختگی وجود ندارد. برای مطالعه بیشتر پاورپوینت آن را خریداری کنید