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 – Garip Dünyalar #17

Kafamızdaki Topoloji

Sürekli olaylara bakış açımızı değiştirmekten bahsediyorum. Örneğin bir bebekle karşılaştığınızda aklınıza öncelikle bebeği sevmek ve onu güldürmeye çalışmak gelir. Halbuki bebeğin saçlarına dikkat ederseniz, burada çok önemli bir matematik bilgisinin saklı olduğunu görebilirsiniz:

Her bebeğin kafasında yukarıdaki gibi bir nokta vardır. Görüldüğü üzere bu noktanın dışında kalan saçlar, bebeğin kafasının hemen her yönüne doğru uzuyor. Peki noktanın bulunduğu yerde çıkan saçların yönü neresidir?

Bunun açıklaması topolojide saçlı top teoremi ile yapılmıştır.

Saçlı Top Teoremi

Saçlı top teoremine göre tüylü (veya bulabilirseniz saçlı) bir topu herhangi bir yöne doğru taramaya çalışın. Topun en az bir noktasında bulunan bir tüyün (veya saçın) istenilen yöne doğru taranması mümkün değildir.

Bunu yapmaya çalıştığınızda en az bir tüy (veya saç) taranmak istenen yönde olmaz. Bu tüyün bulunduğu noktada bir tür tekillik bulunur; tüy istenilen tarafa yatmayıp dik durmakta ısrar eder.

Bebeğin kafası da bir nevi saçlı top teoremi örneğidir. (Bir nevi dememin sebebi, saçlı top teoremine göre topun yüzeyinin tamamının tüyle kaplı olmasıdır. Halbuki bir insanın kafasının her yeri saçla kaplı değildir.) Bu sebeple yukarıdaki resimde gösterdiğimiz noktada bir tekillik vardır; o noktada saç dik kalır. O saç bir türlü tarakla yatırılamaz.

Torus

İçi boş (bir diğer deyişle; delikli) bir cisim olan torusta saçlı top teoremi işlemez. Yani tüylü bir torusun tamamını tek bir yöne taramak mümkündür.

Hiç Rüzgar Yok

Saçlı top teoreminin kullanım alanlarından biri meteorolojidir. Teoreme göre herhangi bir anda dünyanın herhangi bir noktasında hiç rüzgar yoktur.

Bunu ispatlamak için tüylü topu tarama yöntemini düşünmeniz yeterli. Diyelim ki dünyanın her yerinde doğudan batıya doğru rüzgar esiyor olsun.

Bu durumda kuzey ve güney kutup noktalarında rüzgar olmaz. Yani saçlı top teoremi haklıdır.

Haritadayım

Saçlı top teoremi Brouwer’in sabit nokta teoreminin bir başka türüdür. Hatta bu teorem de L.E.J. Brouwer tarafından 1912 yılında ispat edilmiştir.

Sabit nokta teoremi için verilebilecek örneklerden biri de haritalarla ilgilidir. Örneğin bulunduğunuz ülkenin haritasının çıktısını alın ve sınıf içerisinde yere koyun:

Daha küçük bir harita da olur.

Harita üzerinde öyle bir nokta vardır ki, haritanın bulunduğu coğrafi konumla aynıdır.

Avm veya otobüs duraklarındaki “buradasın” haritaları buna örnek olarak gösterilebilir.

Bi’ Göz Atmakta Fayda Var

Aşağıdakilerin tüylü olduğunu varsayın. Hangisi /hangileri aynı yöne doğru taranabilir? Neden?

M. Serkan Kalaycıoğlu