KonkurStudy

سوال ۷۴ کنکور ارشد علوم کامپیوتر ۱۴۰۴

اهمیت
۰/۵

nn فایل داریم که طول فایل iiاُم LiL_i و احتمال دسترسی به آن PiP_i است که به ما داده شده است. می‌خواهیم این فایل‌ها را طوری پشت سرهم قرار دهیم که میانگین زمان دسترسی به فایل‌ها کمینه شود. به عبارت دیگر می‌خواهیم این فایل‌ها را به ترتیب از ۱ تا nn شماره‌گذاری کنیم به‌طوری که

∑i=1n(Pi∑j=1iLj)\sum_{i=1}^{n}\left(P_i\sum_{j=1}^{i} L_j\right)

کمینه شود. کدام‌یک از راه‌های زیر بهترین ترتیب برای این کار است؟

#greedy#exchange-argument#scheduling#weighted-completion-time#smith-rule#optimality