Sınavdan Çakma Algoritması (S.Ç.A.)
1990’ların sonu…
Eve sonunda bilgisayar alındı. Ali’nin abileriyle girdiği “bilgisayarı kullanma sırası kimde?” savaşından galip çıkmasının en önemli nedeni ders notlarının yüksekliği. Bu sayede Carmageddon’da zombi ezen, Fifa 98’de şampiyonlar ligini gol yemeden kazanan Ali’nin Duke Nukem’de neler yaptığını ise size ancak bir latte karşılığında anlatabilirim.
Ali’nin bir seneden uzun süren bilgisayar oyunu çılgınlığı menajerlik oyunlarıyla önünü alamadığı bir noktaya çıktı. Üstüne üstlük, hala haftada birkaç gün arkadaşlarıyla futbol&basketbol oynamaya da devam eden Ali, bir felakete doğru hızla ilerliyordu. Tanrım, nasıl da fark edememişti?! Sınavlarından çakmak üzereydi!
İlk uyarı matematik sınavıydı. Ali’nin sınava çalışması için önünde sadece son bir gün kalmıştı. Fakat Ali’de artık bazı alışkanlıklar baş göstermişti. Ders çalışmak yerine yapabileceği bir sürü seçeneği vardı:
1. Evde Kalmak
Ali evde kalmayı tercih ettiğinde hemen bilgisayarının başına oturuyordu. Bilgisayarı açmasının nedeni tabi ki dersleriyle alakalı değildi. Masaüstünde bulunan üç oyundan birini oynuyordu:
a. Fifa
b. Carmageddon
c. CM (Menajerlik oyunu)
2. Dışarı Çıkmak
Ali dışarı çıktığında da arkadaşlarıyla buluşup kütüphaneye gitmiyordu:
a. Top peşinde koş
b. Aylaklık yap
S.Ç.A. Grafı
Önceki yazılarda bahsettiğim graf konusu, Ali’nin durumunu açıklarken büyük bir kolaylık sağlar. Ali’nin ders çalışmamayı seçtiği durumlarda yapacağı tercihler sınavdan düşük not almasına yol açar:
Grafın Bize Anlattıkları
Yukarıdaki grafta çizgiler Ali’nin yaptığı seçimleri, noktalar ise Ali’nin hangi durumda olduğunu gösterir. Graf bize kesin olarak iki şeyi söyler: Ali, ders çalışmamayı seçer ve sonuçta sınavdan çakar.
Bu yüzden Ali’nin seçimlerini gösteren çizgilerin bir yönü vardır.
Seçimler yapılırken bazı adımlar atlanamaz. Örneğin, Fifa oynamak için önce bilgisayarın başına oturmak, onun için de evde kalmayı seçmek gerekir.
Ali’nin seçimlerinin aşağıdaki gibi olduğunu varsayalım:
Evde kal -> Bilgisayarı Aç -> Fifa oyna.
Bu durumda kısıtlı zamanı olan Ali’nin, zamanını Fifa oynamaya ayırdıktan sonra başa dönüp sınava çalışmasına olanak yoktur. Artık Ali için sınavdan kötü not almak kaçınılmaz bir son olacaktır.
Grafın bize anlattığı bir başka şey ise, Ali’nin yaptığı herhangi bir seçime geri dönememesidir. Matematikçiler bu tür grafları “yönlü çevrimsiz/asiklik/zincirleme graf” olarak adlandırmıştır.
***
Biraz Bilgi
Yönlü Çevrimsiz Graf
Bir yönlü çevrimsiz grafta döngü yoktur. Yani bir noktadan başlayıp yönlü çizgileri takip ettiğinizde, aynı noktaya bir daha dönemezsiniz.
Yönlü (ve sonlu) çevrimsiz graflarda en az bir “kaynak” ve yine en az bir “alış noktası” olarak adlandırılan noktalar bulunur.
Kaynak noktası, başka herhangi bir noktadan kendisine doğru çizgi gelmeyen noktadır. Yukarıdaki grafta “ders çalışma” isimli nokta, kaynak noktasıdır.
Alış noktası ise kendisinden başka herhangi bir noktaya doğru çizgi gitmeyen noktadır. Grafımızda “sınavdan çak” isimli nokta, alış noktasıdır.
***
Bi’ Göz Atmakta Fayda Var
Rutin işlerinizi yaparken aslında yönlü çevrimsiz grafları kullanıyorsunuz. Buna bir örnek göstermek için yine Ali’nin hayatından yararlanacağım.
Ali, her okul günü sabahında uyanır uyanmaz duş alıp okula hazırlanır. Bunu yaparken Ali’nin izlediği yol şunlardan oluşur:
Uyan
Duşa gir
Duş sonrası diş fırçala
Giyin
(Ali’nin okul kıyafeti pantolon, gömlek, kravat ve yelekten oluşuyor.)
Soru: Ali’nin okula hazırlanışını gösteren grafı çizin.
Not: Ali duştan sonra giyinirken her adımı doğru yönde tamamlamalıdır. Örneğin boxer’ını giymeden önce pantolonunu giyemez, değil mi?!
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 