Startseite
 
 
Fragen
 
Suchen
 
Über Uns
 
 
Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » pseudopolynomielle Laufzeit » Hallo Gast [Anmelden|Registrieren]
Letzter Beitrag | Erster ungelesener Beitrag Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen
Neues Thema erstellen Antwort erstellen
Zum Ende der Seite springen pseudopolynomielle Laufzeit
Autor
Beitrag « Vorheriges Thema | Nächstes Thema »
informatiker
Grünschnabel


Dabei seit: 11.08.2009
Beiträge: 5
pseudopolynomielle Laufzeit Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
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 verwirrt
12.08.2009 00:04 informatiker ist offline E-Mail an informatiker senden Beiträge von informatiker suchen Nehmen Sie informatiker in Ihre Freundesliste auf
Thomas Thomas ist männlich
Administrator


Dabei seit: 06.09.2006
Beiträge: 68
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
Gibt es spezielle Schritte bei der Wikipedia-Erklärung, die du nicht verstehst?
12.08.2009 12:27 Thomas ist offline E-Mail an Thomas senden Homepage von Thomas Beiträge von Thomas suchen Nehmen Sie Thomas in Ihre Freundesliste auf
informatiker
Grünschnabel


Dabei seit: 11.08.2009
Beiträge: 5
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
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.

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von informatiker: 12.08.2009 14:40.
12.08.2009 14:38 informatiker ist offline E-Mail an informatiker senden Beiträge von informatiker suchen Nehmen Sie informatiker in Ihre Freundesliste auf
Thomas Thomas ist männlich
Administrator


Dabei seit: 06.09.2006
Beiträge: 68
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
Polynomiell (http://de.wikipedia.org/wiki/Polynomialzeit) hast du verstanden?
12.08.2009 22:44 Thomas ist offline E-Mail an Thomas senden Homepage von Thomas Beiträge von Thomas suchen Nehmen Sie Thomas in Ihre Freundesliste auf
informatiker
Grünschnabel


Dabei seit: 11.08.2009
Beiträge: 5
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
Polynomielle und exponentielle Laufzeit sind bekannt.
13.08.2009 15:33 informatiker ist offline E-Mail an informatiker senden Beiträge von informatiker suchen Nehmen Sie informatiker in Ihre Freundesliste auf
Thomas Thomas ist männlich
Administrator


Dabei seit: 06.09.2006
Beiträge: 68
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
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.
14.08.2009 01:10 Thomas ist offline E-Mail an Thomas senden Homepage von Thomas Beiträge von Thomas suchen Nehmen Sie Thomas in Ihre Freundesliste auf
informatiker
Grünschnabel


Dabei seit: 11.08.2009
Beiträge: 5
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
Warum kodiert man dann nicht im unären?
Hätte man das Problem dadurch nicht gelöst?
14.08.2009 21:37 informatiker ist offline E-Mail an informatiker senden Beiträge von informatiker suchen Nehmen Sie informatiker in Ihre Freundesliste auf
informatiker
Grünschnabel


Dabei seit: 11.08.2009
Beiträge: 5
Auf diesen Beitrag antworten Zitatantwort auf diesen Beitrag erstellen Diesen Beitrag editieren/löschen Diesen Beitrag einem Moderator melden       Zum Anfang der Seite springen
Hat sich erledigt.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von informatiker: 16.08.2009 14:19.
15.08.2009 18:37 informatiker ist offline E-Mail an informatiker senden Beiträge von informatiker suchen Nehmen Sie informatiker in Ihre Freundesliste auf
Baumstruktur | Brettstruktur
Gehe zu:
Neues Thema erstellen Antwort erstellen
Informatiker Board » Themengebiete » Theoretische Informatik » pseudopolynomielle Laufzeit

© by Informatikerboard.de
Forensoftware: Burning Board, entwickelt von WoltLab GmbH

 
© 2005-2020 bei Informatikerboard.de | Archiv, alt, neueste | Kontakt | Jugendschutz | Nutzungsbedingungen