Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


1. Grundlagen



Themenübersicht

Nachstehend folgen kurze Beschreibungen der Hauptteile des Buches, wobei wir einige der behandelten speziellen Themen aufführen und gewisse Hinweise darauf geben werden, wie wir an die Thematik herangehen. Diese Themenauswahl soll so viele grundlegende Algorithmen wie möglich einbeziehen. Einige der behandelten Gebiete gehören zum »Kern« der Informatik. Diese werden wir recht intensiv studieren, um Basisalgorithmen mit einem weiten Anwendungsfeld kennenzulernen. Andere Gebiete sind Gegenstand eines weiterführenden Studiums der Informatik und damit zusammenhängender Themen wie numerischer Analysis, Operations Research, Compilerbau und Algorithmentheorie; in diesen Fällen wird unsere Abhandlung als eine Einführung in diese Gebiete durch die Betrachtung einiger grundlegender Verfahren dienen.

GRUNDLAGEN sind im Rahmen dieses Buches die Werkzeuge und Verfahren, die in den nachfolgenden Kapiteln durchgehend verwendet werden. Nach einer kurzen Einführung in Pascal folgt eine Einführung in grundlegende Datenstrukturen wie Felder, verkettete Listen, Stapel, Schlangen und Bäume. Wir erörtern praktische Anwendungen der Rekursion und legen dar, wie wir an die Analyse und Implementierung von Algorithmen herangehen.

SORTIERVERFAHREN zur Ordnung von Dateien sind von grundlegender Bedeutung und werden ausführlich behandelt. Eine Vielzahl von Verfahren wird entwickelt, beschrieben und verglichen. Algorithmen für verschiedene verwandte Probleme wie Prioritätsschlangen, Selektion und Mischen werden behandelt. Einige dieser Algorithmen werden später als Basis für andere Algorithmen verwendet.

SUCHVERFAHREN für das Auffinden von Elementen in Dateien sind ebenfalls von fundamentaler Bedeutung. Wir behandeln grundlegende und weiterentwickelte Verfahren für die Suche unter Verwendung von Bäumen und digitalen Schlüsseltransformationen, darunter binäre Suchbäume, ausgeglichene Bäume, Hashing, digitale Suchbäume und Tries, sowie Verfahren, die für sehr umfangreiche Dateien geeignet sind. Es werden Beziehungen zwischen diesen Verfahren erörtert und Ähnlichkeiten zu Sortierverfahren aufgezeigt.

ALGORITHMEN DER ZEICHENFOLGEN-VERARBEITUNG umfassen eine Reihe von Verfahren zur Behandlung (langer) Zeichenfolgen. Die Zeichenfolgensuche führt zur Mustererkennung und diese wiederum führt zur Syntaxanalyse (Parsing). Techniken zur Komprimierung und Verschlüsselung von Dateien werden ebenfalls betrachtet. Es wird wiederum eine Einführung in weiterführende Themen durch die Behandlung einiger elementarer Probleme gegeben, die auch für sich von Bedeutung sind.

GEOMETRISCHE ALGORITHMEN sind eine Gruppe von Verfahren zur Lösung von Problemen, bei denen Punkte und Linien (und andere einfache geometrische Objekte) eine Rolle spielen und die erst seit kurzem angewandt werden. Wir betrachten Algorithmen zur Bestimmung der konvexen Hülle einer Menge von Punkten, zur Bestimmung von Schnittmengen von geometrischen Objekten, zur Lösung von Problemen des nächsten Punktes und für die mehrdimensionale Suche. Viele dieser Verfahren stellen eine interessante Ergänzung zu elementareren Sortier- und Suchverfahren dar.

ALGORITHMEN FÜR GRAPHEN sind für eine Vielzahl komplizierter und wichtiger Probleme von Nutzen. Es wird eine allgemeine Strategie für die Suche in Graphen entwickelt und auf grundlegende Zusammenhangsprobleme angewandt, einschließlich der Probleme des kürzesten Wegs, des minimalen Spannbaumes, des Flusses in einem Netzwerk und der Paarung. Eine vereinheitlichte Behandlung dieser Algorithmen zeigt, daß sie alle auf der gleichen Verfahrensweise beruhen, und diese Verfahrensweise hängt von einer vorher entwickelten grundlegenden Datenstruktur ab.

MATHEMATISCHE ALGORITHMEN umfassen grundlegende Verfahren aus der Arithmetik und numerischen Analysis. Wir untersuchen Verfahren für das Rechnen mit ganzen Zahlen, Polynomen und Matrizen sowie Algorithmen zur Lösung einer Vielzahl mathematischer Probleme, die in vielen Zusammenhängen auftreten: Erzeugung von Zufallszahlen, Lösung von Gleichungssystemen, Datenanpassung und Integration. Die Betonung liegt auf den algorithmischen Aspekten und nicht auf den mathematischen Grundlagen.

WEITERFÜHRENDE THEMEN werden mit dem Ziel erörtert, den Stoff des Buches mit verschiedenen anderen weiterführenden Studiengebieten zu verknüpfen. Spezial-Hardware, dynamische und lineare Programmierung, erschöpfendes Durchsuchen und NP-Vollständigkeit werden von einem elementaren Standpunkt aus im Überblick dargestellt, um dem Leser einen Eindruck von den interessanten weiterführenden Studiengebieten zu vermitteln, die sich aus den in diesem Buch behandelten elementaren Problemen ergeben.

Das Studium von Algorithmen ist interessant, weil es ein neues Gebiet ist (fast alle Algorithmen, die wir untersuchen, sind weniger als 25 Jahre alt), das eine lange Tradition besitzt (einige wenige Algorithmen sind seit Jahrtausenden bekannt). Ständig werden neue Entdeckungen gemacht, und nur wenige Algorithmen sind vollständig erforscht. Im vorliegenden Buch werden wir umständliche, komplizierte und schwierige Algorithmen ebenso betrachten wie elegante, einfache und leichte. Wir sind gehalten, die ersteren zu verstehen und die letzteren im Zusammenhang mit vielen verschiedenen potentiellen Anwendungen zu beurteilen. Indem wir das tun, werden wir eine Vielzahl von nützlichen Werkzeugen erforschen und eine »algorithmische Denkweise« entwickeln, die uns bei der Bewältigung der Herausforderungen der Berechnungstechniken der Zukunft von großem Nutzen sein wird.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]