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

0 beğenilme 0 beğenilmeme
248 kez görüntülendi

$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.

25, Ocak, 2018 Uygulamalı Bilgisayar Bilimi kategorisinde murad.ozkoc (9,641 puan) tarafından  soruldu

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.


2 Cevaplar

0 beğenilme 0 beğenilmeme

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}

8, Şubat, 2018 OkkesDulgerci (1,775 puan) tarafından  cevaplandı
Teşekkür ederim.
0 beğenilme 0 beğenilmeme

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.


17, Temmuz, 17 Oktay Cesur (30 puan) tarafından  cevaplandı
...