Matematik ve Algoritmanın Gücü

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ı sağlar. Ancak sadece evren değil aslında her an elimizin altında olan bilgisayarlarda matematikten yapılmıştır.

Bilgisayarlar bildiğiniz üzere hızlı işlem yapabilen, verileri saklayabilen bir cihazdır. 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ürecin planlama kısmına biz algoritma diyoruz. Bir başka deyişle kafamdakini bilgisayara nasıl anlatırım sorusunu düşünmeye algoritma diyoruz. Ben de sizlere matematiği bilgisayara nasıl anlatırız onu anlatacağım. Yani matematiğin algoritmasını…

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.

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.

  1. İlk sayının ilk basamağını al ve ikinci sayının ilk basamağını al
  2. İkisini topla
  3. 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.

  1. İkinci sayının ilk basamağını al ve ilk sayının ilk basamağından başlayarak sola doğru her basamakla çarp
  2. Sonucu yaz.
  3. İ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.
  4. Sonuçları topla

Çarpma algoritmamızı yazdık. Burada da n basamaklı 2 sayıyı çarptığımızı düşünelim. n2 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 = niş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

  1. 4967 * 5147 işlemini gerçekleştirelim.
  2. Ş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

  1. 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.

  1. Ş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 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 matematiği bilgisayara nasıl anlatırız, algoritmaların matematiksel açıklamaları nasıl olur bunu tartışacağız. Küçük parçalar toplayarak acaba büyük parçada neler göreceğiz?

Sağlıcakla kalın.

Yusuf Önder

Matematiksel

Yazıyı Hazırlayan: Matematiksel

Bu yazı gönüllü yazarlarımız tarafından hazırlanmış veya sitemiz editörleri tarafından belirtilen kaynaktan aslına uygun kalınarak eklenmiştir.

Bunlara da Göz Atın

Matematikçi Şairler Algoritması – Turgut Uyar

“nedir sonsuzdan bir önceki sayının adı diyelim sonsuz eksi bir sonsuz eksi bir hayatın adıdır …

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

ga('send', 'pageview');