 |
|
| HSG |
|
Auszug aus dem Artikel aus Duden, Informatik:
Algorithmus: Unter einem Algorithmus versteht man eine Verarbeitungsvorschrift, die so präzise formuliert ist, dass sie von einem mechanisch oder elektronisch arbeitenden Gerät durchgeführt werden kann. Aus der Präzision der sprachlichen Darstellung des Algorithmus muß die Abfolge der einzelnen Verarbeitungs-schritte eindeutig hervor-gehen. Hierbei sind Wahlmöglichkeiten zugelassen. Nur muß dann genau festliegen, wie die Auswahl einer Möglich-keit erfolgen soll.
Beispiele für Algorithmen sind Vorschriften zum Addieren, Subtrahieren oder Multiplizieren von Zahlen, der euklidische Algorithmus zur Berechnung des größten gemeinsamen Teilers und alle in einer Program-mier-sprache formulierten Verfahren. Kochrezepte, Bastelanleitungen, Partituren, Spielregeln und alltägliche Vorschriften erinnern an Algorithmen; sie sind aber nur selten exakt ausformuliert und enthalten oft Teile, die vom Ausführenden beliebig interpretiert werden können.
(..............)
Der Begriff des Algorithmus ist von zentraler Bedeutung für die Informatik. Er faßt verschiedene Ansätze wie "Programm", "berechenbare Funktion", "Lösung logischer Formeln", "Normalform zu einem l-Ausdruck" ( Lambda-Kalkül) usw. zusammen und charakterisiert alles, was man mit Maschinen prinzipiell bearbeiten kann. Computer führen Algorithmen aus und Probleme, die man algorithmisch nicht lösen kann ( Entscheidbarkeit), können auch nicht Computern oder anderen Maschinen zur Lösung übertragen werden.
(............)
Algorithmen besitzen charakteristische Eigenschaften:
a) Im Allgemeinen löst ein Algorithmus eine Klasse von Problemen. Die Auswahl eines einzelnen Problems erfolgt über Parameter.
b) Algorithmen sind determiniert ( Determiniertheit), d. h.: wird ein Algorithmus mit den gleichen Ein-gabe-werten und Startbedingungen wiederholt, so liefert er stets das gleiche Ergebnis. Eine Erweiterung bilden die nichtdeterminierten Algorithmen, die bei gleichen Startbedingungen unterschiedliche Ergebnisse (auch falsche) liefern können. Diese Eigenschaft nimmt man manchmal in Kauf, z. B. wenn ein exakter Lösungsalgorithmus eine hohe Komplexität besitzt. Stochastische Algorithmen sind nichtdeterminiert.
c) Die Beschreibung eines Algorithmus besitzt eine endliche Länge (statische Finitheit). Ferner darf zu jedem Zeitpunkt, zu dem man die Abarbeitung eines Algorithmus unterbricht, der Algorithmus nur endlich viel Platz belegen (dynamische Finitheit).
d) Für die Praxis sind meist nur solche Algorithmen von Bedeutung, die für jede Eingabe nach endlich vielen Schritten ein Resultat liefern und anhalten (Terminierung). Ausnahmen sind z. B. Steuerungs-algorithmen wie das zentrale Steuerprogramm eines Rechnersystems ( Betriebssystem).
e) Ein Algorithmus heißt deterministisch ( Determinismus), wenn zu jedem Zeitpunkt seiner Ausführung höchstens eine Möglichkeit der Fortsetzung besteht. Z. B. stellen Programme in imperativen Programmier-sprachen meist deterministische Algorithmen dar. Hat ein Algorithmus an gewissen Stellen mehrere Möglichkeiten der Fortsetzung, von denen man nach Belieben eine auswählen kann, so heißt er nicht-deterministisch. Kann man den Fortsetzungsmöglichkeiten Wahrscheinlichkeiten zuordnen, so spricht man von stochastischen Algorithmen.
Informatiker, Mathematiker und andere Wissenschaftler versuchen oft, Lösungen zu Problemen in Form von Algorithmen zu finden. Ist ein solcher Lösungsalgorithmus entdeckt und ausformuliert worden, dann kann das gestellte Problem als "entwertet" angesehen werden, da jetzt kein Problem mehr vorliegt. Wenngleich durch Algorithmen große Problembereiche als "gelöst", "entwertet" oder "nun uninteressant" erscheinen, so suchen Informati-ker oft noch weiter nach einem möglichst guten Algorithmus ( Effizienz). Man kann beweisen, daß es zu jedem Algorithmus unendlich viele verschiedene Algorithmen gibt, die das gleiche Problem lösen. Die Suche nach möglichst guten Algorithmen, bzw. der Beweis, daß es keine besseren Algorithmen geben kann, führt meist auf sehr komplizierte Probleme, für deren Lösung man keine generell einsetzbaren Methoden kennt.
(.......)
Der Name "Algorithmus" leitet sich aus dem Namen des persisch-arabischen Mathematikers Ibn Mûsâ Al-Chwârismî ab, der bereits im 9. Jahrhundert ein Buch über die "Regeln der Wiedereinsetzung und Reduktion" schrieb