Robert Sedgewick: Algorithmen

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


Vorwort


Das Ziel dieses Buches ist, einen Überblick über die wichtigsten gegenwärtig benutzten Algorithmen für Computer zu geben und diese dem wachsenden Personenkreis, der Kenntnisse über grundlegende Methoden auf diesem Gebiet benötigt, zu vermitteln. Das Buch kann als Lehrbuch für das zweite, dritte oder vierte Studienjahr der Informatik verwendet werden, nachdem die Studenten einige Fertigkeiten bei der Programmierung und eine gewisse Vertrautheit mit Computersystemen erworben haben, doch bevor sie Spezialvorlesungen über weiterführende Gebiete der Informatik oder Computer-Anwendungen absolviert haben. Außerdem kann das Buch für das Selbststudium oder als Nachschlagewerk für diejenigen von Nutzen sein, die sich mit der Entwicklung von Computersystemen oder Anwendungsprogrammen beschäftigen, da es eine Reihe von Implementationen nützlicher Algorithmen sowie eingehende Informationen über die Merkmale ihrer Leistungsfähigkeit enthält. Dank der breit angelegten Betrachtungsweise, die für das Buch kennzeichnend ist, stellt es eine geeignete Einführung in das genannte Gebiet dar.


Umfang

Das Buch enthält 45 Kapitel, die in acht Hauptteilen angeordnet sind: Grundlagen, Sortieren, Suchen, Verarbeiten von Zeichenfolgen, geometrische Algorithmen, Algorithmen für Graphen, mathematische Algorithmen und weiterführende Themen. Ein Hauptziel bei der Erstellung dieses Buches war es, die grundlegenden Verfahren aus diesen verschiedenen Gebieten zusammenzustellen, um einen Zugang zu den besten bekannten Methoden für Problemlösungen mittels Computer zu ermöglichen. Einige Kapitel enthalten einführende Erläuterungen zu weiterführendem Material. Der Autor hofft, daß die im Buch gegebenen Beschreibungen den Lesern das Verständnis der wesentlichen Eigenschaften grundlegender Algorithmen, von Prioritätswarteschlangen und Hashing bis zur Simplexmethode und zur schnellen Fourier-Transformation, ermöglichen werden.

Die Absolvierung von ein oder zwei Vorlesungen über Informatik oder eine gleichwertige Erfahrung auf dem Gebiet der Programmierung ist wünschenswert, damit der Leser in der Lage ist, das im Buch dargelegte Material vollständig zu verstehen: eine Vorlesung über Programmierung in einer höheren Programmiersprache wie Pascal und eventuell eine weitere Vorlesung, in der Grundbegriffe von Programmiersystemen vermittelt werden. Das vorliegende Buch ist somit für jedermann bestimmt, der eine moderne Programmiersprache beherrscht und mit den Grundzügen moderner Computersysteme vertraut ist.

Der größte Teil der mathematischen Grundlagen, mit denen die Ergebnisse der Analysen untermauert werden, ist in sich abgeschlossen (oder als »über den Rahmen dieses Buches hinausführend« gekennzeichnet), so daß für den größten Teil des Buches nur wenige spezielle mathematische Vorkenntnisse erforderlich sind. Nichtsdestotrotz ist eine gewisse mathematische Vorbildung mit Sicherheit von Nutzen. In einigen Kapiteln im letzten Teil des Buches werden Algorithmen behandelt, die mit komplizierteren mathematischen Gebieten zusammenhängen; das Ziel besteht hierbei darin, die Beziehung der Algorithmen zu anderen im Buch betrachteten Methoden herzustellen, nicht jedoch in der Vermittlung des mathematischen Stoffes. Daher erfolgt die Erläuterung weiterführender mathematischer Begriffe in einer kurzen, allgemeinen und beschreibenden Form.


Einsatz als Lehrmittel im Studium

Bezüglich der Art und Weise, wie das hier zusammengestellte Material gelehrt werden kann, ist ein weiter Spielraum gegeben. Die einzelnen Kapitel dieses Buches können weitgehend unabhängig voneinander vorgetragen werden, obwohl in manchen Fällen bei Algorithmen eines Kapitels auf Verfahren aus einem vorangegangenen Kapitel zurückgegriffen wird. Das Material kann an die Verwendung in unterschiedlichen Studienjahren angepaßt werden, indem eventuell 25 oder 30 der 45 Kapitel ausgewählt werden, je nach der Absicht des Dozenten und der Vorbereitung der Studenten.

In einer Grundvorlesung »Datenstrukturen und Algorithmen« könnte auf einige der mathematischen Algorithmen und der weiterführenden Themen verzichtet werden. Stattdessen könnte der Schwerpunkt darauf gelegt werden, wie verschiedene Datenstrukturen bei den Implementationen verwendet werden. In einer sich anschließenden Vorlesung über »Entwicklung und Analyse von Algorithmen« könnten einige der mehr an praktischen Fragen orientierten Abschnitte ausgelassen werden, und es könnte die Erkennung und Untersuchung der Wege betont werden, auf denen bei Algorithmen ein gutes asymptotisches Verhalten erzielen. Bei einer Vorlesung über »Software-Tools« könnte das mathematische und weiterführende algorithmische Material entfallen. Stattdessen könnte Schwerpunkt sein, wie sich die hier angegebenen Implementationen in umfangreiche Programme oder Systeme einfügen lassen. Eine Vorlesung über »Algorithmen« könnte den Charakter eines Überblicks haben und der Vorstellung von Ideen aus all diesen Gebieten dienen.

Manche Dozenten haben vielleicht den Wunsch, die oben beschriebenen Vorlesungen durch zusätzliches Material zu ergänzen, um ihre speziellen Neigungen zur Geltung zu bringen. Bei »Datenstrukturen und Algorithmen« könnte weiteres Material über grundlegende Datenstrukturen gelehrt werden; bei »Entwicklung und Analyse von Algorithmen« könnten gründlichere mathematische Analysen hinzugefügt werden; bei »Software-Tools« könnten schließlich Methoden der Entwicklung von Software eingehender behandelt werden. Im vorliegenden Buch wird allen diesen Fragen Beachtung geschenkt, wobei der Schwerpunkt jedoch bei den Algorithmen selbst liegt.

Dieses Buch (und vorangehende Versionen) wurde in den letzten Jahren an der Princeton University und an der Brown University für die zweite oder dritte Vorlesung über Informatik benutzt, welche die Voraussetzung für alle späteren Vorlesungen ist. Gewöhnlich handelt es sich bei etwa der Hälfte der Studenten, die die Vorlesung besuchen, um solche, die sich auf Informatik spezialisieren. Unsere Erfahrung zeigt, daß die Breite der Abhandlung des Stoffes in diesem Buch unsere Informatikstudenten mit Grundkenntnissen der Informatik ausstattet, auf denen in späteren Vorlesungen über Algorithmenanalyse, Systemprogrammierung und theoretische Informatik aufgebaut werden kann, während gleichzeitig allen Studenten eine große Menge an Verfahren vermittelt werden, die sie unmittelbar anwenden können. Außerdem haben wir festgestellt, daß die Studenten ihr Studium mit einer immer besseren Vorbereitung auf dem Gebiet der Programmiergrundlagen aufnehmen und in der Lage sind, die Vielzahl der Algorithmen in diesem Buch aufzunehmen.

Das Buch enthält 450 Übungsaufgaben, zehn nach jedem Kapitel, die gewöhnlich einem von zwei Typen angehören. Die meisten sind dazu bestimmt zu prüfen, ob die Studenten das Material des Kapitels verstanden haben, und enthalten die Aufforderung, ein Beispiel durchzuarbeiten oder im betreffenden Kapitel beschriebene Ideen anzuwenden. Einige Aufgaben erfordern jedoch die Implementation und Zusammensetzung mancher Algorithmen und eventuell die Durchführung empirischer Untersuchungen zum Vergleich von Algorithmen und zum Kennenlernen ihrer Eigenschaften.


Algorithmen mit praktischem Nutzen

Im Vordergrund des Buches stehen Algorithmen, die von praktischem Nutzen sein dürften. Schwerpunkt ist das Bestreben, den Studenten ein solches Handwerkszeug zu vermitteln, das sie in die Lage versetzt, nützliche Algorithmen sicher zu implementieren, auszuführen und zu debuggen. Vollständige Implementationen der betrachteten Verfahren (in einer realen Programmiersprache) wurden in den Text eingefügt, zusammen mit Beschreibungen der Arbeitsweise dieser Programme anhand einer abgestimmten Menge von Beispielen.

Ausführlich werden Eigenschaften der Algorithmen und Situationen, in den sie von Nutzen sein könnten, betrachtet. Verbindungen zur Algorithmenanalyse und zur theoretischen Informatik werden zwar nicht betont, jedoch aufgezeigt. An geeigneten Stellen werden empirische und analytische Ergebnisse erörtert, um zu veranschaulichen, warum gewisse Algorithmen bevorzugt werden. Wo es von Interesse ist, wird die Beziehung der untersuchten praktischen Algorithmen zu rein theoretischen Ergebnissen beschrieben.

Die in diesem Buch durchgehend verwendete Programmiersprache ist Pascal. Der Vorteil von Pascal besteht darin, daß es weit verbreitet und sehr bekannt ist; der Nachteil ist, daß Pascal viele Merkmale fehlen, die für komplizierte Algorithmen benötigt werden. Die Programme können leicht in andere moderne Programmiersprachen übertragen werden, da relativ wenige Pascal-spezifische sprachliche Konstruktionen benutzt werden. Einige Programme können durch Verwendung höherentwickelter Sprachmerkmale (von denen einige in Pascal nicht zur Verfügung stehen) vereinfacht werden, doch ist das seltener der Fall, als man meinen könnte.

Ein Ziel dieses Buches besteht darin, die Algorithmen in einer möglichst einfachen und direkten Form vorzustellen. Die Programme sollten nicht für sich gelesen werden, sondern als Bestandteil des sie umgebenden Textes. Dieser Stil wurde als Alternative zur Verwendung von Kommentaren innerhalb der Programme gewählt. Der Stil wurde, wo immer dies möglich ist, vereinheitlicht, so daß Programme, die ähnlich sind, auch ähnlich aussehen.


Änderungen in der zweiten Auflage *)

In dieser zweiten Auflage wurden überall Korrekturen, aktualisierte Informationen und Verbesserungen aufgenommen, wozu auch drei größere Änderungen gehören, die sich auf das gesamte Buch auswirken.

Erstens wurde ein neuer Abschnitt hinzugefügt, der einführendes Material zu Datenstrukturen und zur Entwicklung und Analyse von Algorithmen enthält. Dies ist die Basis für das restliche Buch und liefert einen Rahmen, innerhalb dessen weiterentwickelte Algorithmen behandelt werden. Einige Leser können diesen Abschnitt überspringen oder nur flüchtig durchsehen; andere können sich hier mit den Grundlagen vertraut machen.

Zweitens wurde die Analyse der Algorithmen vollständiger und strenger dargelegt als in der ersten Ausgabe. Spezielle Informationen zu Merkmalen der Leistungsfähigkeit von Algorithmen werden grundsätzlich als »Eigenschaften« hervorgehoben, wichtige Tatsachen zu den Algorithmen, die eine weitere Untersuchung verdienen.

Drittens (und diese Änderung ist am augenscheinlichsten) wurden Hunderte von Abbildungen hinzugefügt. Die visuelle Dimension, die durch diese Abbildungen geliefert wurde, erleichtert das Verständnis vieler Algorithmen auf einer intuitiven Ebene.


Danksagung

Viele Personen gaben mir nützliche Hinweise auf der Grundlage früherer Entwürfe dieses Buches. Insbesondere haben Studenten der Princeton University und der Brown University während der letzten Jahre unter den ersten Versionen der Darlegung des Materials in diesem Buch gelitten. Mein besonderer Dank gebührt Trina Avery, Tom Freeman und Janet Incerpi. Janet lieferte umfangreiche, ausführliche Kommentare und Vorschläge, die mir halfen, zahllose technische Mängel und Auslassungen zu beseitigen. Tom prüfte viele der Programme, und Trinas Redaktion des Manuskripts (beider Ausgaben) half mir, den Text klarer zu gestalten und seiner Korrektheit näher zu kommen. Ich möchte auch gern den vielen Lesern danken, die mir ausführliche Kommentare zur zweiten Ausgabe übermittelten, darunter Guy Almes, Jay Gischer, Kennedy Lemke, Udi Manber, Dana Richards, John Reif, M. Rosenfeld, Stephen Seidman und Michael Quinn.

Ganz besonders habe ich Janet Incerpi zu danken, die das Buch am Anfang in das Format TEX umwandelte, die Tausende von Änderungen hinzufügte, die ich nach dem »letzten Entwurf« der ersten Ausgabe vornahm, die Dateien durch verschiedene Systeme leitete, um das Manuskript auszudrucken, und sogar, neben vielen anderen Dingen, das Standardprogramm zur Bildrasterwandlung für TEX erstellte, das zur Herstellung von Manuskripten des Entwurfs benutzt wurde. Erst nachdem ich viele dieser Arbeiten für die zweite Ausgabe selbst ausgeführt habe, weiß ich die Unterstützung von Janet richtig zu schätzen.

Die Gestaltung der Abbildungen in der zweiten Ausgabe beruht in vielen Fällen auf der gemeinsamen Arbeit mit Marc Brown am Projekt »elektronisches Klassenzimmer« an der Brown University im Jahre 1983. Für die Unterstützung und Hilfe bei der Schaffung der Entwürfe (nicht zu reden von den Systemen, mit denen wir arbeiteten) möchte ich Marc meinen Dank aussprechen. Außerdem möchte ich Sarantos Kapidakis für die Hilfe bei der Herstellung der Reprovorlagen danken.

Diese zweite Ausgabe verdankt ihre Existenz in hohem Maße der Unterstützung von Keith Wollman von Addison-Wesley, der mich am Anfang überzeugte, mit der Arbeit zu beginnen. Unter anderem gab Keith mir einen unmöglichen Zeitplan vor, den ich halbwegs einhalten konnte.

Vieles von dem, was ich hier aufgeschrieben habe, erfuhr ich aus den Vorlesungen und Veröffentlichungen von Don Knuth, meinem Lehrer an der Stanford University. Obwohl Don keinen direkten Einfluß auf diese Arbeit hatte, ist seine Gegenwart in diesem Buch zu spüren, denn er war es, der das Studium von Algorithmen auf eine wissenschaftliche Grundlage stellte, die ein Werk wie dieses möglich macht.

Sehr dankbar bin ich für die Unterstützung durch die Brown University und INRIA, wo ich den größten Teil der Arbeit an diesem Buch vollbrachte, sowie durch das Institute for Defense Analyses und das Xerox Palo Alto Research Center, wo ich während eines Aufenthaltes als Gast einige Arbeiten am Buch ausführte. Viele Teile des Buches beruhen auf Forschungsarbeiten, die von der National Science Foundation und vom Office of Naval Research großzügig unterstützt wurden. Schließlich möchte ich Bill Bowen, Aaron Lemonick und Neil Rudenstine von der Princeton University für ihre Hilfe bei der Schaffung eines wissenschaftlichen Arbeitsklimas danken, in dem es mir möglich war, trotz zahlreicher anderer Verpflichtungen diese zweite Auflage vorzubereiten.


Robert Sedgewick
Marly-le-Roi, Frankreich, Februar 1983
Princeton, New Jersey, Januar 1988



*)
des amerikanischen Originals; A.d.Ü.


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