Matematik Atölyesi: Algoritma #2

Algoritma kelimesi 9. yüzyılın ortalarına dek yaşamış olan İran asıllı bilim insanı El Harezmi’nin isminin Latince’deki karşılığıdır. Fakat matematikte algoritmanın (ya da yöntemin) bilinen en eski örneklerinden biri Harezmi’den yaklaşık 1300 önce yazılmış bir eserde bulunur.

Neredeyse her yazıda bahsettiğim Öklid’in Elementleri tarihin en önemli geometri eserlerinden biri olarak bilinir. Fakat Elementler bir geometri eseri olarak adlandırılamayacak kadar geniş kapsamlı 13 kitaptan oluşur. Bu kitapların içinde yedinci kitabın ikinci önermesi ilkokuldan itibaren aşina olduğumuz bir soru tipinden bahseder.

Ortak Bölen

Elementler’in yedinci kitabının ikinci önermesine bugün Öklid’in Algoritması denilir. Algoritma kitapta “Aralarında asal olmayan iki sayı verildiğinde, bunların en büyük ortak ölçüsünü bulmanın yolu.” olarak tanımlanmıştır. Gelin bir örnek üzerinden Öklid’in ne demek istediğine bakalım. (Aralarında asal olmayan iki sayı: Kabaca aynı sayıya bölünemeyen sayılardır.)

Örnek: 10 ve 6 sayılarının en büyük ortak ölçüsünü Öklid’in yöntemiyle bulmak.

Hatırlatmakta yarar var, Öklid sayı yerine uzunluk kullanıyordu. O yüzden algoritması da uzunluklarla işlem yapmayı içerir. En basit haliyle Öklid’in algoritması şu şekilde ilerler: Kalan iki sayı birbirinin eşiti olana dek büyük olandan küçüğü çıkar.

Adım 1 => Büyük sayıdan küçüğü çıkar.

öa1

 

AB uzunluğu 10, CD uzunluğuysa 6 birimdir. Büyük uzunluktan küçüğü çıkarırsak geriye 4 birimlik başka bir uzunluk kalır.

 

 

Adım 2 => Kalan ile CD uzunluklarından hangisi büyükse, ondan küçük olanı çıkar.

öa2

 

CD 6, kalan uzunluk olan EF ise 4 birimdir. Birbirlerinin farkı 2 birimdir.

 

Adım 3 => Yeni kalan ile EF uzunluklarından hangisi büyükse, ondan küçük olanı çıkar.öa3

EF 4, kalan uzunluk olan GH ise 2 birimdir. Birbirlerinin farkı yine 2 birim yapar.

 

Adım 4 => Yeni kalan ile GH uzunluklarından hangisi büyükse, ondan küçük olanı çıkar.

öa4GH ile IJ uzunlukları birbirine eşittir. O halde sonuç 2 birimdir.

 

Yani 10 birimlik bir uzunlukla 6 birimlik bir uzunluğun en büyük ortak ölçüsü 2 birimdir.

EBOB

İlkokuldan beri “en büyük ortak bölen” (kısaca EBOB) kavramı bir çok defa karşınıza çıkmıştır. Belki de yüzlerce adet soru çözdüğünüz bu konunun tarihi aslında milattan önce 400’lere dek uzanır. Okulda iki sayının EBOB’unu bulurken sayıları asal çarpanlarına ayırmak en çok kullanılan yöntemdir. Sayıların sahip olduğu asal çarpanlardan ortak olanlar en büyük ortan böleni verir. Aynı soruyu bir de bu yöntemle çözelim.

10=2.5 ve 6=2.3 olur. Bu yüzden cevap 2‘dir.

Karşılaştırma: 60 ve 40 sayılarının en büyük ortak böleni kaçtır?

  • Öklid’in Algoritması:
    60-40=20
    40-20=20
    20-20=0
    Cevap 20.
  • Çarpanlara Ayırmak:
    60=2.2.3.5
    40=2.2.2.5
    Ortak olanlar => 2.2.5=20.

Taş Ustasının Problemi

En büyük ortak bölen bulmak için bir yöntem daha var: Yer döşemek.

Antik zamanlarda Ege’de yaşayan bir döşeme ustası yapılacak yeni tapınağın inşaatında çalışmak üzere tutulur. Ustadan tapınağın girişinde 40 metreye 60 metrelik bir dikdörtgen alanı kare şeklinde taşlarla döşemesi istenir. Bu işi yaparken ustanın en az kaç adet taşa ihtiyacı vardır? (Aslında bu soru ile “40 ile 60 sayılarının en büyük ortak böleni kaçtır?” sorusu aynıdır.)

kare1

Usta, Öklid’den haberdardır. Onun algoritmasını temel mantık olarak düşünerek yeni bir yöntem yaratır. Taş ustası dikdörtgen şeklindeki alan tamamen dolana dek içine dikdörtgenin kısa kenarının uzunluğuna sahip kareler çizer. En son çizilen karelerin bir kenarı cevabı verir.

 

Adım 1 => Dikdörtgenin içini kısa kenarın boyutlarına sahip karelerle doldur.

kare2

 

 

Kısa kenar 40 metre uzunluğundadır. Bu yüzden dikdörtgenin içine kenarları 40 metre olan karelerden sadece bir tane sığar.

 

 

Adım 2 => Şimdi elinizde 40’a 20’lik bir dikdörtgen vardır. Aynı şeye devam edilir; kısa kenarın boyutlarına sahip kareler çizilir.

kare3

 

 

Kısa kenar 20 metre olduğu için, çizilen kareler 20’ye 20’liktir. Büyük dikdörtgen tamamen dolunca cevabı en son karenin boyutları verir: 20.

 

India_Goa_Cathedral_Floor
Kötü usta…

M. Serkan Kalaycıoğlu

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s