Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > de.sci.mathematik > #71548 > unrolled thread
| Started by | Hans-Peter Diettrich <DrDiettrich1@aol.com> |
|---|---|
| First post | 2017-11-19 23:18 +0100 |
| Last post | 2017-12-01 19:25 +0000 |
| Articles | 20 on this page of 28 — 8 participants |
Back to article view | Back to de.sci.mathematik
Lineare Abhängigkeit? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2017-11-19 23:18 +0100
Re: Lineare Abhängigkeit? Detlef Müller <lef-65@arcor.de> - 2017-11-20 14:39 +0100
Re: Lineare Abhängigkeit? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2017-11-21 13:05 +0100
Re: Lineare Abhängigkeit? Jens Kallup <kallup.jens@web.de> - 2017-11-21 19:24 +0100
Re: Lineare Abhängigkeit? Detlef Müller <lef-65@arcor.de> - 2017-11-21 19:38 +0100
Re: Lineare Abhängigkeit? Marc Olschok <nobody@nowhere.invalid> - 2017-11-26 02:37 +0000
Re: Lineare Abhängigkeit? Carlo XYZ <carloxyz@invalid.invalid> - 2017-11-26 10:19 +0100
Re: Lineare Abhängigkeit? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2017-11-26 13:56 +0100
Re: Lineare Abhängigkeit? Carlo XYZ <carloxyz@invalid.invalid> - 2017-11-26 16:17 +0100
Re: Lineare Abhängigkeit? qdl@gmx.net (H0Iger SchuIz) - 2017-11-26 17:01 +0100
Re: Lineare Abhängigkeit? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2017-11-26 20:01 +0100
Re: Lineare Abhängigkeit? qdl@gmx.net (H0Iger SchuIz) - 2017-11-26 20:11 +0100
Re: Lineare Abhängigkeit? Andreas Leitgeb <avl@logic.at> - 2017-11-26 21:13 +0000
Re: Lineare Abhängigkeit? Carlo XYZ <carloxyz@invalid.invalid> - 2017-11-27 07:41 +0100
Re: Lineare Abhängigkeit? Martin Vaeth <martin@mvath.de> - 2017-11-27 08:43 +0000
Re: Lineare Abhängigkeit? Carlo XYZ <carloxyz@invalid.invalid> - 2017-11-27 11:23 +0100
Re: Lineare Abhängigkeit? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2017-11-27 21:40 +0100
Re: Lineare Abhängigkeit? Martin Vaeth <martin@mvath.de> - 2017-12-01 19:56 +0000
Re: Lineare Abhängigkeit? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2017-12-02 09:36 +0100
Re: Lineare Abhängigkeit? Detlef Müller <lef-65@arcor.de> - 2017-12-02 13:39 +0100
Re: Lineare Abhängigkeit? Carlo XYZ <carloxyz@invalid.invalid> - 2017-12-03 12:18 +0100
Re: Lineare Abhängigkeit? Martin Vaeth <martin@mvath.de> - 2017-12-03 11:05 +0000
Re: Lineare Abhängigkeit? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2017-12-04 23:03 +0100
Re: Lineare Abhängigkeit? Martin Vaeth <martin@mvath.de> - 2017-12-05 17:28 +0000
Re: Lineare Abhängigkeit? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2017-12-04 23:12 +0100
Re: Lineare Abhängigkeit? Martin Vaeth <martin@mvath.de> - 2017-12-05 17:29 +0000
Re: Lineare Abhängigkeit? Hans-Peter Diettrich <DrDiettrich1@aol.com> - 2017-12-13 23:20 +0100
Re: Lineare Abhängigkeit? Martin Vaeth <martin@mvath.de> - 2017-12-01 19:25 +0000
Page 1 of 2 [1] 2 Next page →
| From | Hans-Peter Diettrich <DrDiettrich1@aol.com> |
|---|---|
| Date | 2017-11-19 23:18 +0100 |
| Subject | Lineare Abhängigkeit? |
| Message-ID | <f7ee9lFn46bU1@mid.individual.net> |
Folgendes abstraktes Problem: Wie kann aus einer Menge von Mengen eine Teilmenge von N Mengen gefunden werden, deren Vereinigungsmenge N Elemente hat? Dabei erscheint mir noch recht gängig zu sein: Welche N (linear unabhängige) Gleichungen aus einem Gleichungssystem erlauben die Bestimmung von N Variablen? Etwas konkreter: Welche N Ziffern können in einer Zeile oder Spalte eines Sudoku nur in genau N Feldern auftreten? Gibt es effiziente Algorithmen zur Bestimmung solcher Teilmengen? DoDi
[toc] | [next] | [standalone]
| From | Detlef Müller <lef-65@arcor.de> |
|---|---|
| Date | 2017-11-20 14:39 +0100 |
| Message-ID | <ouulv1$bm1$1@gwaiyur.mb-net.net> |
| In reply to | #71548 |
Am 19.11.2017 um 23:18 schrieb Hans-Peter Diettrich:
> Folgendes abstraktes Problem:
> Wie kann aus einer Menge von Mengen eine Teilmenge von N Mengen gefunden
> werden, deren Vereinigungsmenge N Elemente hat?
Das dürfte zu Allgemein sein, als das man dazu konkrete Ansätze
liefern könnte.
Nennen wir M die Menge von Mengen.
Wie sollen Elemente m aus M aussehen: sollen
es endliche Mengen sein?
Soll M selbst endlich sein?
Gibt es irgend eine Einschränkung für die Vereinigungsmenge
G von M (d.h. sind die Teilmengen m aus M aus einer bestimmten
Grundmenge G)?
Eine Mögliche Wahl für M:
M könnte die Vereinigung der Mengen
Q_3={q teilmenge von IQ| #q = 3} (3-elementigen Teilmengen der
rationalen Zahlen) sowie der Menge I_e aller endlichen, nicht
leeren Mengen von irrationalen Zahlen.
Hier wäre G die Menge der Reellen Zahlen.
Für N<=3 ist das Ausgangsproblem nicht lösbar.
> Dabei erscheint mir noch recht gängig zu sein:
> Welche N (linear unabhängige) Gleichungen aus einem Gleichungssystem
> erlauben die Bestimmung von N Variablen?
Wie siehst Du den Zusammenhang zum allgemeinen Problem oben,
was entspricht konkret den Mengen M bzw. der Grundmenge G?
> Etwas konkreter:
> Welche N Ziffern können in einer Zeile oder Spalte eines Sudoku nur in
> genau N Feldern auftreten
(die Rolle von N ist mir hier nicht klar. Gleichzeitig die
Kardinalität einer Ziffernmenge und obendrein eine Anzahl von
Feldern?)
Wieder wäre es hilfreich, was hier konkret das M und das G sein und
das N (im allgemeinen Problem) sein soll,
so daß dies in das "allgemeine Problem" übersetzt wird.
> Gibt es effiziente Algorithmen zur Bestimmung solcher Teilmengen?
In der Allgemeinheit kann ich mir das nicht vorstellen. Es wird
ja so gut wie nichts an M vorausgesetzt!
Ich vermute, Du hast für das allgemeine Problem doch
eine ganze Reihe von impliziten Voraussetzungen (z.B.
Endlichkeitsbedingungen), die der Leser hier aber nicht
kennt.
Eine genaue Formulierung des Problems ist bekanntlich meist
der wichtigste Schritt zur Analyse.
Beim "allgemeinen Problem" vermute ich daß ich da nicht das
herauslese, was Du meinst.
Beim 2-ten Problem könnte ich mir einen Zusammenhang zum
"allgemeinen Problem" vorstellen - nur kann man sich viel
vorstellen, wenn der Tag lang ist ...
um nicht aneinander vorbei zu reden, sollte klar gestellt
werden, wie das 2-te Problem als Spezialfall aufgefasst
wird.
Beim 3-ten Problem ist mir die Problemstellung nach dem
zweiten Lesen nicht mehr so klar, wie sie beim Überfliegen
schien.
Eigentlich bin ich guter Dinge, daß das "allgemeine Problem",
welches Dir vorschwebt, kein mathematisches Neuland ist (im
Gegenteil).
Gruß,
Detlef
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
[toc] | [prev] | [next] | [standalone]
| From | Hans-Peter Diettrich <DrDiettrich1@aol.com> |
|---|---|
| Date | 2017-11-21 13:05 +0100 |
| Message-ID | <f7ij55FlogjU1@mid.individual.net> |
| In reply to | #71548 |
Am 19.11.2017 um 23:18 schrieb Hans-Peter Diettrich: > Folgendes abstraktes Problem: > > Wie kann aus einer Menge von Mengen eine Teilmenge von N Mengen gefunden > werden, deren Vereinigungsmenge N Elemente hat? Hat niemand eine Idee? DoDi
[toc] | [prev] | [next] | [standalone]
| From | Jens Kallup <kallup.jens@web.de> |
|---|---|
| Date | 2017-11-21 19:24 +0100 |
| Message-ID | <ov1r24$8o0$1@news.albasani.net> |
| In reply to | #71561 |
Am 21.11.2017 um 13:05 schrieb Hans-Peter Diettrich: >> Wie kann aus einer Menge von Mengen eine Teilmenge von N Mengen >> gefunden werden, deren Vereinigungsmenge N Elemente hat? > > Hat niemand eine Idee? man hat einen Suppentopf; voll mit Erbsen. Jede Erbse ist eine Menge (von Zellen) Jetzt perürren wir die Erbsen zu Erbsenbrei; und erhalten eine Vereinigungs-Menge. Wir können nun mit nen Löffel etwas Erbsenbrei aus dem Topf nehmen und unserer Oma, Kind, whatever zum essen geben. Getreu nach dem Motto: "Alete kotzt das Kind." Ne, Spaß Aber ernsthaft: weil keine N Menge angegeben wurde, kann das alles mögliche sein. Und ich würde sagen, dass der Koch, der den Brei hergestellt hat auch nicht mehr unterscheiden kann, von welcher Erbse die N Menge(n) stammen - oder? Anders schaut es aus, wenn Du aus N eine 2 machst; also 2 Mengen von jeder Erbse, so wie es Mändel - dieer Mönsch, der Erbsen züchtete und DNS abglich. Dann kann man vielleicht sagen: Du nimmst 2 Erbsen, und entnimmst aus dem inneren jeder Erbse 2 Proben. dann hast du aus 2 Erbsen also 4 Proben; wobei vorher festgelegt ist, das 2 Erbsensorten vorliegen; 1 mal eine Kichererbse und 1 mal eine Kidnaybohne. Dann hast du 2 weise und 2 schwarze Proben. Jetzt könnte man theoretisch hergehen und von den 2 Proben wieder 1 Erbse zu machen - also 1 mal weis und 1 mal schwarz = würde dann beim pflanzen und wachsen braun draus werden - oder man geht davon aus, das schwarz die dominierente Farbe ist und sich durchsetzt und aus 1 mal (schwarz und weis) wieder schwarz wird. Dann hätten wir 3 Erbsen; 1 weise und 2 schwarze. Jetzt wirds haarig: Mengen > 2 können schwarz überspringen, was dann zur Folge hat das hier evtl. mit Wahrscheinlichkeitsrechnung weiter gerechnet werden kann; oder nur noch schwarze, anstelle weis oder braun entsteht. Aber dieses Beispiel mit den Erbsen ist sehr natürlich und wahlos - im Gegensatz zur Mathematik, die eher streng und monoton sein kann - Außnahmen sind hier natürlich auch möglich. Gruß Jens
[toc] | [prev] | [next] | [standalone]
| From | Detlef Müller <lef-65@arcor.de> |
|---|---|
| Date | 2017-11-21 19:38 +0100 |
| Message-ID | <ov1rrp$etc$1@gwaiyur.mb-net.net> |
| In reply to | #71561 |
Am 21.11.2017 um 13:05 schrieb Hans-Peter Diettrich:
> Am 19.11.2017 um 23:18 schrieb Hans-Peter Diettrich:
>> Folgendes abstraktes Problem:
>> Wie kann aus einer Menge von Mengen eine Teilmenge von N Mengen
>> gefunden werden, deren Vereinigungsmenge N Elemente hat?
> Hat niemand eine Idee?
Wie schon gesagt, ist das wirklich sehr allgemein ...
Als erstes würde ich die Menge M_1 der Elemente von M mit
maximal N Elementen bilden.
gibt es ein x in M_1 mit #x=N, so ist {x} eine Teilmenge,
die das gewünschte leistet.
Ansonsten bilde für k=2 , ... , N die Mengen
M_k = {(x_1,...,x_k)| x_i in M_0, #(x_1 u ... u x_k)<=N}
(wobei man vermutlich viel Arbeit spart, wenn man sukzessive
M_{k+1} aus den Elementen von M_k und M_1 konstruiert)
Sobald man ein Tupel mit #(x_1 u ... u x_k)=N findet, ist man
fertig, ansonsten ist die Anforderung nicht erfüllbar.
Wenn genaueres über die im Spiel befindlichen Mengen bekannt
ist, kann man womöglich noch effektivere Methoden finden als
das beschriebene Durchprobieren.
Gruß,
Detlef
> DoDi
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
[toc] | [prev] | [next] | [standalone]
| From | Marc Olschok <nobody@nowhere.invalid> |
|---|---|
| Date | 2017-11-26 02:37 +0000 |
| Message-ID | <ovd9cs$n7v$1@news.albasani.net> |
| In reply to | #71561 |
Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote:
> Am 19.11.2017 um 23:18 schrieb Hans-Peter Diettrich:
> > Folgendes abstraktes Problem:
> >
> > Wie kann aus einer Menge von Mengen eine Teilmenge von N Mengen gefunden
> > werden, deren Vereinigungsmenge N Elemente hat?
>
> Hat niemand eine Idee?
Wieso sollte das (außer für N=0) überhaupt immer möglich sein?
Nimm z.B. { {1,2} , {1,2,3} }
--
Marc
[toc] | [prev] | [next] | [standalone]
| From | Carlo XYZ <carloxyz@invalid.invalid> |
|---|---|
| Date | 2017-11-26 10:19 +0100 |
| Message-ID | <carloxyz-3B5EBE.10194826112017@46.sub-75-242-165.myvzw.com> |
| In reply to | #71561 |
Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote:
> Am 19.11.2017 um 23:18 schrieb Hans-Peter Diettrich:
> > Folgendes abstraktes Problem:
> >
> > Wie kann aus einer Menge von Mengen eine Teilmenge von N Mengen gefunden
> > werden, deren Vereinigungsmenge N Elemente hat?
>
> Hat niemand eine Idee?
Doch, die Idee, dass wir[1] uns eine bessere Beschreibung
und ein Beispiel gewünscht hätten. Ich hole das einmal nach:
Gegeben eine endliche Grundmenge G, eine Menge C
von Teilmengen von G, und eine Zahl N<=|G|.
Frage: Gibt es in C eine Menge mit N Elementen,
deren Vereinigung N Elemente hat?
Man denkt sofort an "set cover"[2], aber die Reduktionen funktionieren
nicht so einfach (in keiner der beiden Richtungen) wegen der genauen
Festlegung auf N. Überhaupt ist die Fragestellung ..eigenwillig, z.B.:
G={1,2,3,4} und C={ {1} , {2} , {1,3,4} , {2,3,4} }
Für N=1 und N=2 geht's, für N=3 nicht, für N=4 doch wieder. Komisch.
Außerdem: was hat das mit "linearer" Abhängigkeit zu tun?
Nein, ich will's gar nicht wissen.
[1] Zumindest Detlef und ich.
[2] <http://www.csc.kth.se/~viggo/wwwcompendium/node142.html>
[toc] | [prev] | [next] | [standalone]
| From | Hans-Peter Diettrich <DrDiettrich1@aol.com> |
|---|---|
| Date | 2017-11-26 13:56 +0100 |
| Message-ID | <f7vrv7FnmjpU1@mid.individual.net> |
| In reply to | #71644 |
Am 26.11.2017 um 10:19 schrieb Carlo XYZ:
> Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote:
>
>> Am 19.11.2017 um 23:18 schrieb Hans-Peter Diettrich:
>>> Folgendes abstraktes Problem:
>>>
>>> Wie kann aus einer Menge von Mengen eine Teilmenge von N Mengen gefunden
>>> werden, deren Vereinigungsmenge N Elemente hat?
>>
>> Hat niemand eine Idee?
>
> Doch, die Idee, dass wir[1] uns eine bessere Beschreibung
> und ein Beispiel gewünscht hätten. Ich hole das einmal nach:
>
> Gegeben eine endliche Grundmenge G, eine Menge C
> von Teilmengen von G, und eine Zahl N<=|G|.
Jein, ein solches (minimales) N (von ggf. vielen) wird gesucht. Dabei
soll die triviale Lösung N=|G| immer existieren, sie interessiert aber
nicht weiters.
> Frage: Gibt es in C eine Menge mit N Elementen,
> deren Vereinigung N Elemente hat?
>
> Man denkt sofort an "set cover"[2], aber die Reduktionen funktionieren
> nicht so einfach (in keiner der beiden Richtungen) wegen der genauen
> Festlegung auf N.
Danke für das Stichwort, mir fehlen weitgehend die passenden
mathematischen Begriffe zu meinem Problem. Ich rate mal, daß "set" die
englische Bezeichnung für eine mathematische "Menge" ist?
> Überhaupt ist die Fragestellung ..eigenwillig, z.B.:
>
> G={1,2,3,4} und C={ {1} , {2} , {1,3,4} , {2,3,4} }
>
> Für N=1 und N=2 geht's, für N=3 nicht, für N=4 doch wieder. Komisch.
Die Be-/Verwertung der Ergebnisse hängt vom konkreten Problem ab. Beim
Sudoku könnten sofort die Felder für die Elemente 1 und 2 bestimmt
werden, diese Elemente aus der Grundmenge entfernt und in der Restmenge
weitergesucht werden.
Bei einem Gleichungssstem könnte man aus den gefundenen N Gleichungen
die N Variablen bestimmen, und (wie im Sudoku) diese Werte in die
restlichen Gleichungen einsetzen, und dann darin weiterrechnen.
> Außerdem: was hat das mit "linearer" Abhängigkeit zu tun?
Das war ein Ausrutscher zum Beispiel des Gleichungssystems, bei dem N
Gleichungen linear unabhängig sein müssen, damit ein System mit N
Variablen lösbar bleibt. Ich dachte auch an eine Basis eines
Vektorraums, aus N linear unabhängigen Vektoren, aber auch das hat mit
dem Problem nichts zu tun.
> Nein, ich will's gar nicht wissen.
Jau, vergessen wir das.
>
> [1] Zumindest Detlef und ich.
>
> [2] <http://www.csc.kth.se/~viggo/wwwcompendium/node142.html>
Sehr beeindruckend, vielleicht steht dort irgendwo schon eine Lösung
(Verfahren) für mein Problem. Nur fehlen mir dazu die mathematischen
Definitionen der ganzen Begriffe :-(
DoDi
[toc] | [prev] | [next] | [standalone]
| From | Carlo XYZ <carloxyz@invalid.invalid> |
|---|---|
| Date | 2017-11-26 16:17 +0100 |
| Message-ID | <oveltr$meg$1@dont-email.me> |
| In reply to | #71647 |
Am 26.11.17 um 13:56 schrieb Hans-Peter Diettrich:
> Am 26.11.2017 um 10:19 schrieb Carlo XYZ:
>> Gegeben eine endliche Grundmenge G, eine Menge C
>> von Teilmengen von G, und eine Zahl N<=|G|.
>
> Jein, ein solches (minimales) N (von ggf. vielen) wird gesucht. Dabei
> soll die triviale Lösung N=|G| immer existieren, sie interessiert aber
> nicht weiters.
>
>> Frage: Gibt es in C eine Menge mit N Elementen,
>> deren Vereinigung N Elemente hat?
Mit "minimal" änderst du das Problem.
N gehört zum Problem, also ist "N=|G|" keine "Lösung".
Wenn du mit "trivialer Lösung" meinst, dass es zu N=|G|
immer eine Lösung gibt, ist Folgendes ein Gegenbeispiel:
G={1}, C={ }, N=1;
aber auch G={1,2,3}, C={ {1}, {2}, {1,2} }, N=3.
Ich schlage vor, dass du dir erst einmal darüber
klar wirst, was eigentlich dein Problem ist.
[toc] | [prev] | [next] | [standalone]
| From | qdl@gmx.net (H0Iger SchuIz) |
|---|---|
| Date | 2017-11-26 17:01 +0100 |
| Message-ID | <1ng3utt.1mgm9i7542ytzN%qdl@gmx.net> |
| In reply to | #71647 |
Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote: > Jein, ein solches (minimales) N (von ggf. vielen) wird gesucht. Suchst du einen (minimalen) Buchstaben oder eine (minimale) natürliche Zahl N? hs
[toc] | [prev] | [next] | [standalone]
| From | Hans-Peter Diettrich <DrDiettrich1@aol.com> |
|---|---|
| Date | 2017-11-26 20:01 +0100 |
| Message-ID | <f80hd0FsrmdU1@mid.individual.net> |
| In reply to | #71650 |
Am 26.11.2017 um 17:01 schrieb H0Iger SchuIz: > Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote: > >> Jein, ein solches (minimales) N (von ggf. vielen) wird gesucht. > > Suchst du einen (minimalen) Buchstaben oder eine (minimale) natürliche > Zahl N? Eine Suche erscheint mir am effizientesten, wenn zuerst nach Mengen mit möglichst wenigen Elementen gesucht wird, also minimales N. Eigentlich wollte ich nur die triviale Lösung N=|G| ausschließen, die darf nur dann herauskommen, wenn sonst keine Lösung existiert. DoDi
[toc] | [prev] | [next] | [standalone]
| From | qdl@gmx.net (H0Iger SchuIz) |
|---|---|
| Date | 2017-11-26 20:11 +0100 |
| Message-ID | <1ng45e5.j3kywhqiyl4wN%qdl@gmx.net> |
| In reply to | #71658 |
Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote: > Am 26.11.2017 um 17:01 schrieb H0Iger SchuIz: > > Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote: > > > >> Jein, ein solches (minimales) N (von ggf. vielen) wird gesucht. > > > > Suchst du einen (minimalen) Buchstaben oder eine (minimale) natürliche > > Zahl N? > > Eine Suche erscheint mir am effizientesten, wenn zuerst nach Mengen mit > möglichst wenigen Elementen gesucht wird, also minimales N. Eigentlich > wollte ich nur die triviale Lösung N=|G| ausschließen, die darf nur dann > herauskommen, wenn sonst keine Lösung existiert. Offensichtlich hast du meine Frage nicht verstanden. Es ging mir um die blödsinnige Sprechweise vom "minimalen N". hs
[toc] | [prev] | [next] | [standalone]
| From | Andreas Leitgeb <avl@logic.at> |
|---|---|
| Date | 2017-11-26 21:13 +0000 |
| Message-ID | <slrnp1mbka.5mg.avl@logic.at> |
| In reply to | #71658 |
Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote: > Am 26.11.2017 um 17:01 schrieb H0Iger SchuIz: >> Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote: >>> Jein, ein solches (minimales) N (von ggf. vielen) wird gesucht. >> Suchst du einen (minimalen) Buchstaben oder eine (minimale) natürliche >> Zahl N? > Eine Suche erscheint mir am effizientesten, wenn zuerst nach Mengen mit > möglichst wenigen Elementen gesucht wird, also minimales N. Eigentlich > wollte ich nur die triviale Lösung N=|G| ausschließen, die darf nur dann > herauskommen, wenn sonst keine Lösung existiert. Das größere Problem ist da wohl, dass N=|G| selbst nicht zwingend überhaupt eine Lösung ist - es sei denn, du hättest uns bei der Problembeschreibung relevantes vorenthalten (oder wir haben es bloß überlesen).
[toc] | [prev] | [next] | [standalone]
| From | Carlo XYZ <carloxyz@invalid.invalid> |
|---|---|
| Date | 2017-11-27 07:41 +0100 |
| Message-ID | <ovgc2a$ubk$1@dont-email.me> |
| In reply to | #71658 |
Am 26.11.17 um 20:01 schrieb Hans-Peter Diettrich: > wollte ich nur die triviale Lösung N=|G| ausschließen, die darf nur dann > herauskommen, wenn sonst keine Lösung existiert. Wie gesagt, ist das keine "Lösung", sondern ein Spezialfall, in dem es nicht unbedingt eine Lösung gibt - zumindest in der von mir improvisierten Formalisierung deines Problems.
[toc] | [prev] | [next] | [standalone]
| From | Martin Vaeth <martin@mvath.de> |
|---|---|
| Date | 2017-11-27 08:43 +0000 |
| Message-ID | <ovgj89$ivg$1@gioia.aioe.org> |
| In reply to | #71644 |
Carlo XYZ <carloxyz@invalid.invalid> wrote:
>
> Gegeben eine endliche Grundmenge G, eine Menge C
> von Teilmengen von G, und eine Zahl N<=|G|.
> Frage: Gibt es in C eine Menge mit N Elementen,
> deren Vereinigung N Elemente hat?
Du scheinst im Folgetext zu meinen:
... deren Vereinigung _genau_ N Elemente hat.
Ich vermute aber, dass es so gemeint war, wie es dort steht:
... deren Vereinigung (mindestens) N Elemente hat.
Es würde mich extrem überraschen, wenn das nicht NP-vollständig wäre.
> Außerdem: was hat das mit "linearer" Abhängigkeit zu tun?
Wenn es so gemeint ist, wie es dort steht, würde ich vermuten:
Fasse die Grundmenge G als Basis eines K-Vektorraums oder R-Moduls auf,
und interpretiere die Teilmengen von G als Summe dieser Basiselemente;
setze also $C_0 = \{ a : a = \sum_{e\in A} e, A\in C \}$.
Dann ist eine N-elementige linear unabhängige Teilmenge von $C_0$ gesucht.
(Man muss vermutlich voraussetzen, dass K bzw. R die Charakteristik 0 hat).
Ich bezweifle allerdings, dass diese Interpretation das Problem wesentlich
vereinfacht. (Sonst wäre P=NP zu einfach zu zeigen...)
[toc] | [prev] | [next] | [standalone]
| From | Carlo XYZ <carloxyz@invalid.invalid> |
|---|---|
| Date | 2017-11-27 11:23 +0100 |
| Message-ID | <ovgp39$3re$1@dont-email.me> |
| In reply to | #71668 |
Am 27.11.17 um 09:43 schrieb Martin Vaeth: > Du scheinst im Folgetext zu meinen: > ... deren Vereinigung _genau_ N Elemente hat. Natürlich, weil der OP das so geschrieben hat. > Ich vermute aber, dass es so gemeint war, wie es dort steht: > ... deren Vereinigung (mindestens) N Elemente hat. Zitat OP: **Wie kann aus einer Menge von Mengen eine Teilmenge von N Mengen **gefunden werden, deren Vereinigungsmenge N Elemente hat? Da steht nichts von "mindestens". Wenn du das Problem änderst, kann es sehr gut sein, dass irgendein set cover darauf reduziert werden kann (oder umgekehrt). Aber ich spekuliere ungern, was der OP nun genau gemeint haben könnte.
[toc] | [prev] | [next] | [standalone]
| From | Hans-Peter Diettrich <DrDiettrich1@aol.com> |
|---|---|
| Date | 2017-11-27 21:40 +0100 |
| Message-ID | <f83bheFihi3U1@mid.individual.net> |
| In reply to | #71669 |
Am 27.11.2017 um 11:23 schrieb Carlo XYZ: > Am 27.11.17 um 09:43 schrieb Martin Vaeth: > Zitat OP: > > **Wie kann aus einer Menge von Mengen eine Teilmenge von N Mengen > **gefunden werden, deren Vereinigungsmenge N Elemente hat? > > Da steht nichts von "mindestens". > > Wenn du das Problem änderst, kann es sehr gut > sein, dass irgendein set cover darauf reduziert > werden kann (oder umgekehrt). > > Aber ich spekuliere ungern, was der OP nun genau > gemeint haben könnte. Ich verstehe die Rückfragen und Spekulationen nicht. Was ist denn an obiger Aufgabenstellung noch unklar? Wer schon mal Sudoku von Hand gelöst hat, der weiß auch wie obiger Algorithmus helfen kann, die/eine Lösung zu finden. DoDi
[toc] | [prev] | [next] | [standalone]
| From | Martin Vaeth <martin@mvath.de> |
|---|---|
| Date | 2017-12-01 19:56 +0000 |
| Message-ID | <ovsc52$158m$1@gioia.aioe.org> |
| In reply to | #71678 |
Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote: > > Ich verstehe die Rückfragen und Spekulationen nicht. Was ist denn an > obiger Aufgabenstellung noch unklar? Offensichtlich wurde sie schon auf mindestens 2 Arten verstanden, und bei der Rückfrage kam heraus, dass sie anscheinend noch irgendwie ganz anders gemeint war. > Wer schon mal Sudoku von Hand gelöst hat, der weiß auch wie obiger > Algorithmus helfen kann, die/eine Lösung zu finden. Wenn es Dir auf Sudoku ankommt, hättest Du das direkt nachfragen können: Es ist bekannt, dass Sudoku NP-vollständig ist. Es gibt 'zig Arten, Sudoku auf set-cover-ähnliche Probleme zurückzuführen; es ist vollkommen unklar, an welche Du gedacht hast. Wenn Du Sudoku darauf zurückführen kannst, hast Du damit dann schon nachgewiesen, dass Dein Problem mindestens NP-schwer ist...
[toc] | [prev] | [next] | [standalone]
| From | Hans-Peter Diettrich <DrDiettrich1@aol.com> |
|---|---|
| Date | 2017-12-02 09:36 +0100 |
| Message-ID | <f8f7f1Fajp0U1@mid.individual.net> |
| In reply to | #71697 |
Am 01.12.2017 um 20:56 schrieb Martin Vaeth: > Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote: >> >> Ich verstehe die Rückfragen und Spekulationen nicht. Was ist denn an >> obiger Aufgabenstellung noch unklar? > > Offensichtlich wurde sie schon auf mindestens 2 Arten verstanden, > und bei der Rückfrage kam heraus, dass sie anscheinend noch irgendwie > ganz anders gemeint war. Das verstehe ich nicht. Wenn jemand die Aufgabenstellung ändern möchte, dann hat das mit meiner Frage nichts mehr zu tun. >> Wer schon mal Sudoku von Hand gelöst hat, der weiß auch wie obiger >> Algorithmus helfen kann, die/eine Lösung zu finden. > > Wenn es Dir auf Sudoku ankommt, hättest Du das direkt nachfragen > können: Es ist bekannt, dass Sudoku NP-vollständig ist. Ich hatte Sudoku direkt als Beispiel angegeben. Aber das war für mich nur der Ausgangspunkt für die allgemeinere Frage. > Es gibt 'zig Arten, Sudoku auf set-cover-ähnliche Probleme > zurückzuführen; es ist vollkommen unklar, an welche Du gedacht hast. Da ich immer noch nicht weiß, was set-cover ist, kann ich dazu nichts sagen. DoDi
[toc] | [prev] | [next] | [standalone]
| From | Detlef Müller <lef-65@arcor.de> |
|---|---|
| Date | 2017-12-02 13:39 +0100 |
| Message-ID | <ovu6tm$7cs$1@gwaiyur.mb-net.net> |
| In reply to | #71700 |
Am 02.12.2017 um 09:36 schrieb Hans-Peter Diettrich:
> Am 01.12.2017 um 20:56 schrieb Martin Vaeth:
>> Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote:
>>> Ich verstehe die Rückfragen und Spekulationen nicht. Was ist denn an
>>> obiger Aufgabenstellung noch unklar?
Die Frage war so formuliert:
(Prosa):
"Wie kann aus einer Menge von Mengen eine Teilmenge von N Mengen
gefunden werden, deren Vereinigungsmenge N Elemente hat?"
das ominöse "wie" wurde später in
"Gibt es effiziente Algorithmen zur Bestimmung solcher Teilmengen"
spezifiziert.
Hier taucht eine "Menge von Mengen" auf, nennen wir sie M.
Über die Elemente m von M wird keinerlei Voraussetzung
gemacht. Sie können also beliebig komplex sein.
Auch über M wird keinerlei Voraussetzung gemacht.
Es taucht ein "N" auf, das anscheinend eine Kardinalität bezeichnet.
Man kann vermuten, dieses N soll eine natürliche Zahl sein - in
dieser Allgemeinheit könnte es sich aber auch um aleph_0 oder irgend
eine Mächtigkeit handeln.
Dann taucht eine "Teilmenge von N Mengen" auf, nennen wir sie T.
Zur Beschreibung (Prosa) fallen mir folgende Interpretationen
ein:
- Wir finden N Elemente m_i aus M, so daß für jedes der m_i die
Vereinigung die Kardinaltät N hat. Unser T soll Teilmenge all dieser
m_i sein.
- Wir finden eine Teilmenge T von M, die selbst die Kardinalität
N hat und deren Vereinigung ebenfalls die Kardinalität N hat.
(z.B. eine Abzählbar unendliche Teilmenge von M, deren Elemente
paarweise disjunkt, nicht leer und endlich sind). für den Fall
N=aleph_0.
Es scheint abstrus, das es einen endlichen Algorithmus geben sollte, um
aus völlig beliebigen, überabzählbaren Mengensystemen nach einem
(nicht völlig trivialen) Kriterium irgend etwas herausfinden kann
(etwa für N=aleph_0 überhaupt Aussagen über Vereinigungen von N
völlig beliebigen Mengen zu machen).
An der Stelle macht der Mathematiker, der mit Nicht-Mathematikern
ernsthaft kommunizieren möchte einen Reality-Check und fragt
sich:
Was wird ein Mensch mit dem berühmten "gesunden Menschenverstand"
wohl wirklich gemeint haben?
Mit meiner Antwort habe ich versucht, Dir entsprechende
Konkretisierungen zu entlocken, da ich recht sicher war, daß
ich abstruse Fälle verwendet haben, die Dich sensibilisieren
sollten dafür, was Du noch konkretisieren willst.
Carlo hat dies z.B. gemacht und die Problemstellung bereits für
Dich konkretisiert - auf die Gefahr hin, auch mal daneben zu
liegen.
Soll die Grundmenge G endlich sein?
Dann muß N eine natürliche Zahl sein etc.
Aus Deinen Antworten geht hervor, daß Die Vermutung, daß
Du eben _nicht_ das gemeint hast, was Du in dieser Allgemeinheit
aufgeschrieben hast, richtig war.
Deshalb verstehe ich nicht, warum Du die Rückfragen und
Spekulationen nicht verstehst.
[...]
> Das verstehe ich nicht. Wenn jemand die Aufgabenstellung ändern möchte,
> dann hat das mit meiner Frage nichts mehr zu tun.
Die ursprüngliche Aufgabenstellung war offensichtlich nicht, was
Du im Sinn hattest.
Versuch, sie einfach in der Allgemeinheit, die Dir wirklich vorschwebt
zu formulieren - das sollte sich recht schnell klären lassen.
>>> Wer schon mal Sudoku von Hand gelöst hat, der weiß auch wie obiger
>>> Algorithmus helfen kann, die/eine Lösung zu finden.
Mit der Konkreten Formulierung, was für einen Algorithmus Du suchst,
wäre das auch klarer - obwohl ich mich auch händisch an Sudokus
versucht habe, ist mir das nicht wirklich klar.
Irgendwann betrachtet man natürlich Mengen von Zahlen (möglichen
Lösungen) und will irgendwie die Kombinationen so hin bekommen,
daß {1,...,9} heraus kommt ...
>> Wenn es Dir auf Sudoku ankommt, hättest Du das direkt nachfragen
>> können: Es ist bekannt, dass Sudoku NP-vollständig ist.
Dafür bräuchte man eine Verallgemeinerung des Sudoku mit einem
Parameter, ansonsten ist es natürlich O(1).
Gruß,
Detlef
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de
[toc] | [prev] | [next] | [standalone]
Page 1 of 2 [1] 2 Next page →
Back to top | Article view | de.sci.mathematik
csiph-web