Çanakkale Gezisi

Hafta sonunu Çanakkale'de geçirdim. Şehri beğendim. Tam bir öğrenci şehri. İzmir'den sonra şehir içinde her yere yürüyerek gitmek tam bir güzellik. Sevdim. Söylenecek en önemli şey mutlaka görülmesi gerektiği. Şehrin her yeri zaten Milli Park. Yeşil ve mavi'nin çok güzel buluştuğu bir yer.

Aşağıda çekmiş olduğum resimlerden (400 civarı resim çektim :) ) seçtiğim 5 tanesini görebilirsiniz:



Kısayol tuşları

Web tarayıcıma adres girerken kısayol olarak Ctrl+Enter tuşlarını kullanıp www. ve .com kelimelerini yazma zahmetinden kurtuluyordum. Bugün yanlışlıkla Ctrl+Shift+Enter tuşlarına bastım, www. ve .org olarak geldi site; bunu görünce Shift+Enter ne yapıyor diye baktım; www. ve .net ekliyormuş.

Tarayıcının adres çubuğuna "google" yazıp
Ctrl+Enter yapın: www.google.com
Shift+Enter yapın: www.google.net
Ctrl+Shift+Enter yapın: www.google.org gelecektir.

Böl ve İşgal Et (Divide & Conquer)

Başlık sizi şaşırtmasın. Siyasetten falan bahsetmeyeceğim. Bu yazıda bir başka algoritma tasarım tekniği olan böl ve işgal et tekniğinden bahsedeceğim.

Bilgisayar bilimlerinde böl ve işgal et (D&C) önemli bir algoritma tasarım tekniğidir. Bir problemin iki veya daha fazla benzer alt probleme parçalanarak özyinelemeli olarak çözülmesine dayanmaktadır. Daha sonra bu alt problemlerin çözümleri arasından çözüm seçilir. Arama (Mergesort, Quicksort), "Discrete Fourier Transforms" (FFTs) dahil olmak üzere bir çok algoritma bu yöntemi kullanmaktadır.

D&C algoritmaları özyinelemeli yordamlar şeklinde gerçekleştirilmektedir. Dilerseniz sonuçların bir veri tipinde saklandığı özyinelemeli olmayan şekilde de kullanabilirsiniz.

Örnek vererek ne olduğunu anlatmaya çalışayım.

Problemimiz bir dizi içerisindeki en büyük sayıyı bulmak. Bunu aşağıdaki çok kolay algoritma yardımıyla tek geçişte bulabilirsiniz, evet ama anlaşılması için basit bir örnek veriyorum.

private static void normalMAX(double[] dizi) {
double max = dizi[0];
for (int i = 0; i < dizi.length; i++) {
if (dizi[i] > max)
max = dizi[i];
}
System.out.println("MAX:" + max);
}


Aşağıdaki kod parçasında ise bu problemin D&C yöntemi kullanılarak hazırlanmış çözüm algoritmasını görmektesiniz:
private static void dcMAX(double[] dizi) {
System.out.println("MAX:"+max(dizi,0,dizi.length/2));
}

private static double max(double a[], int l, int r) {
if (l == r)
return a[l];
int m = (l + r) / 2;
double u = max(a, l, m);
double v = max(a, m + 1, r);
if (u > v)
return u;
else
return v;
}

Bu şekilde çözdüğünüz zaman mesela 100000 elemanlık bir dizi için 1 milisaniye kazancınız oluyor :)

Bir başka kullanıldığı alan Hanoi kulelerinin çözüm algoritmasıdır. Bunu nasıl yapıyor derseniz problemi alt problemlere bölerek çözerek yapıyor :)

D&C yöntemi zor problemlerin çözülmesinde verimli algoritmalar bulunmasında çok kullanılmaktadır. Problemi alt parçalara ayırarak paralelliği de desteklemektedir.

En önemli dezavantajı özyinelemeden kaynaklanan yavaşlıktır. Tekrar eden altyordam çağrıları yeterince büyük olmayan çağrı yığıtlarında problemler yaratabilmektedir. Bir başka dezavantajı parçalara bölerek çözmenin, işlemlerin karmaşıklaşmasına neden olmasıdır.

Bazı problemler için, çoğu alt problemin sonucu aynı olabilmektedir. Bu durumda çözümlerin tekrar tekrar kullanılması önem kazanmaktadır. Bu yönteme memoization adı verilmektedir. Dinamik programlamanın özyinelemeli türüdür.


Bağlantılar:

http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm
http://www.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html
http://en.wikipedia.org/wiki/Memoization
http://members.comu.edu.tr/kadayif/algoritmaanalizi/algoritmaanalizi.htm

Coca Cola İle Eller Havaya

Son zamanlarda televizyonlarda karşımıza sıkça çıkan bir Coca Cola reklamı var. Bir haftalık aşkına hemen seni seviyorum diyen kız, eller havaya! İşe öğlen başlamak isteyenler, eller havaya! Saçının döküldüğünü gizlemek için sürekli kazıtan adam, eller havaya(özellikle bu kısım canımı sıkıyor :)) vs... Sonunda da Coca Cola light içip asla içmem diyenler eller havaya şeklinde bağlıyorlar reklamı.

Öncelikle Coca Cola'nın bütün reklamlarında belirttiği ana reklam sloganı hakkında bir şeyler söylemek istiyorum: Hayatın Tadı!... Bu kadar iddialı bir slogan olabilir mi ya? Bütün dünyadaki milyonlarca tat arasından kendi tadını nasıl hayatın ortak bir tadı olarak belirleyebilirsin? Fırsatım olsa sormak isterdim Coca Cola yetkililerine sen hiç çocukken köy ekmeğine ev salçası sürüp üstüne biber ekleyip yedin mi? Terleme nedir bilir misin? Ya da boğazından bir damla yayık ayranı geçti mi diye... Bana kalırsa bu iddialı sloganları da bütün dünyayı Amerika sanmalarından kaynaklanıyor gibi.

Yukarda ilk belirttiğim reklama dönecek olursak, bu reklamı son izlediğimde kafamda farklı bir reklam oluştu, sizlerle paylaşayım dedim:

İlk kurulduğu günlerde "Çocuk emeği dünya üzerindeki bütün ülkelerde başarının ölçüsüdür" diyen patronları(Asa Chandler) sayesinde çocukları köleler gibi çalıştıranlar, eller havaya!

1970'lerde Guetamala'da ve Kolombiya'da kendi çalışanları arasındaki sendikacıların üzerine kiralık katilleri ve işkencecileri salanlar, eller havaya!

Yine 1970'lerde Güney Afrika'da ırkçı rejimin hapse attığı siyah mahkumları ayda 7,5 dolara çalıştıranlar, eller havaya!

2000 Yılındaki Amerikan seçimlerinde George W. Bush'un seçim kampanyasına 1 milyon dolar bağış yapanlar, eller havaya!

Günümüzde, Dudullu'daki fabrikasından sendikaya üye oldukları için 103 işçiyi işten çıkaranlar, eller havaya!

Bağlantılar:
http://www.bianet.org/2004/02/23/26216.htm
http://www.barisarock.org/haber.php?haber_id=22

Exif

Exif sayısal fotoğraf makineleri tarafından kullanılan bir resim bilgisi saklama belirtimidir. Exif ile tanışmam fotoğrafçılığa meraklı bir arkadaşımın yeni aldığım ikinci el makinede daha önce kaç poz çekilmiş olduğunu sorması ve devam eden sohbet sonrasında oldu. Sayısal makinelerde jpg içerisine birçok bilgi saklanıyor. Bu bilgileri okumak için ise özel yazılımlar gerekiyor.

Hemen araştırma yaptım, neyin nesiymiş bu diye. ExifTool yazılımını indirip kurduktan sonra ilk çektiğim RAW resmin özelliklerini inceledim. Shutter count resim sayısı bilgisini tutan bir başlık sahası (Fotoğrafla ilgili bir çok bilgi saklanıyor). Bu saha sayesinde daha önce 1420 kere "shutter"'a basıldığını anladım. :) Eğer fotoğrafçılık ilginizi çekiyorsa mutlaka Exif konusunu biliyorsunuzdur. Bilmeyenler için bağlantıları vermektir tek amacım :D

Bağlantılar:
http://en.wikipedia.org/wiki/Exif
http://netzreport.googlepages.com/hidden_data_in_jpeg_files.html
http://www.exif.org/

Not: Bu yazıyla birlikte yeni bir etiketi de günlüğe eklemiş oluyoruz :)

Köy havası - Hamamözü

Amasya'nın merkezine girmedim ama, namı diğer "Tarla kuşu" arkadaşımın memleketi, Hamamözü'nü gördüm. Çocukluktan kalma birçok alışkanlığı yeniden yaşayabilirsiniz burada. Ve birkaç saat içerisinde, şehirdeki hayatın hızına olan alışkanlığınız ömrünüz 4 katına çıkmış hissi verir gibi yavaşlayacaktır.

Arada bir farklı yaşam tarzlarının da olduğunu hatırlamak, ilerisi için yaptığım planları da etkiliyor tabii. Fotoğraflar anlatabilir mi bilmiyorum ama, ilk fırsatta gidin yakın bir köye; yaşamın ve doğanın güzelliklerini hatırlayın.

Kendi halinde küçük bir kaplıca da var Hamaözü'nün merkezinde; buraya da uğrayabilirsiniz fırsatınız olursa, dinlendiriyor insanı iyice. Yalnız fazla kalmayın ilk defa giriyorsanız, çıkışta içeriye göre oksijen fazla geldi ve kendime gelemedim bir süre :)

işte birkaç fotoğraf:











Başkalarının Hayatı

1984 Doğu Almanya'sının vatandaşları üzerinde baskı kurmak için kullandığu en büyük silah Ministerium für Staatssicherheit yani Devlet Güvenlik Bakanlığı'dır ve bu kurumun en başarılı subaylarından birisi Gerd Wiesler'dir.

Tam bir yavşak politikacı profili çizen dönemin Kültür Bakanı, yine o dönemde Doğu Almanya'nın en başarılı yazarlarından birisi olarak kabul edilen Georg Dreyman'ın yavuklusuna gözü koyar ve yazarımızın açığının bulunması için Gerd Wiesler görevlendirilir.

Zaman, başbakan hakkında bir fıkra anlattığınız zaman kariyerinizin sonlandığı; gazetelerin, tiyatroların, kitapların yasaklandığı bir zaman. Dolayısıyla pek bir entellektüel olan Georg Dreyman'ın mutlaka bir açığını yakalarız diye düşünürler ve yazarın evde olmadığı bir gün eve girip bütün dinleme teşkilatını eve bir güzel döşerler. Yazarımız etliye sütlüye dokunmadan yaşamını devam ettirirken en yakın arkadaşlarından olan yasaklı bir tiyatro yönetmeni içinde olduğu duruma dayanamaz ve intihar eder. Bu olay yazarımızı artık bişey yapmalı şeklinde dürter ve alır kaleme girişir yazmaya...

Görevinin gereklerinden asla taviz vermeyen sert yüzbaşı, yazarın evini dinlerken içinde bulunduğu durumda bir terslik olduğunu anlamaya başlar. Kendi bildiği doğrularla yazarın savunduğu doğrular çelişmektedir. Sonuç olarak görevi açısından asla yapmaması gerekeni yapar, yani yazarın hayatına ufak müdahalelerde bulunur. Ama aslında kendisi yazarın hayatına girdikçe; yazarın hayatı, savunduğu fikirler de kendi aklına, zihnine girmektedir. Ve sonuçta kaçınılmaz olan gerçekleşir, değişim başlar...

Yönetmen, Florian Hencel Von Donnersmack'ın aynı zamanda senaryosunu da yazdığı film, 79. Oscar Töreni'nde en iyi yabancı film dalında Almanya'dan Oscar'a aday oldu ve sonuçta da aldı. Film aynı zamanda 19. Avrupa Film Ödülleri'nde en iyi film ödülünü almıştı. İzledikten sonra bu ödülleri haketmediğini söylemek zor. Dönemin baskıcı Doğu Almanya'sı duru ve net bir şekilde aktarılıyor. Mekanların sinir bozucu sadeliği ve soğukluğu o zamanın doğu bloku ülkesi havasını kesinlikle size hissettiriyor. Yüzbaşıyı canlandıran başrol oyuncusu Ulrich Muche de kesinlikle çok başarılı. Psikopatlık derecesinde görevine bağlı bir adamın yaşadığı ikilemi ve akabinde yaşadığı değişimi izleyiciye aktarırken kullandığı abartıdan uzak mimikleri ve Kevin Spacey'i anımsatan donuk bakışları kendisini öne çıkartan faktörler...

Sonuç olarak:
- Hediye paketi mi olsun?
- Hayır, bu benim için...

Dinamik Programlama

Bugün dinamik programlama hakkında bir örnek yapmaya karar verdim. İlk olarak dinamik programlamanın ne olduğundan bahsedeceğim. Daha sonra Fibonacci sayılarına dayanan örneği vereceğim.
Dinamik programlama problemleri tekrarlayan alt problemler şeklinde ele alıp çözen bir tekniktir. Bu yöntemde amaç tekrarlayan problem çözümlerini saklayarak, bu çözümleri gerektiğinde tekrar kullanmaktır. Her üretilen çözüm bir tabloda (veri yapısında) saklanarak gerektiğinde tekrar tekrar kullanılmaktadır.
Bu yöntemi en iyi Fibonacci sayılarıyla anlatabiliriz. Fibonacci sayıları aşağıdaki formülle özetlenebilecek bir seriyi tanımlar;
F(n) = F(n-1) + F(n-2)
Yukarıdaki formülü pozitif bir sayıya uyguladığımız zaman Fibonacci sayısını elde edebiliriz. Aşağıda 10 için Fibonacci elde etme incelenebilir:
0 1 1 2 3 5 8 13 21 34
En temel şekliyle Fibonacci sayılarını özyinelemeli yöntemle çözebiliriz:
F(n)
if n<=1 return n else return F(n-1) + F(n-2)
Yukarıdaki özyinelemeli yöntem küçük sayılar için ne kadar başarılı olsa da mesela 5 sayısını hesaplamak için 5 seviyeli bir ağaç oluşmasına neden olmaktadır. Ayrıca mesela F(2) yukarıdaki algoritmada 3 kere tekrar tekrar hesaplanmaktadır. Benim dizüstü F(50)'yi hesaplayamamakta, işlemcinin ısınması sonucu kendisini kapatmaktadır (:)). Bu algoritmanın başarım değerinin çift üssel olduğu yapılan analiz sonucu bulunabilir (bu yazının konusu değil :D )
Bu algoritmayı dinamik programlama yöntemiyle daha etkin bir şekilde yazabiliriz. Tekrar tekrar hesaplamak yerine hesapladığımız değeri saklayarak çözüme ulaşabiliriz:
F(n)
F[0] = 0
F[1] = 1
for i=2 to n do
F[i] = F[i-1]+F[i-2]
return F[n]
Bu iki algoritmayı karşılaştırmak için çok basit bir Java örneği yaptım (Kodunu en aşağıda bulabilirsiniz). Bilgisayarın kapanması nedeniyle sadece 10-20-30 ve 40 için Fibonacci sayı hesaplama sürelerini karşılaştırdım. Bu değerler bile ikinci algoritmanın başarısını göstermek için yeterlidir (Soldaki parantez içindeki özyinelemelinin süresi, sağdaki DP süresi):
[10]55(0) 55(0)
[20]6765(2) 6765(0)
[30]832040(130) 832040(0)
[40]102334155(2595) 102334155(0)
Hatta çok büyük sayıları problem yaşamadan DP algoritması ile bulabilirsiniz.

Bağlantılar:
http://kodveus.blogspot.com/2006/05/fibonacci-saylar-ve-pivolka.html
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg
http://en.wikipedia.org/wiki/Dynamic_programming

Kitap Önerisi:
Introduction to the Design and Analysis of Algorithms

Bağlantılar:
Introduction to Dynamic Programming

Kaynak Kod: (Biçimlendirme Serkan'ın önerisi ile Java2Html çevirici ile yapıldı ;))

package tekrei;
/**
* Bu sinifin amaci Devingen Programlamayi (Dynamic Programming) orneklemektir.
*
* @author emre
*
*/
public class DevingenProgramlama {
public static void main(String[] args) {
for (int i = 1; i < 5; i++) {
System.out.print("[" + i * 10 + "]");
long baslangic = System.currentTimeMillis();
System.out.print(fibRec(i * 10));
System.out.print("(" + (System.currentTimeMillis() - baslangic)
+ ")");
baslangic = System.currentTimeMillis();
System.out.print(" " + fibDP(i * 10));
System.out.println("(" + (System.currentTimeMillis() - baslangic)
+ ")");
}
System.out.println("Fib(1000):" + fibDP(100));
}

/**
* * Fibonnaci Sayilari: * F(n) = F(n-1) + F(n-2) {n>=2 için} {Baslangic
* Degerleri: F(0) = 0 F(1) = 1}
*
* Ornek bir seri: 0 1 1 2 3 5 8 13 21 34 55 .......
*/

/**
* Ozyineli olarak fibonacci sayisini hesaplayan metod
*/
private static long fibRec(int sayi) {
if (sayi <= 1)
return sayi;
return fibRec(sayi - 1) + fibRec(sayi - 2);
}

/** * Devingen programlama yontemiyle fibonacci sayisini * hesaplayan metod */
private static long fibDP(int sayi) {
long[] deger = new long[sayi + 1];
deger[0] = 0;
deger[1] = 1;
for (int i = 2; i < sayi + 1; i++) {
deger[i] = deger[i - 1] + deger[i - 2];
}
return deger[sayi];
}
}

Kavgamıza

Gördün mü cehaletimi,
İki insanı dahi inandırmadım kavgama.
Önce kendim inanmadım,
sonra kimseyi inandıramadım.
Hep böyleydi yaşam sandım,
ve hep böyle kalacaktı.

Okuduk, okuduk da durduk,
ulu bir önder bekledik durduk.
Önderlik dünde kaldı oysa,
değişen çok şey gibi,
savaşımın yöntemi de değişti.
Oysa çok düşündük,
biz günlerce toplandık,
insan olalım, fikir üretelim, birlik olalım.
Sonra kardeşler bile kızdı birbirine,
ve biz kardeşler bile inanmadık kavgamıza.

İki insanı dahi inandırmadım kavgama,
dağıldık, döküldük memleketimin kanayan ırmaklarına.
Kaybeden hep memleketim oldu,
umutlar gelecek nesile mi kaldı yine,
başaramadık sanırım biz de.

mki