---

Geschrieben von informatiker am 12.08.2009 um 00:04:

  pseudopolynomielle Laufzeit

Hallo
Habe mich mit dem Rucksackproblem beschäftigt.
Nun verstehe ich nicht, warum der Algorithmus pseudopolynomielle Laufzeit besitzt. Dieser Begriff ist mir neu. Die Erklärung bei Wikipedia verstehe ich nicht. Kann das bitte evtl. jemand erklären? Ich zermater mir echt das Hirn

---

Geschrieben von Thomas am 12.08.2009 um 12:27:

 

Gibt es spezielle Schritte bei der Wikipedia-Erklärung, die du nicht verstehst?

---

Geschrieben von informatiker am 12.08.2009 um 14:38:

 

Der Beispiel-Algorithmus zur Bestimmung von Primzahlen (siehe http://de.wikipedia.org/wiki/Pseudopolynomiell) hat eine Laufzeit von n. Dann wird gesagt, dass die Eingabelänge eine Rolle spielt. Nimmt man die Binärdarstellung von Zahlen, benötigt man ca. log(n) Bits für eine Zahl n. Warum kommt man auf eine exponentielle Laufzeit? Was hat das eine (lineare Laufzeit n) mit dem anderen (Logarithmus) zu tun? Ist die algorithmische Berechnung des Logarithmus gemeint? Dieser hat ja exponentielle Laufzeit, wenn man eine Potenzreihe zugrunde legt.

---

Geschrieben von Thomas am 12.08.2009 um 22:44:

 

Polynomiell (http://de.wikipedia.org/wiki/Polynomialzeit) hast du verstanden?

---

Geschrieben von informatiker am 13.08.2009 um 15:33:

 

Polynomielle und exponentielle Laufzeit sind bekannt.

---

Geschrieben von Thomas am 14.08.2009 um 01:10:

 

Der Knackpunkt liegt im Unterschied zwischen Länge und Wert bei unterschiedlichen Kodierungen, nur bei der unären Kodierung fällt dies zusammen und der pseudopolynomielle wird zum polynomiellen Fall.

---

Geschrieben von informatiker am 14.08.2009 um 21:37:

 

Warum kodiert man dann nicht im unären?
Hätte man das Problem dadurch nicht gelöst?

---

Geschrieben von informatiker am 15.08.2009 um 18:37:

 

Hat sich erledigt.