توجه : این پروژه به صورت فایل power point (پاور پوینت) ارائه میگردد
پاورپوینت تحلیل الگوریتم ها دارای 15 اسلاید می باشد و دارای تنظیمات کامل در Power Point می باشد و آماده پرینت یا چاپ است
فایل پاور پوینت پاورپوینت تحلیل الگوریتم ها کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه و مراکز دولتی می باشد.
دانلود پاورپوینت تحلیل الگوریتم ها
توجه فرمایید.1-در این مطلب، متن اسلاید های اولیه
دانلود پاورپوینت تحلیل الگوریتم ها
قرار داده شده است2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید
4-در صورت مشاهده بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد
5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار داده نشده است
اسلاید 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 :
v برای دو تابع f(n) و g(n) داریم f(n) = (g(n)) اگروفقط اگر f(n) = O(g(n)) و f(n) = (g(n)) .
v اكثر ویژگی های رابطه ای اعداد حقیقی در مقایسه های مجانبی نیز به كار میروند .
تعدی :
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))
برای دریافت اینجا کلیک کنید
تعداد کل پیام ها : 0