Ingo Wegener Livres

Complexity theory is the theory of determining the necessary resources for the solution of algorithmic problems and, therefore, the limits of what is possible with the available resources. An understanding of these limits prevents the search for non-existing efficient algorithms. This textbook considers randomization as a key concept and emphasizes the interplay between theory and practice: New branches of complexity theory continue to arise in response to new algorithmic concepts, and its results - such as the theory of NP-completeness - have influenced the development of all areas of computer science. The topics selected have implications for concrete applications, and the significance of complexity theory for today's computer science is stressed throughout.

Die Theoretische Informatik ist älter als die Praktische und Angewandte Informatik und hat sich als wissenschaftliche Disziplin weiter entwickelt. Ihre Ergebnisse sind oft schwer zugänglich, da sie auf einem tiefen Fundament basieren. Stark verästelte Theorien neigen dazu, als Selbstzweck betrachtet zu werden. In dieser Einführung wird der Orientierung moderner Theorien an den Anwendungen besondere Beachtung geschenkt. Novalis wies bereits darauf hin, dass die Theorie häufig den Anwendungen vorauseilt. Die Anwendungen der Theoretischen Informatik sind nicht immer so direkt erkennbar wie in anderen Bereichen. Insbesondere negative Resultate haben klare Konsequenzen: Wenn bewiesen wird, dass bestimmte wünschenswerte Werkzeuge oder Algorithmen nicht existieren, sollte die Suche nach praktikablen Alternativen beginnen. Positive Resultate hingegen sind nicht automatisch anwendungsorientiert; viele Algorithmen mit exponentieller Laufzeit sind praktisch wertlos. Diese Einführung verfolgt eine konsequent algorithmenorientierte Sichtweise und strebt bei positiven Ergebnissen stets die Umsetzung in praktisch und theoretisch effiziente Algorithmen an. Dies stellt einen neuen Ansatz in der Theoretischen Informatik dar und berücksichtigt den didaktischen Hintergrund.

Die Komplexitätstheorie ist inzwischen eine ausgefeilte Theorie. Viele wichtige und nützliche Ergebnisse sind schwer vermittelbar, da der Weg zu Ergebnissen für konkrete Probleme lang und beschwerlich ist. Während die NP-Vollständigkeitstheorie die gesamte Informatik beeinflußt hat, werden die neueren Ergebnisse in der Ausbildung an den Rand gedrängt. Dieses Lehrbuch trifft eine Auswahl unter den Ergebnissen, so dass die Bedeutung der Komplexitätstheorie für eine moderne Informatik in den Mittelpunkt rückt.

Dieser Band enthält die Beiträge einer Ringvorlesung Highlights aus der Informatik an der Universität Dortmund, in der Wissenschaftler, die durch ihre Forschung und didaktischen Fähigkeiten ausgewiesen sind, Glanzlichter aus der neueren Informatikforschung aufbereiteten und sie so Studenten und interessierten Laien zugänglich gemacht haben. Dabei wird das ganze Spektrum von tiefliegenden theoretischen Ergebnissen über anwendungsorientierte Entwicklungen bis zur überraschenden Lösung altbekannter kombinatorischer Probleme behandelt. Die Autoren zeigen kenntnisreich und bisweilen humorvoll, wie aufregend aktuelle Forschung sein kann!

Der erfolgreiche Einsatz von Rechnern zur Problemlösung in vielen Lebensbereichen basiert auf technologischen Entwicklungen, die schnellere Rechner mit größerem Speicher und benutzerfreundlicheren Schnittstellen hervorgebracht haben, sowie auf effizienteren Algorithmen. Das Buch behandelt den Entwurf effizienter Algorithmen für grundlegende Probleme, die oft als Teilprobleme in komplexeren Kontexten auftreten. Während auf der Hardware-Ebene bereits mit hoher Parallelität gearbeitet wurde, ermöglicht die Zunahme an Prozessoren nun auch auf höherer Ebene paralleles Rechnen. Der Fokus liegt auf Algorithmen, die hinsichtlich paralleler Rechenzeit und Hardwaregröße (bei Hardwarelösungen) sowie paralleler Rechenzeit, Anzahl der Prozessoren und Speicherplatz (bei Softwarelösungen) effizient sind. Es werden effiziente Algorithmen für den Entwurf optimaler PLA's diskutiert, gefolgt von grundlegenden arithmetischen Funktionen wie Addition, Subtraktion, Multiplikation und Division sowie symmetrischen und Speicherzugriffsfunktionen, wobei hauptsächlich Hardwarelösungen betrachtet werden. Für Matrizenrechnungen, einfache Graphprobleme, Sortierprobleme und elementare Zahlentheorie werden effiziente Softwarelösungen präsentiert. Zudem werden allgemeine Methoden zur automatischen Parallelisierung sequentieller Algorithmen, Reduktionskonzepte zur Komplexitätsbewertung und effiziente Simulationen zwischen den Rechenmodellen behandelt.