تالار گفتمان مانشت

شما هم‌، هر کمکی تونستید، دریغ نکنید

تعداد درخت BST بصورت زیر محاسبه می شود:

الگوریتم LCS برای یافتن بزرگترین زیر دنباله مشترک بکار می رود( تست طراحی الگوریتم سال قبل گرایش هوش مصنوعی) که با فرض اینکه دو دنباله با طول های n و m داریم در زمان تتای (mn) صورت میگیرد( 2 حلقه تودرتو) و چاپ این زیر رشته در زمان (O(m+n

در مورد ضرب زنجیره ای ماتریس ها:

1.(تمرین 15.2.4 CLRS) تعداد کل ارجاع‌ها به درایه های ماتریسی که جواب‌ها در آن نگهداری میشود برابر است با:


2. (تمرین 15.2.5 CLRS) یک عبارت n عنصری که پرانتزگذاری کامل شده است، دقیقاً n-1 جفت پرانتز دارد.

الگوریتم فلوید:
جهت یافتن تمام کوتاه ترین مسیر‌ها بین گره‌ها بکار میرود
روش کار الگوریتم به این صورت است که با توجه به ماتریس هزینه بین 2 گره کار شروع میشود . سپس با توجه به این ماتریس کوتاهترین مسیر بین 2 گره بشرطی که مسیر مستقیمی وجود داشته باشد( بدون واسط )و یا اینکه گره 1 واسط این 2 گره باشد کار را ادامه می دهیم تا اینجا ماتریس A1 رو داریم . حالا کوتاهترین مسیر بین 2 گره را با واسط قرار دادن گره2 بررسی می کنیم الی آخر . در پایان کار ماتریس Ak داریم که در آن k تعداد رئوس هست.
یعنی k تا ماتریس ایجاد می شود اما نیازی نیست که همه ماتریس‌ها رو در حافظه نگه داشت بلکه نگه داشتن ماتریس نهایی در مرحله جاری کافی است

در تکمیل بحث الگوریتم فلوید باید گفت که این مسئله‌، یک مسئله بهینه سازی است‌، پس زیر جواب های آن نیز حتماً بهینه است . اگر به فرمول زیر که در قلب این الگوریتم بکار رفته

دقت کنید متوجه میشوید برای یافتن مسیر بهینه 2 گره‌، 2 راه وجود دارد
1- وجود یک یال مستقیم
2- وجود یک مسیر بین 2 گره مورد نظر بشرطی که از گره ای مثل k عبور کند که این یک زیر جواب بشمار می آید پس طبق مطالب بالا این زیر جواب بهینه است( زیر جواب بهینه i به k و سپس از k به j)

کسانی که کتاب پیام نور دارند به صفحه 209 نگاه کنید . در پایین صفحه 3 خط بعنوان مثال آورده شده که اولی رو بررسی می کنیم( با توجه به گراف داده شده در بالای این جملات):
قصد داریم مسیر بهینه بین گره 2 و 4 رابیابیم( به اندیس ماتریس D دقت کنید )2 راه بالا را بررسی میکنیم:
1- یال مستقیم بین 2 گره با وزن 2 وجود داره
2- مسیری با وزن 10 وجود داره که از راس 1 عبور میکنه( از گره 2 به 1 با وزن 9 و سپس از 1 به 4 با وزن 1 )در واقع این همان ماتریس D1 یا همان A1 است که در پست قبلی درباره آن بحث شده( یعنی مسیر بهینه بشرطی که از گره 1 عبور کنیم)
واضح است که جواب همان یال مستقیم با وزن 2 است
اما در خط بعد قصد یافتن کوتاهترین مسیر بین 2 و 5 داریم و از آنجا که یال مستقیم بین 2 گره وجود ندارد هزینه آنرا بی نهایت در نظر میگیریم سپس بررسی میکنیم که اوضاع با واسط قرار دادن گره1 به چه صورت است( از گره 5 به 1 با هزینه 3 و از گره 1 به 2 با هزینه 1) مشخص است مینمم همان 4 است( 3+1))

البته من دانشجوی پیام نور نیستم

در روش پویا الگوریتم سری فیبوناتچی بسیار سریعتر از روش تقسیم و حل انجام می گیرد .

در روش تقسیم و غلبه داشتیم [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] انجام می گیرد .(سراسری ۸۴)

منبع :راهیان ارشد

ضریب دو جمله ای به روش برنامه نویسی پویا : (همون مثلث خیام)

این الگوریتم از دو حلقه for تودر تو استفاده کرده پس از مرتبه [tex]\Theta (n^{2})[/tex] می باشد .