Datenrettung Lexikon - A - Algorithmus
Algorithmus
Ein Algorithmus gibt eine generell gültige Handlungsanweisung zur Bereinigung eines Problems oder eines gewissen Problembereichs.
Algorithmen begegnen uns oft unbewusst sogar in den banalsten Bereichen unseres Lebens. Ein Exempel dafür können Kochrezepte sein. Alle nötigen Anweisungen sind vollständig und genau gestellt. Es wichtig, dass sogar für die einzelnen Teilbereiche wie Braten, Rühren die Arbeitsanweisungen angegeben sind. Weitere Beispiele für Algorithmen sind Reparatur- und Bedienungsanleitungen oder Assistenten zum Ausfüllen von Formularen. Das Programmieren einer Waschmaschine zählt hierbei wohl zu den eindeutigsten Algorithmen, denn eine Arbeitsanweisung ist erst dann als Algorithmus erkennbar wenn der Vorgang bereits zu Beginn auf eine gewisse Anzahl an Arbeitsschritten beschränkt ist. Es ist also nötig ein Ende des Handlungsstranges festzulegen. Im Bezug auf das Kochrezept, bedeutet dies, dass genau aufgeführt werden muss wie oft man rühren muss bzw. wie lange, um beim Erreichen des angestrebten Ziels aufhören zu können.
Algorithmen stellen einen der Hauptsschwerpunkte der Informatik dar. Außerdem bilden sie den Hintergrund einiger Spezialgebiete der theoretischen Informatik (Algorithmentheorie, Komplexitätstheorie, Berechenbarkeitstheorie). Sie kommen bei der Lenkung von Computern und vielen weiteren Maschinen, in Form von Computerprogrammen und elektronischer Schaltkreise, zum Einsatz.
Bei ausführlicherer Betrachtung erkennt man jedoch, dass dieser eigentlich eindeutig verständliche Begriff keine einhellige und exakte Beschreibung aufweist. Jeder Autor nutzt seine eigene Definition, deshalb ist die eindeutige Beschreibung dieses Wortes ein allgegenwärtiger Forschungsgegenstand.
Vorstellungen gibt es einerseits in die Richtung, dass Algorithmen als abstraktes Gegenstück zu den anschaulichen Programmen, die für verschiedene Maschinen konzipiert wurden, zu sehen. Hierbei ist die Abstraktion einfach das Auslassen von Einzelheiten der wirklichen Maschinen. Programme sind anschauliche Varianten von Algorithmen, die an die Notwendigkeiten und Möglichkeiten von wirklichen Maschinen angeglichen sind. Andere Vorstellungen besagen, dass die Algorithmen durch Maschinenprogramme von Turingmaschinen dargestellt werden. Hierbei existiert die Abstraktion durch die Nutzung der Turingmaschinen allgemein, d.h. eine ideale mathematische Maschine.
Die Geschichte
Die Bezeichnung Algorithmus entstammt aus der Umformung des Namens Muhammad Musa al-Chwarizmi (* ca. 783, † ca. 850). Er war der Verfasser des Buches Hisab al-dschabr wa-l-muqabala (825 Regeln zur Wiederherstellung und Reduktion), anhand dieses Buches wurde die Algebra auch im Westen populär. Bei der lateinischen Übersetzung dieses Buches besteht der Anfang aus den folgenden Worten: „Dixit Algorithmi“, mit diesen Worten zielte man auf den Autor des Buches ab. Die Bezeichnung „Algebra“ (al-Jabr – „Einrenkung“) entstammt gleichermaßen einer Passage des Buches. Im Grunde wurde die Bezeichnung Algorism ausschließlich für den Umgang der Arithmetik mit arabischen Zahlen genutzt. In der heutigen Sprachweise wird sie für alle jene vorgeschriebenen Prozesse, anhand derer man verschiedenartige Probleme korrigieren kann, genutzt.
Erster Computeralgorithmus
Jener erste Algorithmus, der für die Anwendung in einem Computer konzipiert wurde, entstammt den 1842 gemachten Notizen von Ada Lovelace, in ihren Notizen zu Charles Babbages Analytical Engine. Aus diesem Grund steht sie als erste Programmiererin fest. Jedoch konnte Ada Lovelaces Algorithmus nie angewandt werden, da Charles Babbage seinen Analytical Engine nie vervollständigen konnte.
Formale Definition
Eine Reihe von Mathematikern und Logikern des 19. und 20. Jahrhundert störten sich an der ungenauen Definition des Wortes Algorithmus. Dies entstammt der Tatsache, dass die von uns genutzte Sprache durch Unklarheiten und Gegensätzlichkeiten geprägt ist, was dem Drang der Wissenschaft nach Klarheit und Eindeutigkeit ein Dorn im Auge war.
Turingmaschinen und Algorithmusbegriff
Bis Mitte des 20 Jahrhundert gab es einige Anstrengungen zur genauen Begriffsbestimmung. Formalisierungen des Berechenbarkeitsbegriffs sind die Turing-Maschine (Alan Turing), der Lambda-Kalkül (Alonzo Church), rekursive Funktionen, Chomsky-Grammatiken und Markow-Algorithmen.
Nach der Entwicklung der unterschiedlichen Methoden wurde – mit ausschlaggebender Mitwirkung von Alan Turing - bewiesen, dass jede einzelne dieser Methoden vom gleichen Rang ist, d.h. dass sie vergleichbar gute Ergebnisse liefern. Man kann sie anhand einer Turing Maschine emulieren, man kann aber wiederum auch eine Turing Maschine emulieren. Anhand der Bezeichnung der Turing Maschine kann man kommende Definition entwickeln:
„Eine Berechnungsvorschrift zur Lösung eines Problems heißt Algorithmus genau dann, wenn eine zu dieser Berechnungsvorschrift äquivalente Turingmaschine existiert, die für jede Eingabe stoppt“.
Die folgenden Attribute eines Algorithmus sind auf Grund der Definition erkennbar:
1. Die Arbeitsschritte müssen endlich sein und eindeutig definiert werden
(Finitheit).
2. Jede Arbeitsanweisung des Verfahrens muss wirklich realisierbar sein
(Ausführbarkeit).
3. Die Durchführung darf zu jeder Zeiteinheit ausschließlich einen gewissen
endlichen Speicherbedarf haben (Dynamische Finitheit, siehe
(Platzkomplexität).
4. Die Auführung muss ein Ende haben, es darf nur eine bestimmte Anzahl an
Arbeitsschritten geben (Terminierung, siehe auch Zeitkomplexität).
Außerdem wird die Bezeichnung Algorithmus bei praktischen Anwendungen auf folgende Kennzeichen beschränkt:
1. Der Algorithmus muss bei gleichen Gegebenheiten ständig dasselbe
Resultat aufweisen (Determiniertheit).
2. Jede anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt
unverwechselbar beschrieben (Determinismus).
Church-Turing-These
Die Church Turing These besagt: „Jedes intuitiv berechenbare Problem kann durch eine Turingmaschine gelöst werden.“ Als formales Merkmal für einen Algorithmus nimmt man die Implementierbarkeit eines beliebigen zu einer Turing Maschine umwandelbaren Formalismus an, besonders die Implementierbarkeit in einer Programmiersprache, hierbei ist die erforderliche Terminiertheit jedoch noch nicht gewährleistet. Der Ausdruck Berechenbarkeit ist somit folgendermaßen beschrieben, ein Problem ist dann berechenbar, sobald ein terminierter Algorithmus zu diesem Problem existent ist, d.h. sobald eine dermaßen konzipierte Turing Maschine das Problem in einem vorgegebenen zeitlichen Rahmen bereinigen kann.
Abstract State Machines
Turing Maschinen lassen sich sehr gut durch abstrakt mathematische Funktionen beschreiben, jedoch sind wirkliche Probleme bei Weitem vielschichtiger und komplizierter. Aus diesem Grund wurde der Ruf nach alternativen Maschinen laut. Diese Maschinen unterscheiden sich beispielsweise im Umfang der Befehle. Im Gegensatz zu den leichten Arbeitsvorgängen der Turing Maschine, sind diese dazu fähig komplexere Arbeitsschritte, wie Fourtiertransformationen, in nur einem Rechenschritt zu bewältigen. Ein anderer Vorteil ist, dass sie mehrer Rechenschritte synchron ausführen können (Addition von 2 Vektoren in einem Schritt). Eine Darstellung einer solchen realen Maschine ist die Sequential Abstract State Machine
(seq. ASM) (http://www.eecs.umich.edu/gasm/papers/seqthesis.html).
Sie kann folgende Attribute aufweisen:
Ein Algorithmus einer seq. ASM soll:
- durch einen endlichen Programmtext gekennzeichnet werden können.
- Etappenweise durchführbar sein.
- Gewisse Gegebenheiten terminieren, muss jedoch nicht ständig
terminieren (sinnvolle Gegenbeispiele für die Forderung, dass immer
terminiert werden muss, seien der Sieb des Erastothenes, der fortgesetzt
Primzahlen findet, oder ein Betriebssystem).
- nur eine bestimmte, vorgeschriebene Anzahl an Zustände pro Schritt
alternieren können (Begrenzung der Parallelität).
- Nur eine bestimmte, vorgegebene Anzahl an Zustände pro Schritt
kontrollieren können (Begrenzung der Exploration).
Ein Beispiel: der Euklidische Algorithmus
Der Euklidische Logarithmus wurde schon um etwa 300 v. Chr. artikuliert, er hat die Aufgabe den größten gemeinsamen Teiler von zwei gegebenen natürlichen Zahlen „A“ und „B“ ausfindig zu machen.
1. Falls „B“ die größere der beiden Zahlen ist, werden „A“ und „B“ vertauscht,
damit keine negativen Ergebnisse entstehen können.
2. Es gilt jeweils: A = A –B
3. Sobald „A“ und „B“ nicht identisch sind wird wieder mit Schritt 1 begonnen,
sobald „A“ und „B“ jedoch identisch sind ist diese Zahl der größte
gemeinsame Teiler.
Beispiel:
Es soll der größte gemeinsame Teiler der Zahlen 14 und 8 berechnet werden. Hierzu wird der euklidische Algorithmus verwendet:
A; B; A-B
1. 14; 8; 6
2. 8; 6; 2
3. 6; 2; 4
4. 4; 2; 2
5. 2; 2; gleich
Das Ergebnis ist also 2.
Eigenschaften
Nichtdeterministische Algorithmen werden hauptsächlich in der theoretischen Informatik genutzt, auf den anderen Gebieten wird deshalb von Vornherein angenommen, dass sie sich mit deterministischen Algorithmen befassen. Abweichungen davon gibt es bei den stochastischen, randomisierten oder probablisierten Algorithmen, hierbei werden bewusst Zufallsfaktoren eingearbeitet. Diese Algorithmen gehören somit nicht den deterministischen oder determinierten an. Algorithmen, die in der Stochastik eingesetzt werden, sind in der Regel deterimistisch, richten sich jedoch nach Erfahrungswerten aus.Als nächstes finden sie die unterschiedlichen formalen Attribute kompakt zusammengefasst.
Determiniertheit
Bei der Nutzung derselben Startwerte muss auch dasselbe Resultat heraus kommen.
Algorithmen sind dann determiniert, wenn sowohl die Ergebnisse als auch die Anfangswerte und sämtliche Gegebenheiten übereinstimmen. Hierbei kann man randomisierte Algorithmen ausschließen, da ihr Resultat in bestimmter Weise vom Zufall beeinflusst wird.
Allgemein kann man sagen, dass alle deterministischen Algorithmen ebenfalls auch determiniert sind, jedoch ist die Umkehrung nicht gültig, da nicht jeder determinierte Algorithmus auch deterministisch sein muss.
Determinismus
Dabei darf es nur einen einzigen Folgeschritt geben.
Bei deterministischen Algorithmen besteht zu jedem Arbeitsschritt ausschließlich ein möglicher Folgeschritt. Sobald es eine Vielzahl möglicher Programmfortsetzungen gibt, denen alle eine gewisse Wahrscheinlichkeit zukommen kann, nennt man das stochastische, randomisierte oder probabilistische Algorithmen. Die theoretische Informatik weist neben dem Determinismus ebenfalls den so genannten Nichtdeterminismus auf, dieser wird jedoch in praxisnahen Anwendungen selten gebraucht. Der Nichtdeterminismus erhält seine Daseinsberechtigung hauptsächlich in der Anwendung von Quantencomputern. Diese Technologie kann auch mit diesen Algorithmen viel versprechend umgehen.
Finitheit
1. Statische Finitheit
Die Beschreibung ist endlich. Die Darstellungsform des Algorithmus muss begrenzt sein. Durch die statische Finitheit wird beschrieben, dass der Quelltext endlich sein muss. Also darf der Quelltext eine vorgeschriebene Nummer an Arbeitsschritten nicht überschreiten, auch wenn die Anzahl der Arbeitsschritte sehr hoch sein kann.
2. Dynamische Finitheit
Die Anzahl an Datenstrukturen und Zwischenspeicherungen ist zu jedem Zeitpunkt begrenzt. Der vom Algorithmus genutzte Speicherplatz darf zu keiner Zeit unendlich groß sein, sondern stets endlich. Wird diese Bedingung nicht gewährleistet, ist der Algorithmus nicht realisierbar.
Terminiertheit
Nach vorgegebener Zeitspanne erfolgt ein kontrollierter Stopp.
Die terminierende Eigenschaft von Algorithmen besagt, dass bei jeder durchführbaren Eingabe jeweils nach einer festgelegten Anzahl von Arbeitsschritten ein Resultat erzielt wird. Hierbei kann die Anzahl der nötigen Schritte variieren. Für Steuerungs- und Betriebssysteme sowie einen Großteil von Programmen, die anhand der Kommunikation mit dem Benutzer agieren, ist diese Bedingung nicht realisiert. Dies erkennt man daran, dass ein Programm ewig fortgeführt wird sofern der User es nicht beendet. Aus diesem Grund präsentiert Donald Knuth den Vorschlag, dass nicht terminierte Algorithmen als rechnergestützte Methoden ("Computational Methods") vermerkt werden.
In der Regel kann man bei beliebigen Algorithmen nicht frei darüber verfügen ob sie terminiert sind oder nicht (siehe auch Haltepunkt).
Algorithmenanalyse
Die Erkundung und Untersuchung von Algorithmen gehört zu den Aufgabenfeldern der Informatik. Sie wird in den häufigsten Fällen auch nur theoretisch umgesetzt, d.h. ohne Überprüfung durch die Programmiersprache. Somit ist sie analog zu den Verfahren in verschiedenen mathematischen Bereichen, in denen Untersuchungen zumeist auf fundamentale Vorgehensweisen als auf die wirkliche Realisierung abzielen. Zu Untersuchungszwecken konvertiert man Algorithmen zunächst in eine erheblich formalisierte Form, in dieser „Umgebung“ kann man sehr gut die formale Semantik zur Erforschung nutzen.
Die Analyse besteht aus unterschiedlichen Bereichen. Die Komplexitätstheorie ist einer davon und befasst sich mit dem Umgang von Algorithmen mit dem Ressourcenbedarf wie Rechenzeit und benötigter Speicherplatz. Die daraus erfolgenden Resultate werden als asymptotische Laufzeiten betrachtet. Hierbei untersucht man die Gebundenheit des Ressourcenbedarfs an die Länge der Eingabe. Dies bedeutet soviel dass die Komplexität mit der Größe der Zahlen, deren ggT erforscht wird, gekoppelt ist oder davon abhängt wie viele Teile anzuordnen sind, usw..
Die Berechenbarkeitstheorie befasst sich mit der Einstellung in Hinsicht auf die Terminierung, d.h. ob es möglich ist den Algorithmus überhaupt erfolgreich ab zu schließen.
Nach oben
Begriffe + Definitionen im Glossar zur Datenrettung, die mit dem Buchstaben A beginnen
.
Nach oben
Dieser Artikel basiert auf dem Artikel Algorithmus aus der freien Enzyklopädie Wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der Wikipedia ist eine Liste der Autoren zum Begriff Algorithmus verfügbar.
wichtige weitere Stichwörter zu dieser Detailerläuterung im Lexikon zur Datenrettung: Computer, Informatik, euklidischer Algorithmus, Such-Algorithmen, Probabilistischer Algorithmus, Suchverfahren
Copyright 2005 by CMS-Ranking & Suchmaschinenoptimierung mit dem Open-Source CMS Typo3 - Alle Beschreibungen & Definitionen im Lexikon & Glossar zur Datenrettung unterliegen dem Urheberrecht von www.datenrettung-lexikon.de, soweit nicht anders vermerkt. Alle auf diesen Seiten verwandten Markennamen sind eingetragene Markenzeichen der jeweiligen Markeninhaber.