Algorithmen und Datenstrukturen

Grundlagen und probabilistische Methoden für den Entwurf und die Analyse

verfasst von: Prof. Dr. Helmut Knebl

Verlag: Springer Fachmedien Wiesbaden

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

Lernen Sie in diesem Buch mehr über Algorithmen und Datenstrukturen

In diesem Lehrbuch werden Algorithmen und Datenstrukturen exakt aber auch anschaulich und nachvollziehbar vermittelt, denn Algorithmen sind heute allgegenwärtig und vielfältig. Sie sind Gegenstand intensiver Forschung und zählen zu den fundamentalen Konzepten der Informatik.

Dieses Buch über Algorithmen und Datenstrukturen ist aus Vorlesungen für Studierende der Informatik sowie der Medien- und Wirtschaftsinformatik an der Technischen Hochschule Nürnberg entstanden. Die grundlegenden Themen werden in den Bachelorkursen behandelt. Fortgeschrittene Teile, wie zum Beispiel die probabilistischen Algorithmen, stammen dagegen aus Masterkursen.

Der Inhalt des Werks im Überblick

Im ersten Kapitel seines Buchs über Algorithmen und Datenstrukturen führt Knebl relevante Grundlagen und Designprinzipien für Algorithmen ein.Die anschließenden Kapitel 2 – 6 sind nach Problembereichen organisiert: Sortieren und Suchen (2), Hashverfahren (3), Bäume zur Speicherung von Daten und zur Datenkomprimierung (4), fundamentale Graphenalgorithmen, wie Tiefen- und Breitensuche und Anwendungen davon (5), die Berechnung von minimalen aufspannenden Bäumen und von kürzesten Wegen in gewichteten Graphen als auch die Lösung des Flussproblems in Netzwerken (6).

Probabilistische Methoden sind grundlegend für einfache sowie effiziente Algorithmen und Datenstrukturen. Deshalb wird in jedem Kapitel dieses Buchs mindestens ein Problem mit einem probabilistischen Algorithmus gelöst. Die notwendigen mathematischen Grundlagen werden im ersten Kapitel sowie im Anhang entwickelt. Lösungen zu den zahlreichen Übungsaufgaben stehen Ihnen bequem zum Download bereit.

Inhaltsverzeichnis

Frontmatter

Kapitel 1. Einleitung

Zusammenfassung

Im ersten Kapitel diskutieren wir Grundlagen. Differenzengleichungen ermöglichen präzise Aussagen zu den Laufzeiten von Algorithmen. Als erste Anwendung erhalten wir eine exakte Version des Mastertheorems und einen Algorithmus zur Berechnung der Fibonacci-Zahlen. Anschließend studieren wir populäre Algorithmen, um gängige Designprinzipien für die Entwicklung von Algorithmen zu erklären. Eine Einführung in probabilistische Algorithmen rundet das Kapitel ab.

Helmut Knebl

Kapitel 2. Sortieren und Suchen

Zusammenfassung

Die Sortiermethoden Quicksort und Heapsort, binäre Suche und die Suche nach dem k–kleinsten Element sind Gegenstand von Kapitel 2. Besonderer Wert wird auf die Analyse der Laufzeit der Algorithmen gelegt. Es werden explizite Formeln oder präzise Abschätzungen für die Laufzeiten der betrachteten Algorithmen entwickelt.

Helmut Knebl

Kapitel 3. Hashverfahren

Zusammenfassung

Hashfunktionen, insbesondere universelle Familien von Hashfunktionen, Verfahren zur Behandlung von Kollisionen und eine detaillierte Analyse von Hashverfahren studieren wir in Kapitel 3. Die für die Analyse notwendigen Grundlagen aus der Wahrscheinlichkeitsrechnung sind im Anhang zusammengefasst. Bei Hashverfahren finden wir ein gespeichertes Objekt im Idealfall mit einem einzigen Zugriff. Dies erreichen wir durch Anwendung einer Hashfunktion, die die Adresse des Objekts berechnet.

Helmut Knebl

Kapitel 4. Bäume

Zusammenfassung

In Kapitel 4 werden binäre Suchbäume, AVL-Bäume und probabilistische binäre Suchbäume behandelt. B-Bäume dienen zum Speichern von Daten auf dem Sekundärspeicher. Codebäume zur graphischen Darstellung von Codes zur Datenkomprimierung runden das Kapitel ab.

Helmut Knebl

Kapitel 5. Graphen

Zusammenfassung

Die grundlegenden Graph-Algorithmen Tiefen- und Breitensuche und als Anwendung davon topologisches Sortieren und die Berechnung der starken Zusammenhangskomponenten studieren wir in Kapitel 5. Ein probabilistischer Algorithmus zur Berechnung eines minimalen Schnitts zeigt die Stärke von probabilistischen Methoden auf.

Helmut Knebl

Kapitel 6. Gewichtete Graphen

Zusammenfassung

Grundlegende Optimierungsprobleme, wie die Berechnung minimaler aufspannender Bäume und kürzester Wege als auch das Flussproblem in Netzwerken, sind der Inhalt von Kapitel 6. Die Algorithmen von Borůvka, Kruskal und Prim konstruieren minimale aufspannende Bäume und der Algorithmus von Dijkstra löst das Abstandsproblem für gewichtete Graphen. Der probabilistische Algorithmus von Karger, Klein und Tarjan berechnet in linearer Laufzeit einen minimalen aufspannenden Baum. Wesentlich dafür ist ein Algorithmus, der in linearer Laufzeit die Verifikation eines minimalen aufspannenden Baums durchführt. Der Algorithmus von Warshall ermittelt den transitiven Abschluss eines Graphen und der Algorithmus von Floyd die Abstandsmatrix. Die Algorithmen von Ford-Fulkerson und Edmonds-Karp lösen das Flussproblem in Netzwerken.

Helmut Knebl

Backmatter

Titel: Algorithmen und Datenstrukturen
verfasst von: Prof. Dr. Helmut Knebl
Verlag: Springer Fachmedien Wiesbaden
Electronic ISBN: 978-3-658-32714-9
Print ISBN: 978-3-658-32713-2
DOI: https://doi.org/10.1007/978-3-658-32714-9