Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > de.sci.mathematik > #71705

Re: Lineare Abhängigkeit?

From Martin Vaeth <martin@mvath.de>
Newsgroups de.sci.mathematik
Subject Re: Lineare Abhängigkeit?
Date 2017-12-03 11:05 +0000
Organization Aioe.org NNTP Server
Message-ID <p00lp5$6sr$1@gioia.aioe.org> (permalink)
References (3 earlier) <ovgj89$ivg$1@gioia.aioe.org> <ovgp39$3re$1@dont-email.me> <f83bheFihi3U1@mid.individual.net> <ovsc52$158m$1@gioia.aioe.org> <f8f7f1Fajp0U1@mid.individual.net>

Show all headers | View raw


Hans-Peter Diettrich <DrDiettrich1@aol.com> wrote:
> 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.

Niemand wollte irgendeine Aufgabenstellung ändern. Es wurde spekuliert,
was Du gemeint haben könntest, weil die Frage offensichtlich auf
verschiedene Arten plausibel interpretiert werden kann.

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

Du hast erwähnt, dass es damit etwas zu tun hat. Was genau -
ob Du Sudoku mit dem Problem lösen kannst oder umgekehrt
und wie - blieb unklar.
Nachdem Du jetzt aber nun spezifiziert hast, dass Du Sudoko
mit der Antwort lösen kannst (was ich als Reduktion in max.
polynomieller Zeit interpretiere), kann man Dir eben sogar die
Antwort geben, auch ohne zu klären, welches Problem genau Du
gemeint hast: Es muss mindestens NP-schwer sein.
Mit anderen Worten: Es ist kein Polynomialzeit-Algorithmus bekannt;
wesentlich effizienter als mit systematischem Durchprobieren geht
es in ungünstigen Fällen nach heutigem Wissensstand nicht.

> Da ich immer noch nicht weiß, was set-cover ist

Wikipedia u.a. existieren.
https://en.wikipedia.org/wiki/Set_cover_problem
Die deutsche Übersetzung enthält zwar viel weniger Informationen,
ist aber ebenfalls korrekt:
https://de.wikipedia.org/wiki/Mengenüberdeckungsproblem

Back to de.sci.mathematik | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

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

csiph-web