Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Laufzeit eines Algorithmus polynomiell bestimmen

Laufzeit eines Algorithmus polynomiell bestimmen

Universität / Fachhochschule

Polynome

Tags: Exponentielles Wachstum, Laufzeitkomplexität, polynom

av1406 aktiv_icon

22:38 Uhr, 08.02.2012

Hallo zusammen,

ich bin eigentlich ein Informatikstudent und bin auf die Hilfe von euch Mathematikern nun angewiesen und hoffe dass ich hier die entpsrechende Hilfe finden kann.

Vlt. sollte ich nebenbei erwähnen, dass ich auf das Forum durchs googlen gestoßen bin. Sucheingabe: "Matheforum"

Nun zu der Problemstellung:

Gegeben sind $n$ Mengen, jede Menge hat $m_{i}$ Elemente. Es gibt einen Algorithmus bzw. für die Mathematikwelt eine Funktion, die alle Kombinationen von den vorhandenen Elementen ermittelt.

Das heißt, beispielsweise sind folgende zwei Mengen gegeben:

$M 1 = {a 1, b 1} \Rightarrow | M 1 | = 2$
$M 2 = {a 2, b 2, c 2} \Rightarrow | M 2 | = 3$

Algorithmus $A : A (M 1, M 2) = {{a 1, a 2}, {a 1, b 2}, {a 1, c 2}, {b 1, a 2}, {b 1, b 2}, {b 1, c 2}}$
Mit anderen Worten ist die Laufzeit des Algorithmus $2 \times 3 = | M 1 | \times | M 2 |$

Nun bleibt die Frage, ob der Aufwand bzw. die Laufzeit dieses Algorithmus exponentiell oder polynomiell ist?

Man hätte auch 3 Elemente in der Menge $M 1$ haben können, dann wäre die Laufzeit: $3 \times 3 = 3^{2}$ (exponentiell?)

Formal würde das Ganze wahrscheinlich so aussehen: $\prod_{i = 1}^{n} | M_{i} |$

Wenn die Laufzeit der o.g. Formel polynomial ist, wie kann ich das beweisen bzw. zeigen? welches Polynom könnte diese Laufzeit definieren? und Wenn es exponentiell ist, wie kann ich das zeigen?

Danke im Voraus,

A.V.

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Polynomfunktionen / ganzrationale Funktionen - Einführung

dapso aktiv_icon

09:25 Uhr, 09.02.2012

Hallo.
Ich nehme jetzt mal an, dass du das kartesische Produkt von

n

Mengen bestimmen möchtest, also alle

n

-Tupel, wobei jedes Element aus einer der der

n

Mengen kommt. Falls jetzt noch

n - 1

Tupel usw zugelassen sind, gilt die Begründung (mit einer weiteren Abschätzung) ebenso.
Beim kartesischen Produkt gibt es

\prod_{i = 1}^{n} ∣ M_{i} ∣

Möglichkeiten. Sei mal

t := min {∣ M_{i} ∣ ∣ i \in {1, . . ., n} \land ∣ M_{i} ∣ \neq 1}

. Dann gilt:

\prod_{i = 1}^{n} ∣ M_{i} ∣ \geq \prod_{i = 1}^{n} t = t^{n}

. Das sieht sehr exponentiell aus.
Sollten

k

Mengen die Mächtigkeit 1 haben, so kann man das abwandeln zu

\prod_{i = 1}^{n} ∣ M_{i} ∣ = \prod_{i = 1}^{n - k} ∣ M_{i} ∣ \geq t^{n - k}

, was auch exponentiell ist.

av1406 aktiv_icon

10:30 Uhr, 09.02.2012

Vielen Dank für deine Antwort.

Die Theoretiker bzw. die Mathematiker versuchen immer einen Weg zu finden um die exponentielle Schreibweise für die Problemstellung zu finden. In diesem Fall hast du den Trick mit dem min verwendet. Jedoch frag ich mich, ob es genügt das ganze so umzuformulieren um irgendwo dann den exponenten zu bekommen und somit zu zeigen dass die laufzeit exponentiell ist?

hätte man an der stelle 4 mengen mit mit 3,6,2 und 8 elementen. dann hätten wir 3x6x2x8 möglichkeiten. das kann man ja nicht exponentiell aufschreiben. hätte die erste menge auch 6 elemente, dann wärs möglich mit 6^2x2x8

es ist ja so, dass der algorithmus, der innerhalb dieser laufzeit terminiert, definitiv eine kürzere laufzeit hat, als einer, der die potenzmenge von einer menge bestimmt. die laufzeit des 2. algorithmus ist definitiv 2^n. und für jedes weitere element was der menge M hinzugefügt wird, wächst das n um genau 1. Das Kartesische Produkt hingegen wächst viel langsamer, und für einen praxisorientierten informatiker wie mich, sieht das auch nciht nach einem exponentiellen "problem" aus. denn wenn es so wäre, dann müsste ich zeigen, dass dieses problem auf ein bekanntes problem (wie. z.b. das SAT-Problem) abgebildet werden kann, und so mit NP-vollständig ist.

Es ist für mich schon weichtig, das vorliegende problem richtig zu klassifizieren, um dann mit den bereits bekannten methoden für diese klasse von problemen, versuchen das problem zu "lösen".

dapso aktiv_icon

10:47 Uhr, 09.02.2012

Also fuer mich ist die Anzahl der Mengen die Problemgroesse. Ich kann dann ja jedes Problem nach unten abschaetzen, indem ich die Maechtigkeit der Mengen die mehr als zwei Elemente habe auf 2 setzen. Damit ergeben sich dann

2^{n}

Schritte. Fuege ich jetzt eine weiter Menge hinzu, erhoeht sich der Exponent um 1 also

2^{n + 1}

Schritte. Die Anzahl der Schritte hat sich also verdoppelt.

av1406 aktiv_icon

11:05 Uhr, 09.02.2012

vorausgesetzt diese mengen haben alle die gleiche anzahl an elementen...

stell dir vor, es sind 40 Mengen vorgegeben, darunter weisen nur 2 mengen die gleiche anzahl an elementen auf, und 38 haben unterschiedliche größen.

natürlich kann man die zwei mengen zusammenführen und exponentiell aufschreiben, aber würdest du wegen den zwei mengen dann behaupten, der algorithmus hat einen exponentiellen aufwand? weisst du was ich meine?

dapso aktiv_icon

11:13 Uhr, 09.02.2012

Ich geh ueber eine Abschaetzung. Ich schau mir einfach ein Problem an, dass weniger Schritte braucht als mein altes Problem. Das schaffe ich, indem ich Elemente weglasse. Von diesem vereinfachten Problem kann ich aber leicht die Anzahl der Schritte bestimmen. Da dieses Problem aber bereits eine exponentielle Laufzeit hat, hat das urspruengliche Problem auch exponentielle Laufzeit. Da sind die genauen Maechtigkeiten der einzelnen Mengen nicht so wichtig.

av1406 aktiv_icon

12:06 Uhr, 09.02.2012

danke für diese aufklärung, jetzt hab ich es geschnallt!!!

hagman aktiv_icon

18:07 Uhr, 09.02.2012

Es kommt alles darauf an, was exponentiell bzw. polynomiell in was sein soll.

Es ist einfach einen Algorithmus zu schreiben, der das kartesische Produkt in einer Zeit proportional zur Ausgabelänge errechnet, also in linearer Abhängigkeit von der Ausgabe.

Wenn man zu gegebenem

n

das Tupel

(| M_{1} |, ..., | M_{n} |)

als Problemgöße angibt, dann ist idie Laufzeit ebenfalls ein Polynom hierin (nämlich das Polynom

\prod x_{i})

Die gegebene Zahl

n

kann man keinesfalls als (einzige) unabhängige nehmen, da schon mit

n = 2

unbeschränkt große Ausgaben und Laufzeiten denkbar

sin,

wenn die Mengen nur groß genug gewählt werden.

Üblicherweise bezieht man sich ja auch auf die gesamte Eingabe als unabhöngige Größe.
Hier würde man sinnvollerweise die Eingabe wie folgt kodieren:
Für jedes Element von

M_{1}

ein entsprechendes Symbol, dann ein Trennzwichen, dann für jedes Element von

M_{1}

das entsprechende Symbol, dann ein Trennzeichen,

...,

schließlich ein Endezeichen.
Dadurch hätte die Eingabe eine Länge von

N := n + 1 + \sum | M_{i} |

.
Zu gegebenem

N

könnte die Eingabe dann durchaus bestehen aus:

n = [\frac{N - 1}{3}]

sowie

n

Mengen mit je zwei Elementen (ggf. ein oder zwei hiervon sogar mit drei Elementen).
Die Ausgabe umfasst dann midestens eni Symbol für jedes der mindestens

2^{n} \approx {(\sqrt[3]{2})}^{N}

Elemente des Kreuzproduktes, erfordert also zum bloßen Hinschreiben mindestens exponentielle Zeit.

972131

971999

	Status: nicht eingeloggt	Noch nicht registriert?