دانلود پاورپوینت تجزیه و تحلیل رابطه های بازگشتی درتکنیک های شمارش

  دانلود پاورپوینت تجزیه و تحلیل رابطه های بازگشتی درتکنیک های شمارش

تکنیک های پیشرفته شمارش

عنوان های پاورپوینت تجزیه و تحلیل رابطه های بازگشتی درتکنیک های شمارش  ، تکنیک های پیشرفته شمارشعبارتند از :

تجزیه و تحلیل رابطه های بازگشتی درتکنیک های شمارش
تکنیک های پیشرفته شمارشبخش 7.1 روابط بازگشتی (Recurrence Relations)
Rabbits Numbers - Leonardo Pisano
رابطه های بازگشتی
رابطه های بازگشتی
مثال: مسئله برج هانوی
مثال: مسئله برج هانوی
مثال
مثال
مثال
فصل هفتم: تکنیک های پیشرفته شمارشبخش 7.2حل روابط بازگشتی خطی (Solving Linear Recurrence Relations)
رابطه بازگشتی همگن خطی ازدرجه kLinear Homogeneous Recurrence Relation of Degree k
حل رابطه های بازگشتی همگن خطی با درجه k با ضرایب ثابت
مثال: رابطه فیبوناچی

کنجکاوی – خارج از بحث کتاب
حل رابطه های بازگشتی غیر همگن خطی با درجه k با ضرایب ثابتLinear Nonhomogeneous Recurrence Relations with Constant Coefficients
حل رابطه های بازگشتی غیر همگن خطی با درجه k با ضرایب ثابت
حل رابطه های بازگشتی غیر همگن خطی با درجه k با ضرایب ثابت

تکه ها و قسمت های اتفاقی از فایل تجزیه و تحلیل رابطه های بازگشتی درتکنیک های شمارش  ، تکنیک های پیشرفته شمارش

تکنیک های پیشرفته شمارشبخش 7.1 روابط بازگشتی (Recurrence Relations)
Rabbits Numbers - Leonardo Pisano
رابطه های بازگشتی
یک رابطه بازگشتی برای دنباله {an} معادله ای است که an را بر پایه ی یک عبارت یا عبارات بیشتر قبلی دنباله a0, a1,…, an-1 ، برای همه اعداد صحیح n با شرط n≥n0 که n0 عددی صحیح و نامنفی است ، بیان می کند. یک دنباله جواب یک رابطه بازگشتی است اگر عباراتش در رابطه بازگشتی صادق باشند.
رابطه های بازگشتی
رابطه‌ای را بازگشتی می‌نامیم که در آن برای محاسبه هر عنصر نیاز به مقادیر تعدادی از عناصر قبلی آن داشته باشیم و براساس آنها بیان شده باشد.
نقطه مقابل رابطه بازگشتی رابطه صریح می‌باشد که در آن با دانستن شماره عنصر مستقیماً مقدار آن توسط تابع صریح آن پیدا می‌گردد.
رابطه بازگشتی را به صورت زیر می توان بیان نمود (ui عنصر iام از دنباله است)
مثال: مسئله برج هانوی
مثال: مسئله برج هانوی
مثال
مثال

  دانلود پاورپوینت تجزیه و تحلیل رابطه های بازگشتی درتکنیک های شمارش
تکنیک های پیشرفته شمارش
مثال
n سکه یکسان 50 تومانی داریم. فرض می‌کنیم xn تعداد روش‌هایی باشد که این n سکه را در دو ردیف افقی روی هم چنان مرتب کنیم که هر سکه در ردیف بالا، دقیقاً در فضای خالی دو سکه زیری قرار گرفته باشند.

برای محاسبه xn رابطه بازگشتی بدست آورید.
فصل هفتم: تکنیک های پیشرفته شمارشبخش 7.2حل روابط بازگشتی خطی (Solving Linear Recurrence Relations)
رابطه بازگشتی همگن خطی ازدرجه kLinear Homogeneous Recurrence Relation of Degree k
یک رابطه بازگشتی همگن خطی از درجه k با ضرایب ثابت، رابطه ای بازگشتی به شکل
an= c1an-1 + c2 an-2 + … + ck an-k
که c1 , c2, …,ck اعداد حقیقی و 0 ≠ ck

مثال
fn = fn-1 + fn-2
حل رابطه های بازگشتی همگن خطی با درجه k با ضرایب ثابت
فرض کنیدc1 و c2اعداد حقیقی باشند و r2 - c1r - c2 = 0 (که معادله مشخصه رابطه بازگشتی نامیده می شود) دو ریشه متمایز r1 و r2 داشته باشد. دنباله {an} ، جواب رابطه بازگشتی an= c1an-1 + c2 an-2 است اگر و فقط اگر an= α1r1n + α2 r2n برای n=0,1,2,… باشد، وقتی که α1 و α2 ثابت باشند.

معادله مشخصه (Characteristics Equation)
ریشه های مشخصه (Characteristics Roots)
مثال: رابطه فیبوناچی

فرض کنید c1 و c2و... و ckاعداد حقیقی باشند، و فرض کنید rk - c1rk-1 -…- ck = 0 دارای k ریشه متمایز r1 و r2و...و rkباشد. دنباله {an} ، جواب رابطه بازگشتی
an= c1an-1 + c2 an-2+ … + ck an-k
است اگر و فقط اگر an= α1rn1 + α2 rn2+ … + αk rnk برای n=0,1,2,… باشد، وقتی که α1 و α2 و ... و αk ثابت باشند.

فرض کنید c1 و c2اعداد حقیقی باشند و r2 - c1r - c2 = 0 تنها یک ریشه مضاعف r0 داشته باشد. دنباله {an} ، جواب رابطه بازگشتی an= c1an-1 + c2 an-2 است اگر و فقط اگر an= α1r0n + α2 n r0n برای n=0,1,2,… باشد، وقتی که α1 و α2 ثابت باشند.

مثال:
an = 6an-1-9an-2
a0=1
a1=6
با تشکر از توجه شماتو پروژه
2pro.ir

فرض کنید c1 و c2و... و ckاعداد حقیقی باشند، و فرض کنید rk - c1rk-1 -…- ck = 0 دارای k ریشه متمایز r1 و r2و...و rt با تعداد تکرارهای m1 و m2و ... و mtکه mi≥1 و k= mt+...+m2+ m1 باشد. دنباله {an} ، جواب رابطه بازگشتی
an= c1an-1 + c2 an-2+ … + ck an-k
است اگر و فقط اگر
an= (α1,0 + α1,1 n+ … + α1,m1-1 n m1-1 )rn1 +
(α2,0 + α2,1 n+ … + α2,m2-1 n m2-1 )rn2 +
+ … + αt,0 + αt,1 n+ … + αt,m1t-1 n mt-1 )rnt +
برای n=0,1,2,… باشد، وقتی که αi,j ها ثابت باشند.

کنجکاوی – خارج از بحث کتاب

اگر ریشه معادله مشخصه مختلط باشد؟؟؟

برای جواب می توان از ایده حل معادلات مرتبه دوم خطی همگن با ضرایب ثابت در درس معادلات استفاده نمود.

  دانلود پاورپوینت تجزیه و تحلیل رابطه های بازگشتی درتکنیک های شمارش
تکنیک های پیشرفته شمارش
حل رابطه های بازگشتی غیر همگن خطی با درجه k با ضرایب ثابتLinear Nonhomogeneous Recurrence Relations with Constant Coefficients
an= c1an-1 + c2 an-2+ … + ck an-k + F(n)
که F(n)یک تابع غیر صفر است، رابطه بازگشتی غیر همگن خطی با درجه k با ضرایب ثابت است.و
an= c1an-1 + c2 an-2+ … + ck an-k
رابطه بازگشتی همگن منسوب به آن نام دارد.
حل رابطه های بازگشتی غیر همگن خطی با درجه k با ضرایب ثابت
اگر {an(p)} جواب ویژه رابطه بازگشتی خطی غیر همگن با ضرایب ثابت
an= c1an-1 + c2 an-2+ … + ck an-k + F(n)
باشد، آنگاه هر پاسخی به شکل {an(p) + an(h)} است که
{ an(h)} پاسخ رابطه بازگشتی همگن منسوب an= c1an-1 + c2 an-2+ … + ck an-k است.
حل رابطه های بازگشتی غیر همگن خطی با درجه k با ضرایب ثابت
فرض کنید که {an} در رابطه بازگشتی غیرهمگن خطی صادق باشد. و
F(n)=( btnt+ bt-1nt-1+ …+ b1n+ b0) sn
که …, bt b0, b1, و s اعداد حقیقی هستند. وقتی که s ریشه معادله مشخصه رابطه بازگشتی منسوب نباشد، پاسخ ویژه ای به شکل
( ptnt+ pt-1nt-1+ …+ p1n+ p0) sn
وجود دارد. وقتی که s ریشه معادله مشخصه رابطه بازگشتی منسوب باشد و تکرارش نیز برابر با m باشد، پاسخ ویژه ای به شکل
nm ( ptnt+ pt-1nt-1+ …+ p1n+ p0) sn
دارد.

30 تا 70 درصد پروژه | پاورپوینت | سمینار | طرح های کارآفرینی و  توجیهی |  پایان-نامه |  پی دی اف  مقاله ( کتاب ) | نقشه | پلان طراحی |  های آماده به صورت رایگان میباشد ( word | pdf | docx | doc | )