Danimarkalı iki bilgisayar bilimcisi, 1990 dan beri çözülemeyen matematik sorusunu çözdü.
Söz konusu soyut problemin konusu grafik teorisi ile ilgili. Çözülemeyen nokta ise dinamik bir grafiğin düzlemselliğini çözmek için algoritma bulunamaması.. Bu biraz ürkütücü gelebilir, grafik teorileri ile ilgili bilgileriniz yetersizse daha eğlenceli bir yol ile düşünebiliriz.
1913’ lü yıllara gittiğimizde, matematik bilmeceleri için 3 yardımcı program sorunu vardı.
Basitçe anlatalım. Bir kağıda 3 tane ev çizin, bu evlerin altına da 3 tane kamu hizmeti, elektrik su ve doğalgaz olsun.
İlginizi çekebilir: Milenyum Problemleri: Her Biri 1 Milyon Dolar Değerinde Olan 7 Matematik Problemi
Şimdi bu kamu hizmetlerini her eve bağlamamız lazım ama buradaki zorluk şu; çizgilerinin hiçbiririn birbirini kesmemesi gerekiyor. Bunu yapabiliyor muyuz?
Ne yazıkki mümkün değil, bu evlerin hepsi keşismeden bağlantıları alamıyor en azından 2 boyutlu bir kağıt üzerinde.
Ama bu zaten çözülmesi gereken bir problem değil. Sadece grafik ağlarının nasıl düzlemsel olmadığına bir örnek.. Grafikler de tıpkı bu evler gibi köşelere ve şekildeki gibi kesişimlere sahip.
Daha fazla köşe içeren, daha karmaşık grafiklerle uğraşırken matematikçiler, grafiklerin düzlemsel olup olmadığını belirlemek için Kuratowski’ nin teoremini kullanırlardı ve 1970 lerden beri aynı şeyi daha hızlı yapabilmek için algoritma geliştirmeye çalışıyorlardı.
Bilmeceyi çözmekten neredeyse vazgeçmiştik
Nihayetinde 1990 larda bu konuda biraz ilerleme kaydedilmişti. En azından dinamik grafiklerin çözümü için son yıllarda kaydedilen en önemli gelişmelerden biriydi.
Geçen yıla baktığımızda Kopenhag Üniversitesi’ nden bilgisayar bilimcileri Jacop Holm ve Danimarka Teknik Üniversitesi’ nden Eva Rotenberg bu konuda çalışıyorlardı.
Holm, “ son işlemleri yapmaktan ve bu bilmeceyi çözmekten neredeyse vazgeçmiştik çünkü en iyi ihtimalle 5 yıllık bir çalışma daha olması gerektiğini düşünüyorduk,” diyor.
Tam da o noktada , nerdeyse kazara, problemin çoğunu başka bir araştırmada çözdüklerini fark ettiler. Sözü geçen araştırma, 2019’ da çevrimiçi olarak ön çalışmasının yayınlandığı düzlemsel kavramlar ile ilgili bir araştırma.
İki araştırmacı bunun üzerine, hali hazırda yayınlanmış olan gizli çözümle kendi araştırmalarını harmanladı ve 1990’ lardan beri ilerleme kaydedilememiş grafik algoritmasında iyileştirme yaptıklarını resmi olarak duyurdu.
Rotenberg , “ Makale üzerinden hiç durmadan 5-6 hafta çalıştık, 80 sayfalık bir makale oluşturduk,” diyor.
Algoritma son haliyle bize şunu sunuyor; dinamik bir grafikteki köşeler ve bunları birleştiren fakat kesişen çizgiler silinebilir mi , bu çizgiler eklenebilir mi ve ya bu grafik düzlemsel olarak yerleştirilebilir mi.. Daha basit bir ifade ile ; evler ve kamu hizmetleri kağıda çizilir mi ? Çizilirse çizgiler kesişirmi? Ve bunu en az hesaplama süresinde yapıyor.
Bu büyük bir ilerleme, çünkü burda verdiğimiz örnekte sadece 3 tane çizgi vardı. Ancak mikroçip tasarımı veya yol planlaması gibi 3 ev ve 3 kamu hizmetinden çok daha fazla köşelere sahip alanlarda durum daha karmaşık hale geliyor.
Holms, “ Dinamik grafik problemleri için şöyle bir sonuca vardık. Grafikte yaptığınız her değişiklikte sonra sıfırdan hesap yapmaktan çok daha hızlı bir şekilde hesaplamak için kullanılabilecek bazı veri yapılarının mümkün olduğu ortaya çıkmış oldu” .
“Bu sonuç bizim için ciddi bir kişisel zafer”
Zehra ORUÇ
