Forums Neueste Beiträge
 

Explosivste Teilmenge

10/10/2011 - 02:50 von Björn Kaiman | Report spam
Hallo!

Ich bin kein Mathematiker, habe aber ein mathematisches Problem, bei
dessen Lösung ich mich über ein wenig Hilfe freuen würde. Es könnte also
sein, dass ich im folgenden einige Begriffe oder Notationsweisen falsch
benutze. Ich bitte um Nachsicht.

Gegeben sind:

Eine endliche Menge M = { a1, a2, a3, ... an }.

Eine Funktion f(x, y): (x, y) -> t
mit x, y e M und t e I = [-k, k] c Z

Die Potenzmenge P(M).

(e bedeutet "ist Element von" und c bedeutet "ist Teilmenge von")

Die Funktion f ist dabei als Aufzàhlung/Wertetabelle definiert, sie folgt
also keiner Zuordnungsvorschrift (jedenfalls keiner, die man
sinnvollerweise als Ausdruck hinschreiben würde).

Gesucht ist:

ein m e P(M) mit SUMME{x, y e m}(f(x,y)) >= SUMME{a, b e n}(f(a, b)) für
alle n e P(M). x != y bzw. a != b

Der letzte Ausdruck soll heißen, dass die Teilmenge m von M gesucht ist,
für die die Summe der Funktionswerte für alle verschiedenen Elemente
dieser Teilmenge maximal wird.

Als ein Beispiel könnte man sich folgendes denken. M ist eine Menge von
Chemikalien. f(x, y) gibt an, wie gefàhrlich es ist, die Chemikalie x der
Chemikalie y hinzuzufügen. Gesucht ist die (un)gefàhrlichste Kombination
von Chemikalien. Dabei ist i. A. f(x, y) != f(y, x). Man denke z. B. an
das Hinzufügen von Wasser zu Sàure und umgekehrt (eines davon ist
gefàhrlich). Für die Ermittlung der Summen sollen immer beide Richtungen
berücksichtigt werden, im Beispiel Wasser+Sàure und Sàure+Wasser.

Man könnte nun alle Elemente der Potenzmenge durchgehen und für alle Paare
die Funktionswerte berechnen. Leider ergibt das in der praktischen
Druchführung eine exponentielle Laufzeit, ich bin aber auf der Suche nach
einem effizienten Algorithmus (polynomielle Laufzeit)...

Vielen Dank für jede Hilfe!

vg Björn
 

Lesen sie die antworten

#1 Detlef Müller
10/10/2011 - 17:17 | Warnen spam
Am 10.10.2011 02:50, schrieb Björn Kaiman:
Hallo!

Ich bin kein Mathematiker, habe aber ein mathematisches Problem, bei
dessen Lösung ich mich über ein wenig Hilfe freuen würde. Es könnte also
sein, dass ich im folgenden einige Begriffe oder Notationsweisen falsch
benutze. Ich bitte um Nachsicht.

Gegeben sind:

Eine endliche Menge M = { a1, a2, a3, ... an }.

Eine Funktion f(x, y): (x, y) -> t
mit x, y e M und t e I = [-k, k] c Z

Die Potenzmenge P(M).

(e bedeutet "ist Element von" und c bedeutet "ist Teilmenge von")

Die Funktion f ist dabei als Aufzàhlung/Wertetabelle definiert, sie
folgt also keiner Zuordnungsvorschrift (jedenfalls keiner, die man
sinnvollerweise als Ausdruck hinschreiben würde).

Gesucht ist:

ein m e P(M) mit SUMME{x, y e m}(f(x,y)) >= SUMME{a, b e n}(f(a, b)) für
alle n e P(M). x != y bzw. a != b



Sicher meinst Du nicht das selbe n wie oben (die Anzahl der Elemente
von M), ich schreibe einmal lieber s dafür.

Naja, etwa m := M wird das sicher erfüllen. Andererseits wird
kein anderes t e P(M) die Bedingung erfüllen, da ja für jede andere
Teilmenge als M weniger Summanden in der zugehörigen Summe sind.

Das ist sicher nicht das, was Du wirklich suchst. Ich denke,
es sollte noch eine Einschrànkung der Anzahl der Elemente der
m e P(M) und s e P(M) geben ?!

Gruß,
Detlef

Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de

Ähnliche fragen