Bilgisayar Olimpiyatı 2024, 1. Aşama, Soru 29

[27-29 soruları için açıklama]
Elinizde tek çekirdekli bir bilgisayar ve bu bilgisayar üzerinde çalıştırmanız gereken n adet bilgisayar programı vardır. Bilgisayar programları 1'den n'ye kadar numaralandırılmış olsunlar. Girdi olarak size her bir bilgisayar programı için 2 pozitif sayı verilmektedir.
- \(p_j > 0\) sayısı j. bilgisayar programının çalışma süresini,
- \(w_j > 0\) sayısı ise j. bilgisayar programının önemini göstermektedir.
Bilgisayar \(t = 0\) anında kullanımınıza hazırdır. Bilgisayar aynı anda en fazla bir programı çalıştırabilmektedir. Sizin göreviniz hangi bilgisayar programının hangi zaman aralığında çalışacağını belirlemektir.
Oluşturduğunuz zaman çizelgesine göre j. bilgisayar programının çalışmasının sonlandığı zaman \(C_j\) olsun.
Amacınız zaman çizelgesini \(\sum_{j=1}^{n} w_j C_j\) değerini en küçükleyecek şekilde oluşturmaktır.
\(n\)
\(\sum_{j=1}^{n} w_j C_j\) değerini en küÇüklemek istediğiniz için çalıştıracağınız ilk bilgisayar programını \(t = 0\) anında başlatmanız gerektiğine ve her bir bilgisayar programını çalıştırmaya bir önceki bilgisayar programının çalışması biter bitmez başlamanız gerektiğine dikkat ediniz.
Örnek: \(p\) ve \(w\) değerleri aşağıdaki tabloda verilen şekilde olan 3 adet bilgisayar programınız olsun.
<table><tr><td></td><td>1. program</td><td>2. program</td><td>3. program</td></tr><tr><td>\(p\)</td><td>3</td><td>4</td><td>2</td></tr><tr><td>\(w\)</td><td>6</td><td>1</td><td>2</td></tr></table>
Bu örnekte verilen programları 3! = 6 farklı şekilde sıralamak mümkündür.
Programlar 1, 2, 3 şeklinde sıralanırlarsa çalışmalarının sonlanma süreleri \(C_1 = 3\), \(C_2 = 7\), \(C_3 = 9\) olur.
Bu sıralamaya göre \(\sum_{j=1}^{n} w_j C_j = 6 \times 3 + 1 \times 7 + 2 \times 9 = 43\) olur.
Programlar 1, 3, 2 şeklinde sıralanırlarsa çalışmalarının sonlanma süreleri \(C_1 = 3\), \(C_2 = 9\), \(C_3 = 5\) olur. Bu sıralamaya göre \(\sum_{j=1}^{n} w_j C_{j} = 6 \times 3 + 1 \times 9 + 2 \times 5 = 37\) olur. Bu sıralama \(\sum_{j=1}^{n} w_j C_j\) değerini en küçükleyen sıralamadır.

---

p ve w değerleri aşağıdaki tabloda verilene şekilde olan 8 adet bilgisayar programınız olsun
<table><tr><td></td><td>1. program m</td><td>2. program m<td>3. program m</td><td>4. program m</td><td>5. program m</td><td></td><td>6. program m</td><td>7. program m</td><td>8. program m</td></td></tr><tr><td>p</td><td>1</td><td>2</td><td>1</td><td>2</td><td></td><td>4</td><td>2</td><td>3</td><td>4</td></tr><tr><td>w</td><td></td><td>2</td><td>3</td><td>3</td><td>4</td><td>6</td><td>6</td></tr></table>
toplamını en küçükleyen kaç sıralama vardır?

Şıklar:
A) 6 | B) 24 | C) 48 | D) 72 | E) 144

Cevap: D 72

Çözüm:
Bu soru bilgisayar programlarını \(\frac{w_j}{p_i}\) değerlerine göre büyükten küçüğe sırlayan açgözlü bir algoritma ile çözülebilir.
\[
\frac{w_3}{p_3} = \frac{w_5}{p_5} = 3 \text{ olduğu için } 3 \text{ ve 6 numaralı programlardan ilk başta olmalıdır ve 2 farklı şekilde sıralanabilirler.}
\]
\[\frac{w_1}{p_1} = \frac{w_4}{p_4} = \frac{w_7}{p_7} = 2 \text{ olduğu için 1, 4 ve 7 numaralı programlardan daha sonra gelmelidir ve 6 farklı şekilde sıralanabilirler.}\]
\[\frac{w_2}{p_2} = \frac{w_5}{p_5} = \frac{w_8}{p_8} = 1.5 \text{ olduğu için 2, 5 ve 8 numaralı programlar en sonda gelmelidir ve kendi aralarında 6 farklı şekilde sıralanabilirler.}\]
\[\text{Doğru cevap } 2 \times 6 \times 6 = 72' \text{ dir.}\]