Robert Sedgewick: Algorithmen

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


1. Grundlagen



Algorithmen

Wenn man ein Programm schreibt, realisiert man im allgemeinen ein Verfahren zur Lösung eines Problems, das zuvor entwickelt worden ist. Dieses Verfahren ist oft unabhängig von dem speziellen Computer, der benutzt werden soll; es ist wahrscheinlich für viele Computer in gleichem Maße geeignet. Jedenfalls ist es das Verfahren und nicht das Programm selbst, welches untersucht werden muß, um zu erfahren, wie an das Problem herangegangen wird. Der Begriff Algorithmus wird in der Informatik verwendet, um ein Verfahren zur Lösung eines Problems zu beschreiben, das für eine Realisierung in Form eines Programms geeignet ist. Algorithmen sind der »Stoff« der Informatik: Sie sind zentraler Untersuchungsgegenstand in vielen, wenn nicht den meisten Bereichen dieses Fachgebiets.

Die meisten interessierenden Algorithmen erfordern komplizierte Verfahren zur Organisation der Daten, die in die Berechnung einbezogen sind. Objekte, die auf diese Weise geschaffen werden, werden Datenstrukturen genannt und gehören ebenfalls zu den zentralen Objekten der Informatik. Somit gehen Algorithmen und Datenstrukturen Hand in Hand. In diesem Buch setzen wir voraus, daß Datenstrukturen Neben- oder Endprodukte von Algorithmen sind und folglich ebenfalls untersucht werden müssen, um die Algorithmen zu verstehen. Es ist möglich, daß einfache Algorithmen zur Entstehung von komplizierten Datenstrukturen führen, und umgekehrt, daß komplizierte Algorithmen einfache Datenstrukturen verwenden. Wir werden im vorliegenden Buch die Eigenschaften vieler Datenstrukturen gründlich studieren; tatsächlich hätte das Buch ebensogut Algorithmen und Datenstrukturen genannt werden können.

Wenn ein sehr umfangreiches Programm erstellt werden soll, muß ein großer Teil der Arbeit für das Verständnis und die Formulierung des zu lösenden Problems, für die Beherrschung seiner Komplexität und für seine Zerlegung in kleinere, leicht implementierbare Teilaufgaben aufgewandt werden. Oft ist es so, daß die Implementierung vieler Algorithmen, die nach der Zerlegung erforderlich sind, trivial ist. Jedoch gibt es in den meisten Fällen einige Algorithmen, deren Auswahl kritisch ist, weil ihre Ausführung den größten Teil der System-Ressourcen verwendet. Im vorliegenden Buch werden wir eine Vielzahl von grundlegenden Algorithmen untersuchen, die die Basis für umfangreiche Programme in vielen Anwendungsgebieten bilden.

Die gemeinsame Nutzung von Programmen in Computersystemen findet immer mehr Verbreitung, so daß ernsthafte Anwender von Computern zwar einen großen Teil der Algorithmen aus diesem Buch benutzen werden, aber eventuell nur einen kleineren Teil von ihnen zu implementieren brauchen. Jedoch hilft uns die Realisierung einfacher Varianten von Basisalgorithmen, sie besser zu verstehen und folglich weiterentwickelte Varianten effizienter anzuwenden. Auch erschweren es Mechanismen zur gemeinsamen Nutzung von Software auf vielen Computersystemen oft, Standardprogramme so anzupassen, daß sie spezifische Aufgaben effizient erfüllen. Daher ist es häufig angebracht, Basisalgorithmen neu zu implementieren.

Programme sind oft überoptimiert. Manchmal lohnt es nicht, sich die Mühe zu machen und zu gewährleisten, daß eine Implementierung auf dem Computer die effizienteste mögliche Variante ist, es sei denn, daß ein Algorithmus für eine sehr umfangreiche Aufgabe oder sehr oft verwendet werden soll. Anderenfalls wird eine sorgfältige, relativ einfache Implementierung ausreichen; Man kann recht sicher sein, daß sie ihren Zweck erfüllen wird, auch wenn sie vielleicht fünf- oder zehnmal langsamer ablaufen wird als die bestmögliche Variante, was bedeutet, daß sie ein paar Sekunden mehr benötigen kann. Im Gegensatz dazu kann die richtige Auswahl eines Algorithmus zu Beginn einen Unterschied vom Faktor hundert oder tausend oder mehr bewirken, was sich in Minuten, Stunden oder noch größerer Laufzeit ausdrücken kann. Im vorliegenden Buch konzentrieren wir uns auf die einfachsten sinnvollen Realisierungen der besten Algorithmen.

Oft stehen für die Lösung des gleichen Problems mehrere verschiedene Algorithmen (oder Implementierungen) zur Verfügung. Die Auswahl des besten Algorithmus für eine spezielle Aufgabe kann ein sehr komplizierter Prozeß sein, der häufig eine ausgeklügelte mathematische Analyse erfordert. Der Zweig der Informatik, der solche Fragen untersucht, heißt Algorithmenanalyse. Für viele der Algorithmen, die wir betrachten werden, ist analytisch nachgewiesen worden, daß sie sehr leistungsfähig sind, während bei anderen einfach die Erfahrung gemacht wurde, daß sie gut arbeiten. Wir werden nicht näher auf Fragen des Vergleichs der Leistungsfähigkeit eingehen; unser Ziel besteht darin, einige brauchbare Algorithmen für wichtige Aufgaben kennenzulernen. Man sollte einen Algorithmus jedoch nicht anwenden, ohne eine Vorstellung davon zu haben, welche Ressourcen er benötigt; daher werden wir darauf achten, welche Leistung von unseren Algorithmen erwartet werden kann.


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