Der Algorithmus von Howgrave-Graham und Joux zur Lösung von Rucksackproblemen

Ludwig, Michael

Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.18419/opus-2891

Langanzeige der Metadaten

DC Element	Wert	Sprache
dc.contributor.author	Ludwig, Michael	de
dc.date.accessioned	2012-08-13	de
dc.date.accessioned	2016-03-31T07:59:44Z	-
dc.date.available	2012-08-13	de
dc.date.available	2016-03-31T07:59:44Z	-
dc.date.issued	2012	de
dc.identifier.other	370887190	de
dc.identifier.uri	http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-76103	de
dc.identifier.uri	http://elib.uni-stuttgart.de/handle/11682/2908	-
dc.identifier.uri	http://dx.doi.org/10.18419/opus-2891	-
dc.description.abstract	In dieser Diplomarbeit werden Algorithmen für schwere Rucksackinstanzen (in diesem Fall Subset Sum) behandelt. Eine Instanz heißt schwer, wenn sie eine Dichtekennzahl nahe 1 hat. Die behandelten Algorithmen bauen aufeinander auf. Beginnend beim Horowitz-Sahni-Algorithmus wurde zunächst der Schroeppel-Shamir-Algorithmus und danach der Algorithmus von Howgrave-Graham und Joux hergeleitet. Letzterer hat einen Speicher-Zeit-Tradeoff, welcher in dieser Arbeit ausgebaut werden konnte. Die neuen Algorithmen verwenden außerdem eine Heuristik, deren Korrektheit ebenso bewiesen wurde.	de
dc.language.iso	de	de
dc.rights	info:eu-repo/semantics/openAccess	de
dc.subject.ddc	004	de
dc.title	Der Algorithmus von Howgrave-Graham und Joux zur Lösung von Rucksackproblemen	de
dc.title.alternative	The algorithm of Howgrave-Graham and Joux for solving knapsack problems	en
dc.type	masterThesis	de
ubs.fakultaet	Fakultät Informatik, Elektrotechnik und Informationstechnik	de
ubs.institut	Institut für Formale Methoden der Informatik	de
ubs.opusid	7610	de
ubs.publikation.typ	Abschlussarbeit (Diplom)	de
Enthalten in den Sammlungen:	05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Dateien zu dieser Ressource:

Datei	Beschreibung	Größe	Format
DIP_3259.pdf		722,96 kB	Adobe PDF	Öffnen/Anzeigen

Zur Kurzanzeige

Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.

Universität Stuttgart

OPUS - Online Publikationen der Universität Stuttgart