K-Point Crossover

Genetik algoritmalardaki crossing over kavramı malum; iki çözümü bir yerden kesip kesilen noktadan itibaren olan kısımları yer değiştiriyoruz, böylece elimizde 2 yeni sonuç oluyor.

 

OnePointCrossover.svg

 

Tek noktadan yapılan crossover işleminin yetersiz olması sonucu 2-point crossover, N-point crossover gibi yöntemler de çıkmış. Bu yöntemleri kullanarak çözümü birden fazla noktadan bölüp crossover'ı o noktalardan yapıyoruz. Maksat çözüm uzayındaki genetik çeşitliliği korumak.

 

kpoint

Aklıma gelen soru ise şu; bu crossover noktalarını uniform random olarak belirlediğimizi düşünelim. Bu olasılık da \(0.5\) olsun, yani bir noktanın crossover noktası (üstteki resimde yeşil çizgilerin kestiği noktalar yani) olma olasılığı \(0.5\). N-point crossover'daki N sayısının beklenen değeri bu durumda kaç olacaktır?

Her bölme noktasını var/yok şeklinde alacak olursak, elde edeceğimiz farklı bölme kombinasyonları, \(n\) çözüm kümesinin boyutu olmak üzere, \(|S| = 2^{n-1}\) tane olacak. Kesim noktalarının olduğu kümenin altküme sayısını bulmuş olduk aslında.

Bu \(2^{n-1}\) elemana bakarsak, çözümü hiç kesmediğimiz 1 durum, 1 kez kestiğimiz \(n-1\) durum ... olduğunu görürüz. Genel olarak bakınca her \(k\) noktadan kesme işlemini \(\binom{n-1}{k}\) defa yapıyoruz. Toplam durum sayısı da \(2^{n-1}\) olduğuna göre, \(E[n]\) beklenen değerini

\[E[n] = \frac{1}{2^{n-1}} \sum\limits_{k = 1}^{n-1} k \times \binom{n-1}{k}\]

ile hesaplayabiliriz. Bunu da uzun uzun hesaplamaya gerek yok çünkü yukarıdaki denklem bize \(B(n-1, 0.5)\) binom dağılımının ortalama değerini veriyor. \(B(n, p)\) dağılımının ortalaması

\[\mu=np\]

olduğuna göre, \(n\) elemanlı bir çözüm kümesi için sorunun cevabı \(\frac{n-1}{2}\) olacaktır.

LeetCode Online Judge

LeetCode, yazılımcı mülakatlarına hazırlanmak için bir sürü sorular barındıran bir site. Sorulara C, C++, Java ve Python'la cevap verilebiliyor.

Birkaç gündür buradaki soruları inceliyordum, gördüm ki C# desteği için bir çalışma başlatmışlar, mevcut soruları C#'a çevirecek insanlar arıyorlar. İşin asıl güzel tarafı da 10 tane çevirene kitap veriyorlar. Beleş kitaptan daha değerli ne var diyerek atladım. Bu akşam 7 tane soru çevirdim, yarın 10'a tamamlayıp kitabımı beklemeye başlayacağım :)

Beleş kitap candır diyenler admin@leetcode.com adresine "sorularınızı C#'a çevirmek istiyorum, email adresim de bu, şu kadar senedir C#'la uğraşıyorum" tarzı bir mail atıp şifre alabilirler.

Dizideki Eksik Elemanı Bulma

İş görüşmelerinde sorulan klasik bir soru var; \([-1, 2, -1, 3, 2]\) gibi bir dizinin içinde, biri hariç tüm sayılardan 2 tane, diğer sayıdan ise 1 tane vardır. Bu sayı hangisidir?

Bu sorunun envai çeşit çözümü var. Her elemanın dizideki diğer çiftini arayabiliriz (\(O(n^2)\), hatta genelleştirilmiş durumda, k tekrar varsa \(O(n^k)\)), diziyi sıralayıp kontrol edebiliriz (\(O(nlogn)\)), hashtable'a atıp sayılarını tutabiliriz (\(O(n)\), fakat ekstradan alan gerekli) falan filan.

En yaygın çözümü de tüm elemanları xorlayıp çıkan sonucu dönmektir. Bu çözüm aşağıdaki iki kurala dayanır

\[a \oplus a = 0\]

\[a \oplus 0 = a\]

Bu durumda tüm 2 sayılar 0 olacak, tek sayıyı da 0'la xorlayıp sayının kendisini elde edeceğiz.

Peki bu problemi daha da genelleştirirsek nasıl çözebiliriz? Diyelim ki elimizdeki sayı dizisindeki sayılar, biri hariç \(n\) defa tekrar ediyor, diğer sayı da, \(0 < k < n\) olmak üzere, \(k\) defa tekrar ediyor olsun. \(k\) defa tekrar eden sayıyı nasıl bulabiliriz? Tabii ki yöntem olarak da \(O(1)\) ekstra alan kullanan ve \(O(n)\) işlemde biten bir yöntemi tercih ediyoruz.

İlk durumda sayıların 1 bitlik olduğunu düşünelim, yani dizi sadece 1 ve 0'lardan oluşuyor. Dizinin toplamını alırsak sonuç ya \(0 \times n + 1 \times k\) ya da \(1 \times n + 0 \times k\) olacak. Bu toplamların \(n\)'e göre modunu aldığımızda çıkan sonuç \(0\) ya da \(k\) olacak. Bu sonuclar da aslında

\[k \times a\]

ifadesine eşit. \(a\) da bizim aradığımız sayı.

Kısacası; ifadenin modu \(0\) ise aradığımız sayı \(0\), değilse \(1\).

32 bitlik sayı dizilerinde ise yapmamız gereken, bu işlemi tüm sayılardaki her bite uygulamak. sonrasında çıkan sonuçlar tek tek bize \(k\) defa tekrarlanan sayıyı verecek.

Genel çözümün kodu aşağıdaki gibi olacak.

Bu çözümde işaret bitini de dikkate aldığımız için bu çözüm negatif sayılar için de çalışacaktır.

İTÜ IEEE Yazılım Maratonu

İTÜ IEEE kulübü 2 turdan oluşan bir yazılım maratonu düzenliyor. Yarışmanın ilk turu dün gece başladı ve bu gece sona erecek. 2. turunda ise ilk turda ilk 20'ye giren takımlar İTÜ kampüsünde yarışacak.

Sorular Yeditepe SAP Contest'e göre daha eğlenceli. Yine aynı yarışmaya göre test case'leri daha iyi hazırlanmış gibi duruyor.

C ve E soruları güzeldi. Yarışma bittikten sonra burada çözmeye çalışayım.

SAP Code Contest

Ocak ayı içinde Yeditepe Üniversitesi SAP ile birlikte bir kod yarışması düzenledi. Ben de yaşını başını almış bir alaylı competitive programmer olarak şansımı deneyeyim dedim.

6 soruluk ilk tur SAP'nin sitesinden online olarak yapıldı. Çözmek için 5 gün süre vardı. İlk turun soruları (şu an yarışma sitesine erişilemiyor o yüzden hatırlayamıyorum tam olarak) 5 gün sürecek bir yarışmaya göre çok da zor değildi açıkçası. Codeforces falan gibi sitelerden farklı olarak soruları dan diye sormuşlar, öyle hikayeydi geyikti yoktu pek. Bir soruda edge'leri vermiş, bu ağaç balanced mıdır değil midir onu bulun demiş mesela.

İlk turda belirli bir puan alanları da onsite finale davet ettiler. Normalde competitive programming'den gerçekten zevk alan biri olarak diyebilirim ki, bir odaya toplaşıp yarışmak çok daha heyecanlıymış. Burada nispeten daha zor sorular olsa da (haliyle) yine de ilk turdaki gibi çok lafı dolandırmayan sorulardı. 170 max puan üzerinden 156 alıp üniversite öğrencileri arasında 4. oldum. Bir araba eşantiyon ve 2 t-shirt dışında bir şey kazanamadım ama güzel bir tecrübe oldu diyebilirim benim için :).

Bir fotoğraf falan edinebilirsem bir yerlerden (o kadar fotoğraf çekmişler ama kimse bir yerlerden paylaşmadı henüz) buraya da koyarım :).