Informatiker Board | Berechenbarkeits- und Komplexitätstheorie

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Komplexität Erbteilproblem

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Komplexität Erbteilproblem

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

_Rhodan_
Grünschnabel

Dabei seit: 03.02.2013
Beiträge: 4

Komplexität Erbteilproblem

Zitatantwort auf diesen Beitrag erstellen

Hi, ich sitze gerade über dem Erbteilproblem, d. h. ich möchte eine Menge von Münzen mit unterschiedlichem Wert gleichmäßig aufteilen. Das Problem an sich habe ich mit Hilfe von Backtracking gelöst - soweit gut.

Nun denke ich über die Komplexität dieser Suche nach einer Lösung bzw. nach allen Lösungen nach. Das Problem dürfte eine exponentielle Laufzeit haben - dies leite ich mir her, indem ich mir Bäume für 1, 2, 3, 4 ... Münzen aufzeichne und überlege, wie viele Zweige ich jeweils mit unterschiedlichen Lösungen erzeugen kann ...

... nur, wie kann ich das mathematisch herleiten ?

Kann mir da jemand helfen, oder hat etwas, wo ich dies genauer nachlesen kann?

Viele Dank im Voraus!!

27.01.2015 18:28

Nehmen Sie _Rhodan_ in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Wow, google findet nur 2 Treffer zu "Erbteilproblem". Ich habe davon auch noch nie etwas gehört.
Für [latex]m[/latex]

Münzen und [latex]e[/latex]

Erben hast du [latex]e^m[/latex]

Verteilungsmöglichkeiten.

__________________
Syntax Highlighting fürs Board (Link)

27.01.2015 19:19

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

_Rhodan_
Grünschnabel

Dabei seit: 03.02.2013
Beiträge: 4

Naja, das mit dem exponentiellen Zusammenhang habe ich ja auch schon, ab wie erkläre ich mir das mathematisch ...

Das Erbteilproblem funktioniert im Prinzip wie alle Verteilungsprobleme - evtl. gibt es für dieses spezielle Problem auch noch ähnliche Namen.

27.01.2015 20:17

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Was gibt es da noch herzuleiten, die Formel ist doch offensichtlich?
Eine Münze kann einem der [latex]e[/latex]

Erben gegeben werden, also [latex]e[/latex]

Möglichkeiten.
Da das für jede der Münzen unabhängig voneinander gilt, eben $[latex]e\cdot e\cdot\dots = e^m[/latex]$

__________________
Syntax Highlighting fürs Board (Link)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 27.01.2015 20:25.

27.01.2015 20:25

_Rhodan_
Grünschnabel

Dabei seit: 03.02.2013
Beiträge: 4

Hm, denke ich evtl. zu kompliziert ..., d. h. wenn das gesamte Erbe in zwei wertgleiche Teile aufgeteilt werden soll ... 2^n ...

27.01.2015 21:12

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Ja.
Stelle dir eine Binärzahl mit n Stellen vor - jede kann 0 oder 1 sein. Bei 0 kriegt die entsprechende Münze der eine Erbe, bei 1 der andere. Und wie viele Zahlen man mit einer solchen Binärzahl bilden kann, weißt du hoffentlich: 2^n. Damit hätten wir dann auch gleich eine nichtrekursive Methode, alle Möglichkeiten durchzugehen: einfach hochzählen und die einzelnen Bits auswerten.

__________________
Syntax Highlighting fürs Board (Link)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 27.01.2015 21:17.

27.01.2015 21:16

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

Ist es vielleicht eine spezielle Form dieses Problems?

http://de.wikipedia.org/wiki/Teilsummenproblem

ED

PS: Wenn ich mich recht entsinne beschreibt Bruce Schneier in Applied Cryptography ein Public key-Verfahren das auf der Komplexität dieses Problems basiert

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von ed209: 28.01.2015 22:41.

28.01.2015 22:40

Nehmen Sie ed209 in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Komplexität Erbteilproblem