AG Theoretische Informatik (Prof. Dr. Georg Schnitger)

Ein Beispiel eines schwierigen Problems ist das Rucksackproblem:
In einen Rucksack sind Objekte mit unterschiedlichen Gewichten und unterschiedlichen Werten einzupacken. Leider können wir im Rucksack nur Objekte tragen, deren Gesamtgewicht die Kapazität des Rucksacks nicht übersteigt. Welche Objekte sollten wir auswählen, so dass die Kapazität nicht überschritten wird, der Wert der eingepackten Objekte aber größtmöglich ist?

Leider ist bis heute nicht bekannt, ob das Rucksackproblem effizient lösbar ist.
Aber viele Indizien deuten daraufhin, dass eine effiziente Lösung nicht gelingen wird.

Aber was ist dann zu tun? Können wir zumindest eine "fast-optimale" Bepackung bestimmen?

Zur Webseite der AG Theoretische Informatik

Überblick über die Arbeitsgruppen im Bereich "Grundlagen der Informatik"

AG Algorithm Engineering

Prof. Dr. Ulrich Meyer

AG Theorie komplexer Systeme

Prof. Dr. Nicole Schweikardt

AG Theoretische Informatik

Prof. Dr. Georg Schnitger

AG Theorie der Informatik

Prof. Dr. Isolde Adler