Galileo zamanında matematik için “Matematik, Tanrı’nın evreni yazdığı dildir.” demiştir. Gerçekten de matematik bizi her türlü büyüler; evreni anlamamızı, kendimizi keşfetmemizi sağlar. Ben ise bir bilgisayar mühendisi olarak matematik ile bilgisayarı size anlatmak istiyorum. Yazılarımda da bundan bahsedeceğim. Tabi nerelere gideriz zamanla orası belli olmaz.
Bilgisayar, önceden belleğine yüklenmiş bir yazılıma göre komuta edilerek, çok sayıda ve karmaşık mantıksal ve aritmetiksel işlemlerden oluşan bir işi çok kısa sürede yapıp sonuçlandırabilen aygıta verilen isimdir. Bilgisayar üzerinde işlem yapabilmek için bir takım komutlar yazarsınız ve çalıştırırsınız. Basit bir 4 işlemden tutun pi sayısının keşfine kadar her işlemi bir insanın yapabileceğinden kat kat hızlı bir şekilde bilgisayarla yapabilirsiniz. Fakat bilgisayarlarda işlem yapabilmek sistematik bir süreç gerektirir. İşte bu sistematik sürece biz algoritma diyoruz. Algoritma sadece bilgisayar biliminde kullanılan bir kavram değildir. Günlük hayattaki planlarınız, herhangi bir probleme yaklaşımınızda aslında bir algoritmadır. Ama biz yazılarımızda algoritmanın tanımını “Aklımızdakini bilgisayara anlatma yolu” olarak hafızaya atalım. Ben de sizlere bazı problemlerin algoritmasını oluştururken matematiğin bize nasıl yardımcı olacağını anlatacağım. İlk konumuz ise ilk okuduğumda çok ilginç olan çarpma…
Mesela basit bir örnek yapalım. Öncelikle bilgisayar 4 işlemi nasıl yapıyor? Normal bir bilgisayarda 8 basamaklı bir sayı ile 6 basamaklı bir sayıyı milisaniye altında hesaplayabiliyoruz. Peki, bilgisayar bunu nasıl yapıyor? 4 işlemin algoritması nedir? Bunun için önce bilgisayarların çalışma prensibine kısaca değinelim.
Bizler bildiğiniz gibi günlük hayatta 10’luk taban kullanırız. Yani elde dediğimiz sayı toplam 10’u ve katlarını geçtiğinde hesaba katılır. Bilgisayar ise 2’lik(binary) taban kullanır. Yani bizdeki 5 sayısı bilgisayar için 101’dir. Ve bilgisayarlar işlem yaparken bu 2’lik tabanı kullanır. Tabanlar farklı olmasına rağmen hesaplama tarzı aynıdır. Yani “grade school” algoritması kullanılır. -Bakın aslında bir algoritma kullanıyormuşsunuz- Peki nedir bu “grade school” algoritması? Hepimizin bildiği 4 işlem hesaplamalarına “grade school” algoritması denir. Örnek vermek gerekirse 324 + 193 işlemini ele alalım.
- 4 + 3 = 7
- 2 + 9 = 1 (elde var 1)
- 3 + 1 = 4 + 1 = 5
- 517
Sonucu 517 olarak bulduk. Şimdide bilgisayar gözünden bakalım fakat binary sistem kullandığımız için küçük sayılar seçelim. Mesela 7 + 5 işlemini ele alalım.
- Denkliklerimizi yazalım (7)10=(111)2 ve (5)10 = (101)2
- 111 + 101
- 1 + 1 = 0(elde var 1)
- 1 + 0 = 1 + 1 = 0(elde var 1)
- 1 +1 = 10 + 1 = 11(son eleman olduğu için bir basamak daha artırmış olduk)
- (1100)2 = (12)10
Gördüğünüz gibi bilgisayarlar da 2’lik sistemde herkesin bildiği gibi toplama işlemini gerçekleştirdi. Bilgisayarlarda bu işlemler donanım temelli olarak ALU dediğimiz devrelerde gerçekleştirilir. Bir ALU üzerinde toplama, çıkarma, “ve”, “veya” işlemleri tanımlıdır. ALU’lar kapı dediğimiz lojik devrelerden oluşurlar. Fakat şimdi konumuz bu olmadığı için fazla detaylı anlatmanın lüzumu yok.
Tekrar algoritmalara dönecek olursak, algoritmaların karmaşıklığı dediğimiz bir nokta vardır. Kısaca açıklamak gerekirse algoritmanın verimi diyebiliriz. Algoritmaların verimi pek çok açıdan ölçülebilir. Buna zaman, yer(bellekte kapladığı alan) örnek olarak verilebilir. Biz şimdilik zaman açısından ele alalım. Algoritmanın zamansal verimi algoritmanın girdisi ile ölçülür. O halde “Grade School” algoritmasına göre toplama işleminin karmaşıklığını inceleyelim.
- İlk sayının ilk basamağını al ve ikinci sayının ilk basamağını al
- İkisini topla
- Ve 2. Adımı bir sol basamak kayarak sayı bitimine kadar sürdür.
Algoritmamızı yazdık. Burada n basamaklı 2 sayıyı topladığımızı düşünelim. Yani algoritmamızda n tane basamağı tek tek dolanıyoruz. Yani karmaşıklığımız n karmaşıklıktır. Çarpma işlemini ele alalım.
- İkinci sayının ilk basamağını al ve ilk sayının ilk basamağından başlayarak sola doğru her basamakla çarp
- Sonucu yaz.
- İlk adımı ikinci sayıyı bir sol basamak kaydırarak sayı sonuna kadar ilerlet ve sonucu bir önceki sonucun bir soluna kaydırarak yaz.
- Sonuçları topla
Çarpma algoritmamızı yazdık. Burada da n basamaklı 2 sayıyı çarptığımızı düşünelim. n^2 bir karmaşıklık olduğunu görüyoruz değil mi? İkinci sayının her basamağını ilk sayının her basamağı ile çarpıyoruz. n tane n işlem yapıyoruz. Haliyle n * n = n^2 işlem yapmış olduk.
Peki, çarpma işlemini daha hızlı yapabileceğimizi söylesem? Yani bilgisayara çarpma işlemini daha hızlı yapabileceği şekilde anlatabileceğimizi? İşte algoritmanın gücü…
Rus Matematikçi Anatoly Karatsuba çarpma işlemini daha hızlı gerçekleştiren bir çarpma algoritması yazmıştır ve Karatsuba Algoritması adını vermiştir. Bu algoritmada amaç çarpılacak sayıları alt gruplara bölerek işlem yapmaktır. Gelin bir örnekle açıklayalım bunu
- 4967 * 5147 işlemini gerçekleştirelim.
- Şimdi bu sayıları gruplara bölelim. Bu işlemi yaparken aşağıdaki denklem gibi böleceğiz
X = X1Bm+X0
Y = Y1Bm+Y0
4967 = 4 * 103 + 967
5147 = 5 * 103 + 147
- Bu durumda çarpma işlemi
X*Y = (X1Bm+X0) * (Y1Bm+Y0) şeklinde olacaktır. Düzenlersek
X*Y = Z2B2m + Z1Bm+Zo olacaktır. Burada
Z2 = X1Y1
Z1 = X1Y0 + X0Y1 = (X1 + X0)(Y1 + Y0) − Z2 − Z0
Z0 = X0Y0
Olarak tanımlanmış olacaktır.
- Şimdi ise sadece eşitlikleri yerine yazalım.
4 * 5 * 106 + ((4 + 967) * (5 + 147) – 4*5 – 147 * 967) * 103 + 967 * 147
Ve sonucumuz = 25.565.149 çıkacaktır.
Peki, bu algoritmanın karmaşıklığı nedir? Bu algoritmanın karmaşıklığı nlog23 tür. Yani yaklaşık olarak n1,585tir. Gördüğünüz gibi “Grade School” algoritmasına göre daha az karmaşıklıkta bir algoritma ile çarpma işlemini gerçekleştirmiş olduk. Karmaşıklık hesabı ayrı bir konu ve daha derin matematik bilgisi içerir. Belki bir blog yazımızda da ona değiniriz.
Evet, gördüğünüz gibi matematik ve algoritma tencere ve kapağı gibi yuvarlanıp birbirini tamamlar 🙂 Bu yazımızda da sizinle algoritmalara ve matematiksel işlemlerin algoritmalarına girmiş bulunmaktayız. Zaten yazılarımda hep matematik aklımızdakini bilgisayara anlatmamızda nasıl yardımcı olur, algoritmaların matematiksel açıklamaları nasıl olur bunu konuşacak bunu tartışacağız. Çok faydalı bilgiler elde edeceğimiz kesin. Küçük parçalar toplayarak acaba büyük parçada neler göreceğiz?
Sağlıcakla kalın.
Kaynakça: https://en.wikipedia.org/wiki/Karatsuba_algorithm
