Algoritma, özellikle yapay zekâ alanında yapılan uygulamaların günlük hayatta daha sık kullanılmaya başlaması ile birlikte kodlama derslerinin popülerliği artmış durumda. Neredeyse okul öncesi öğrencilerinden veri bilimcilerine kadar tüm bireylerin içerik gündemlerine göz attığınızda bir algoritma başlığını görebilirsiniz. Aslında çok farkında olmasak da algoritmalar uzun zamandır hayatlarımızın bir parçası. Kullandığımız vatandaşlık numaralarından kredi kartlarımıza, sosyal medya görünürlüklerinden, dizi platformlarının tavsiye listelerine kadar bu yazının hacmini aşacak kadar çok mecrada insanların yaşamı algoritmalarla sürekli birliktelik hâlindedir.
Algoritmayı tanımlayarak başlamak hem matematiği karakterize eden aksiyomatik yapıdaki temel öneme sahip unsur olması, hem de algoritma kapsamı olarak neden mevzu bahis edildiğinin sınırlarını çizmesi açısından oldukça önemli. Bilgisayar bilimleri perspektifinden algoritma, bir sorunu çözmek veya bir görevi yerine getirmek için belirli ve açık bir şekilde tanımlanmış yönerge veya adımların sonlu bir sırasıdır. Matematiksel bir bakış açısıyla ise algoritma, bir hesaplama yapmak, bir matematiksel sorunu çözmek veya kararlar almak için kullanılan sistematik, adım adım bir prosedürdür.
Algoritmalar, sayılar teorisinden çizge teorisine kadar çeşitli matematik alanlarında sıkça kullanılır. Bir algoritmayı, bir problemi çözmek için bir prosedürü doğal bir dilde tanımlayarak veya prosedürü uygulayan bir bilgisayar programı yazarak tanımlayabiliriz [1] . Algoritma kavramını tanımlamak için evrensel olarak kabul edilmiş bir ifade olmamasına rağmen, kavramın ne anlama geldiği konusunda genel bir mutabakat vardır: Algoritma, bir problemi çözmek için, yani herhangi bir meşru/uygun girdi için gerekli bir çıktıyı sonlu bir süre içinde elde etmek için takip edilen kesin talimatlar dizisidir [2]. Şekil 1’de bu tanımın basit bir diyagramı gösterilmektedir.
Şekil 1. Hareld ve Fieldman tarafından yapılan tanımın Levitin [3] tarafından verilen diyagramı.
Tanımın içerisinde geçen “talimatlar” kelimesi, bu talimatları anlayabilen ve uygulayabilen bir şey veya kişinin varlığını ima eder. Biz bu varlığa “bilgisayar” diyoruz ve burada akılda tutmalıyız ki, elektronik bilgisayar icat edilmeden önce “bilgisayar” terimi, sayısal hesaplamalara katılan insanları da tanımlardı. Günümüzde ise bilgisayarlar, neredeyse her yaptığımız işte vazgeçilmez hâlegelmiş olan yaygın elektronik cihazlar şeklindebilinen bir tanıma sahiptir. Bilgisayarlaryardımıyla tanımlanan algoritmalar oldukça hızlı çözümleri insanların hesaplayamayacağı ölçüde yapabilir. Bu anlamda bir algoritmanın sahip olması gereken özelliklerin belirlenmesi önemlidir. Levitin (2008) bir algoritmanın sahip olması gereken özellikleri aşağıdaki maddeler hâlinde vermektedir.
Soyutlama bir algoritmanın genel çerçevesini oluşturmak için (değişkenler, döngüler, metodlar, fonksiyonlar vd.) mutlaka uygulanmalıdır.
Bir algoritmanın çalıştığı girdi aralığı dikkatli bir şekilde belirtilmelidir.
Algoritma verilen görevi sonlu bir zaman aralığında ve en verimli biçimde yapmalıdır.
Aynı algoritma birkaç farklı şekilde temsil edilebilir.
Aynı problemi çözmek için birden fazla algoritma mevcut olabilir.
Aynı problem için algoritmalar çok farklı fikirlere dayanabilir ve problemi önemli ölçüde farklı hızlarda çözebilir.
Bu özelliklere göz attığımızda problemlerin çözümüne yönelik tek bir algoritmadan ziyade farklı çözümlerin ele alınabileceği ve böylelikle kapasite, işlem hızı gibi sınırlamaları daha kolaylaştırıcı çözümlerin bulunabileceği de görülmektedir.
Algoritma kavramını açıklayan örnekler, matematik eğitiminin her düzeyinde karşımıza çıkar. Okul öncesinden liseye farklı matematik konuları içerisinde algoritmik bir yaklaşımın aynı problemi farklı olarak ele aldığını ve çözümler ürettiğini de görebilirsiniz. Bu yazı kapsamında iki tam sayınınen büyük ortak bölenini (EBOB) hesaplamak problemini çözmek için algoritma temelli iki yöntemi ele alacağız.
Öklid (M.Ö.) 3. yüzyılda yazdığı ve belki de tüm zamanların en önemli matematik kitaplarından biri olan Elemanlar isimli eserinde yüzyıllar boyunca Öklid Algoritması olarak anılacak Ebob değerini hesaplayabilen bir algoritma tanımlar. Aslında bu algoritma bir eşitliğin tekrarlı (iterative) olarak kullanılmasını temel almaktadır. Bu tekrar;
ebob(m, n)= ebob(n, m mod n)
eşitliğini ardışık biçimde tekrar etmesi ile oluşur. Örneğin, m =60 ve n=24 sayıları için eşitliği çalıştırdığımızda 24 modunda 60 sayısının kalanını 12 olarak hesaplarız. İşleme devam ettiğimizde 24 sayısının 12 modunda değeri 0 olacağından 12 iki sayının EBOB’u olarak elde edilir. Eşitlik üzerinde gösterecek olursak,
ebob (60, 24) = ebob (24, 12) = ebob (12, 0) = 12 olacaktır.
Şimdi bu tekrarlı yinelemeyi bir algoritma yapısına dönüştürmeye çalışalım.
Öklid Algoritması I (EBOB).
Adım 1. n = 0 ise, m değerini cevap olarak döndürün ve durun(örneğin EBOB(12,0)=12); aksi takdirde, Adım 2'ye geçin.
Adım 2. m'yi n'ye bölün ve kalanın değerini r'ye atayın.
Adım 3. n değerini m'ye ve r değerini n'ye atayın. Adım 1’e gidin.
Aynı algoritmayı, bilgisayar diline daha yakın bir gösterimle yazmaya çalışalım.
Öklid Algoritması II (EBOB).
//Öklid algoritması kodları
//Girdi: negatif olmayan, en az bir tanesi sıfırdan farklı iki pozitif tam sayı m ve n
//Çıktı: EBOB(m,n)pozitif tamsayısı
while n = 0 do
r ← m(mod n)
m←n
n←r
return m
II. algoritma temsilinin birinciden farkı, ikincinin bilgisayar diline daha yakın bir yapısının olması ve ikinci algoritmada algoritmanın hangi durumda duracağının belirlenmiş olmasıdır. İlk algoritmada buna ihtiyaç duyulmamıştır. Zira, işlemin devam etmeyeceğini insan hissedebilir ve durdurabilir, ancak bilgisayara sınırlılıkları net biçimde belirlememiz gerekir.
Algoritmalar, matematiksel yapıları gelişmek ve daha hızlı çalışmak için bir basamak olarak kullanırlar. Çok fazla zaman ve yer kaplama ihtimali olan problemler temel matematik bilgilerinin algoritmaya uygulanması ile kısa zamanda ve etkili biçimde çözülebilir. Bu bağlamda aşağıdaki soruyu inceleyelim.
Soru 1. 13195 sayısının asal bölenleri 5, 7, 13 ve 29 dur. Buna göre, 600851475143 sayısının en büyük asal bölenini 1 saniyeden az sürede bulan bir algoritma yazınız [4].
Sorudaki 1 saniyeden az süre kısmının biraz tedirgin edici olduğu açık. Bu kadar büyük bir sayının en büyük asal bölenini bulmak için önce problemimizi parçalara bölelim. Bu yönteme bilgisayar bilimlerinde böl ve yönet (divide and conquer) ismi verilir. Buna göre,
Önce sayının tüm bölenlerini bulalım.
Bu bölenlerden asal olanların hangileri olduğunu belirleyelim.
Belirlenen asal bölenleri sıralayalım.
Sıralanan asal sayılardan en büyüğünü ekrana yazdıralım.
oldukça akla yatkın bir yaklaşım olarak görünse bile algoritma karmaşıklığı ve kaynak kod karmaşıklığı açısından verimli bir yöntem değildir. Örneğin sadece birinci basamağın tamamlanması için
1. Önce sayının tüm bölenlerini bulalım
a. 1’den 600851475143’e kadar bir döngü yazalım.
b. 1. basamakta tanımlanan döngünün indeks değerinin 600851475143 sayısını tam
bölüp bölmediğini kontrol edelim.
c. Belirlenen sayıyı bir veri yapısı içine depolayalım
Şekil 2’de 100 sayısının asal çarpanlarının bulunması işlemi bir ortaokul öğrencisinin çözümü ile gösterilmiştir.
Şekil 2. Bir tam sayının asal çarpanlarının bulunması işlemi
Eğer Şekil 2’de verilen işlemler incelenirse; aşağıdaki algoritmaya ulaşmak zor olmayacaktır.
En Büyük Asal Çarpan Algoritması.
Adım 0. i değerini 2 olarak belirle.
Adım 1. Sıfırdan farklı bir m pozitif tamsayısı belirle.
Adım 2. Eğer i sayısı m değerini tam bölüyorsa Adım 2a. bölmüyorsa Adım 2b.’ye geç.
Adım 2a. m değerini m/a değeri ile değiştir, eğer m=1 ise Adım 3’e geç değilse Adım 2’ye dön.
Adım 2b. m değerini değiştirme, i değerini 1 artır ve Adım 2’ye dön.
Adım 3. i değerini ekrana yazdır.
Bu algoritmaya göre, bulunan son i değeri en büyük asal bölen olacaktır. Şimdi de bu algoritmayı C diline aktaralım.
#include
int main() {
long int n=600851475143;
int i=2, maxFact=-1;
while(n!=0) {
if(n % i !=0){
i = i + 1;
}
else {
maxFact = n;
n = n / i;
if(n == 1) {
printf("%d en büyük asal çarpandır !",maxFact);
break;
}
}
}
return 0;
}Eğer bu kodu kendi bilgisayarınızda çalıştırırsanız cevabın 0.001 saniye gibi çok kısa bir sürede ekrana 6857 olarak yazdığını görebilirsiniz. Aslında bu sorunun daha da hızlı çalışan bir çözümü de yapılabilir. Bu çözümün peşine düşmeyi okuyucuya bırakıyoruz.
Son yaptığımız çözümün etkililiğini daha iyi anlamak için kendi geliştirdiğiniz algoritma ile üstteki çözümü karşılaştırabilirsiniz. Böylelikle iki algoritma arasındaki çalışma zamanları farkını da net biçimde görmüş olursunuz.
Matematik, algoritmaların her zaman en büyük dayanağı olmuştur. Bu dayanak o kadar güçlüdür ki, bazen oldukça zor görünen algoritmaların arkasında bile oldukça temel matematiksel yapılar bulunabilir. Öklid veya Fermat, yüzlerce yıl evvel buldukları yöntemlerin bir gün bilgisayar bilimciler için hayat kurtarıcı olacağını hiç düşünmüşler midir bilinmez ancak, siz de matematik ve bilgisayar bilimleri birlikteliğini sınıflarınıza taşıyarak öğrencilerinizin bunu hissetmesini ve düşünmesini sağlayabilirsiniz.




