Uni-Logo
Sie sind hier: Startseite Bibliothek Lehrbücher Algorithmen und Datenstrukturen Kapitel 1
Artikelaktionen

Kapitel 1: Grundlagen


Multimedia-Ergänzungen zum Buch: Algorithmen und Datenstrukturen, Kapitel 1: Grundlagen

Spektrum Verlag

In der Informatik unterscheidet man üblicherweise zwischen Verfahren zur Lösung von Problemen und ihrer Implementation in einer bestimmten Programmiersprache auf bestimmten Rechnern. Man nennt die Verfahren Algorithmen. Sie sind das zentrale Thema der Informatik. Die meisten Algorithmen erfordern jeweils geeignete Methoden zur Strukturierung der von den Algorithmen manipulierten Daten. Algorithmen und Datenstrukturen gehören also zusammen. Die richtige Wahl von Algorithmen und Datenstrukturen ist ein wichtiger Schritt zur Lösung eines Problems mit Hilfe von Computern. Thema dieses Buches ist das systematische Studium von Algorithmen und Datenstrukturen aus vielen Anwendungsbereichen. In diesem Kapitel werden grundsätzliche Überlegungen zum Algorithmenbegriff und zur Leistungsanalyse vorausgeschickt. Ferner werden einige einfache Datenstrukturen behandelt.

Wie wichtig die richtige Algorithmenwahl zur Lösung eines Problems sein kann, zeigt ein von Jon Bentley vorgeschlagenes Problem, das in diesem Kapitel genauer diskutiert wird. Es handelt sich um das Maximum-Subarray-Problem.

Lineare Listen basieren auf dem in der Mathematik wohlbekannten Konzept einer endlichen Folge von Elementen eines bestimmten Grundtyps. Man denke etwa an eine endliche Folge ganzer oder reeller Zahlen. Man kann an eine Folge ein Element anhängen, ein Element an einer bestimmten Stelle einfügen oder entfernen und aus zwei Folgen durch Hintereinanderhängen (Verketten) eine neue Folge machen.

Statt das Einfügen und Entfernen von Elementen an einer beliebigen Position innerhalb einer linearen Liste zuzulassen, genügt es für viele Anwendungen, wenn diese Operationen am Anfang oder am Ende einer Liste ausgeführt werden können. Dies führt zu den Datenstrukturen Stapel und Schlangen.

Im letzten Abschnitt wird eine mögliche Implementation von verkettet gespeicherten lineare Listen vorgestellt, die es erlaubt, alle drei Operationen Suchen, Einfügen und Entfernen von Schlüsseln für eine Liste von N Elementen mit hoher Wahrscheinlichkeit in Zeit O(log N) auszuführen. Diese von W. Pugh vorgeschlagene Datenstruktur mit dem Namen Skip-Liste ist ein erstes Beispiel für eine randomisierte Datenstruktur.

Folien

Übungen

Programme

Bilder

 

resolveuid/3fbff31de4bcc5beac26d7f6a9d6811c

 

Bei Fragen zu dem Inhalt des Buches senden Sie bitte eine Email an ad-buch@informatik.uni-freiburg.de.

 

Benutzerspezifische Werkzeuge