Algoritma

Matematik Atölyesi – Algoritma #7

Sınavdan Çakma Algoritması (S.Ç.A.)

1990’ların sonu…

Eve sonunda bilgisayar alındı. Ali’nin abileriyle girdiği “bilgisayarı kullanma sırası kimde?” savaşından galip çıkmasının en önemli nedeni ders notlarının yüksekliği. Bu sayede Carmageddon’da zombi ezen, Fifa 98’de şampiyonlar ligini gol yemeden kazanan Ali’nin Duke Nukem’de neler yaptığını ise size ancak bir latte karşılığında anlatabilirim.

Ali’nin bir seneden uzun süren bilgisayar oyunu çılgınlığı menajerlik oyunlarıyla önünü alamadığı bir noktaya çıktı. Üstüne üstlük, hala haftada birkaç gün arkadaşlarıyla futbol&basketbol oynamaya da devam eden Ali, bir felakete doğru hızla ilerliyordu. Tanrım, nasıl da fark edememişti?! Sınavlarından çakmak üzereydi!

İlk uyarı matematik sınavıydı. Ali’nin sınava çalışması için önünde sadece son bir gün kalmıştı. Fakat Ali’de artık bazı alışkanlıklar baş göstermişti. Ders çalışmak yerine yapabileceği bir sürü seçeneği vardı:

1. Evde Kalmak

Ali evde kalmayı tercih ettiğinde hemen bilgisayarının başına oturuyordu. Bilgisayarı açmasının nedeni tabi ki dersleriyle alakalı değildi. Masaüstünde bulunan üç oyundan birini oynuyordu:

a. Fifa

b. Carmageddon

c. CM (Menajerlik oyunu)

2. Dışarı Çıkmak

Ali dışarı çıktığında da arkadaşlarıyla buluşup kütüphaneye gitmiyordu:

a. Top peşinde koş

b. Aylaklık yap

S.Ç.A. Grafı

Önceki yazılarda bahsettiğim graf konusu, Ali’nin durumunu açıklarken büyük bir kolaylık sağlar. Ali’nin ders çalışmamayı seçtiği durumlarda yapacağı tercihler sınavdan düşük not almasına yol açar:

Grafın Bize Anlattıkları

Yukarıdaki grafta çizgiler Ali’nin yaptığı seçimleri, noktalar ise Ali’nin hangi durumda olduğunu gösterir. Graf bize kesin olarak iki şeyi söyler: Ali, ders çalışmamayı seçer ve sonuçta sınavdan çakar.

Bu yüzden Ali’nin seçimlerini gösteren çizgilerin bir yönü vardır.

Seçimler yapılırken bazı adımlar atlanamaz. Örneğin, Fifa oynamak için önce bilgisayarın başına oturmak, onun için de evde kalmayı seçmek gerekir.

Ali’nin seçimlerinin aşağıdaki gibi olduğunu varsayalım:

Evde kal -> Bilgisayarı Aç -> Fifa oyna.

Bu durumda kısıtlı zamanı olan Ali’nin, zamanını Fifa oynamaya ayırdıktan sonra başa dönüp sınava çalışmasına olanak yoktur. Artık Ali için sınavdan kötü not almak kaçınılmaz bir son olacaktır.

Grafın bize anlattığı bir başka şey ise, Ali’nin yaptığı herhangi bir seçime geri dönememesidir. Matematikçiler bu tür grafları “yönlü çevrimsiz/asiklik/zincirleme graf” olarak adlandırmıştır.

***

Biraz Bilgi

Yönlü Çevrimsiz Graf

Bir yönlü çevrimsiz grafta döngü yoktur. Yani bir noktadan başlayıp yönlü çizgileri takip ettiğinizde, aynı noktaya bir daha dönemezsiniz.

Yönlü (ve sonlu) çevrimsiz graflarda en az bir “kaynak” ve yine en az bir “alış noktası” olarak adlandırılan noktalar bulunur.

Kaynak noktası, başka herhangi bir noktadan kendisine doğru çizgi gelmeyen noktadır. Yukarıdaki grafta “ders çalışma” isimli nokta, kaynak noktasıdır.

Alış noktası ise kendisinden başka herhangi bir noktaya doğru çizgi gitmeyen noktadır. Grafımızda “sınavdan çak” isimli nokta, alış noktasıdır.

***

Bi’ Göz Atmakta Fayda Var

Rutin işlerinizi yaparken aslında yönlü çevrimsiz grafları kullanıyorsunuz. Buna bir örnek göstermek için yine Ali’nin hayatından yararlanacağım.

Ali, her okul günü sabahında uyanır uyanmaz duş alıp okula hazırlanır. Bunu yaparken Ali’nin izlediği yol şunlardan oluşur:

Uyan

Duşa gir

Duş sonrası diş fırçala

Giyin

(Ali’nin okul kıyafeti pantolon, gömlek, kravat ve yelekten oluşuyor.)

Soru: Ali’nin okula hazırlanışını gösteren grafı çizin.

Not: Ali duştan sonra giyinirken her adımı doğru yönde tamamlamalıdır. Örneğin boxer’ını giymeden önce pantolonunu giyemez, değil mi?!

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Algoritma #6

2600ler…

Sonunda Dünya dışında yaşayabileceğimiz bir gezegen keşfedildi. Bilim insanlarının T-489 ismini verdiği bu gezegende yaşam koşulları Dünya’ya benzer görünüyor. Uydu görüntüleri T-489’da su bulunduğunu gösterirken gezegenin atmosferinin de Dünya’nınki ile tıpatıp aynı olduğu keşfedildi.

Büyük devletlerin uzay ajansları ortak bir ekip gönderip T-489’da yaşam olup olmadığını kontrol etmekte anlaştı. Hazırlanan plana göre uydu görüntülerinden elde edilen veriler ışığında T-489’da belirlenen bir noktaya inecek ilk ekip, burada güvenli alan ve merkez üs oluşturacak.

Güvenli alan oluşturulduktan sonra ise yine uydu sayesinde belirlenmiş olan noktalara üç ayrı ekip gönderilecek. Bu ekipler hem bulundukları bölgelerde yaşam koşullarını inceleyecek, hem de farklı yaşam formları olup olmadığını kontrol edecek.

T-489’da bulunan merkez üs, keşfe çıkacak ekipler için bir harita yapacak. Merkez üssün hazırladığı harita hem gezegen üzerinde yolculuğun nasıl yapılabileceğini, hem de ekiplerden herhangi birinin sorun yaşaması durumunda üsse nasıl geri dönmesi gerektiğini açıklamak zorunda.

Haritanın görünümü: Sarı nokta merkez üs, diğer noktalar ise keşif ekiplerinin ziyaret edeceği konumlar.

Herhangi bir anda bir ekibin nerede olduğunun bilinemeyeceği durumlar için merkez üste çalışanlar çizdikleri haritaya bir de algoritma eklemeli. Bu, öyle bir algoritma olmalı ki, algoritmayı takip eden ekip(ler) sonunda merkez üsse varır.

Yol Boyama Problemi

1970’de Roy Adler’in ortaya attığı bir problem olan yol boyama problemi (road coloring problem), 2007’de yılında İsrailli matematikçi Trahtman tarafından çözülmüştü.

Trahtman, yukarıdaki gibi bir graf (veya harita) düşünmüştü; noktalar arasında bulunan yolların belirli yön ve renkleri vardı. Bu yön ve renkleri bulduğu algoritmaya göre oluşturan Trahtman’a göre grafın herhangi bir noktasından başlayıp üç kere mavi-kırmızı-kırmızı yolları izleyen biri her zaman sarı noktada duracaktır.

T-489’da Kaos

Gezegende keşfe çıkacak ekipler için harita yapmanız gerekiyor. Merkez üs ve gezilmesi gereken noktalar aşağıdaki gibi:

Keşif ekiplerinin yaşayabileceği en kötü duruma hazırlanmanız gerekiyor. Eğer ekiplerden birinin iletişimi kopar ve haritaya ulaşma şansı kalmazsa, yaratacağınız algoritma hayatlarını kurtaracaktır.

Geliştirdiğiniz fikir şöyle ilerliyor: Gidilmesi gereken her konumun girişine bir tabela konulacak. Bu tabelalarda sadece yolun yönü ve rengi yazacak. (Tabelalara haritaların asılmamasının nedeni, zeki bir uzaylı türüyle karşılaşılması durumunda merkez üssün yerinin direk uzaylılara gösterilmemesidir.)

Yarattığınız algoritmaya göre iki defa kırmızı-mavi yapmak ekipleri merkez üsse ulaştırır:

Bi’ Göz Atmakta Fayda Var

Keşif yapılacak bir nokta daha olsun. Haritanız için öyle bir algoritma yaratın ki, izlenen algoritma sizi hep M noktasına (yani merkez üsse) geri döndürsün.

(Bunu yaparken en az sayıda yol kullanmaya özen gösterin.)

Matematik Atölyesi – Algoritma #5

Doğru Pizza Dilimi

Üç arkadaş üç farklı pizza dilimini paylaşacaktır.

Pizzalar:

Pizza 1: Dört peynirli.

Pizza 2: Tavuklu.

Pizza 3: Ananaslı.

Üç arkadaş bu üç pizzayı altı şekilde paylaşabilir:

Ne Kadar Çok İstiyorsun?

Birer dilim pizza yemek çok basit bir işmiş gibi görünse de olayın arka planında tahmin edilemeyecek kadar çok detay vardır. Öncelikle bu üç dilimin maliyeti işin içindedir. Bir de tercih meselesi vardır; malum herkesin damak tadı aynı değil.

Diyelim ki bu üç dilim toplam 6 lira tuttu. Ali, Steve ve Jane için pizza tercihleri de aşağıdaki gibi olsun:

Ali için ilk tercih dört peynirli. Eğer onu alamazsa tavuklu; son tercihi ise ananaslı.
Steve için ilk tercih tavuklu, ikincisi ananaslı ve son olarak dört peynirli.
Jane’in tercihleri sırasıyla tavuklu, dört peynirli ve ananaslı şeklindedir.

Bu durumda kimin hangi dilimi kaç liraya alacağına (adil bir şekilde) nasıl karar verilebilir?

Ev Arkadaşı Problemi (Kira Harmonisi Problemi)

İki (veya daha fazla) arkadaş kiraladıkları evde odaları ve kirayı adil olarak nasıl bölüşür sorusu uzun yıllar matematikçileri meşgul etmiştir. Ev arkadaşı problemi olarak bilinen bu soru adil paylaşmanın en bilindik problemlerinden biridir.

Ev arkadaşı probleminin adil ve kıskanç olmayan çözümlerinden biri 2004’te yayımlanan Atila Abdulkadiroğlu, Tayfun Sönmez ve Utku Ünver’in ortak çalışmasında yer alır. Bu üçlünün açık artırma algoritması adil paylaşımın en ünlü çözümlerinden biridir. (Hatta ev arkadaşı problemini çözmek için kurulmuş olan Spliddit isimli web sitesinde uzun yıllar 2004’teki algoritma kullanılmıştı.)

Algoritmanın İşleyişi

Kirayı bölüşecek kişiler kapalı her oda için kapalı zarfta teklif verir. Odalara yapılan teklifler toplam kirayı vermelidir. (Örneğin 3000 liralık bir evdeki iki odaya yapılacak tekliflerin toplamı tam olarak 3000 lira etmelidir.)
Zarflar herkesin gözü önünde açılır. Bir odanın kazananı o odaya en yüksek teklifi yapandır.
Bir oda için teklifi kazanan kişinin diğer teklifleri geçersizdir.
Kazanan tüm teklifler toplanınca tam olarak kiraya denk geliyorsa, herkesin vereceği miktar belirlenmiş demektir.
Eğer tekliflerin toplamı kiradan az veya fazla ise, basit orantı işlemleriyle herkes için verilmesi gereken kira belirlenir.

Pizza Dilimi Cevabı

Üç arkadaşın pizza dilimi seçimi açık artırma algoritmasıyla çözülebilir. Üçlünün kapalı zarf teklifleri aşağıdaki gibi olsun:

Tek tek pizzalara bakıldığında ilk pizzayı Ali 4 liraya, ikinciyi Steve 4 liraya, üçüncüyü ise Jane 2 liraya kazanmış olur:

Tekliflerin toplamı

4 + 4 + 2 = 10

liradır. Teklif toplamları pizza dilimlerine verilecek 6 liradan fazla olduğu için tekliflerin oranları hesaplanır:

Bu durumda Ali ve Steve 4 lira vermeye hazır oldukları pizza dilimlerine 2,4’er liraya, Jane ise 2 lira vermeye hazır olduğu pizza dilimine 1,2 liraya kavuşur. Algoritma sonucunda hem herkes istediği pizza dilimini düşündüklerinden daha ucuza almış olur.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Algoritma #4

Adil Pasta Kesimi

Adil bir şekilde pasta kesmenin bir yolu var mı?

Bunu resmen bir matematik problemi olarak gören ilk kişi Hugo Steinhaus isminde bir matematikçiydi. Steinhaus 1944 yılında bir pastayı iki kişinin nasıl paylaşabileceği üzerine kafa yormuştu.

Ona göre birbirlerinin seçimlerini kıskanmadan iki kişinin pastayı paylaşmasının yolu “biri keser, diğeri seçer” yöntemiydi:

İlk kişi pastayı ikiye böler, ikinciyse iki parçadan istediğini alır. Bu yöntemde ikinci kişi istediği parçayı alabildiği için tercihinden memnundur. İlk kişiyse pastayı eşit olarak iki parçaya ayırdığını düşündüğü için iki parçadan kendisine hangisi kalırsa kalsın memnun olacaktır. Steinhaus’un bu yöntemi bilinen ilk kıskanç olmayan yöntemdi.

Peki üç kişi bir pastayı birbirlerinin seçimlerini kıskanmadan nasıl paylaşabilir?

İnanılmaz ama bu soru ancak 1962’de cevaplanmıştı. Soruyu birbirinden bağımsız olarak çözen J. H. Conway ve J. Selfridge’e göre yöntem şu şekilde ilerler:

Ali, Steve ve Jane

Ali pastayı üç (kendince) eşit parçaya böler.
Steve bu parçaları kontrol eder. Eğer Steve kontrol sonrası bir şey yapmazsa sıra Jane’e geçer.
İlk seçimi Jane, ikinci seçimi Steve, son seçimiyse Ali yapar.

Gelin yöntemi ayrıntılarıyla açıklayalım:

Adım #1: Ali ne yapmalı?

Ali göz kararı bir şekilde pastayı üç eşit (ya da en azından denk) parçaya böler:

Adım #2: Steve ne yapmalı?

Steve bu parçaları kontrol eder. Burada ihtimaller Ali’nin kesiminin değerlendirilmesiyle şekillenir:

Eğer Steve parçalardan en az ikisinin en iyi (yani en büyük) parçalar olduğuna kanaat getirirse bir şey yapmaz ve sıra Jane’e geçer. Steve’e göre böyle bir durumda iki ihtimal vardır:
a. Parçaların hepsi birbirine eşitse Jane hangisi seçerse seçsin kalan parçaların hepsi Steve’i memnun eder:

Üç parça da eşitse ikinci seçimi yapacak olan Steve mutlu olacaktır.

b. Eğer iki parça birbirine eşit ve üçüncü parçadan büyükse, Jane büyük parçalardan birini alsa dahi diğer büyük parça Steve’e kalır ki bu da onu memnun eder.
Parçalardan biri diğer ikisinden büyükse Steve bir şey yapmak zorundadır. Aksi takdirde Jane tek büyük parçayı alır:

Steve ortadaki parçanın diğer ikisinden daha büyük olduğunu fark eder. Eğer bir şey yapmazsa bu parça Jane’e gidecektir.

Bu durumda Steve büyük parçayı traşlayarak düzenler ve fazla parçayı bir kenara ayırır. Böylece Steve Jane’e seçmesi için en kötü ihtimalle birbirine eşit iki büyük parça bırakmış olur:

Steve ortadaki parçayı traşlar ve fazlalığı başka yere koyar. Örnekte orta ve sağ en iyi parçalardır. Jane bu ikisinden birini aldığı takdirde diğeri Steve’e kalacaktır.

Adım #3: Jane ne yapmalı?

Steve memnun olduğuna kanaat getirdikten sonra sıra Jane’e gelir:

Eğer Steve hiçbir şey yapmamışsa üç parça birbirine eşit demektir. Bu durumda ilk Jane seçimini yapar, sonra da Steve. Son parça ise Ali’nindir. Böylece kıskanç olmayan kek kesimi gerçekleşmiş olur.
Eğer Steve’e göre Ali’nin kestiği üç parçadan biri diğer ikisinden büyükse Steve bu büyük parçayı yukarıdaki adımda anlatıldığı gibi düzeltir ve sıra Jane’e öyle gelir. Böyle bir durumda Jane istediği parçayı seçer. Fakat Jane’in seçtiği parça yöntemin geri kalanını etkiler:
a. Eğer düzenlenmiş kek parçasını Jane seçerse kalan iki parçayı sırasıyla Steve ve Ali alır. Bu durumda ayrılmış olan dördüncü parçayı Steve eşit üç parçaya böler. Bu üç parçayı sırasıyla Jane, Ali ve Steve seçer ve adil paylaştırma sona erer:

b. Eğer Jane düzenlenmiş kek parçasını almazsa bu parçayı Steve almak zorundadır. Bu durumda ayrılmış olan dördüncü parçayı Jane eşit üç parçaya böler. Bu üç parça sırasıyla Steve, Ali ve Jane tarafından seçilir ve adil paylaştırma sona erer.

Bi’ Göz Atmakta Fayda Var

Buraya kadar olan senaryo kıskançlıktan uzak mıdır?

(Okumadan önce cevap üzerine bir süre kendiniz düşünün.)

Cevaplar

Ali İçin: Evet. Çünkü orijinal keki üç eşit parçaya ayırdığını düşündüğü için hangi parça gelirse gelsin memnun olacaktır. Artan kısım olursa Ali için zaten eşit olduğunu düşündüğü parçaya biraz daha fazla pay gelmiş olacaktır.

Steve İçin: Evet. Çünkü kek parçalarından en az ikisinin en iyi (yani en büyük) olmasını garantilemeden Jane’e sırayı vermez. Eğer parçalardan birinde düzeltme yaptıysa ve bu parçayı Jane aldıysa, artan parçayı üç eşit parçaya bölen Steve olur ki bu da Steve’in herhangi bir artan parça ile memnun olacağı anlamına gelir.

Jane İçin: Evet. Çünkü orijinal parçalardan ilk seçimi yapan o olur: Bu sayede kendinden en iyi parçayı seçebilir. Ayrıca Steve’in üçe böldüğü artan kısımda da ilk seçimi yapacağı için paylaşımdan memnun olacaktır.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Algoritma #3

Kağıt Oyunları

Küçüklüğümde matematik notlarım bana büyük bir sorumluluk vermişti. Haftada ortalama bir gün aile ziyaretlerinde babalar hoşkin isimli kağıt oyununu oynardı. Maalesef matematiğimin iyi olduğu yönündeki iddialar yüzünden dünyanın en garip puanlama sistemine sahip olan bu kağıt oyununda puanları tutma görevi bana düşerdi: “300 yaz, 4200 bize, 640 yaz, 20 yazdın mı bize?”

Üniversitede kampüs hayatı yaşayanlar çok iyi bilir: Yurt hem büyük sefalet hem de inanılmaz eğlence demekti. Şahsen yurtta en çok eğlendiğim zamanlar dört kişi masaya kurulup saatlerce batak ve/veya king oynadığım zamanlardı. Küçüklüğümde zerre hazzetmediğimi kağıt oyunlarına dört yıl sonunda bağımlı olmuştum.

Dolaylı olsa da kağıt oyunlarında rekabet etmek dışında beni en çok çeken şey kullanılan algoritmalardır. Her oyuncunun kafasında oluşturduğu bir algoritması vardır ve birbirini tanıyan oyuncular algoritmalarında ufak değişiklikler yaparak oyunda avantaj sağlamaya çalışır.

Pico

Algoritma kurup onu uygulamak için yaratılan bir Alman oyunu olan Pico, matematikle kağıt oyunları arasındaki ilişkiyi gösteren en güzel örnektir. Pico’nun özelliği çok basit kurallara sahip olmasına rağmen oyunun arkasında harikulade matematik bilgileri barındırmasından gelir.

İki oyunculu olan Pico’da üzerinde 2, 3, 4, 5, 6, 7, 8, 9, 10, 13 ve 16 sayıları yazan on bir tane kağıt vardır.
Oyunculardan biri kağıtları karıştırır ve her oyuncuya beşer tane kağıt verilir.
Kalan tek kağıt açık şekilde ortaya konur. Böylece oyuncular birbirlerinde hangi kağıtların olduğunu bilir.
Oyunda her el oyuncuların ortaya attığı birer kağıtla devam eder.
Elin kazananı büyük kağıda sahip olandır.
Fakat büyük kağıttaki sayı küçük kağıttakinin iki katından fazlaysa, kazanan küçük kağıt olur.
Eli kazanan kağıt kazanan oyuncunun önüne açık şekilde konur. Kağıtta yazan sayı kazanılan puandır.
Kaybeden kağıt sahibine geri döner.
Oyun herhangi bir oyuncunun elinde tek kağıt kalana dek devam eder.
13 yerine K, 16 yerineyse Joker(J) kullanarak evde bulduğunuz herhangi bir desteyle Pico’yu oynayabilirsiniz.

Seko

Pico’dan feyiz alıp Seko adını verdiğim bir oyun yazdım:

Oyuncular 2-50 arasındaki sayılardan sırayla altışar tane seçer. Seçime ilk başlayanı belirlemek için havaya para atılır.
Bu sayılar boş bir kağıdın üzerinde sıralanır.
Oyuncular teker teker sayıları seçer. Yine seçime ilk başlayanı belirlemek için para kullanılır.
Her oyuncu altışar sayıya sahipken oyun başlar. Her elde oyuncular birer sayı seçer.
Sayılar arasındaki fark tek ise büyük sayıyı seçen, çift ise eğer fark 20’den az ise küçük sayıyı seçen eli kazanır.
Eli kazanan sayı puan olarak kazananın hanesine yazılır, kaybeden sayı sahibine geri döner.
Oyun oyunculardan birinde tek bir sayı kalana dek devam eder.
Oyunun bitiminde en çok sayıya sahip olan oyunu kazanır.

Bi’ Göz Atmakta Fayda Var

Seko’da farklarını almak yerine sayıları toplayın. Eğer toplam tek ise büyük sayı, çift ise toplam 50’dan küçük olduğu takdirde küçük sayı kazansın.

Seko oyunlarında her zaman uygulayabileceğiniz bir algoritma bulabilir misiniz?

M. Serkan Kalaycıoğlu

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.

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.

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.

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.

GH 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.)

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.

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.

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.

M. Serkan Kalaycıoğlu

Matematik Atölyesi: Algoritma #1

Materyal: Kağıt ve kalem.

Matematik dersinde bir öğrenci seçilir.

Öğrenci robottur. Sadece komutlar doğrultusunda hareket eder.

Amaç öğrencinin bir sıra üzerinde bulunan kutuyu sınıfın dışına taşımasını sağlamak.

Öğrencilerin komutları kesin ve kısa olmalı.

Kesinlik: Robotun gözünde ölçü birimlerini gösteren bir alet olmadığı için “1 metre ilerle” demenin bir anlamı yoktur. Onun yerine “sağ, dur, ilerle, dur” veya “3 fayans kadar ileri” şeklinde komutlar verilmeli. Ayrıca “kutuyu al” diye bir komut da yetersizdir. “Eğil, sol kol ileri, aşağı, geri” şeklinde komutlar kullanılması mecburdur.
Kısalık: Komutlar mümkün oldukça cümle şeklinde verilmemeli. Robotun sağa dönmesi isteniyorsa “sağ” komutu, yeterince döndüğü düşünüldüğünde de “dur” komutu verilmesi gibi.

Öğrencilerin kağıda yazdığı komutlar bir algoritma örneğidir.

Algoritma Nedir?

Son zamanlarda neredeyse tamamen bilişim teknolojisinde kullanılan algoritma kelimesinin Türkçe’de karşılığı yöntemdir. Yani hayatın hangi alanında yöntem içeren bir iş varsa, orada algoritma vardır. Evden işe giderken kullandığımız yoldan, oyun kağıdı karıştırma şeklimize, hatta PlayStation’da Fifa oynarken kullandığımız tuşlara dek hep bir algoritma kullanıyoruz.

Peki algoritma kelimesinin kökeni nedir?

Yöntem Bey

8. ile 13. yüzyıl arasında kalan zaman dilimi İslam’ın Altın Çağı olarak adlandırılır. Müslümanlar 500 yıl boyunca hayatın her alanında yaşanan gelişmeleri kontrol etmişti. Doğal olarak bilimde de sürükleyici güç Müslümanlardı.

Altın Çağın başlangıcı başkenti Bağdat olan Abbasi Devleti’ne dayanıyordu. 8. yüzyılın sonuna doğru Müslümanlar (özellikle Araplar) bilim ve sanat konusunda diğer milletlerden geride kalmıştı. Bu durumu değiştirmek isteyen Halife Harun Reşid ve oğlu Halife Memun işe bilimle ilgili yazılmış ne kadar önemli eser varsa hepsinin Arapça’ya çevrilmesini sağlayarak başlamıştı. Bu döneme dek en önemli bilimsel çalışmaları Yunanlar yazmıştı. Bu yüzden Abbasi Halifeleri öncelikle bulunabilen tüm Yunan eserlerin çevrilmesini emretmişti. Bu uğurda Beyt’ül Hikmet isimli bir kütüphane kuran El Memun, elinin altındaki tüm tercümanları etraf ülkelere göndermişti(Beyt’ül Hikmet daha sonra kütüphaneden çok bir bilim merkezi gibi işlev görmüştü).

Memun’un bu çabası sayesinde Sokrates, Aristoteles, Öklid, Diyofantus ve daha nice Yunan bilim insanının eserleri günümüze dek ulaşmıştır. Çünkü günümüzde eski Yunan eserlerinin en eski versiyonları sadece Arapça olarak bulunmaktadır. Antik Yunan eserlerin Arapça’ya tercüme edilmesi, Müslümanların Yunanların etkisinde kalmasına yol açmıştı. Öyle ki, Aristotelesçi düşünce Müslümanları derinden etkilemiş, hatta bir çok İslam düşünürü için kutsal sayılan bir felsefe olarak görülmüştü.

Müslüman matematikçiler de antik Yunan çalışmalarından büyük ölçüde etkilenmişti. Bunlardan biri İran kökenli El Harezmi idi. Harezmi sadece Yunan matematiğiyle yetinmemiş, Hint matematiğini de öğrenmişti. İlk olarak Hindistan’da ortaya çıkan on tabanlı basamak sistemini Hindistan’ın dışına taşıyan kişinin El Harezmi olduğu bilinir. Harezmi dünyaya sayı sistemi dışında çok önemli bir armağan daha vermişti. Yazdığı “Cebir ve Denklem Hesabı Üzerine Özet Kitap” bugün matematiğin en eski ve en geniş alanlarından birine ismini vermişti: Cebir.

contribution_of_al-khwarizmi_02 — Özbekistan’da bulunan El Harezmi heykeli. (Foto: Alain Juhel)

El Harezmi’nin eserleri 12. yüzyılda Latince’ye çevrilirken, ismi “Algoritma” olarak tercüme edilmişti. Yani algoritma kelimesi bir Müslüman matematikçinin ismidir. Bu, El Harezmi’nin yazdığı Cebir kitabının içeriğinden kaynaklıdır. Harezmi’den önce matematikte yöntem yok denecek kadar azdı çünkü problemler çoğu zaman sadece özel durumlar için çözülürdü. Cebir’de ise matematik problemlerinin genel çözümlerinin nasıl (yani hangi yöntemle) yapılacağı gösterilmişti ki bu başlı başına bir devrim niteliğindeydi.

Harezmi’nin Algoritması

El Harezmi matematik problemlerinin çözümünü sembol kullanmadan sadece kelimelerle yapmıştı. Ayrıca çözümlerinde geometriden de yardım almıştı. Bunun bir nedeni, onun yaşadığı dönemde bilinmeyene bugün atadığımız gibi bir harfin atanmıyor olmasıydı. Bir problemde bilinmeyene x demeye başlamamız Harezmi’den yüzlerce yıl sonraydı.

Harezmi ikinci dereceden bir bilinmeyenli denklemlerin genel çözümü için algoritmalar kurmuştu. Bu tür denklemleri günümüzde a,b ve c sayı, x değişken olmak üzere;

ax² + bx + c = 0

şeklinde gösteriyoruz. Harezmi ikinci dereceden bir bilinmeyenli denklemlerin genel çözümü için şöyle bir yöntem geliştirmişti:

xkare — Bir kenar uzunluğu x olan karenin alanı = x²

kareartıx — Bir kenar uzunluğu x olan kare ile kenar uzunlukları x ve 2 olan dikdörtgenin alanları toplamı=x²+2x

Sonuç

Bugün algoritma bir bilgisayar programının arka planında bulunan kod anlamında düşünülüyor. Algoritmalar yazılımın her yerindedir ve bilgisayarlara bir problemi nasıl çözmesi gerektiğini gösterir. Bilgisayar teknolojisinin günlük hayatımızın içine iyice girmesi yüzünden algoritmanın matematiksel anlamı unutulmuş ya da geri plana atılmıştır. Fakat algoritma kelimesi ilk olarak 800 yıl önce El Harezmi’nin Cebir’iyle tanışan Avrupalılar tarafından matematiksel yöntem anlamında kullanılmıştı. Bu yüzden çocuklara yazılım dersleri verirken matematiği bir kenara atmamak, her iki şeyin de aslında birbiriyle iç içe olduğunu göstermek gerekir.

Ek Soru: Harezmi’nin geometrik yöntemini kullanarak

2x² + 10x = 30x – 2x²

denklemini çözünüz.

M. Serkan Kalaycıoğlu

Steve ortadaki parçayı traşlar ve fazlalığı başka yere koyar. Örnekte orta ve sağ en iyi parçalardır. Jane bu ikisinden birini aldığı takdirde diğeri Steve’e kalacaktır.