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