Bibliograph. Daten | Ludwig, Michael: Der Algorithmus von Howgrave-Graham und Joux zur Lösung von Rucksackproblemen. Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Diplomarbeit Nr. 26 (2012). 67 Seiten, deutsch.
|
Kurzfassung | 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.
|
Volltext und andere Links | Volltext
|
Abteilung(en) | Universität Stuttgart, Institut für Formale Methoden der Informatik, Formale Konzepte
|
Betreuer | Diekert, Prof. Volker |
Eingabedatum | 4. November 2019 |
---|