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?
Zur Webseite der AG Theoretische InformatikÜberblick über die Arbeitsgruppen im Bereich "Grundlagen der Informatik"


AG Theorie komplexer Systeme
Prof. Dr. Nicole Schweikardt
AG Theoretische Informatik
Prof. Dr. Georg Schnitger