Darstellung und Vereinigung unendlicher Mengen



  • Hallo zusammen,

    ich brauche etwas geistigen Input, daher die Frage, wie würdet ihr folgendes "Problem" lösen?

    Ich bekomme eine Zahl, und einen Operator. Dieses Paar stellt letztlich einen Wertebereich dar. Zum Beispiel bekomme ich eine Zahl 95, und einen Operator "größer als", so dass sich ein Wertebereich aller Zahlen ergibt, die größer als 95 sind. Das ist mein erster Wertebereich.

    Dann bekomme ich aber noch einen zweiten Wertebereich rein, wieder mitgeteilt durch eine Zahl und einen Operator. Nehmen wir als Beispiel die Zahl 100 und den Operator "kleiner gleich", d.h. ich hab alle Zahlen die kleiner als 100 sind in meinem Wertebereich.

    Ich will jetzt wissen, ob diese beiden mir bekannten Wertebereiche gemeinsame Werte haben. Da würde sich natürlich eine einfache Schnittmenge anbieten, so dass ich hinterher nur schauen muss, ob diese Schnittmenge nicht leer ist. In meinem Beispiel hätte ich ja eine nicht leere Schnittmenge.

    Das Problem ist jetzt die mögliche Unendlichkeit der Mengen. Gut, ich bin jetzt etwas in meiner Unendlichkeit beschränkt, da ich ja auf die Typen der Programmiersprache festgenagelt bin (übrigens Java). Wenn ich jetzt also einen Double nehme, und bekomme die Zahl 95 und den Operator "größer gleich", dann sind in meiner Menge halt alle Zahlen größer gleich 95, die ich in einem double darstellen kann, also 95.1, 95.01, 95.001, .....

    Wie modelliere ich sowas am besten, vor allem im Hinblick darauf dass es effektiv ist? Eine stumpfe Herangehensweise wäre, einfach eine Collection zu nehmen, die ein Mengenverhalten hat (z.B. in Java alles was Set implementiert), und alle Zahlen, die der Datentyp hergibt, reinzustecken. Das ist aber sehr speicherintensiv und wenig effektiv. Man könnte sich auch nur die Anfangs- und Endwerte einer Menge merken, was aber Probleme bei der zweiten Frage verursacht.

    Die zweite Frage ist, wie vergleiche ich dann zwei Wertebereiche am besten miteinander? Wenn ich ein Set habe, wäre eine Schnittmenge naheliegend. Aber auch die wäre speicherintensiv, weil letztlich noch eine dritte Menge gebildet wird. Merke ich mir nur Anfangs- und Endwerte, wäre es das einfachste, jeden Operator hart zu codieren - was aber im Hinblick auf Erweiterbarkeit nicht gerade der Renner ist. Zum Beispiel: (mal auf int beschränkt)

    if (ersterWertebereich.Operator == "größer gleich")
    {
      for (int i = ersterWertebereich.Zahl; i < INT_MAX; ++i)
      {
         if (zweiterWertebereich.Operator == "größer gleich")
            for (...)
    
         if (zweiterWertebereich.Operator == "ungleich")
            for (..)
    
         if (zweiterWertebereich.Operator == "kleiner gleich")
            for (int j = zweiterWertebereich.Zahl; i > INT_MIN; --i)
               if (i == j)
                   success = true;
      }
    }
    

    Das Problem, wenn ich mir nur Anfangs- und Endwerte merke ist, dass jeder Operator seine eigene Behandlung benötigt.

    Bin da gerade etwas ratlos und dankbar für gute Anregungen!



  • beselbube schrieb:

    Ich bekomme eine Zahl, und einen Operator. Dieses Paar stellt letztlich einen Wertebereich dar. Zum Beispiel bekomme ich eine Zahl 95, und einen Operator "größer als", so dass sich ein Wertebereich aller Zahlen ergibt, die größer als 95 sind. Das ist mein erster Wertebereich.

    Also ein Intervall, $$(95,\infty)$$

    Dann bekomme ich aber noch einen zweiten Wertebereich rein, wieder mitgeteilt durch eine Zahl und einen Operator. Nehmen wir als Beispiel die Zahl 100 und den Operator "kleiner gleich", d.h. ich hab alle Zahlen die kleiner als 100 sind in meinem Wertebereich.

    (-\infty, 100]

    Ich will jetzt wissen, ob diese beiden mir bekannten Wertebereiche gemeinsame Werte haben. Da würde sich natürlich eine einfache Vereinigung der Mengen anbieten, so dass ich hinterher nur schauen muss, ob diese Vereinigung nicht leer ist. In meinem Beispiel hätte ich ja eine nicht leere Vereinigung.

    Schnitt, nicht Vereinigung. Der Schnitt ist $$(95,100]$$. Solange du immer nur schneidest, bleibt es ein Intervall. Das kannst du mit zwei Grenzen darstellen, jede Grenze ist inklusive oder exklusive (bzw. geschlossen oder offen) mit einer Zahl, oder unendlich (hier musst du wissen, ob du unendlich mit dabei haben willst oder nicht ... double hat ja unendlich mit drin, das ginge also, in der Mathematik macht man das aber nur, wenn man es wirklich braucht). Das Schneiden müsstest du dir überlegen, das ist aber nicht so schwer. Das Intervall kann auch leer werden.

    Wenn du Vereinigungen brauchst, ist es aber sofort vorbei mit der Hübschheit.

    Das ist im Grunde deine Idee. Die Bedenken bezüglich der Erweiterbarkeit kann ich nicht ganz nachvollziehen. Wenn du das erweitern willst, hast du ein anderes mathematisches Konzept, und musst dir nochmal von vorne Gedanken machen.



  • Du hast Recht, ich meine natürlich Schnitt (intersection), habe ich gerade mal strikt im deutschen verwechselt 🙂 Ich mache mir mal Gedanken über dein Geschriebenes..

    weitere Gedanken sind aber natürlich willkommen 🙂



  • Bashar: Im Code-Beispiel hat der OP auch die Operation "ungleich", wodurch man im schlechtesten Fall beim Schneiden drei disjunkte Intervalle erhält.

    beselbube: Was genau hast du denn mit den Intervallen vor? Du schreibst etwas von "vergleichen", aber ich weiß nicht, was ich mir darunter vorzustellen habe. In deinem Code-Beispiel prüfst du, ob der Schnitt zweier Mengen nicht leer ist. Das geht aber auf einzelne Intervalle bezogen schneller, indem du ne zugegebenermaßen nicht ganz schöne Fallunterscheidung machst, wie die jeweiligen Grenzen zueinander liegen.



  • Also die Intervalle die ich da hereinbekomme sind halt Teil eines größeren. Letztlich geht es darum, zu schauen ob die Intervalle miteinander vereinbar sind, dass heißt ob eine Schnittmenge von ihnen Werte enthält oder nicht. Ich denke mittlerweile auch, dass die Überprüfung der Intervallgrenzen die effektivste (im Sinne von schnell und ressourcenschonend) Methode ist. Hätte nur gerne was "cooles" gehabt, und da auf geistigen Input gehofft 🙂



  • Unendliche Mengen, was soll das sein? 😕 Wir sind hier im Forum "Rund um die Programmierung" unterwegs, da kennen wir doch nur endliche Mengen im RAM, auf HDD oder woanders. Ist das jetzt eine mathematische oder eine philosophische Frage?? Ich weiss nur: "Die Menge des Geldes auf dem Konto oder in Tasche ist stets endlich und oft zu gering!" 🙄



  • Du stellst die internen Gegebenheiten des Rechners über die Problemstellung? Bist du nicht sonst eigentlich derjenige, der sich über Informatiker beschwert, die vor lauter Informatik-Wissen Probleme haben, Kundenanforderungen zu verstehen?



  • @Bashar: Gut, den Begriff 'unendliche Menge' gibt es in der Mathematik, z.B. die Mengen der natürlichen oder reellen Zahlen. Im realen Leben sind solche unendlichen Mengen jedoch eher unbekannt. Was will der Fragesteller denn programmieren? Mit unendlich vielen Elementen einer Menge kann kein Programm umgehen. Es bleibt allein eine spezielle Sache der Mathematik zur Vollständigkeit des Begriffes Menge, also eine rein theoretische Angelegenheit. Wo denn sollen bei einem Kunden unendliche Mengen tatsächlich vorkommen, noch dazu die Vereinigung solcher unendlichen Mengen? Meinen Ausflug zur Menge von Geld möge man mir gnädig verzeihen wie auch manche sonst salopp formulierten Bemerkungen von mir zu anderen Dingen hier im Forum.



  • Mit unendlich vielen Elementen einer Menge kann kein Programm umgehen.

    Doch, wenn man eine geeignete Abstraktion findet. Und darum geht es ja. Auch sind deine anderen Behauptungen wie

    Im realen Leben sind solche unendlichen Mengen jedoch eher unbekannt

    einfach nur Bullshit. Ich habe damit staendig zu tun.

    Wie modelliere ich sowas am besten, vor allem im Hinblick darauf dass es effektiv ist?

    Was willst du mit den Wertebereichen machen?

    Die zweite Frage ist, wie vergleiche ich dann zwei Wertebereiche am besten miteinander?

    Zu welchem Zweck? Normalerweise kann nicht festgestellt werden, ob zwei (unendliche) Mengen die gleichen Elemente enthaelt. Das ist ein generelles Problem der Berechenbarkeit.

    Es ist einfach zu testen, ob ein Wert in der Menge enthalten ist. Anderes beispielsweise ist schwer: ueber die Menge zu iterieren, was aber meist nicht gefordert oder unnoetig ist. Wie willst du z.B. alle reelen Zahlen ausgeben? Was ist der Nachfolger von 0.1?



  • worin besteht eigentlich das Problem?

    Intervalle stellt man durch seine zwei Grenzen dar (mit +/-inf für unbeschränkte Int.) und dann:

    $I\_1:=[a\_1,b\_1],\ I\_2:=[a\_2,b\_2]$\medskip\\ Vereinigg: $I\_1\cup I\_2=[\min(a\_1,a\_2),\ \max(b\_1,b\_2)]$\medskip\\ Schnitt: falls $\max(a\_1,a\_2)>\min(b\_1,b\_2)\Rightarrow\emptyset$\medskip\\ sonst: $I\_1\cap I\_2=[\max(a\_1,a\_2),\min(b\_1,b\_2)]$

    Mengen-Darstellung in aufzählender Schreibweise dürfte sich bei 64-Bit-Zahlen wohl verbieten, es sei denn mit seeeeeeehr viel RAM 😃



  • knivil schrieb:

    Was ist der Nachfolger von 0.1?

    Und mit dieser Frage sind wir dann wieder beim Thema angelangt! Reelle Zahlen sind unendlich und nicht in einzelnen konkreten Elementen - sondern nur in Wertebereichen - darstellbar und auch diese bleiben notwendig in der Anzahl und der Grösse begrenzt. Zwischen 0.1 und 0.2 liegt wieder eine unendliche Menge reeller Zahlen vor. Einen Nachfolger von 0.1 gibt es nicht! Ingenieure kennen und verwenden für diese Zwecke einen Zuverlässigkeitswert eps = 1.e-xx z.B bei Iterationen.



  • !rr!rr_. schrieb:

    worin besteht eigentlich das Problem?

    Intervalle stellt man durch seine zwei Grenzen dar (mit +/-inf für unbeschränkte Int.) und dann:

    $I\_1:=[a\_1,b\_1],\ I\_2:=[a\_2,b\_2]$\medskip\\ Vereinigg: $I\_1\cup I\_2=[\min(a\_1,a\_2),\ \max(b\_1,b\_2)]$

    Klappt nicht, wenn I_1 und I_2 sich nicht berühren oder überschneiden.

    Schnitt: falls $\max(a\_1,a\_2)>\min(b\_1,b\_2)\Rightarrow\emptyset$\medskip\\ sonst: $I\_1\cap I\_2=[\max(a\_1,a\_2),\min(b\_1,b\_2)]$

    Betrachte [0,1) ,(1,2]. Damit siehst du das allgemeinere Problem, dass du unterscheiden musst, ob die Grenzen im Intervall enthalten sind oder nicht. Gerade hier hast du auch Schwierigkeiten mit den Fließkommaeigenschaften, wenn die Grenzen irgendwie berechnet wurden.



  • Michael E. schrieb:

    Klappt nicht, wenn I_1 und I_2 sich nicht berühren oder überschneiden.

    ?? Dann ist der Schnitt aber kein Intervall, sodaß er mit einer Datenstruktur für Intervalle ohnehin nicht auskommt.

    Michael E. schrieb:

    Betrachte [0,1) ,(1,2]. Damit siehst du das allgemeinere Problem, dass du unterscheiden musst, ob die Grenzen im Intervall enthalten sind oder nicht.

    Fallunterscheidung, na und ?



  • !rr!rr_. schrieb:

    ?? Dann ist der Schnitt aber kein Intervall, sodaß er mit einer Datenstruktur für Intervalle ohnehin nicht auskommt.

    meinte "Vereinigung", nicht "Schnitt"



  • Ok, danke soweit für den Input.

    Letztlich muss ich es so hinkriegen, das ich mir nur die Intervall-Grenzen merke und diese dann miteinander vergleiche.

    Der große Rahmen des ganzen ist, dass ich eine Anfrage habe und ein Angebot dazu, und ich muss prüfen ob diese beiden zueinander kompatibel sind. Das aber nur am Rande 🙂

    Das mit den unendlichen Wertebereichen ist tatsächlich eher ein theoretischs Problem - aber das Programm sollte in der Lage sein, auch das zu handlen. Jedenfalls ist das die Vorgabe.



  • !rr!rr_. schrieb:

    Michael E. schrieb:

    Klappt nicht, wenn I_1 und I_2 sich nicht berühren oder überschneiden.

    ?? Dann ist der Schnitt aber kein Intervall, sodaß er mit einer Datenstruktur für Intervalle ohnehin nicht auskommt.

    Richtig, er braucht eine Menge von Intervallen. Die braucht er aber sowieso.

    Michael E. schrieb:

    Betrachte [0,1) ,(1,2]. Damit siehst du das allgemeinere Problem, dass du unterscheiden musst, ob die Grenzen im Intervall enthalten sind oder nicht.

    Fallunterscheidung, na und ?

    Nichts anderes hab ich gesagt.



  • Es reicht für mein Problem übrigens das ich weiß, ob der Schnitt leer oder nicht leer ist - deshalb ist es auch nicht so wichtig, ob ich nach einer Vereinigung/Schnittmenge die richtigen Intervalle bekomme. Deshalb ist der obige Vorschlag eigentlich schon ganz brauchbar - und sehr effizient! 🙂



  • berniebutt schrieb:

    @Bashar: Gut, den Begriff 'unendliche Menge' gibt es in der Mathematik, z.B. die Mengen der natürlichen oder reellen Zahlen. Im realen Leben sind solche unendlichen Mengen jedoch eher unbekannt.

    Das spielt keine Rolle, ein Programm blickt auf das reale Leben immer durch die Brille eines Modells. Wenn du deine Kaninchenzüchtersoftware anschaust, hast du da sicher irgendwo sowas wie einen Gewichtsbereich, z.B. "zwischen 1 und 2 Kilo". Das ist mathematisch eine unendliche Menge von Zahlen. Praktisch könntest du natürlich sagen, dass du nur auf Gramm genau misst. Trotzdem würdest du mit einem Objekt, dass die Aussage "zwischen 1 und 2 kg" verkörpert, arbeiten, und nicht alle Zahlen von 1,0 bis 1,999 in ein set knallen. Schon allein aus Performance und Wartbarkeitsgründen. Es hätte zusätzlich den Nachteil, dass du beim Durchschnitt von 2 Kaninchen eventuell eine "ungerade" Zahl, z.B. 1,5005, bekommst, die dann gar nicht mehr in der Menge ist. Du müsstest also runden usw. Wozu diese Komplexität?

    Was will der Fragesteller denn programmieren? Mit unendlich vielen Elementen einer Menge kann kein Programm umgehen.

    Na und, aber es kann mit der Menge umgehen, das reicht doch.


Log in to reply