Algorithmus
aus www.iwiki.de, der freien Wissensdatenbank
Unter einem Algorithmus versteht man allgemein eine genau definierte Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen.
Inhaltsverzeichnis |
Algorithmen in der Informatik
Algorithmen werden im normalen Leben nicht bis ins letzte Detail beschrieben bzw. verfeinert. Dort verläßt man ergänzend sich auf die menschliche Komponente Verstand. Deswegen können solche Algorithmen nicht ohne weiters auf einem Rechner umgesetzt oder ausgeführt werden. Falls ein Algorithmus auf einem Rechner laufen soll, muss der Algorithmus mit knappen Resourcen des Computers zurecht kommen und der Algorithmus muss in einer klaren, stukturierten Form vorliegen.
Diese Probleme führen dazu, dass in der Informatik sogenannte 'deterministische Algorithmen' von besonderer Bedeutung sind. Ein deterministischer Algorithmus ist eine Funktion, die Eingabedaten in Ausgabedaten schrittweise transformiert und dabei folgende Bedingungen erfüllt:
- Determinismus: Schrittfolge liegt fest - Ergebnistreue,
- Exaktheit: präzise und formale Beschreibung,
- Finitheit: endliche Beschreibung,
- Vollständigkeit: alle denkbare Fälle beschrieben,
- Effektivität: Schritte real ausführbar,
- Terminierung: der Algorithmus kommt zum Ende.
Ein Programm ist eine Beschreibung eines Algoritmus und seiner Daten in einer Programmiersprache.
Entwurf von Algorithmen
Im folgenden Abschnitt wird erläutert, wie man einen Algorithmus im Rahmen der Informatik entwickelt.
Top-down-Design
Diese Methode beschreibt die Zerlegung einer Aufgabe kleinere Bestandteile. Die so entstandenen Teile werden sukzessive weiter verfeinert. Der Prozess wird so oft wiederholt bis ein gewisser Detailgrad erreicht wird. Für die Darstellung dieser Zerlegung nutzt man eine Meta-Sprache, die eine spätere Realisierung des Algorithmuses in einer Programmiersprache unterstützt. Einzelne Teilaufgaben werden unabhängig von den anderen bearbeitet und dargestellt.
Man kann bei Top-Down-Design sowohl grafische als auch textuelle Methoden verwenden.
Zu grafischen Methoden zählen beispielsweise Programmablaufpläne und Nassi-Shneiderman-Struktogramme. Ein Beispiel für eine textuelle Methode ist Pseudocode.
Bottom-up-Design
Wenn man nach dieser Methode vorgeht, entwickelt man zuerst kleine Bausteine für ein oder mehrere Programme, die später zusammengesetzt werden. Einzelne Bausteine werden nach Funktionen gruppiert und zu einer Bibliotek zusammengefasst.
Spezielle Algorithmen
Die Rekursion stellt eine Sonderform eines Algorithmus dar. Als Rekursion bezeichnet man den Aufruf einer Methode in der Methode selbst. Beim zweiten Aufruf bekommt die Methode andere Aufrufparameter als beim ersten. Die Methode selbst muss eine Abbruchbedingung haben. Wenn die Begingung erfüllt ist, erfolgt keinen weiteren Aufruf.
Mit Hilfe von einem Sortieralgorithmus werden Elemente eines Feldes nach einem Sortierbegriff geordnet.
Berechenbarkeit und Komplexität
Berechenbarkeit ist eine Eigenschaft einer Funktion mit Hilfe eines Algorithmus das Ergebnis aus der Eingabe zu berechnen.
Um die Berechenbarkeit eines Algorithmus festzustellen, werden verschiedene Methoden benutzt. Eine Methode verwendet ein rein theoretisches Konstrukt, die sogenannte Turing-Maschine. Die Turing-Maschine besteht aus einem Lese-Schreibe-Kopf und einem unendlich großen Speicher (Band). Die Maschine kann einen bestimmten Zustand aus einer endlichen Menge von zugelassenen Zuständen annehmen. Die Zustände representieren die Steuerung der Maschine und beschreiben was die Maschine in dem laufenden Schritt machen und in welchen Zustand die Maschine für den nächsten Schritt wechseln muss.
Wenn für eine Funktion eine Turing-Machine existiert, dann ist diese Funktion berechenbar.
Die Komplexität eines Algorithmus stellt den Aufwand an Betriebsmitteln dar. Die Betriebsmittel die von Algoritmen benötigt bzw. verbraucht werden sind primär Laufzeit und Speicherbedarf.
Die Laufzeitkomplexität wird mit Ordnung gekennzeichnet. Die Ordnung zeigt, wie die Laufzeit eines Algorithmus von der Anzahl der Eingabeparameter abhängt. Bubble-Sort beispielsweise ist von der Ordnung n2 und Quick-Sort von Ordnung n * log(n). Dies bedeutet im wesentlichen, dass Bubble-Sort in der Regel viel mehr Zeit braucht um einen Feld zu sortieren als Quick-Sort. Das wird besonders bei größeren Felder spürbar.
Siehe auch
Literatur
- Bernd Breutmann: Data and Algorithms. An Introductory Course, Carl Hanser Verlag, München 2001 , ISBN 3-446-21591-3
- Donald E. Knuth: The Art of Computer Programming. Bd 1–3. Addison Wesley, Reading Mass. 1998, ISBN 0201485419
- Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag, Heidelberg 2002 (4. Aufl.), ISBN 3-8274-1029-0
- Uwe Schöning: Algorithmen - kurz gefasst, Spektrum Akademischer Verlag, Heidelberg 1997, ISBN 3-8274-0232-8
Weblinks
- http://de.wikipedia.org/wiki/Algorithmus Wikipedia
