طراحی الگوریتم ها (روش های حل معادلات بازگشتی)

طراحی الگوریتم ها (روش های حل معادلات بازگشتی)

اسلاید 1: طراحی الگوریتم - مهندس محمد اکبرپور1طراحي الگوريتم هاComputer algorithms

اسلاید 2: طراحی الگوریتم - مهندس محمد اکبرپور2Week4Computer algorithms روش‌هاي حل معادلات بازگشتي 1- حل معادلات بازگشتي با استفاده از استقراي رياضي2- حل معادلات بازگشتي به روش جايگزيني3- حل معادلات بازگشتي با فرمول تقسيم و حل4- حل معادلات بازگشتي همگن خطي با ضرايب ثابت5- حل معادلات بازگشتي غير همگن خطي با ضرايب ثابت6- حل معادلات بازگشتي به روش تغيير متغير

اسلاید 3: week4طراحی الگوریتم - مهندس محمد اکبرپورپيچيدگي الگوريتم‌هاي بازگشتياگر تعداد فراخوانی های بازگشتی رو c در نظر بگیریم پیچیدگی تابع فوق به صورت زیر میباشد: اگر در الگوريتم فوق بخواهيم، تعداد كل جمع‌هاي انجام شده را بدست آوريم، بايد معادله بازگشتي زير را حل كنيم:

اسلاید 4: week4طراحی الگوریتم - مهندس محمد اکبرپور

اسلاید 5: week4طراحی الگوریتم - مهندس محمد اکبرپور1- حل معادلات بازگشتي با استفاده از استقراي رياضي بازگشتي زير را به روش استقراي رياضي حل كنيد.حل : ابتدا باید یک حل کاندیدا برای معادله فوق پیدا کنیم و سپس درستی این حل کاندیدا را به روش استقرا اثبات نماییم:با توجه به معادلات فوق می توان گفت که حل کاندیدا به صورت زیر است:

اسلاید 6: week4طراحی الگوریتم - مهندس محمد اکبرپوربا استفاده از استقراء ثابت مي كنيم كه اين حل درست است.مبناي استقراء:براي n = 1 داريم:فرض استقراء: فرض كنيد براي مقدار دلخواه n > 0 كه n تواني از 2 است، داشته باشيم:گام استقراء: چون رابطه بازگشتي براي n هاي تواني از 2 است، عدد بعدي كه بايد در نظر گرفته شود، 2n مي‌باشد لذا بايد نشان دهيم:

اسلاید 7: week4طراحی الگوریتم - مهندس محمد اکبرپورابتدا 2n را در رابطه بازگشتي مسأله قرار داده و با استفاده از فرض استقراء ، حكم را اثبات مي‌كنيم:چون حکم استقرا یا گام استقرا اثبات شد بنابراین حل کاندیدا صحیح میباشد . یعنی داریم :

اسلاید 8: week4طراحی الگوریتم - مهندس محمد اکبرپور2- حل معادلات بازگشتي به روش جايگزيني بازگشتي زير را به روش جايگزيني حل كنيد.با توجه به اينكه روش جايگزيني عكس روش استقراء است، داريم:کلیه مقادیر را در معادله اصلی جایگزین می کنیم.

اسلاید 9: week4طراحی الگوریتم - مهندس محمد اکبرپور3- حل معادلات بازگشتي با فرمول تقسيم و حل بازگشتي زير را در نظر بگيريد:معادلاتي كه به فرم كلي فوق باشند معادلات بازگشتي روش تقسيم و حل مي‌باشند و آنها را مي‌توان به صورت زير حل نمود:براي بدست آوردن U(n) بايد h(n) را بدست آورد:حال با توجه به مقدار بدست آمده براي h(n) و با توجه به جدول زير، U(n) را محاسبه مي‌كنيم:

اسلاید 10: week4طراحی الگوریتم - مهندس محمد اکبرپوراگر h(n) ثابت و يا لگاريتمي باشد ، براي بدست آوردن U(n) از فرمول دوم استفاده مي‌كنيم.با توجه به جدول فوق، جهت به دست آوردن U(n) با هر يك از h(n) هاي زير از كدام فرمول استفاده مي‌شود؟

اسلاید 11: week4طراحی الگوریتم - مهندس محمد اکبرپوربازگشتي زير را با استفاده از فرمول تقسيم و حل، حل كنيد.جواب: با توجه به معادله بازگشتي فوق، موارد زير را داريم:چون h(n) = 1 است، پس براي محاسبه زمان، از فرمول شماره 2 با i = 0 استفاده مي‌كنيم.

اسلاید 12: week4طراحی الگوریتم - مهندس محمد اکبرپور1- بازگشتي زير را با استفاده از استقراي رياضي حل كنيد.جواب: چند مقدار اوليه عبارتند از:نتيجه مي شود كه:

اسلاید 13: week4طراحی الگوریتم - مهندس محمد اکبرپوربا استفاده از استقراء ثابت مي‌كنيم كه حل درست است.مبناي استقراء: براي n = 1 داريم:فرض استقراء: فرض كنيد براي هر مقدار دلخواه n > 0 كه n تواني از 2 است، داريم:گام استقراء: بايد نشان دهيم:اگر 2n را در بازگشتي قرار دهيم، بدست مي‌آوريم:به اين ترتيب، استقراء ثابت مي‌شود. سرانجام چون: معمولا حل اين بازگشتي را به صورت زير ارائه مي‌كنيم:

اسلاید 14: week4طراحی الگوریتم - مهندس محمد اکبرپور5- الگوريتم بازگشتي پيدا كردن ماكزيمم عضو يك ليست، بصورت زير مي‌باشد:i : انديس خانه اول ليستn : تعداد عناصر ليستالف) درخت فراخواني الگوريتم فوق را براي ليست زير رسم كنيد.ب) معادله بازگشتي الگوريتم پيدا كردن ماكزيمم عضو يك ليست را، نوشته و آن را بصورت جايگزيني حل كنيد.n = 11

اسلاید 15: week4طراحی الگوریتم - مهندس محمد اکبرپورتعداد فراخواني‌هاي با n = 1 برابر با 11 مي‌باشد (تعداد برگها و تعداد عناصر ليست).تعداد فراخواني برابر با 21 مي‌باشد.تعداد اجراي تابع maximum برابر با 10 مي‌باشد.

اسلاید 16: week4طراحی الگوریتم - مهندس محمد اکبرپورب) معادله بازگشتي الگوريتم بصورت زير خواهد بود:حل معادله بازگشتي فوق به روش جايگزيني: (با فرض

اسلاید 17: week4طراحی الگوریتم - مهندس محمد اکبرپور

اسلاید 18: week4طراحی الگوریتم - مهندس محمد اکبرپور

اسلاید 19: طراحی الگوریتم - مهندس محمد اکبرپور19طراحي الگوريتم هاپايان جلسه چهارم