ALGORİTMA

Tanım: Kelime anlamı olarak algoritma; bir sonuç elde etmek için kullanılan yöntemin bu sonuç elde edilinceye kadar sürdürülmesidir. Başka bir deyişle algoritma belirli bir kurala bağlı olan her türlü hesap işlerine verilen addır.
Matematikte ise algoritma bir sorunun yanıtını ya da bir problemin çözümünü sonlu sayıda aşmada veren sistematik yöntemdir.
Algoritma kelimesi IX.yy’ın başında yaşamış olan ünlü Türk matematikçilerinden Muhammed ibni Musa El-Marezini”nin isminden türetilmiştir. Avrupalıların El-Marezmi’nin ismini “Alkhorismi” biçiminde söylemlerinden Algoritma kelimesi doğmuştur.
Çok çeşitli algoritmalar vardır. Örneğin iki sayının en büyük ortak bölenini bulma “öklid algoritması” olarak bilinir. Ayrıca bilgisayar alanında ve otomatik hesap makinalarında algoritmalardan çokça yararlanılır.
* Basit bir algoritma örneği; Bir sayının karekökünü bulma
324 sayısının karekökünü basit işlemlerle bulmaya çalışalım;
ilk önce bir tahmin yapılır. Tahmin edilen sayı 15 olsun
Tahmin doğruluğu denenir 324 ÷ 15 = 21,6
Çıkan sonuçla tahmin edilen 31.6 + 15 = 36.6
Sayının ortalaması alınır. 36.6 ÷ 2 = 18.3
Yeni sonuç tekrar denenir 324 ÷ 18.3 = 17.7
Tekrar ortalama alınır 17.7 + 18.3 = 36
36 ÷ 2 = 18
- Yeni sonuç tekrar denenir. 342 ÷ 18 = 18
Tahmin edilebildiği gibi algoritmalarla hesap makineleri arasında sıkı bir bağ vardır. Öyle ki makineyle yapılabilen herhangi bir işlem bir algaritma şeklinde yazılabilir. Aynı şekilde şimdiye kadar kurulmuş bütün algoritmalar hesap makinasıyla yapılabilir.
Bununla birlikte bilgisayar alanında da problem çözümü için algoritmalardan oldukça fazla yararlanılır.
Bilgisayar kullanarak problem çözerken ilk yapılacak iş problemi anlayarak analiz etmek ve çözüm yollarını ortaya koymaktır. Bilgisayarlar henüz problemin nasıl çözüleceği konusunda insanlara yardımcı olamıyor. Sadece insanların çözüm için gösterdiği yollardan giderek komutları hatasızca uygulamaktadır. Bilgisayarın doğru sonuca ulaşabilmesi için kendisine gösterilen çözüm yolunda hiçbir belirsizlikle ve karışıklıkla karşılaşmaması gerekir. Bu nedenle hazırlanacak çözüm yolunda her türlü detay bulunmalı ve karşılaşılabilecek değişik durumlarda bilgisayarın çözüme nasıl devam edeceği bildirilmelidir.
Problem çözümü için bilgisayara verilen çözüm yöntemleri birer algoritmadır.
* Bir algoritmada olması gereken özellikler;
Sonluluk (Bir algoritma ancak sonlu sayıda adımlarla gerekli sonuca götürürse gerçeklenebilmesi mümkündür).
Kesinlik (Bir algoritmada belirsizliklere yer verilmemelidir).
Genellik (Bir algoritma sınırlı sayıda belirli kurallardan oluşmalıdır).
Şimdi şu örneğe bakalım
Sayıların karesini almak
A = O (A’ya O değerini ver)
B = A x A (A’yı kendisiyle çarp ve B’ye bulduğun değeri ver)
B’yi yaz
A = A + 1 (A’nın değerini 1 arttır)
2. adıma dön.
Tarif sonlu sayıda kuraldan oluşmasına rağmen hiçbir zaman sona eremeyecektir. Bu tarifi uygulamaya çalışan bir kişi ya da bilgisayar O’dan başlayarak sonsuza kadar tüm sayıların karesini almaya çalışacaktır.
Belli bir yerde durmayı sağlamak için tarife yeni bir adım ekleyelim. Acaba bu sefer “algoritma” özelliklerini gerçekleştirebilecek miyiz?
A = O
B = A x A
B’yi yaz
A = A + 1
A çok büyük bir sayı ise dur
2. adıma dön.
Üstteki tarifi uygulamaya çalışan bir insan kedi büyük sayı kavramına göre belirli bir yerde duracaktır. Bu sayı kimisi için 500.000 kimisi için 1.538 vb. olabilir. Ancak bilgisayar için “çok büyük bir sayı” nedir? Bu belirsizlikten dolayı üstteki tarifte bir algoritma değildir. Örnekteki tarifimizi algoritma haline getirmek için “çok büyük sayı”yı 1.000 olarak seçelim.
O’dan 1.000’e kadar olan sayıların karesini alan algoritma:
A = O
B = A x A
B’yi yaz
A = A + 1
A > 1.000 ise dur
2. adıma dön.
Algoritma kavramının tam olarak matematik tarifi 1930’a kadar meydana getirilmemiştir. Bu demek oluyor ki asırlar boyunca matematikçiler tam olarak açık olmayan bir algoritma kavramına göz yummuşlardır. Matematiksel incelemeye yeterli derecede doğru bir tarif için ancak yakın zamanlarda ihtiyaç duyulmuştur. Daha öncelerde, kurulan sistemin herhangi bir veriye uygulandığı zaman aranan sonuca kendi kendine götürdüğünün gösterilmesi yeterliydi. Böylece her ne kadar her matematikçi algoritma kavramına dair temel bir fikre sahipse de kesin bir tarife ait ihtiyaç duyulmamıştır. Ancak matematikçilerin gitgide genelleşen problem tiplerini çözmek için gittikçe daha güçlü olan algoritmaları kurma isteklerinin başlaması “algoritma” kavramı üzerinde biraz daha fazla düşünmelerini sağlamıştır.
* Problem genelleştikçe algoritmasını kurmak göçleşir.
Az önce karekök almak için bir algoritma kullanmıştık. Bu problemi genelleştirirsek;
“verilen herhangi bir sayının herhangi kuvvetten kökünü bulmaya yarayan bir algoritma kurmak” Böyle bir algoritmayı kurmak daha güçtür. Daha da genelleştirirsek;
“Bir a sayısının n. kuvvetten kökünü bulma”
Bu problem Xn = a Xn – a = O denklemini çözme anlamına gelir.
Daha genel olarak aşağıdaki gibi problemi formüle edebiliriz. n Î Zx
an Xn + an-ı Xn-ı + ....... +aı + ao = o (Bittabi denk)
şeklindeki herhangi bir denklemin köklerini bulmaya yarayan bir algoritma kurmak.
Bu algoritmayı kurmak daha da güçtür. Gerçekten de denklemler teorisinin esas içeriği bu algoritmayı kurmaktan ibarettir bunu önemi büyüktür.
Verilen örnekler gittikçe daha genel tipten problemleri çözmeye, gittikçe daha güçlü algoritmalar bulmakta matematikçilerin çabasını göstermektedir. Yukarıdaki * şeklindeki bütün denklemleri çözme örneği gidilebilen sınır göstermez.
Bu şekilde gittikçe genelleşen algoritmaları sonuna götürmek istersek şu problemi göz önüne almalıyız.
“Herhangi bir matematik problemin çözülmesine ait algoritma kurmak”
Bu öyle bir genel problemdir ki bütün olarak matematiğe küstah bir meydan okuma sayılmıştır.
Sonsuz soru sınıflarının pek çoğu için algoritmalar geliştirilmiştir. Ancak kimi sonsuz soru sınıfları içinse bir algoritma bulunamamıştır. Örneğin Pierre de Fermat tarafından 1637’de ortaya atılan bir soru o zamanda bu yana matematikçileri uğraştırmıştır. Fermati; n > 2 olduğundan Xn + yn = zn eşitliğini sağlayan nı Xı Y ve Z tamsayılarını bulunmayacağını kanıtladığını öne sürmüş ama nasıl kanıtladığını açıklamamıştır. O günden bu yana bu teoremin ne kanıtına ulaşılabilmiş ne de yanlışlığını gösterecek bir örnek bulunabilmiştir. Böyle bir örnek bulunabilse aranan tamsayılara sonlu sayıda hesapla ulaşılabilir dolayısıyla bir algoritma oluşturulabilirdi.
BÖLÜNEBİLME
Tanım: a, b tamsayılar olmak üzer b = a t olacak şekilde bir t tamsayısı varsa a b’yi böler denir ve a / b yazılır. a X b sembolü de a’nın b’yi bölmediğini gösterir.
Bu tanıma göre a, b’yi bölerse a, b ‘nin bir bölenidir veya b, a’nın bir katıdır denir. Eğer a / b ve 1 < a =" o" a =" +"> o, b > o ise a <> o ve b tamsayılar için b = aq + r, o £ r <> o olduğu kabul edilmiş. Aslında bu hipotez gerekli değildir. Bu durumda teoremi “a ¹ o olmak üzere a, b tamsayıları için b = aq + r; o £ r < b =" aq" a =" 2" b2 =" 4k2" b2 =" 4k2" 1 =" 4k2" kalan =" O" a =" 3" a =" o" b =" c" b =" c" d =" (b,c)," d =" (b," d =" (a," e =" (ma," e =" ImI" d =" ax" md =" ma" e =" ImI" i =" (a," ise =" 1" d =" ax" 1 =" bulunur" d =" bx" b =" 10," c =" 6" d =" (10," x =" 2" y=" -3" 1 =" o" 1 =" o"> r1 >r2 > ....................... azalan dizisi sonsuz olamaz ve iyi sıralama prensibine göre bir en küçük elemanı vardır. Yani rj = O olacak şekilde bir j vardır.
Teorem: (Euclid Algoritması): verilen a, b tamsayıları için bölme algoritmasını aşağıdaki gibi ard arda uygulayalım
a = bqı + rı O < b =" rı" r2 =" r3" 2 =" rj" 1 =" rj" 10672 =" 4147." 4147 =" 2378.1" 2378 =" 1769." 1769 =" 609." 609 =" 551.1" 551 =" 58.9" 58 =" 29.2" 29 =" 10672" 29 =" 551" 9 =" 551" 9 =" 10" 609 =" 10" 609 =" 10" 2378 =" 39" 2378 =" 39" 2378 =" 39" 4147 =" 10672" x =" -" y =" 175"> o, a / m, b /m ve a ve b nin her n ortak katı için m / n olmasıdır.
Teorem :
Teorem : è= 1 dir
Teorem : (a, b) IabI (a ¹ o ve b ¹ o)
Sonuç : IaIss
Sonuç : (a, 1) = IaI