Bir ailenin topoloji olup olmadığını test eden bir bilgisayar programı

Question

$X$ sonlu bir küme olmak üzere herhangi bir $\tau\subseteq \mathcal{P}(X)$ ailesinin söz konusu $X$ kümesi üzerinde topoloji olup olmadığını kontrol eden bir program (online da olabilir) bilen var mı? Varsa ve paylaşırsa sevinirim.

Comments

Var mıdır bilmiyorum ama yazmak çok zor olmasa gerek. $n$ elemanlı bir kümenin her alt kümesini, girdileri $1$ ve $0$'lardan oluşan bir $v\in \mathbb{R}^n$ vektörü ile eşleyebiliriz. Bu vektörlerin toplamları ve farklarını bir şekilde kullanarak kesişim ve birleşimleri yine vektörler cinsinden açıklayabiliriz. Bu vektörlerin ailemizde olup olmadığını da kontrol edebiliriz.

Küme sonlu olduğu için ikili kesişim ve ikili birleşim yeterli olacaktır.

---

Özgür bunu matlab ile mi yaparız?

---

Herhangi bir dille uygulanabilir. Fakat eleman sayısı arttıkça bu basit kontrol işlemi çok uzun sürer gibi görünüyor.

---

Bir arkadaşım matematica'da bu işi yapacak bir program yazdı. $6$ elemanlı bir kümenin kuvvet kümesinin $30$ elemanlı bir altailesini ele aldık. Topoloji olup olmadığını kontrol etmek için matematica'da yazılan programı çalıştırdığımızda maalesef bilgisayar kilitlendi.

---

Ben cevap vermeyi unutmuşum, özür diliyorum. Verecek cevabım da yok maalesef.

---

Ozgur bahsettigin islemi genelde bit dizileriyle yapiyoruz ve inanilmaz hizli calisiyorlar. bitarray diye aratirsaniz bulabilirsiniz. Ben bu sorunun varligindan haberdar olmadan soyle bir soru sormustum. Kaba kuvvet ile butun olasi topolojileri buluyor. Su sitede $n$ elemanli kume uzerine kac taneolasi topoloji koyabilecegimizi listelemisler.

Anladigim kadari ile topolojiler ile onsiralamalar (preorder in turkcesi bu mu bilemedim) arasinda birebir bir esleme var belki bunu kullanarak daha verimli bir algoritma uretilebilir.

Answer 1

surda var.  https://stackoverflow.com/questions/8814059/generating-topological-space-diagram-in-mathematica/8815337#8815337

 

suraya da bakilabilir. https://mathematica.stackexchange.com/questions/5/generating-a-topological-space-diagram-for-an-n-element-set/165#165

 

Ben test ettim 22 eleman icin 29 saniye, 24 eleman icin 95 saniye aliyor. 27 eleman icin denedim yaklasik 5 dakika sonra sonlandirdim programi.

 

In[1]:= set = Subsets[Range@6]

Out[1]= {{}, {1}, {2}, {3}, {4}, {5}, {6}, {1, 2}, {1, 3}, {1, 4}, {1,
5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {3,
6}, {4, 5}, {4, 6}, {5, 6}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 2,
6}, {1, 3, 4}, {1, 3, 5}, {1, 3, 6}, {1, 4, 5}, {1, 4, 6}, {1, 5,
6}, {2, 3, 4}, {2, 3, 5}, {2, 3, 6}, {2, 4, 5}, {2, 4, 6}, {2, 5,
6}, {3, 4, 5}, {3, 4, 6}, {3, 5, 6}, {4, 5, 6}, {1, 2, 3, 4}, {1, 2,
3, 5}, {1, 2, 3, 6}, {1, 2, 4, 5}, {1, 2, 4, 6}, {1, 2, 5, 6}, {1,
3, 4, 5}, {1, 3, 4, 6}, {1, 3, 5, 6}, {1, 4, 5, 6}, {2, 3, 4,
5}, {2, 3, 4, 6}, {2, 3, 5, 6}, {2, 4, 5, 6}, {3, 4, 5, 6}, {1, 2,
3, 4, 5}, {1, 2, 3, 4, 6}, {1, 2, 3, 5, 6}, {1, 2, 4, 5, 6}, {1, 3,
4, 5, 6}, {2, 3, 4, 5, 6}, {1, 2, 3, 4, 5, 6}}

In[2]:= set2 =Sort@Join[{First@set, Last@set}, RandomSample[Most@Rest@set, 22]]

Out[2]= {{}, {1}, {2}, {3}, {4}, {5}, {6}, {1, 2}, {1, 3}, {2, 3}, {5,
6}, {1, 2, 3}, {1, 3, 4}, {1, 3, 6}, {1, 4, 5}, {1, 5, 6}, {2, 3,
4}, {2, 3, 6}, {2, 4, 5}, {4, 5, 6}, {1, 2, 3, 5}, {2, 3, 4, 5}, {1,
2, 3, 5, 6}, {1, 2, 3, 4, 5, 6}}

In[3]:= topologyQ[x_List] :=Intersection[x, #] === # &[
Union[{Union @@ x}, Intersection @@@ Rest@#, Union @@@ #] &@Subsets@x]

In[4]:= topologyQ@set2 // AbsoluteTiming

Out[4]= {95.7043, False}

 

Comments

Teşekkür ederim.

Answer 2

Konu ile ilgili  zaten  kaynak verilmiş fakat sarpa sardığı durumlarla karşılaşılmış.  Ben buna yönelik bir cevap vereceğim. Bunun için biraz topoloji (hatta çok az), temel kavramları anlayacak kadar da karmaşıklık (özellikle zaman karmaşıklığı) bilmeniz gerekmekte. Elimden geldiğince açık yazmaya çalışacağım fakat yine de tıkanırsanız bu konularda ek okumalar yapabilirsizniz. 

Verilen programı inceleyemedim (zaten koddan karmaşıklık analizi yapmak hakim olduğum bir şey değil.) ama yazması o kadar karmaşık bir program değil. Topolojik uzay tanımı bilgisayara algoritma olarak rahatlıkla aktarılabilir. Fakat işin sıkıştığı nokta karmaşıklığı. Adım adım bakacak olursak. 

$n$ elemanlı bir $\tau$ ailesi verilmiş olsun. Topoloji olma aksiyomlarını zaman karmaşıklığı açısındn inceleyelim.

[T1]: $\emptyset$ ve $X \ \  \tau$ içinde mi? 

En kolay kontrol edilecek olan kısım burası n kaç olursa olsun iki eleman var. $\tau$ içinde bu iki elemanı arayacağız. Basit bir arama algoritması, karmaşıklık $ O(n)$. Bu kabaca şu anlama geliyor, $ n$ sayısı ile bu adımda  yapılması gereken işlem sayısı arasında doğrusal bir ilişki vardır.

 

[T2]: Herhangi elemanın kesişiminin yine $\tau$ içinde mi?

İki eleman seçiyoruz. Bunun için $\frac{n(n+1)}{2}$ seçeneğimiz var. Her adımda arama için yine $n$ işlem yapmak gerekecek.Toplamda ise   $\frac{n^2 (n+1)}{2}$ işlem yapılması gerekir. $0(n^ 3)$ zaman karmaşıklığımızdır ve bu bilgisayar için halletmei kolay bir şeydir.

[T3]: $\tau$ ailesinin herhangi sayıda elemanının birleşimi yine $\tau$  içinde midir?

İşte hesabın şaştığı nokta burası. $n$ tane elemanlı bir kümemiz var ve bu kümenin tüm altkümelerinin elemanlarının birleşimlerinin hesaplaması gerekecek. Bu da $2^n$ tane elemanı kontrol etmemiz demek. Her birleşim bulma işlemi o adıma gelindiğinde polinomsal zamanda halledilebilecek bir iş. Ortalama bir bilgisayar için kolay bir iş fakat bulunacak olan eleman sayısı üstel olduğu için (yani karmaşıklığımız $O(2^n)$) işlemi kitleyen kısım. 

Bunu anlamak için şöyle bir hesap yapabiliriz. 1Ghz güce sahip bir işlemci saniyede $1.000.000.000 (\approx 2^{30} )$ işlem yapar. Bunun içinde sistem, kullanılan diğer programlar filan dahildir. Biz işlemcinin sadece bizim işimizi yaptığını, yani sadece $\tau$ ailesinin kuvvet kümesini yazdığını (hesaplama yok, sadece yazma) varsayalım. Bu da demek ki işlemcimiz 30 elemanlı bir kümenin kuvvet kümesini 1 saniyede yazabilmekte. Aşağıda ise $n$ sayısına göre işlemlerin yaklaşık ne kadar süreceğine bir bakalım.

$n=30 \Longrightarrow $ 1 saniye

$n=31 \Longrightarrow $ 2 saniye

$n=35 \Longrightarrow $ 32 saniye

$n=40 \Longrightarrow $ 17 dakika

$n=50 \Longrightarrow $ 12 gün

$n=60 \Longrightarrow $ 34 yıl

Genel olarak işlemimiz yaklaşık $2^{n-30}$ saniye sürecektir. Görülgüğü üzere eleman sayısı arttıkça sürenin artışı çılgın seviyelere gelmekte. Bu sebeple kaba kuvvet yönteminin kullanıldığı (kuvvet kümesindeki tüm durumların hesaplandığı) algoritmalar en verimsiz algoritmalardır. İlk iki adımdaki işlemden saniyede milyonlarca yapabilecek olan işlemci son adıma geldiğinde yıllarca işlem yapmak zorundadır.

Not: Yapılan yorumlardan birisinde kendi yazdığı algoritmada 30 eleman girişi yapıldığında bilgisayarın kitlendiği söylenmiş. Büyük ihtimal hesaplamanın yapıldığı bilgisayarın işlemci1Ghz den fazladır.Bunun sebebi bilgisayarın sadece açıkken bile saniyede on milyonlarca işlem yapmasıdır. 1ghz$\approx 2^{30}$ olduğu için daha anlaşılır olması için başlangıçta 30 sayısını seçtim.

Answer 3

Galiba daha hizli bir yontem bulmus olabilirim.

Bildigim kadari ile bir kume uzerine yazabilecegim sonlu topolojiler ve preorderlar arasinda birebir ve orten bir fonksiyon var. Asagidaki ifadeyi kullanarak bir topolojiden, preorder yaratmam mumkun.

$x \leq y \iff \forall_{U:\tau}(x \in U)\implies(y \in U)$

(EDIT : Burada dusuncemde soyle bir hata farkettim tamam bu yukarida verilen ifade ile bir topolojiden preorder yaratabiliriz ama bunun her zaman topoloji olmayan bir aile icin preorder olusturmayacaginin garantisini vermek lazim   )

Bir ikili iliski preorderdir eger transitive ve refleksive ise.
 
$M$ ikili iliskinin matriks formunda ifadesi olsun,

$M$ refleksive dir eger $M_{ii} = 1 $ ise.
$M$ transitive dir eger $M_{ij} = 0 \iff (M\cdot M)_{ij}=0$ ise.