AG Theoretische Informatik (Prof. Dr. Georg Schnitger)

• Wie mächtig können Rechner sein?
• Gibt es algorithmische Probleme, die weder von heutigen noch von zukünftigen Rechnertechnologien gelöst werden können?
• Welche Probleme können im Hinblick auf Laufzeit und Speicherplatz effizient geknackt werden?
• Welche Probleme stellen große Herausforderungen dar?

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?

Ü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