WikiDer > Algorithmus

Algoritme
Algorithmus zum Aufteilen eines beliebigen Polyeders in Dreiecke (im Allgemeinen hat dieses Problem mehrere Lösungen, daher hängt die erreichte Lösung vom verwendeten Algorithmus ab)
Grundsätze
Computational Complexity Theory
Modelle
Algorithmus
Turing Maschine
Lambda-Kalkül
Theorien
Berechenbarkeit
Komplexitätsgrad
NP-vollständig

EIN Algorithmus ist ein Rezept zur Lösung eines mathematischen oder Computerproblems. Mathematisch formuliert ist es eine endliche Reihe Anleitung die von einem gegebenen Ausgangszustand zu einem angestrebten Ziel führt. Der Begriff Algorithmus stammt aus dem persisch Wort gaarazmi: خوارزمي, nach dem Namen des persischen Mathematikers Al-Chwarizmi. Algorithmen sind grundsätzlich getrennt von Computer Programms, obwohl für die Ausführung von Algorithmen oft Computers benutzt.

Das Ziel eines Algorithmus ist es, ein Problem mit einem klaren Ergebnis zu lösen. Das Anleitung kann im Allgemeinen mit Eventualitäten (Fehler, Datenqualitätsprobleme, Inkonsistenzen, Randeffekte) umgehen, die während der Ausführung auftreten können. Algorithmen haben im Allgemeinen Schritte (Sequenz), die sich wiederholen können (Wiederholung) oder diese Entscheidungen (Logik oder Gleichungen), um die Aufgabe zu lösen.

Dieselbe Aufgabe kann in der Regel auf unterschiedliche Weise gelöst werden. Der Unterschied liegt in der Regel in der Höhe Zeit, Platz oder Aufwand, der vom Algorithmus benötigt wird; dies kann ein Hinweis auf die Komplexität oder die Effizienz des Algorithmus. Beim ordnungsgemäßen Ausführen eines Computerprogramms ist es wichtig, dass der Algorithmus tatsächlich seine beabsichtigte Funktion ausführt und dass der Algorithmus vom Computerprogramm richtig ausgeführt wird. Alle Fehler oder Probleme sollten gemeldet werden.

Formale Algorithmen

Algorithmen in formale Systeme sind zum Beispiel wesentlich für die Art und Weise, wie Computers Informationen verarbeiten, weil a Computer Programm Ein formaler Algorithmus sagt dem Computer, welche Schritte in einer bestimmten Reihenfolge ausgeführt werden müssen, um ein bestimmtes Endergebnis zu erzielen. Ein größeres Problem wird in mehrere Teilprobleme zerlegt.

Im Allgemeinen mit Algorithmen Information verarbeitet; die Informationen (Daten) werden von einem Eingabegerät gelesen und in ein geschrieben Ausgabegerät; die Informationen können auch für später gespeichert werden. Gespeicherte Daten werden bei der Analyse von Algorithmen als "interner Zustand" des Geräts betrachtet, das den Algorithmus ausführt.

Für jeden Rechenprozess muss ein Algorithmus genau definiert werden: Er gibt an, wie das Gerät auf jede mögliche Eingabe und jeden internen Zustand reagiert. Da ein Algorithmus eine genaue Liste von exakten Schritten ist, ist die Reihenfolge, in der die Berechnung durchgeführt wird, entscheidend für das korrekte Funktionieren des Algorithmus. Einzigartig daran Konzept formaler Algorithmen ist die Zuweisung von a Wert zu einer Variable. Dies ergibt sich aus dem Begriff der Erinnerung als Arbeitsplatz.

Algorithmus vs. Computerprogramm

Wo ein Algorithmus de Beschreibung ist eine Lösung für ein Problem, ist a Computer Programm (in einigen Programmiersprache) das Implementierung dieses Algorithmus. Zum Beispiel kann ein Rechenalgorithmus für reelle Zahlen genaue Berechnungen annehmen, während die Implementierung bestimmt, wie groß die Rundungsfehler kann sein. Die Genauigkeit des Endergebnisses kann (bei einer äquivalenten Methode zur Abrundung von Zwischenergebnissen) vom Algorithmus abhängen, so dass beim Entwurf des Algorithmus oft schon berücksichtigt werden muss, dass Berechnungen in der Implementierung nicht exakt durchgeführt werden. Dies gilt nicht nur für die Computernutzung, sondern auch für manuelle Berechnungen mit Zwischenrundung.

Größere Systeme und Algorithmen werden in Subsysteme, Module, Funktionen und Anweisungen zerlegt, wobei das Design top-down oder bottom-up erfolgt. Im Prinzip ist der Algorithmus unabhängig von der physikalischen Implementierung auf einem bestimmten Computersystem. Dennoch kann (muss) eine bestimmte Architektur beim Design berücksichtigt werden. Die spezifischen Funktionen sind dann in einem separaten Modul untergebracht. Wenn das System ausgetauscht werden muss, beschränken sich die Änderungen auf ein einzelnes Modul.

Die unterschiedliche Betrachtungsweise und Beschreibung eines Problems hat im Laufe der Jahre auch zu unterschiedlichen Formen der Programmierung geführt: zwingende Programmierung, Objekt orientierte Programmierung, aspektorientierte Programmierung, Logikprogrammierung, symbolische Programmierung, funktionale Programmierung.

In der imperativen Programmierung sind Anweisungen explizit aufgeschrieben, wobei die Berechnung oben startet und geht dann Schritt für Schritt nach unten. Das nennt man Kontrollfluss eines Algorithmus.

Eine andere Sichtweise auf Algorithmen ist funktionale Programmierung. In solchen Programmen werden Algorithmen als mathematische Funktionen angesehen, die sich gegenseitig aufrufen können. Dieselben Funktionen können auch Variablen zugewiesen werden und selbst wenn Parameter in einem Funktionsaufruf verwendet werden.

Beispiel

Ein Beispiel für einen Algorithmus ist der Euklids Algorithmus, dass die größter gemeinsamer Teiler von zwei streng positiven Zahlen im Variablen a und b gibt. Die informelle Beschreibung dieses Algorithmus lautet wie folgt:

  • Solange a und b nicht gleich sind:
    • Subtrahiere den anderen von dem größeren der beiden.
  • Sobald sie gleich sind, ist der größte gemeinsame Teiler a (oder b).

Im Pseudocode:

Funktion gcd(a,b) wenn a = b Rückkehr ein sonst wenn a < b Rückkehr gcd(a, b-a) sonstRückkehr gcd(a-b, b)Ende

Dieser Algorithmus ist rekursiv.

Geschichte

Blatt aus einer lateinischen Übersetzung (Cambridge-Manuskript), beginnend mit "Dixit algorizmi"

Der Wortalgorithmus ist eine Verfälschung des altenglischen Wortes Algorithmus, das des lateinischen Wortes algorithmus kommt, was sich wiederum vom Namen des ableitet persisch Mathematiker Al-Chwarizmi (ca. 780 - ca. 845). Er war der Autor aus dem Buch al-Kitab al-mukhtasar fi hisab al-jabr w'al-muqabala (Buch der knappen arithmetischen Algebra undge Handelsbilanz) dass die Algebra in dem westliche Welt eingeführt. Das Wort Algebra selbst kommt von al-Jabrú aus dem Buchtitel. Das Wort Algorithmus ursprünglich nur auf die Regeln für die berechnen mit arabische Ziffern, war aber im 18. Jahrhundert zu Algorithmus entwickelt. Das Wort Algorithmus wird heute für alle endlichen Verfahren verwendet, um Probleme zu lösen oder Aufgaben auszuführen.

Das erste für einen Computer geschriebenen Algorithmus finden Sie in den Notizen von Ada Byron über die analytische Maschine, geschrieben in 1842. Deshalb gilt sie als die erste der Welt Computerprogrammierer berücksichtigt.

Der Mangel an mathematischer Strenge bei der Definition eines "wohldefinierten Verfahrens" für einen Algorithmus stellte die Mathematiker vor ein Problem und Logik des 19. und Start 20. Jahrhundert. Dieses Problem wurde mit der Beschreibung der description Turing Maschine, ein abstraktes Modell eines Computers, von Alan Turing, und die Demonstration, dass jede bisher gefundene Methode zur Beschreibung "wohldefinierter Prozeduren" auf einer Turing-Maschine ausgeführt werden kann (eine Aussage, die als Church-Turing-Theorem).

Heute ist das formale Kriterium für einen Algorithmus, dass es sich um eine Prozedur handelt, die auf einer vollständig spezifizierten Turingmaschine oder einer ihrer äquivalenten Formalisierungen implementiert werden kann. Turings erstes Interesse galt dem Berechenbarkeitstheorie: welche Funktionen und Probleme können mit einem Algorithmus gelöst werden. In der Praxis ist die Komplexitätstheorie wichtig, wo nicht die Frage ist, welche Funktionen berechenbar sind, sondern ob sie gelöst werden können und wie effizient die Lösung ist.

Aufführen

Verwandte Themen

Siehe die Kategorie Algorithmen von Wikimedia Commons für Mediendateien zu diesem Thema.