Entwurf und Analyse von Algorithmen

Trotz aller technologischer Fortschritte der vergangenen Jahrzehnte ist es immer wieder der Einsatz effizienter Algorithmen und Datenstrukturen, der das Lösen eines auf den ersten Blick aussichtslosen Problems ermöglicht und letztlich eine wirtschaftlich rentable Implementierung erlaubt. Eine Sammlung grundlegender Algorithmen und Datenstrukturen bildet die Sprache, in der diese Lösungen formuliert und kommuniziert werden. Eine solche wird in diesem Buch in mathematisch präziser Weise und mit lauffertigem Java-Code präsentiert. Um diesen Baukasten effektiv einsetzen zu können, ist das Verständnis der Stärken und Schwächen seiner Komponenten unabdingbar; dieses gewinnen wir aus der mathematischen Analyse der Algorithmen und der Diskussion der erzielten Ergebnisse - ein zentraler Aspekt dieses Buches. Doch nicht für alle Probleme gelingt eine Lösung aus bereits bekannten Bausteinen. Entwurf und Analyse von Algorithmen lässt seine Leserinnen und Leser die Entdeckung einiger der größten Errungenschaften der Algorithmik nacherleben und führt sie damit an die Lösungfindung für neue Probleme heran. Schließlich zeigt eine kurze, aber ebenso präzise Einführung in die Theorie der Komplexitätsklassen P und NP die (mutmaßlichen) Grenzen der effizienten Lösbarkeit auf. Der Inhalt Elementare Datenstrukturen - Das Wörterbuchproblem - Sortieren - Graph-Algorithmen - String-Algorithmen - Entwurfsmethoden für Algorithmen - Komplexitätstheorie - Entwurfsmethoden für schwere Optimierungsprobleme Die Autoren Prof. Dr. Markus Nebel hat den Lehrstuhl Algorithmen & Bioinformatik an der Universität Bielefeld inne. Er erforscht das Average-Case-Verhalten von Algorithmen sowie von Strukturparametern kombinatorischer Klassen, wie sie in der Molekularbiologie und Chemie auftreten. Ein weiterer Schwerpunkt seiner Arbeit ist die Entwicklung effizienter Algorithmen in der Bioinformatik sowie deren Umsetzungin Werkzeugen für Naturwissenschaftler. Dr. Sebastian Wild ist Postdoctoral Fellow an der University of Waterloo. Er forscht dort an speichereffizienten Datenstrukturen und der Analyse von Such- und Sortieralgorithmen. Seine Dissertation zum Average-Case-Verhalten von Mehrwege-Quicksort, betreut von Prof. Dr. Markus Nebel, erhielt den GI Dissertationspreis 2016, unter anderem für die didaktische Aufbereitung der Thematik.

Prof. Dr. Markus Nebel hat den Lehrstuhl Algorithmen & Bioinformatik an der Universität Bielefeld inne. Er erforscht das Average-Case-Verhalten von Algorithmen sowie von Strukturparametern kombinatorischer Klassen, wie sie in der Molekularbiologie und Chemie auftreten. Ein weiterer Schwerpunkt seiner Arbeit ist die Entwicklung effizienter Algorithmen in der Bioinformatik sowie deren Umsetzung in Werkzeugen für Naturwissenschaftler. Dr. Sebastian Wild ist Postdoctoral Fellow an der University of Waterloo. Er forscht dort an speichereffizienten Datenstrukturen und der Analyse von Such- und Sortieralgorithmen. Seine Dissertation zum Average-Case-Verhalten von Mehrwege-Quicksort, betreut von Prof. Dr. Markus Nebel, erhielt den GI Dissertationspreis 2016, unter anderem für die didaktische Aufbereitung der Thematik.

Elementare Datenstrukturen.- Das Wörterbuchproblem.- Sortieren.- Graph-Algorithmen.- String-Algorithmen.- Entwurfsmethoden für Algorithmen.- Komplexitätstheorie.- Entwurfsmethoden für schwere Optimierungsprobleme.