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

Büyük bir bilgisayar sistemini izlemeye yardımcı olan bir grup güvenlik danışmanı ile çalışıyorsunuz. "Yüksek öncelikli" olarak belirlenmiş süreçlerin (iş) izlenmesine özellikle dikkat ediliyor. Her bir bu tür süreç, önceden planlanmış bir başlangıç ve bitiş zamanına sahip. Danışmanlar, gün boyunca çalışacak olan 1'den n'ye kadar numaralandırılmış n tane "yüksek öncelikli" sürecin başlangıç ve bitiş zamanlarını biliyorlar. Buna göre, j. yüksek öncelikli sürecin başlangıç ve bitiş zamanları sı ve f j ile ifade edilsin ve bu süreç [s, f] zaman aralığında sürekli çalışsın. A[1..n] dizisi indisleri 1'den başlayan ve n elemanlı bir dizi olsun, ve bu dizinin j. elemanı j. yüksek öncelikli sürecin çalıştığı zaman aralığını göstersin.
Danışmanlar ilk olarak, çalıştırıldığında çok çok kısa bir süre (anlık) çalışan ve o anda sistemde çalışan her yüksek öncelikli sürecin çeşitli bilgilerini kaydeden "Kontrol" adında bir program yazıyorlar. Kontrol programının her çalıştırılmasını, çok kısa sürdüğü için bir "an" (zaman aralığı DEĞİL) olarak modelliyorlar. T[1..m] dizisi indisleri 1'den başlayan, ve m tane "an" içeren bir dizi olsun. Kontrol programı yalnızca T[1..m] dizisinde verilen anlarda çalıştırılabiliyor.
Danışmanlar Kontrol programının gün boyunca her yüksek öncelikli sürecin zaman aralığı sırasında en az bir kez çalıştırıldığından emin olmak ve aynı zamanda Kontrol programının toplam çalıştırılma sayısını minimize etmek (en aza indirmek) istiyorlar. Bunu sağlamak için şu stratejiyi düşünüyorlar: Başlangıçta tüm yüksek öncelikli süreçler "işaretlenmemiş" olarak kabul edilir. En fazla işaretlenmemiş yüksek öncelikli süreç aralığı tarafından içerilen T[i] anında Kontrol programı çalıştırılır ve sonra bu anı içeren süreçler işaretlenir. İşaretlenmemiş süreç kalmayana kadar bu işlem tekrarlanır. Bu stratejinin her zaman Kontrol programının çalıştırılma sayısını minimize etmeyeceğini aşağıdaki A ve T dizilerinden hangi çifti örnek gösterecek ispat edebiliriz?

Şıklar:
A) A: {0,5, [6,10], [2,8], [6,12]}, T: {3,4,7,9} | B) A: {0,6, [4,10], [4,10], [4,10], [8,14]}, T: {2,5,7,9,12} | C) A: {0,6, [3,9], [3,9], [3,9], [7,13], [7,13], [7,13], [11,15]}, T: {2,5,8,12,14} | D) A: {0,7, [3,7], [5,9], [7,12], [10,15]}, T: {4,6,8,11,13} | E) Hiçbiri

Cevap: C A: {0,6, [3,9], [3,9], [3,9], [7,13], [7,13], [7,13], [11,15]}, T: {2,5,8,12,14}

Çözüm:
Soruda verilen stratejiye göre C şıkkında verilen örnekte Kontrol programı 3 kere çalıştırılır. İlk olarak altı farklı aralık tarafından içerilen 8 anı seçilir, bu seçimden sonra sadece ilk ve son aralıklar işaretlenmemiş olarak kalır. Kalan anlardan (2,3, 5, 12, 14) her biri birer işaretlenmemiş aralık tarafından içerildiği için bunlardan biri rastgele seçilir. Örneğin 2 anı seçilsin. Bunun sonucunda işaretlenmemiş olarak sadece son aralık kalır, bu aralığın içerdiği 12 veya 14 anlarından biri seçilir. Kontrol programının çalıştırılması için toplam 3 an seçilmiş olur. Fakat sadece 5 ve 12 anları seçilerek hem bütün aralıklarda en az bir kez çalıştırılma koşulu sağlanıp hem de Kontrol'ün 2 defa çalıştırılması ile problem çözülebilir. Bu durumda 3'ten daha az çalıştırılma ile çözüm mümkün olduğu için C şıkkında verilen A ve T dizileri önerilen stratejinin optimal olmadığını ispatlar. Diğer şıklarda soruda önerilen strateji optimal çözümle aynı sonucu verdiğinden karşı örnek olarak kullanılamazlar.
Derinlik Öncelikli Aramanın (DFS) a düğümünden başladığında ve bu düğüme geri gelmeden önce önce her komşu düğüm boyunca mümkün olduğu kadar uzağa gider. Bu çizgede ilk olarak a düğümünden sonra DFS, bu düğüme komşu olan c düğümüne geçebilir. DFS, c düğümünden d düğümüne ve ardından e düğümüne geçmek zorundadır. Son olarak DFS, e düğümüne komşu olan b düğümünü ziyaret eder. Dolayısıyla, şıklardan tek doğru ziyaret edilen düğüm sıralaması a,c,d,e,b dir.