Skip to main content
main-content

Über dieses Buch

Effiziente Algorithmen und Datenstrukturen haben sich in den letzten Jahrzehnten selbst bei der Lösung aussichtslos erscheinender praktischer und theoretischer Probleme bewährt. Dieses Buch führt in die Algorithmik mit Java ein und präsentiert dafür eine Sammlung grundlegender Algorithmen und Datenstrukturen – mathematisch präzise und mit lauffertigem Java-Code.

Die Autoren entwickeln die Ideen iterativ, so dass Leserinnen und Lesern die einzelnen Schritte von der naiven Lösung bis zum fertigen Lehrbuchalgorithmus nachvollziehen können. Einzelne Algorithmen werden hinsichtlich ihrer Stärken und Schwächen und der erzielten Ergebnisse diskutiert. Dadurch lernen Nutzer, die im Buch vorgestellten Elemente des Baukastens effektiv einzusetzen. Zahlreiche Beispiele und Abbildungen sowie 100 vertiefenden Übungsaufgaben unterstützen sie dabei.

Nicht für alle Probleme kann eine Lösung aus bereits bekannten Bausteinen entwickelt werden. Wie lassen sich mithilfe der Algorithmik dennoch Lösungen finden? Die Autoren lassen ihre Leser die Entwicklung der Algorithmik miterleben und leiten aus den Beispielen allgemeine Entwurfsmethoden ab, so dass Studierende und andere Leser lernen, wie sich auch für neue Probleme Lösungen finden lassen. Eine kurze, präzise Einführung in die Theorie der Komplexitätsklassen P und NP zeigt darüber hinaus die Grenzen der effizienten Lösbarkeit und stellt gängige Auswege für die praktische Lösung NP-harter Probleme vor.

Neben elementaren Datenstrukturen, Entwurfsmethoden, Suchbäumen sowie Sortier-, Graph- und String-Algorithmen werden auch Themen wie Approximation, randomisierte Algorithmen oder das Lineare Programmieren kurz angerissen, um einen Ausblick darauf zu geben, was die Algorithmik darüber hinaus noch leisten kann.

Das fachlich ebenso wie didaktisch fundierte Buch erscheint in der Reihe der „Studienbücher Informatik“ und begleitet Studierende in Vorlesungen zu Datenstrukturen und Algorithmen. Es unterstützt sie außerdem bei der gezielten Prüfungsvorbereitung.

Inhaltsverzeichnis

Frontmatter

Kapitel 1. Einleitung

Ein Computer bedarf der Programmierung, um sinnvoll eingesetzt werden zu können. Möchte man ihn zur Lösung bestimmter Probleme verwenden, wie etwa das Sortieren von Daten oder die Multiplikation von Matrizen, so muss die Programmierung eine Vorschrift beschreiben, die festlegt, in welcher Reihenfolge der Computer welche Aktionen durchzuführen hat, damit letztlich die gesuchte Lösung erzeugt wird. Dabei ist es unsinnig, die Vorschrift für eine einzige Eingabe maßzuschneidern.

Markus Nebel, Sebastian Wild

Kapitel 2. Elementare Datenstrukturen

Wie wir im vorherigen Kapitel gesehen haben, unterscheiden wir zwischen einem Abstrakten Datentyp und seiner Implementierung. In diesem Kapitel werden wir einige fundamentale Abstrakte Datentypen kennenlernen und verschiedene Möglichkeiten der Implementierung beleuchten. Ziel dabei ist, die Vor- und Nachteile der jeweiligen Implementierung zu erkennen.

Markus Nebel, Sebastian Wild

Kapitel 3. Das Wörterbuchproblem

In diesem Kapitel befassen wir uns mit der Suche nach bereits gespeicherten Daten. Hierfür nehmen wir an, dass jeder Datensatz (jedes Element der Menge gespeicherter Daten) durch einen sog. Schlüssel eindeutig identifiziert wird. In der Anwendung kann dies z.B. die Matrikelnummer sein, die einen Studenten unter allen anderen eindeutig identifiziert.

Markus Nebel, Sebastian Wild

Kapitel 4. Sortieren

In diesem Kapitel wollen wir uns einem anderen Standardproblem der Informatik zuwenden, dem Sortieren. Dabei geht es darum, eine Menge von Daten, deren Elemente in der Regel eindeutig über einen Schlüssel identifiziert werden, in die bzgl. des Schlüssels aufsteigend sortierte Anordnung zu bringen.

Markus Nebel, Sebastian Wild

Kapitel 5. Graph-Algorithmen

Ein Graph-Algorithmus ist ein Algorithmus, der auf einem Graphen operiert. Da Graphen für die Modellierung der unterschiedlichsten Dinge und Zusammenhänge eingesetzt werden, ist auch die Anzahl unterschiedlicher Graph-Algorithmen immens. Wir haben diese Vielfalt bei unseren formalen Definitionen von Graphen in Abschnitt 2.4 schon zu spüren bekommen: Graphen haben je nach Anwendung gerichtete oder ungerichtete Kanten, die Kanten können Gewichte tragen oder ungewichtet sein und Mehrfachkanten und Self-Loops sind i.d.R. nicht erlaubt, manchmal aber doch erwünscht.

Markus Nebel, Sebastian Wild

Kapitel 6. String-Algorithmen

Die Modellierung von Objekten als Wörter (Strings) ist in der Informatik allgegenwärtig; durch das wachsende Interesse an der Bioinformatik hat sie in jüngerer Zeit verstärkt Aufmerksamkeit erhalten. Wir studieren deshalb in diesem Kapitel grundlegende Algorithmen und Datenstrukturen zur Verarbeitung von Wörtern. Dazu zählen Verfahren zur exakten Suche von Wörtern in Texten genauso wie Methoden zur Bestimmung von Wiederholungen in einem Wort.

Markus Nebel, Sebastian Wild

Kapitel 7. Entwurfsmethoden für Algorithmen

Jetzt, da wir eine ganze Reihe konkreter Algorithmen besprochen haben, ist es an der Zeit, nach Gemeinsamkeiten zu suchen, um zu sehen, ob es allgemeine Techniken, Tricks und Methoden gibt, die beim Algorithmenentwurf immer wieder zum Erfolg geführt haben, und die wir auf neue Probleme anwenden können. Tatsächlich haben Informatiker über die Zeit eine ganze Reihe solcher Methoden herausgearbeitet, die wir in diesem Kapitel besprechen.

Markus Nebel, Sebastian Wild

Kapitel 8. Komplexitätstheorie

Bisher haben wir uns ausschließlich mit Problemen beschäftigt, für die eine algorithmische Lösung existierte, die mit einer in der Eingabegröße polynomiellen Laufzeit auskommt.

Markus Nebel, Sebastian Wild

Kapitel 9. Entwurfsmethoden für schwere Optimierungsprobleme

Im vorherigen Abschnitt haben wir Entscheidungsprobleme in Probleme formaler Sprachen transformiert, indem wir L ⊆ Σ* als die Sprache all jener codierten Instanzen des Problems definierten, für die das Entscheidungsproblem das Ergebnis Ja liefert. In diesem Kapitel wollen wir unseren Blickwinkel erweitern und (ähnlich wie in Abschnitt 7.6 zur linearen Programmierung) Optimierungsprobleme untersuchen.

Markus Nebel, Sebastian Wild

Backmatter

Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise