لطفا به نکات زیر در هنگام خرید دانلود فایل پاورپوینت تحليل الگوريتم ها توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود فایل پاورپوینت تحليل الگوريتم ها قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 4 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

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

اسلاید ۱ :

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

 ۱ . با استفاده ازاستقراي رياضي نشان دهيد زماني كه توان صحيحي از ۲ است جواب رابطه بازگشتي زيربرابرچيست ؟

                               اگر = ۲                                      ۲

                               اگربراي k>1 ، = ۲      T( ) =    ۲T( /2) +  

 

۲ . مرتب سازي درجي مي تواند به صورت يك روال بازگشتي بشرح زير بيان شود . به منظور مرتب كردن A[1.. ] ، آرايه A[1… -1] را بطور بازگشتي مرتب كرده و سپس A( ) را درآرايه مرتب شده A[1.. -1] درج مي كنيم . يك رابطه بازگشتي براي زمان اجراي اين نسخه بازگشتي از مرتب سازي درجي بنويسيد .

اسلاید ۲ :

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

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

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

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

اسلاید ۳ :

 درستي قانون Hor er

 قطعه كد زير قانون hor er را براي ارزشيابي چند جمله اي                                  

P(x) = ∑ a  x

        = a  + x(a  + x(a  +…+x(a    + xa  )…)),

با ضرايب داده شده a  ,a  ,…, a   و يك مقدار براي x پياده سازي مي كند :

۱     y ← ۰

۲      i ←

۳      While i ≥ ۰

۴          do  y ← a  + x . y

۵                 i ← i -1  

اسلاید ۴ :

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

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

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

y = ∑ a        x

اسلاید ۵ :

وارونگي

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

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

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

اسلاید ۶ :

رشد توابع

 ۱ . فرض كنيد f( ) و g( ) بطور مجانبي توابع غيرمنفي باشند . با استفاده از تعريف اصلي نماد Θ ، ثابت كنيد كه max(f( ),g( )) = Θ(f( ) + g( ))

 ۲ . توضيح دهيد چرا عبارت ” زمان اجراي الگوريتم A حداقل O(   ) است ” ، بي معني است ؟

 ۳ . آيا ۲    = O(   )  ؟ آيا ۲   = O(2   )  ؟

 ۴ . نشان دهيدهر ثابت حقيقي a  وb كه b>0 ،

                                                                             ( +a )  = Θ(   )

اسلاید ۷ :

 ۵ . آيا ۲    = O(   )  ؟ آيا ۲   = O(2   ) ؟

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

 

اسلاید ۸ :

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

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

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

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

                                                               lg *(lg )   يا lg(lg* )

 

اسلاید ۹ :

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

Lg(lg* )     ۲        (√۲ )                      !         (lg )!

(۳/۲)                   lg          lg( !)        ۲           

L l        lg*      . ۲                      l         ۱

 ۲              (lg )       e            ۴          ( +۱)!       √ lg               

اسلاید ۱۰ :

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

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

 تعدي :

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

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

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

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

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