نوشته های قبل و بعد از کنکور ارشد

اگر در ضرب استراسن مساله کوچک ضرب ماتریسهای ۲*۲ باشد با چند فراخوانی بازگشتی الگوریتم استراسن عمل ضرب دو ماتریس ۸*۸ انجام می پذیرد؟

الف)۳۴۳
ب) ۵۷
ج)۴۹
د)۷

دوستان این سوال  ۵۰ کنکور it ۸۶ هست اگر دوستی کلید این آزمون را در اختیار داره لظفا من را یاری دهد کلید در سایت سنجش قابل دسترسی نیست ( فعلا)

!-- @page { size: ۸.۵in ۱۱in; margin: ۰.۷۹in } P { margin-bottom: ۰.۰۸in } -->همون طور که می دونید روش های مختلفی برای به دست آوردن کوتاه ترین مسیر بین یک گره گراف تا گره دیگر وجود داره :

الگوریتم فلوید : این الگوریتم از درجه n^۳ می باشد ، برای یالهای با طول منفی ولی بدون حلقه منفی نیز کار می کند این الگوریتم کل کوتاه ترین مسیرهای یک گراف را بین هر دو گره به دست می آورد ، الگوریتم ساده است و از سه حلقه تو در تو تشکیل شده است.

الگوریتم دایکسترا : این الگوریتم از درجه n^۲ می باشد ، برای گراف های با یال با طول منفی و همچنین برای گرافهای دا رای حلقه منفی مطلقاً جواب صحیحی نمی دهد. الگوریتم بر اساس تکنیک حریصانه نوشته شده است و کوتاه ترین مسیر بین یک گره تا بقیه گره ها را مشخص می کند.

الگوریتم بلمن & فورد : این الگوریتم تعمیم یافته دایکسترا است که برای گراف های با یال منفی ولی بدون حلقه منفی کار می کند ؛ کاری شبیه به دایکسترا می کند و از درجه ۲ است.

اما راه های پیدا کردن درخت پوشای کمینه وقتی که همه یالها برابرند : بر این اساس می تونیم از چند الگوریتم استفاده کنیم

dfsو bfs : برای اساس این الگوریتم پیچیدگی برابر می شود با( o(e+n و چون که در گراف ها همیشه (اگر درخت نباشد!) e>=n است پس پیچیدگی برابر است با( o(e.

اما چه طور قطر یک درخت را به دست بیاوریم؟

قطر یک درخت طول بلندترین مسیر ابتدایی در درخت است . مثلاً گراف زیر قطر ۲ دارد:

۰-۰-۰

اگر طول همه اضلاع برابر باشد می توان با استفاده از جستجوی عمقی و شمارش عمق قطر را پیدا کرد (البته به نظر من اینطوریه) در این الگوریتم هرگاه یک عمق جلو رفتیم یکی به طول قطر اضافه می کنیم و هر بار backtrack یکی از تعداد قطر کم می کنیم چون که از dfs استفاده می کنیم حداکثر با تعداد(o(v پیچیدگی می توان عمق رو به دست آورد ،‌ یه چیز جالب بگم که این روش همین الان به ذهنم رسید! تا به حال روش های زیادی واسش پیدا کردم ولی این روش واقعاً کار می کنه دی:

حداکثر طول یک کد هافمن برای n عنصرچه قدر است؟

۱)n-۲

۲)

۳)n-۱

۴)

جواب:۳

اما به نظر من جواب گزینه ۴ است زیرا برای ۱ عنصر،حداکثر طول ۱ است

نظر شما چیست؟