Sigma-Algebren angeben

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Hey,

wollte gestern mal ein Programm schreiben, dass mir zu einer Menge Omega alle Sigma-Algebren ausspuckt...
Gibt es dafür einen schlauen Algorithmus?

Ich hatte erstmal so angefangen:

- Erstelle minimale Algebra (0, Omega), füge diese zum Ergebnis hinzu. (O(|Omega|))
- Für i = 1 bis |Omega|/2 (O(|Omega|)
Erstelle alle i-elementigen Teilmengen A von Omega (O(|Omega|über i)
Erstelle neue Algebra (0, A, Ac, Omega), füge sie zum Ergebnis hinzu(O(|Omega|))

Jetzt bräuchte ich noch die "Vermischungen" von Algebren mit unterschiedlichen Teilmengen,
wobei ich natürlich aufpassen muss:
z.B. Würde aus {{}, {1}, {2, 3, 4}, {1, 2, 3, 4}} durch das hinzufügen von {2} ja
{{}, {1}, {2}, {1, 2}, {3, 4}, {2, 3, 4}, {1, 3, 4}, {1, 2, 3, 4}}.
Dies entspricht halt dem Hinzufügen von {1} zu {{}, {2}, {1, 3, 4}, {1, 2, 3, 4}}...

Habt ihr da eine schlaue Idee? Oder gibt es einen Algorithmus dafür?

ffgorcky · Beiträge: 573 WIN XP/2000 & 7Prof (Familie:Win95,Win98)

Ich weiß jetzt leider nicht so ganz, ob Du nur das hier meinst:
http://www.mathepedia.de/Sigma-Algebren.aspx
Ist Dir damit schon geholfen?

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Hey,

war vllt. auch etwas undeutlich geschrieben...

Was eine Sigma-Algebra ist, ist mir klar, es ging darum ein Programm zu schreiben, dem ich eine Menge Omega geben, und das Programm gibt mir die Menge aller Sigma-Algebren aus, deren Menge von Mengen eine Teilmenge der Potenzmenge von Omega ist

Dummerweise ist ja |P(Omega)| = 2^|Omega|, und die hat wieder 2^n Teilmengen, also käme ich schlimmstenfalls auf 2^2^n Mengen, bei denen ich überprüfen müsste, ob sie eine Sigma-Algebra sind, da läuft einem die Laufzeit davon...

(Bsp. dazu:
Sei A = {0, 1}

Dann ist P(A) = {{}, {0}, {1}, {0, 1}}

Das Ding hat schon 16 Teilmengen, von denen allerdings nur zwei
({{}, {0, 1}} und {{}, {0}, {1}, {0, 1}} eine Sigma-Algebra abgeben...)

Horst_H · Verfasst: Fr 08.05.09 21:44

Hallo,

Wenn Du Dir schon merkst, welche Element schon verarbeitet sind
Dann ist Fall 1 {}+{1}
Wenn Du {2} hinzufügst ergibt sich {}+{1}+{2} das selbe, als hättest Du erst {}+{2} erzeugt und dann {1] hinzugefügt zu {}+{1}+{2}
Reciht es denn nicht erst nach einander
1.ten
{}+{1},{}+{2} ..{}+{n2= n div 2} zu erzeugen und dann diese weiter zu verarbeiten.
2.ten
{{}+{1}} +{2}...{n2}//Startwert 2 ,{{}+{2}} +{3]..{n2}//Startwert 3 ....
3.ten
{{}+{1}+{2}+{3}} +{4}...{n2}//Startwert 4,{{}+{2}+{3}} +{5}..{n2}
n2.ten Durchgang
Das ergäbe ein Dreieck der Höhe und Basis n2
Aber sind dann auch alle erwischt?

Gruß Horst

alzaimar · Verfasst: Sa 09.05.09 09:43

Sind das nicht Variationen?

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

Type
  TByteSet = Set Of Byte;

Procedure Variation(Const s: String; k: Integer; aResult: TStrings);
  Procedure _Variation(Const s, q: String; k, n: Integer; B: TByteSet);
  Var
    j: Integer;

  Begin
    If k = 0 Then
      aResult.Add(q)
    Else
      For j := 1 To n Do
        If Not (j In B) Then
          _Variation(s, q + s[j], k - 1, n, B + [j])
  End;

Begin
  _Variation(s, '', k, Length(s), []);
End;

Procedure AllVariations (Const s: String; aResult : TStrings); // Deine Lösung ?
Var
  i : Integer;

Begin
  For i:=1 to Length(s) do 
    Variation (s,i,aResult);
End;

_________________
Na denn, dann. Bis dann, denn.

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Hey,

@alzaimar:
Erstellst du damit nicht "nur" die k-elementigen Teilmengen von Sigma?
Die Algebren müssen ja auch bezüglich der unendlichen Vereinigung von Teilmengen und Komplementierung abgeschlossen sein...

@Horst:
So etwa in die Richtung hatte ich auch gedacht...
Die Algebren zu erstellen, die nur aus der leeren Menge, Sigma, k-elementigen Teilmengen und deren Komplementen bestehen, ist ja noch relativ easy. (Obwohl's natürlich auch schon eine Laufzeit von 2^n hat^^)
Das macht man dann bis |Sigma/2|, und merged die Ergebnisse irgendwie zusammen...
user defined image

Das Problem dabei ist ja, dass es schon wieder 2^n Möglichkeiten gibt, einelementige Teilmengen mit in eine bestehende Algebra zu schmeißen...

"Muss" erstmal los zum Fussball, werd mir nachher nochmal Gedanken dazu machen

Horst_H · Verfasst: So 10.05.09 10:15

Hallo,

dioe Potenzmenge hat 2^n Element aber der Algorithmus, von dem ich immer noch nicht weiß, ob er vollständig ist, hat (n/2)^2 Sigma-algebren.
Das ist erheblich weniger ob 2^10 =1024 oder (10/2)^2 = 25 .
Wenn es nun quadratisch viele sigma-algebren gibt, dann muss auch wohl solange dauern.
( Lüge! : Sortieren ist ein Permuation der Ausgangsmenge und dauert nicht n! sondern n*lb(n) )
Aber teste es doch in Object-Pascal , es gibt ja Mengen .
Wenn die Potenzmenge auch eine Sigma-Algebra ist, wovon ich ausgehe; denn wenn jede Mege enthalten ist, ist auch ihr Komplement enthalten.
Ich will doch nur die Mengen nummerieren und es kommen einfach nur Binärzahlen heraus.
Omega('1111111111111111'); Leere Menge ='0000000000000000' .
Also simpelste Logik Komplement= OMEGA AND NOT(Menge), so sind ja die Mengen in set's repräsentiert, zu früh am Tag...

Gruß Horst

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme