بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
تحليل الگوريتم ها
1 . با استفاده ازاستقراي رياضي نشان دهيد زماني كه توان صحيحي از 2 است جواب رابطه بازگشتي زيربرابرچيست ؟
اگر = 2 2
اگربراي k>1 ، = 2 T( ) = 2T( /2) +
2 . مرتب سازي درجي مي تواند به صورت يك روال بازگشتي بشرح زير بيان شود . به منظور مرتب كردن A[1.. ] ، آرايه A[1... -1] را بطور بازگشتي مرتب كرده و سپس A( ) را درآرايه مرتب شده A[1.. -1] درج مي كنيم . يك رابطه بازگشتي براي زمان اجراي اين نسخه بازگشتي از مرتب سازي درجي بنويسيد .
اسلاید 2 :
مرتب سازي درجي روي آرايه هاي كوچك در مرتب سازي ادغام
1 . يك تغيير در مرتب سازي ادغام را در نظر بگيريد كه درآن /k زير ليست با طول k با استفاده از مرتب سازي درجي ، مرتب شده و سپس با استفاده از فرايند ادغام استاندارد ادغام مي شوند و k مقداري است كه بايد مشخص شود .
a . نشان دهيد كه /k زير ليست هر يك با طول k مي توانند بوسيله مرتب سازي درجي در بدترين حالت در زمان Θ( /k) مرتب شوند.
b . نشان دهيد كه زير ليست ها مي توانند دربدترين حالت درزمان Θ( lg( /k)) ادغام شوند .
اسلاید 3 :
درستي قانون Hor er
قطعه كد زير قانون hor er را براي ارزشيابي چند جمله اي
P(x) = ∑ a x
= a + x(a + x(a +…+x(a + xa )…)),
با ضرايب داده شده a ,a ,…, a و يك مقدار براي x پياده سازي مي كند :
1 y ← 0
2 i ←
3 While i ≥ 0
4 do y ← a + x . y
5 i ← i -1
اسلاید 4 :
a . زمان اجراي مجانبي اين قطعه كد براي قانون Hor er چيست ؟
b . شبه كدي براي پياده سازي الگوريتم ارزشيابي ساده چند جمله اي بنويسيد كه هر جمله از چند جمله اي را از ابتدا محاسبه مي كند . زمان اجراي اين الگوريتم چيست ؟ در مقايسه با قانون Hor er چگونه است ؟
c . ثابت كنيد كه ثابت زير يك ثابت حلقه براي حلقه while در خطوط 3- 5 است .
y = ∑ a x
اسلاید 5 :
وارونگي
1 . چه آرايه اي با عناصر مجموعه {1,2,…, } بيشترين وارونگي ها را دارد ؟ اين آرايه چند وارونگي دارد ؟
2 . چه رابطه اي بين زمان اجراي مرتب سازي درجي و تعداد وارونگي ها درآرايه ورودي وجود دارد ؟
3 . الگوريتمي ارائه دهيد كه تعداد وارونگي ها در يك جايگشت روي عنصر را در بدترين حالت در زمان Θ( lg ) تعيين كند .
اسلاید 6 :
رشد توابع
1 . فرض كنيد f( ) و g( ) بطور مجانبي توابع غيرمنفي باشند . با استفاده از تعريف اصلي نماد Θ ، ثابت كنيد كه max(f( ),g( )) = Θ(f( ) + g( ))
2 . توضيح دهيد چرا عبارت ” زمان اجراي الگوريتم A حداقل O( ) است ” ، بي معني است ؟
3 . آيا 2 = O( ) ؟ آيا 2 = O(2 ) ؟
4 . نشان دهيدهر ثابت حقيقي a وb كه b>0 ،
( +a ) = Θ( )
اسلاید 7 :
5 . آيا 2 = O( ) ؟ آيا 2 = O(2 ) ؟
6 . ثابت كنيد زمان اجراي يك الگوريتم Θ(g( )) است اگر و فقط اگر زمان اجراي آن در بدترين حالت O(g( )) و زمان اجراي آن در بهترين حالت Ω(g( )) باشد .
اسلاید 8 :
نمادهاي استاندارد و توابع عمومي
1 . نشان دهيد اگر f( ) و g( ) توابع صعودي يكنواخت باشند ، آنگاه توابع f( ) + g( ) وf(g( )) نيز صعودي يكنواخت هستند ، و اگر علاوه بر آن f( ) و g( ) غير منفي نيز باشند ، آنگاه f( ). g( ) صعودي يكنواخت است .
2 . آيا تابع ┌ lg ┐! بطور چند جمله اي محدود است ؟ آيا تابع ┌ lg lg ┐! بطور چند جمله اي محدود مي شود ؟
3 . كدام يك بطور مجانبي بزرگتر است :
lg *(lg ) يا lg(lg* )
اسلاید 9 :
a . توابع زير را برحسب مرتبه رشد رتبه بندي كنيد .
Lg(lg* ) 2 (√2 ) ! (lg )!
(3/2) lg lg( !) 2
L l lg* . 2 l 1
2 (lg ) e 4 ( +1)! √ lg
اسلاید 10 :
براي دو تابع 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( ))
