 Thema: Komplexität Erbteilproblem |
|
|
Hm, denke ich evtl. zu kompliziert ..., d. h. wenn das gesamte Erbe in zwei wertgleiche Teile aufgeteilt werden soll ... 2^n ...
|
|
| Thema: Komplexität Erbteilproblem |
|
|
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.
|
|
| Thema: Komplexität Erbteilproblem |
|
|
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!!
|
|
| Thema: ist das eine kontextfreie Grammatik? |
|
|
Hi, ich hoffe, mir kann jemand aus einer Zwickmühle helfen. Ich habe folgende Grammatik (abgekürzt):
T = {a,b}
P = {(S -> aSa | bSb | aa | bb | a | b)}
Nun soll ich nachweisen, dass die von dieser Grammatik erzeugte Sprache nicht mit einem Kellerautomaten erkannt werden kann. Nun ja, gemeint ist wohl ein deterministischer KA. Intuitiv ist mir das klar, da wenn ich nur von links nach rechts lesen kann, nicht erkenne, wann ich die Hälfte überschreite.
Nur ... wenn es keinen Kellerautomaten hierzu gibt, dürfte es keine kontextfreie Grammatik (Sprache) sein. Nach den Regeln, die ich kenne ist es aber eine kontextfreie Grammatik.
Was stimmt nun?
|
|
|
