Greedy Algorithms
الگوریتم‌های حریصانه.
طراحی الگوریتم‌ها کنکور ارشد مهندسی کامپیوتر
A greedy algorithm builds a solution by repeatedly taking the locally best choice; it is optimal exactly when the problem has the greedy-choice property plus optimal substructure, proved by an exchange argument.
فرض کنید برای حل مسئله پوشش حداکثر (maximum Coverage)، از الگوریتم حریصانه استفاده می‌کنید که مجموعه‌ای از عناصر را با کمترین هزینه ممکن پوشش دهد. چرا این الگوریتم نمی‌تواند جواب بهینه را تضمین کند؟
فرض کنید G = (V , E) ، یک گراف هم‌بند وزن‌دار باشد. چند مورد از گزاره‌های زیر درست است؟ اگر وزن تمام یال‌های گراف با هم برابر باشد، می‌توان درخت فراگیر کمینه آن را با الگوریتمی از مرتبه O( E ) بدست…
هریک از کارهای زیر در یک واحد زمان قابل اجرا است. هر یک از این کارها دارای یک زمان خاتمه است و درصورتی‌که بعد از زمان خاتمه انجام شود مشمول یک جریمه خواهد شد. اگر این کارها را برای اجرا به کمترین…
فرض کنید که یک مسئله را بتوان به‌صورت بهینه هم با روش تقسیم و حل، هم با روش برنامه‌ریزی پویا و هم با روش حریصانه حل کرد. در این‌صورت از لحاظ پیچیدگی زمانی کدام‌یک ارجحیت دارد؟
کدام‌یک از مسائل زیر در زمان خطی برحسب تعداد رئوس و یال‌های گراف ورودی قابل‌حل نیست؟
برای پیاده‌سازی مؤثر کدام‌یک از الگوریتم‌های زیر، ساختمان داده heap لازم نیست؟
گراف جهت‌دار و وزن‌دار G = (E, V) با n رأس و O(n) یال و زیرمجموعه S ⊆ V از رأس‌های گراف با اندازه حداقل n/2 داده شده است. فرض کنید وزن تمام یال‌های گراف مثبت است. به‌ازای هر رأس u از گراف، فاصله رأس…
فرض کنید گراف G یک گراف وزن‌دار و مسطح با n رأس است. درخت پوشای کمینه G را در چه زمانی می‌توان محاسبه کرد؟ توجه کنید لزومی ندارد از الگوریتم‌های معروف برای محاسبه درخت پوشای کمینه استفاده شود.…
متنی که هر حرف از چهار نویسه‌ی a,b,c,d است را با الگوریتم هافمن کدگذاری کرده‌ایم. طول کد هافمن این متن ۲۰۲۱ بیت شده است. طول کد چهار نویسه‌ی فوق در کدگذاری هافمن کدام است؟
گراف بدون جهت و وزن‌دار G و رأس مشخص s از این گراف را درنظر بگیرید. از الگوریتم دایکسترا برای محاسبه کوتاه‌ترین مسیر ساده از s به بقیه رئوس استفاده کرده‌ایم. به‌ازای چند حالت زیر این الگوریتم با وجود…
[بخش ابتدایی صورت مسئله در تصویر برش خورده است؛ متن زیر بر پایهٔ گزینه‌ها بازسازی شده و جملهٔ پایانی عیناً همان چیزی است که در تصویر دیده می‌شود.] فرض کنید n کاراکتر با فراوانی‌های a, ۲a, ۴a, ……
در یک گراف بدون جهت و وزن‌دار، کدام‌یک از گزینه‌های زیر در مورد درخت پوشای کمینهٔ تولیدشده توسط الگوریتم Prim و Kruskal درست است؟
متنی شامل ۷۰۰۰ حرف از حروف a، b، c، d، e و f با دفعات تکرار به‌ترتیب ۱۰۰۰ و ۱۲۰۰، ۸۰۰، ۱۵۰۰، ۱۸۰۰ و ۷۰۰ موجود است. چنانچه بخواهیم کدی بهینه برای حروف بالا انتخاب کنیم تعداد کل بیت‌های لازم برای تبدیل…