[نکات] برنامه نویسی پویا - نسخه‌ی قابل چاپ

[نکات] برنامه نویسی پویا - Masoud05 - 30 آبان ۱۳۸۹ ۰۹:۰۲ ب.ظ شما هم‌، هر کمکی تونستید، دریغ نکنید

RE: [نکات] برنامه نویسی پویا - Masoud05 - 12 آذر ۱۳۸۹ ۰۲:۱۴ ب.ظ تعداد درخت BST بصورت زیر محاسبه می شود:

RE: [نکات] برنامه نویسی پویا - Masoud05 - 02 دى ۱۳۸۹ ۰۳:۰۷ ب.ظ الگوریتم LCS برای یافتن بزرگترین زیر دنباله مشترک بکار می رود( تست طراحی الگوریتم سال قبل گرایش هوش مصنوعی) که با فرض اینکه دو دنباله با طول های n و m داریم در زمان تتای (mn) صورت میگیرد( ۲ حلقه تودرتو) و چاپ این زیر رشته در زمان (O(m+n

RE: [نکات] برنامه نویسی پویا - ۵۴m4n3h - 03 دى ۱۳۸۹ ۰۳:۱۱ ب.ظ در مورد ضرب زنجیره ای ماتریس ها: ۱/(تمرین ۱۵/۲/۴ CLRS) تعداد کل ارجاع‌ها به درایه های ماتریسی که جواب‌ها در آن نگهداری میشود برابر است با: ۲/ (تمرین ۱۵/۲/۵ CLRS) یک عبارت n عنصری که پرانتزگذاری کامل شده است، دقیقاً n-1 جفت پرانتز دارد.

RE: [نکات] برنامه نویسی پویا - Masoud05 - 06 دى ۱۳۸۹ ۱۰:۱۲ ب.ظ الگوریتم فلوید: جهت یافتن تمام کوتاه ترین مسیر‌ها بین گره‌ها بکار میرود روش کار الگوریتم به این صورت است که با توجه به ماتریس هزینه بین ۲ گره کار شروع میشود . سپس با توجه به این ماتریس کوتاهترین مسیر بین ۲ گره بشرطی که مسیر مستقیمی وجود داشته باشد( بدون واسط )و یا اینکه گره ۱ واسط این ۲ گره باشد کار را ادامه می دهیم تا اینجا ماتریس A1 رو داریم . حالا کوتاهترین مسیر بین ۲ گره را با واسط قرار دادن گره۲ بررسی می کنیم الی آخر . در پایان کار ماتریس Ak داریم که در آن k تعداد رئوس هست. یعنی k تا ماتریس ایجاد می شود اما نیازی نیست که همه ماتریس‌ها رو در حافظه نگه داشت بلکه نگه داشتن ماتریس نهایی در مرحله جاری کافی است

RE: [نکات] برنامه نویسی پویا - Masoud05 - 08 دى ۱۳۸۹ ۰۱:۲۱ ق.ظ در تکمیل بحث الگوریتم فلوید باید گفت که این مسئله‌، یک مسئله بهینه سازی است‌، پس زیر جواب های آن نیز حتماً بهینه است . اگر به فرمول زیر که در قلب این الگوریتم بکار رفته دقت کنید متوجه میشوید برای یافتن مسیر بهینه ۲ گره‌، ۲ راه وجود دارد ۱- وجود یک یال مستقیم ۲- وجود یک مسیر بین ۲ گره مورد نظر بشرطی که از گره ای مثل k عبور کند که این یک زیر جواب بشمار می آید پس طبق مطالب بالا این زیر جواب بهینه است( زیر جواب بهینه i به k و سپس از k به j) کسانی که کتاب پیام نور دارند به صفحه ۲۰۹ نگاه کنید . در پایین صفحه ۳ خط بعنوان مثال آورده شده که اولی رو بررسی می کنیم( با توجه به گراف داده شده در بالای این جملات): قصد داریم مسیر بهینه بین گره ۲ و ۴ رابیابیم( به اندیس ماتریس D دقت کنید )۲ راه بالا را بررسی میکنیم: ۱- یال مستقیم بین ۲ گره با وزن ۲ وجود داره ۲- مسیری با وزن ۱۰ وجود داره که از راس ۱ عبور میکنه( از گره ۲ به ۱ با وزن ۹ و سپس از ۱ به ۴ با وزن ۱ )در واقع این همان ماتریس D1 یا همان A1 است که در پست قبلی درباره آن بحث شده( یعنی مسیر بهینه بشرطی که از گره ۱ عبور کنیم) واضح است که جواب همان یال مستقیم با وزن ۲ است اما در خط بعد قصد یافتن کوتاهترین مسیر بین ۲ و ۵ داریم و از آنجا که یال مستقیم بین ۲ گره وجود ندارد هزینه آنرا بی نهایت در نظر میگیریم سپس بررسی میکنیم که اوضاع با واسط قرار دادن گره۱ به چه صورت است( از گره ۵ به ۱ با هزینه ۳ و از گره ۱ به ۲ با هزینه ۱) مشخص است مینمم همان ۴ است( ۳+۱)) البته من دانشجوی پیام نور نیستم

[نکات] برنامه نویسی پویا - yaser_ilam_com - 31 فروردین ۱۳۹۱ ۰۲:۱۳ ق.ظ در روش پویا الگوریتم سری فیبوناتچی بسیار سریعتر از روش تقسیم و حل انجام می گیرد . در روش تقسیم و غلبه داشتیم [tex]\Theta (2^{n/2})[/tex] در روش پویا به صورت [tex]\Theta (n)[/tex] که حاصل یک for می باشد محاسبه می شود ۱) تعداد حالاتی که می توان N+1 ماتریس را در هم ضرب کرد ۲) تعداد خرو جی های مختلف یک پشته با n عنصر ورودی ۳) تعداد مثلث خای موجود در یک چند ضلعی محدب ۴) تعداد درخت های دودویی مختلف با n گره [tex](1/(n 1))\binom{2n}{n}[/tex] در یک گراف جهت دار بدون دور و وزن دار طولانی ترین مسیر از یک راس مشخص به بقیه راس ها را با [tex]\Theta (|V^{3}|)[/tex] انجام می گیرد .(سراسری ۸۴) منبع :راهیان ارشد

[نکات] برنامه نویسی پویا - yaser_ilam_com - 01 اردیبهشت ۱۳۹۱ ۰۸:۰۴ ب.ظ ضریب دو جمله ای به روش برنامه نویسی پویا : (همون مثلث خیام) این الگوریتم از دو حلقه for تودر تو استفاده کرده پس از مرتبه [tex]\Theta (n^{2})[/tex] می باشد . کد این برنامه : (int C( int n , int r } ;int arr[10][10] , i , j (++for ( i = 0 ; i <= n ; i (++for ( j = 0 ; j <= min( i , r ) ; j ( if ( j == 0 || j == i ;arr[i][j] = 1 else ;[arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j ;[return arr[n][r {