Berechnungskomplexitäten von Varianten des Subset-Sum-Problems

Max Bannach

Abstract

In dieser Arbeit betrachten wir das Problem subsetsum, bei dem aus ei-
ner gegebenen Menge von natürlichen Zahlen eine Teilmenge bestimmt
werden soll, sodass die Elemente dieser Teilmenge in der Summe ei-
ne vorgegebene Zahl ergeben. Die Komplexität von subsetsum ist für
die Informatik interessant, denn aufgrund des generischen Aufbaus
von subsetsum lassen sich viele weitere Probleme darauf zurückfüh-
ren. In dieser Arbeit soll die Komplexität von mehreren Varianten von
subsetsum untersucht werden, denn obwohl fast alle Varianten des Pro-
blems in der üblichen binären Codierung NP-vollständig sind, haben
diese Probleme oft unterschiedliche Komplexitäten, wenn wir unäre
Kodierungen betrachten. In dieser Arbeit werden einige natürliche Va-
rianten dieses Problems diesbezüglich untersucht und entsprechende
Resultate präsentiert.
OriginalspracheDeutsch
QualifikationBachelor of Science
Gradverleihende Hochschule
Betreuer/-in / Berater/-in
  • Tantau, Till, Betreuer*in
  • Teichert, Hans-Martin , Betreuer*in, Externe Person
PublikationsstatusVeröffentlicht - 2012

Zitieren