پاورپوینت تحلیل الگوریتم ها

توجه : این پروژه به صورت فایل power point (پاور پوینت) ارائه میگردد

 پاورپوینت تحلیل الگوریتم ها دارای ۱۵ اسلاید می باشد و دارای تنظیمات کامل در Power Point می باشد و آماده پرینت یا چاپ است

فایل پاور پوینت پاورپوینت تحلیل الگوریتم ها  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

---

لطفا به نکات زیر در هنگام خرید

دانلودپاورپوینت تحلیل الگوریتم ها

توجه فرمایید.

۱-در این مطلب، متن اسلاید های اولیه 

دانلودپاورپوینت تحلیل الگوریتم ها

قرار داده شده است

۲-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید

۳-پس از پرداخت هزینه ، حداکثر طی ۱۲ ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد

۴-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد

۵-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار داده نشده است

---

بخشی از متن پاورپوینت تحلیل الگوریتم ها :

اسلاید ۱ :

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

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

                               اگر n = 2                                      ۲

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

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

اسلاید ۲ :

مرتب سازی درجی روی آرایه های کوچک در مرتب سازی ادغام

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

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

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

اسلاید ۳ :

 درستی قانون Horner

 قطعه کد زیر قانون horner را برای ارزشیابی چند جمله ای                                  

P(x) = a  x

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

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

۱     y 0

۲      i n

۳      While i 0

۴          do  y a  + x . y

۵                 i i -1  

اسلاید ۴ :

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

 b .

برای مشاهده فایل های مشابه پیشنهاد می‌کنیم پاورپوینت درس طراحی الگوریتم ها را لطفا ببینید.

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

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

y = a        x

اسلاید ۵ :

وارونگی

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

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

 ۳ . الگوریتمی ارائه دهید که تعداد وارونگی ها در یک جایگشت روی n عنصر را در بدترین حالت در زمان (nlgn)  تعیین کند . 

اسلاید ۶ :

رشد توابع

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

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

 ۳ . آیا ۲    = O(n  )  ؟ آیا ۲   = O(2   )  ؟

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

                                                                             ( n+a )  = (n  )

اسلاید ۷ :

 ۵ . آیا ۲    = O(n  )  ؟ آیا ۲   = O(2   ) ؟

 ۶ . ثابت کنید زمان اجرای یک الگوریتم  (g(n))  است اگر و فقط اگر زمان اجرای آن در بدترین حالت O(g(n))  و زمان اجرای آن در بهترین حالت (g(n))  باشد .

اسلاید ۸ :

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

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

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

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

                                                               lg *(lgn)   یا lg(lg*n)

اسلاید ۹ :

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

Lg(lg*n)     ۲        (۲ )           n           n!         (lg n)!

(۳/۲)          n         lg  n        lg(n!)        ۲            n

Ln ln n       lg*n     n. 2         n             ln n        ۱

 ۲              (lg n)       e            ۴          (n+1)!       lg n              

اسلاید ۱۰ :

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))