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.

T-489’un bulunduğu sistem.

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 – Oyun #12

Üçgen İstilası

İki kişilik bir oyun olan üçgen istilasını oynamak için öncelikle bir üçgen çizin ve bu üçgenin köşelerine farklı isimler verin (1-2-3 gibi):

20190530_145646.jpg

Daha sonra büyük üçgenin içine aşağıdaki gibi küçük üçgenler çizin:

20190531_125538.jpg

(Küçük üçgen sayısı istenildiği kadar artırılabilir.)

Üçgende köşeleri aşağıdaki kurallara uyarak adlandırın:

a. 1-2 kenarında bulunan köşeler 1 veya 2 olabilir.

b. 1-3 kenarında bulunan köşeler 1 veya 3 olabilir.

c. 2-3 kenarında bulunan köşeler 2 veya 3 olabilir.

d. Büyük üçgenin içerisinde kalan köşeler 1, 2 veya 3’ten herhangi biri olabilir.

Oyunun İşleyişi

  • Yukarı kuralları izleyerek sırayla köşeler adlandırılır.
  • Oyuncular son köşesini adlandırdıkları üçgenleri istila etmiş sayılır.
  • Amaç 1-2-3 üçgeni yapmamaktır. En az 1-2-3 üçgeni istila etmiş olan kişi oyunu kazanır.

Sperner’in Üçgeni

Üçgen istilası oyunu aslen Sperner üçgeninden gelir. Emanuel Sperner’in bulduğu Sperner üçgeni, çok basit kuralları olmasına rağmen şaşırtıcı bir sonucu içerisinde barındırır. Sperner üçgeni aynı üçgen istilasında olduğu gibi büyük bir üçgenin içine küçüklerinin çizilmesi ve bunların köşelerinin adlandırılmasıyla elde edilir.

Kurallara göre köşeler etiketlendiğinde muhakkak köşeleri 1-2-3 olan bir üçgen bulunur:

20190531_125917.jpg
Örnekte üç tane 1-2-3 üçgeni vardır.

Hatta Sperner bu kurallar çerçevesinde her zaman tek sayıda 1-2-3 üçgenleri olacağını söyler.

Bu yüzden de üçgen istilası hiçbir zaman beraber bitmez.

Çıkmaz Sokak

Sperner üçgeninde 1 ve 2 arasında kalan kenarlar kapı, kalan tüm kenarlar ise duvar olsun. Bir 1-2 kapısından başlanan yürüyüşte karşılaşılan tüm kapılar kullanılmak zorundadır:

Bu durumda üçgenin dışından başlayan bir yürüyüş iki şekilde bitebilir:

  1. Büyük üçgenin içinde bulunan bir 1-2-3 üçgeninde:

    Sol kenarda üç tane 1-2 kapısından başlanan yürüyüşlerin hepsi 1-2-3 üçgenlerinde bitmiştir.

  2. Büyük üçgenin dışında:

    Sol üstteki kapıdan başlayan yürüyüş üçgenin dışında bitmiştir.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Algoritma #5

Doğru Pizza Dilimi

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

Pizzalar:

68591

Pizza 1: Dört peynirli.

20665-white-chicken-pizza-600X600

Pizza 2: Tavuklu.

pineapple pizza

Pizza 3: Ananaslı.

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

20190514_170727.jpg
P1:Pizza 1, P2:Pizza 2, P3:Pizza 3.

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:

  1. Ali için ilk tercih dört peynirli. Eğer onu alamazsa tavuklu; son tercihi ise ananaslı.
  2. Steve için ilk tercih tavuklu, ikincisi ananaslı ve son olarak dört peynirli.
  3. 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:

20190514_170542.jpg

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:

20190514_170507.jpg

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 – Hayat-Matematik İlişkisi #7

H&G Oyunu

Bu ismi çoğunuzun küçükken öğrendiği Hansel ve Gretel’in hikayesinden esinlenerek koydum. (Eğer hikayeyi bilmiyorsanız lütfen okuyun.)

H&G’de amaç iki yer arasındaki en kısa yolu bulmaktır. Fakat oyun oturulan yerden değil, bizzat deneyimlenerek ilerler. Sonuca yaşanılan deneyimlerden çıkarım yaparak ulaşılır.

Şimdiden belirtmem gerekiyor: Bu oyunu böceklerden, özellikle karıncalardan öğrendik. Yazının devamında buna değineceğim.

Peki H&G nasıl oynanır?

  • Oyuncular belirtilen iki yer arasında yürüyüş yapar.
  • Her oyuncunun başlangıç ve bitiş yerleri aynıdır.
  • Yürüyüş için birden fazla yol vardır.
  • Amaç bu iki yoldan hangisinin daha kısa olduğunu bulmaktır.
  • Oyun sırasında kalem dışında hiçbir aletin kullanımına izin verilmez. (Saat, telefon vs. dahil.)
  • Oyuncular başlangıç ve bitişe vardığı her sefer için kalemle bir çizgi çizer.
  • Oyuncuların hızlarının aynı (ya da en azından benzer) olması için koşmaları yasaktır.

Oyun #1

H&G için hazırlanan iki yol aşağıdaki gibi olsun:

20190425_134042.jpg

Bu iki yol üzerindeki ilk yürüyüş başlarken hem A hem de B’de oyuncular bir süre aynı yolu gider, fakat yürüyüş devam ettikçe A’dekiler B yolundaki oyunculardan çok daha önce bitişe varır:

20190425_134109.jpg

B’de yürüyen oyuncular bitişe ulaştığında diğer yoldakilerin ilk çizgiyi koyduğunu görür. Bu da A yolunun B’den daha kısa olduğunu belirtir. Oyuncuların bir kısmı B’ye hala inanıp geri dönüşü yaptığında, bitişe ulaştıklarında A’dakilerin ikinci çizgiyi çektiğini görür.

Böylece B’nin daha uzun olduğunu (gerçekten inatçı olanlar hariç) herkes görmüş olur. Oyun devam ettiği sürece A’dakiler B’dekilere fark atacağı anlaşılmıştır.

Oyun #2

İlk oyunda herkes A yoluna geçmişken A üzerine aşağıdaki gibi bir engel koyalım:

20190425_134136.jpg

Oyunculardan en az biri B’yi denemeye karar verir. Bir kaç tur sonra çizgi sayılarında B’nin A’ya yaklaştığını fark eden oyuncular B yoluna geçmeye başlar:

20190425_134159.jpg
Yavaş da olsa B’deki oyuncular A ile farkı kapatır.

Zamanla oyuncuların hepsi B’nin daha kısa yol olduğunu kabul eder.

Oyun #3

İkinci oyun devam ederken C ismi verilmiş olan üçüncü bir yol açılsın:

20190425_134223.jpg

Yine oyunculardan en az biri C’yi denemeye karar verir. Aynı bir önceki oyun gibi oyunculardan dikkatli olanlar çizgi sayılarına bakarak hangi yolun daha kısa olduğuna karar verir.

En İyi H&G Oyuncuları: Karıncalar

Yazının başında karıncaların bize en kısa yolu bulmayı öğrettiğini söylemiştim. 1992’de Marco Dorigo ismindeki bir bilim insanı karıncaların yemek arayışlarıyla ilgili bir araştırma yapmıştı. Dorigo araştırması sonucunda karıncaların yuvalarıyla besin kaynakları arasındaki yolu nasıl gittiklerini açıklamıştı.

Karınca yuvası ve besin kaynağı aşağıdaki gibi olsun:

20190425_134508.jpg

Karınca besin kaynağını yuvasına aşağıdaki gibi bir yol izleyerek taşısın:

20190425_134535.jpg

Feromon: Aynı türün üyeleri arasındaki sosyal ilişkileri düzenleyen kimyasal madde.

Karıncalar yürürken arkalarında feromon, yani bir tür kimyasal madde bırakır:

20190425_134548.jpg

İşte karıncaların en kısa yolu bulmalarını sağlayan şey de bu maddedir. Bir yoldan ne kadar çok karınca geçerse o yolda o kadar çok feromon vardır. Aynı bizim kalemle çizgi çizmemiz gibi.

Gelin karıncaların yoluna bir engel koyalım:

20190425_134602.jpg

Karıncaların bir kısmı engelin aşağısından, diğer kısmıysa yukarısından yoluna devam eder:

20190425_134620.jpg

I numaralı yol daha kısa olduğu için karıncalar bu yolun üzerinde daha çok tur atarlar. Yani daha çok feronom bırakırlar:

20190425_134631.jpg

Zamanla diğer yoldaki karıncalar daha çok feronom olan yolu tercih eder.

Karınca Kolonileri Algoritması (KKA)

Gündelik hayatta her işimizi en hızlı ve en kısa yoldan halletmeye çalışıyoruz. İşte bunu yaparken bize yardımı olan algoritmalardan birinin adı Karınca Kolonileri Algoritması’dır. Bu algoritmanın mantığı karıncaların en kısa yolu bulma yönteminden gelir.

Quicktron-Alibaba-warehouse
Alibaba’nın içinde sadece robot çalışan deposu.

Örneğin KKA robotların hareketlerini belirlemesinde büyük önem teşkil eder. Bir alanda birden çok robotun birbirine çarpmadan hareket edebilmesi için KKA kullanılır.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Graf #4

2014 yılının Kasım ayında Rusya’nın St. Petersburg şehrinde bulunan dünyaca ünlü Hermitage müzesini ziyaret etmiştim. İçinde 1057 tane oda olan Hermitage’ı baştan sona yürüyen biri 22 km mesafe kat etmiş olur. Müzede bulunan eserlerin tamamına bakmak istiyorsanız, her esere sadece 1 dakika ayırsanız bile bu işi 11 yıldan önce bitirmenin mümkün olmadığını bilmeniz gerekir.

hermitage-map-st-petersburg
Hermitage’ın planı.

Bu yüzden Hermitage’ı sadece birkaç saatliğine ziyaret etmeye çalıştığımda nerede ne kadar süre geçirmem gerektiğini iyi ayarlamalıydım. Çünkü devasa müzeyi kısa sürede gezmem, ama bunu yaparken ilgimi çeken eserleri görmem gerekiyordu.

Aslında bu, çok orijinal bir problem değil. Hemen herkes günlük yaşamında bu tür problemlerle karşılaşır: “Ev-iş arasında hangi saatte hangi yolu kullanmalı?” gibi.

Postacının Yolu

St. Petersburg’da bu problemle karşılaşmam çok hoş bir tesadüftü. Çünkü Petersburg 18. yüzyılda ünlü matematikçi Leonhard Euler’e ev sahipliği yapmıştı. İlk graf yazısından hatırlayacağınız üzere Euler Königsberg’in yedi köprüsü problemiyle birlikte çizge teorisinin ortaya çıkmasına önayak olmuştu.

Königsberg probleminden 230 yıl sonra 1960’da Çinli bir matematikçi olan Mei-Ko Kwan soruyu biraz daha farklı şekilde ele almıştı:

Bir postacı rotasındaki evlere elindeki mektupları dağıtmak üzere posta ofisinden ayrılır. Postacının en kısa sürede tüm evlere uğrayıp tekrar posta ofisine dönmesi için nasıl bir rota izlemesi gerekir?

indir
Mei-Ko Kwan

Kwan’a ithafen Çinli Postacı Problemi olarak bilinen bu problemde önemli olan detaylar şunlardır:

  • Postacı rotası üzerindeki tüm sokakları kullanmalıdır. Fakat her sokak sadece ama sadece bir defa kullanılmalıdır.
  • Postacının rotasında başlangıç ve bitiş posta ofisinde olmalıdır.
  • Postacının amacı en kısa sürede yukarıdaki iki şartı yerine getirmektir.

Çizge Teorisinin Gücü

Mei-Ko Kwan Çinli Postacı Probleminin çözümünde Euler’in Königsberg’in yedi köprüsü için ortaya keşfettiklerinden yararlanmıştı. Kwan’a göre problem Euler’in yaptığı gibi graf haline getirebilirdi. Postacının gitmesi gereken mahalleler noktalarla, mahalleler arasındaki mesafeler (yani sokaklar) ise çizgilerle gösterilebilir.

Örnek Graf:

20190324_210039
A, B, C, D ve E harfleri mahalleri, aralarındaki çizgiler yolları gösteriyor. Çizgilerin üzerindeki sayılarsa postacının bir mahalleden diğerine ne kadar sürede gittiğini ifade ediyor.

Hatırlatma

Euler döngüsü nedir?

Eğer bir grafta Euler döngüsü varsa o grafta bulunan tüm çizgiler bir ama sadece bir defa kullanılarak tam bir tur atılabilir demektir. Ayrıca Euler döngüsünde başlangıç ve bitiş aynı noktadadır.

Euler döngüsü ne zaman vardır?

Bir graftaki bir noktanın sahip olduğu çizgi sayısı, o noktanın derecesini verir. Eğer bir grafta Euler döngüsü varsa, o graftaki tüm noktalar çift derecelidir.

Çözüm

Anlaşıldığı üzere Çinli Postacı Probleminin çözümü için postacının rotasında Euler döngüsü olmalıdır. Örneğin postacının güzergahı aşağıdaki gibi olsun:

20190325_123338.jpg
Çizgilerin üzerindeki sayılar harfler mesafeleri (km cinsinden olsun) gösteriyor.

İlk yapılması gereken şey tüm noktaların (harflerin) sahip olduğu çizgi sayısını bulmak:

20190325_123326.jpg

Yukarı görüldüğü üzere graftaki tüm noktalar çift derecelidir. Bu sayede hiç denememize bile gerek kalmadan bu rotada Euler döngüsü olduğunu söyleyebiliriz. O halde postacının en kısa sürede görevini tamamlaması için graftaki yolları kullanması yeterlidir:

20190325_123311.jpg
En kısa güzergah 11 km sürer.

Tek dereceli noktalar varsa grafa yeni çizgiler eklenerek (yani postacı yeni yollar üretmek zorundadır) tüm noktalar çift dereceye çevrilmelidir. Peki bu nasıl yapılır?

  1. Tek dereceli noktaları bul.
  2. Bu noktaları ikili gruplara ayır.
  3. İkili gruplar arası mesafeleri bul. En düşük mesafeliler eklenmesi gereken çizgileri belirtir.
  4. Çizgileri grafa ekle.

Yukarıda verdiğim mahalle örneği üzerinden giderek açıklamaya çalışalım. Sorun postacının A mahallesinden başlayıp yine A’da bitecek gününü en kısa sürede tamamlamak istemesidir.

Önce her mahallenin (yani noktanın) sahip olduğu yol sayısına (yani çizgi sayısına) bakalım:

20190324_210039
A ve D’nin 3’er, B, C ve E’nin 2’şer çizgisi vardır.

Her nokta çift sayıda çizgiye sahip olsaydı burada bir Euler yolu olurdu ve postacının en kısa turu direk mesafelerin toplanmasıyla bulunabilirdi. Fakat A ve D noktalarının tek sayıda çizgiye sahip olması bunu engelliyor:

20190324_210102

Bu durumda yapılması gereken şey, tek çizgiye sahip noktalar arasında yeni yol veya yollar yapmaktır. A ve D mahalleri arasında üç farklı yol vardır. Bunlardan en kısasını bulup grafa eklersek sorumuz çözülmüş olur:

20190324_210157

A-D mahalleri arasındaki yollar yukarıdaki gibidir. Görüldüğü üzere en kısa süre direk A-D arasındaki yoldadır. O halde A-D arasına yeni bir yol eklersek postacının sorunu çözülmüş olur:

Bi’ Göz Atmakta Fayda Var

Aşağıdaki rotada A’dan başlayıp A’ya dönmesi gereken postacının en kısa yolu ne kadar süre alır? Bunu yapabilmek için kullanması gereken rota nedir?

20190324_210225

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Oyun #6

Oreo Yerleştirme Oyunu – OYO

Ali ile Ayşe (evet, daha klişe isimler bulamadım) ne zaman kahve içmek için buluşsa yanlarında getirdikleri oreolarla bir oyun oynuyor. Oyunun amacı önlerindeki masanın üzerinde serdikleri peçeteye oreoları dizmektir. Bunu yaparken oreolar üst üste gelmemeli ve peçeteden taşmamalıdır. Peçeteye son oreoyu koyan oyunu kazanır.

Kurallar:

  • İki kişi sırayla ve her seferinde sadece bir tane oreoyu peçete üzerinde istediği yere koyar.
  • Peçete çember şeklindedir.
  • Oreolar üst üste binemez.
  • Oreolar peçetenin sınırının ötesine geçemez.
  • Peçeteye sığan son oreoyu koyan kişi oyunu kazanır.

Ali veya Ayşe’den biri için her seferinde oyunu kazanmasını sağlayan bir algoritma var mıdır?

Evet, OYO’da her zaman kazanmak için uygulanabilecek bir algoritma vardır. Fakat bu algoritma sadece oyunda ilk hamleyi yapan kişi için geçerlidir.

Kazanan Algoritma:

  • Oyunda ilk hamleyi yapan kişi ol.
  • İlk hamlede oreoyu peçetenin merkezine koy.
  • Sonraki hamlelerinde rakibin oreosunu nereye koyuyorsa o konumun merkezdeki oreoya göre simetrisini seç.
  • Eninde sonunda ikinci oyuncunun oreosunu koyacak yeri kalmayacak.

Oyuna ilk başlayan oreosunu çemberin merkezine koyar.

İkinci oyuncu oreosunu nereye koyduysa bunu merkeze göre 180 derece çevirin ve oreonuzu oraya koyun.

Stratejisine sadık kaldığı takdirde eninde sonunda oyunu ilk oyuncu kazanır.

Düzgün Çokgen Peçeteler

Peçetenin şekli üçgen iken OYO’da aynı algoritma için farklı durumlar ortaya çıkar. Bunlardan biri ilk oreo üçgenin merkezine konulduğu durumdur. Eğer şeklin içine tek sayıda oreo sığıyorsa ilk oyuncu algoritmayı uygulayarak her zaman oyunu kazanır.

Fakat çift sayıda oreo sığarsa:

O halde oyunu ikinci oyuncu kazanır. Bu durumda ilk oyuncunun her oyunu kazanması için algoritmada ufak bir değişiklik yapılabilir. Oyuncu ilk hamlesinde oreoyu tam merkeze değil de herhangi bir köşeye biraz daha yakın koyabilir:

Üçgendeki durum beşgen şeklinde de aynen geçerlidir:

Görüldüğü üzere ilk oreo merkeze konduğunda kaybetme ihtimali var. Fakat merkezin hafif üzerine doğru konulursa oyunu ilk oyuncu kazanır:

Peki oyuna ilk başlayan olmadığınızda kazanmak için bir algoritma var mı?

Bunu peçetenin şeklini değiştirerek başarabilirsiniz. Oyunun peçetesi bir düzgün çokgen değil de aşağıdaki gibi olsun:

nankon1

Bu gibi durumlarda bir oyuncu hamlesini yaptıktan sonra geriye birer oreonun sığabileceği için iki ayrı boş alan bırakıyorsa oyunu kazanır:

Yukarıdaki gibi bir şekilde akıllı oynadığı takdirde ilk oyuncu her zaman kazanır.

Bu yüzden ikinci oyuncunun oyunu kazanması için oreosunu yerleştirdikten sonra peçete üzerinde birer oreonun sığacağı iki ayrık boşluk kalmalıdır. Bunu aşağıdaki gibi bir peçetenin üzerinde başarabilir:

Bu şekilde ilk oyuncu oreosunu nereye koyarsa koysun inisiyatif ikinci oyuncuda olur:

Bi’ Göz Atmakta Fayda Var

Eğer oreo yuvarlak değil de kare şeklinde olsaydı aynı algoritma işe yarar mıydı? Bunu üçgen ve çember peçeteler üzerinde deneyin.

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Şans #4

Serkan’ın Kahvesi

Haftanın muhtelif günlerinde (tamam kızmayın; haftada en az altı gün) kahveciye gidiyorum. Sık ziyaret etmemden dolayı artık baristalar ne içtiğimi biliyor… gibi.

İçecek tercihlerim altı aylık dönemlerle değişiyor. Ekim-Mart döneminde latte ve filtre kahve, Nisan-Eylül dönemindeyse soğuk latte ve berry tercihlerini yaparım.

Ekim-Mart: Latte içtiğim günün ertesinde yine latte içme ihtimalim %80 iken, filtre kahve içtiğim günün ertesinde yine filtre kahve içme ihtimalim %60’dır.

Nisan-Eylül: Soğuk latte içtiğim günün ertesinde yine aynı şeyi içme ihtimalim %80 iken, berry için aynı ihtimal %90’dır.

20190205_195247
Ekim-Mart arasındaki kahve tercihimi gösteren bir şema.

Soru: Bugün filtre kahve içtiysem iki gün sonra latte içiyor olma ihtimalim kaçtır? (Soru Şubat ayında geçiyor.)

Yukarıda geçen sorunun içinde matematiğin en temel bulgularından biri olan Markov Zinciri bulunur:

20190205_195031
Bir Markov Zinciri örneği. Ne olduğunu yazının devamında açıklayacağım.

Açıkça görülüyor ki iki gün sonra latte içmek için iki ayrı ihtimal vardır. Bu ihtimallerin toplamı bize cevabı verir:

Ertesi gün filtre kahve içip(0,6), iki gün sonra latte içme(0,4) ihtimali: 0,6*0,4 = 0,24.

Ertesi gün latte içip(0,4), iki gün sonra yine latte içme(0,8) ihtimali: 0,4*0,8 = 0,32.

İki gün sonra latte içme ihtimali: 0,24 + 0,32 = 0,56.

Yani %56 ihtimal.

Bi’ Göz Atmakta Fayda Var

  1. Şubat ayının kaçıncı gününde olunduğunun bir önemi var mı?
  2. Bir gün önce filtre kahve içmiş olmamın sonuç üzerinde bir etkisi var mıdır? Cevabınızı açıklayınız.
  3. Haziran ayının 11. gününde soğuk latte içtiysem, 14 Haziran’da berry içme ihtimalim nedir?

Sürücüsüz Arabalar

Eğer Google’da arama yaparsanız “Sene oldu … nerede bu uçan arabalar?!” içeriğine sahip binlerce sayfalık yazı bulabilirsiniz. Bu isyanın sebeplerinin başında Geleceğe Dönüş filmi gelir. Haksız sayılmayız. Sonuçta geleceğe ya da geçmişe gitmek gibi bir derdimiz yok. Uçan arabada olsak yeter.

gelecege-donus-hakkinda-bilmedikleriniz,Z6sLULxzT02ta5L2MlbZvA

Sene oldu 2019 ve ufakken hayallerimizi süsleyen uçan arabalar hala etrafta yok. Teknoloji ancak sürücüsüz araba yapacak kadar gelişti. (Ancak?!)

Sürücüsüz araba yapabilmek için gereken en önemli şeylerden biri karar verme sistemini içeren teknolojidir. Çünkü kendini kullanan bir araba en basit bir yolculukta dahi yüzlerce tercih yapmak zorunda kalacaktır.

Bu teknolojinin ana fikri ise Serkan’ın Kahvesi örneğinde zikrettiğim Markov Zinciri’ne dayanır. Sürücüsüz arabalarda Markov Karar Süreci denilen çok güçlü bir matematiksel metot kullanılır.

Markov Karar Süreci (MDP) : İçinde belirsiz davranışlar barındıran kontrol ve karar problemleri için uygulanan bir matematiksel modeldir.

Belleksiz Olasılık

Markov Zinciri: Bir olay veya sistemde Markov Zinciri varsa o sistemin içinde gelecekte ne olacağı geçmişten bağımsız fakat mevcut duruma bağlı olarak değişir ve hatta tahmin edilebilir.

Markov Zinciri’ne verilebilecek örneklerden biri sarhoşun yürüyüşüdür. Hatırlatalım: Bir sarhoş evini bulmaya çalışırken rastgele kararlar verir. Sarhoş aşağıdaki durumda yürüyüşünü yapmış olsun:

rand1

Bir sonraki tercihini hangi noktaya doğru yapacağı, geçmiş tercihlerine bağlı değildir. Bu, sadece bulunduğu konuma ve tercih olasılıklarına bağlıdır.

rand2
Sarhoşun durduğu son nokta olan F’den gidebileceği dört nokta vardır. Bunlardan hangisini seçeceği önceki adımlarına bağlı değildir.

Sürücüsüz bir arabanın yapacağı tercihler de geçmişte yaptığı tercihlere bağlı değildir. Örneğin trafik ışıklarına gelen bir arabanın yapacağı tercihi 100 metre önce sola dönmüş olması değil, ışığın rengi etkiler.

Markov Zinciri 100 yılı aşkın bir zaman önce ortaya çıkmasına rağmen hala ekonomi, oyun teorisi, meteoroloji, biyoloji ve hatta ses tanıma gibi modern teknolojilerde kullanılmaya devam etmektedir.

Matematikçi Aile

Markov Zinciri’ne ismini veren kişi olan Rus matematikçi Andrey Markov’un küçük kardeşi Vladimir Markov da uluslararası arenada tanınan bir matematikçiydi. Vladimir sadece 25 yaşındayken tüberkülozdan hayatını kaybetti. Andrey’in oğlu Andrey Markov Jr. da matematikçiydi.

Politika ve Andrey

Andrey Markov politik olarak aktif biriydi. Uzun bir süre boyunda (1613’den 1917’ye dek) Rusya’yı yöneten Romanov hanedanlığına karşı olduğunu karakterine uygun bir şekilde göstermişti. Markov, Romanovların 1913’te yaptığı 300. yıl kutlaması yerine büyük sayılar kanununun 200. yılını kutlamıştı. (Sonraki yazılarda büyük sayılar kanunundan bahsedeceğim.)

M. Serkan Kalaycıoğlu

Matematik Atölyesi – Oyun #5

Bana Karşı Hepiniz

Bu yazıda seninle bir oyun oynayacağım. Evet, sana diyorum doğru bildin. Yazının sonunda nerede durursan onu kazanacaksın.

Kurallar:

  • Oyuna sol üst köşeden başlanır.
  • Her hamlede gidilebilecek sadece dört yön var: Aşağı, yukarı, sağ ve sol.

    hepsis
    1000 Euro’dan bir adım atılacaksa bu ya sağındaki 1000 dolara, ya da aşağısındaki Iphone’a doğru olur. Çapraz gitmek serbest olmadığı için 1000 Euro’dan bir adım atarak kahveye geçilemez.
  • İkinci kural izlendiği takdirde istenildiği gibi hareket edilebilir. Yani aynı yere geri dönmek, istenilen yere istenildiği kadar gitmek serbest.
  • Her hamlede adım atmaya en son kaldığınız kutudan devam edilecek.
  • Benim görevim attığın adımlar sonrasında bazı kare/kareler seçip elemek. Eğer elediğim karelerden birinde isen oyunu kazanmış olacaksın.
  • Tekrar ediyorum, çapraz ve benzeri hareket yok. Sadece aşağı-yukarı ve sağ-sol yapılabilir.

Hazır olduğunda başlıyoruz. İyi şanslar.

Oyun

1. Aşağıdaki dokuz kare arasında hareket edeceksin. Başlangıç sol üst köşeden, yani 1000 Euro’nun olduğu yerden olacak şekilde 5 adım at.

hepsi

2. Hareketinden sonra 1000 euro’nun bulunduğu karede olamazsın. Şimdi bulunduğun yerden başlayarak tam 7 adım atacaksın. Attın mı? O halde bir sonraki maddeye geçebilirsin.

hepsi2

3. Adımlardan sonra 1000 doların üzerinde durmuyorsun; değil mi? Bu yüzden 1000 doları da oyundan çıkarıyorum. Oyunu biraz daha hızlandırıyor ve 11 adım atmanı istiyorum.

hepsi3

4. Bu sefer daha iddialı olacağım ve iki kutu seçeceğim: Durduğun yer araba anahtarı ve bir çanta dolusu paranın olduğu kutuların her ikisi de değil. Haklı olduğumu biliyorum ve aşağıdaki şekil üzerinde nerede duruyorsan oradan başlayıp 5 adım atmanı istirham ediyorum.

hepsi4

5. Adımların bittikten sonra Iphone ve 100 doları da eleyebilirim, çünkü biliyorum ki oralarda değilsin. Şimdi bulunduğun yerden sadece 1 adım atmanı istiyorum.

hepsi5

Sonuç: Kahve ve 500 doları eliyorum çünkü biliyorum ki şu an sıfırın üzerindesin. Üzgünüm ama kocaman bir sıfır kazandın.

Bi’ Göz Atmakta Fayda Var

Bu oyunu kim oynarsa oynasın, adımları nasıl atarsa atsın, her zaman sonuç bu olacak. Peki ama neden? Nasıl kendimden bu kadar eminim?

M. Serkan Kalaycıoğlu