C1ph4: Die Seite wurde neu angelegt: „[[Al-Chwarizmi, der Namensgeber des ''Algorithmus'', auf einer sowjetischen…“

2018-05-05T10:02:33Z

Die Seite wurde neu angelegt: „mini|[[Al-Chwarizmi, der Namensgeber des ''Algorithmus'', auf einer sowjetischen…“

Neue Seite

[[Datei:Abu Abdullah Muhammad bin Musa al-Khwarizmi edit.png|mini|[[Al-Chwarizmi]], der Namensgeber des ''Algorithmus'', auf einer [[Sowjetunion|sowjetischen]] Briefmarke anlässlich seines 1200-jährigen Geburtsjubiläums]]

Ein '''Algorithmus''' ist eine eindeutige Handlungsvorschrift zur Lösung eines [[Problem]]s oder einer Klasse von Problemen. Algorithmen bestehen aus endlich vielen, [[Wohldefiniertheit|wohldefinierten]] Einzelschritten.<ref>Hartley Rogers, Jr.: ''Theory of Recursive Functions and Effective Computability'', S. 2.</ref> Damit können sie zur Ausführung in einem [[Computerprogramm]] [[Implementierung|implementiert]], aber auch in [[natürliche Sprache|menschlicher Sprache]] formuliert werden. Bei der [[Problemlösen|Problemlösung]] wird eine bestimmte Eingabe in eine bestimmte Ausgabe überführt.<ref>{{Literatur | Autor=[[Charles E. Leiserson]], [[Ronald L. Rivest]], Clifford Stein| Titel= Algorithmen – Eine Einführung| Verlag= Oldenbourg Verlag| Ort= München| Jahr= 2010| ISBN= 978-3-486-59002-9|Seiten=5}}</ref>

== Begriffsabgrenzung ==
Der Übergang zwischen Algorithmus und [[Heuristik]] ist fließend.

[[Werner Stangl]] greift ihn folgend: ''Ein Algorithmus bezeichnet eine systematische, logische Regel oder Vorgehensweise, die zur Lösung eines vorliegenden Problems führt. Im Gegensatz dazu steht dabei die schnellere, aber auch fehleranfälligere Heuristik.''<ref>{{Internetquelle|url=http://lexikon.stangl.eu/3027/algorithmus-algorythmus-algorhythmus/|titel=Algorithmus|titelerg=|autor=[[Werner Stangl]]|hrsg=|werk=lexikon.stangl.eu|seiten=|datum= |zugriff=2015-07-19|sprache=|format=|kommentar=|zitat=|offline=}}</ref>
Ein Heurismus versucht, basierend auf evtl. unvollständigen Eingangswerten, ein wahrscheinliches Ergebnis zu erzeugen.

'''Rechenvorschriften''' sind eine Untergruppe der Algorithmen. Sie beschreiben Handlungsanweisungen in der Mathematik bezüglich Zahlen.

Andere Algorithmen-Untergruppen sind z. B. (Koch-)Rezepte, Gesetze, Verordnungen, Regeln, Verträge.

== Geschichtliche Entwicklung ==
Schon mit der Entwicklung der Sprache ersannen die Menschen für ihr Zusammenleben in größeren Gruppen Verhaltensregeln, Gebote, Gesetze – einfachste Algorithmen. Mit der Sprache ist auch eine geeignete Möglichkeit gegeben, Verfahren und Fertigkeiten weiterzugeben – komplexere Algorithmen. Aus der Spezialisierung einzelner Gruppenmitglieder auf bestimmte Fertigkeiten entstanden die ersten Berufe.

Der Algorithmusbegriff als abstrakte Sicht auf Aufgabenlösungswege trat zuerst im Rahmen der Mathematik, Logik und Philosophie ins Bewusstsein der Menschen. Ein Beispiel für einen mathematischen Algorithmus aus dem Altertum ist der [[Euklidischer Algorithmus|Euklidische Algorithmus]].

== Wortherkunft ==
[[Datei:Dixit algorizmi.png|mini|Seite aus einer lateinischen Übersetzung (Cambridger Manuskript), beginnend mit „Dixit algorizmi“]]

Das Wort ''Algorithmus'' ist eine Abwandlung oder [[Verballhornung]] des Namens des arabischen Rechenmeisters und Astronomen [[Al-Chwarizmi|Muḥammad Ibn-Mūsā al-H̱wārizmī]], dessen Namensbestandteil ([[Arabische Namen|Nisba]]) ''al-Chwarizmi'' „der Choresmier“ bedeutet und auf die Herkunft des Trägers aus [[Choresmien]] verweist. Sein Lehrbuch ''Über die indischen Ziffern'' (verfasst um 825 im [[Haus der Weisheit (Bagdad)|Haus der Weisheit]] in [[Bagdad]]) wurde im 12. Jahrhundert aus dem Arabischen ins [[Lateinische Sprache|Lateinische]] übersetzt und hierdurch in der westlichen Welt neben [[Leonardo Fibonacci|Leonardo Pisanos]] ''[[Liber abaci|Liber Abaci]]'' zur wichtigsten Quelle für die Kenntnis und Verbreitung des indisch-arabischen Zahlensystems und des schriftlichen Rechnens. Mit der lateinischen Übersetzung al-Hwarizmis wurde auch der Name des Verfassers in Anlehnung an die Anfangsworte der ältesten Fassung dieser Übersetzung (''Dixit Algorismi'' „Algorismi hat gesagt“) latinisiert.<ref>{{Literatur |Autor=Muḥammad Ibn-Mūsā al-H̱wārizmī |Titel=Die älteste lateinische Schrift über das indische Rechnen nach al-Ḫwārizmī |Hrsg=Menso Folkerts, Paul Kunitzsch |Sammelwerk= |Band= |Nummer= |Auflage= |Verlag=Verlag der Bayrischen Akademie der Wissenschaften |Ort=München |Datum=1997 |Seiten= |ISBN=}}</ref> Aus al-Hwarizmi wurde mittelhochdeutsch ''algorismus,'' ''alchorismus'' oder ''algoarismus –'' ein Wort, das aus dem Lateinischen nahezu zeitgleich und gleichlautend ins Altfranzösische (''algorisme'', ''argorisme)'' und Mittelenglische (''augrim'', ''augrym'') übersetzt wurde. Mit Algorismus bezeichnete man bis um 1600 Lehrbücher, die in den Gebrauch der Fingerzahlen, der Rechenbretter, der Null, die indisch-arabischen Zahlen und das schriftliche Rechnen einführen.<ref>[[Kurt Vogel (Mathematikhistoriker)|Kurt Vogel]]: ''Der Trienter Algorismus von 1475.'' In: ''Nova Acta Leopoldina'', Neue Folge, Band 27, 1963, S. 183–200.</ref> Das schriftliche Rechnen setzte sich dabei erst allmählich durch. So beschreibt etwa der englische Dichter [[Geoffrey Chaucer]] noch Ende des 14. Jahrhunderts in seinen [[Canterbury Tales|''Canterbury Tales'']] einen Astrologen, der Steine zum Rechnen („augrym stones“) am Kopfende seines Betts aufbewahrt:

:''This clerk was cleped hende Nicholas. / His augrym stones layen faire apart, / On shelves couched at his beddes heed;''

In der mittelalterlichen Überlieferung wurde das Wort bald als erklärungsbedürftig empfunden und dann seit dem 13. Jahrhundert zumeist als Zusammensetzung aus einem Personennamen ''Algus'' und aus einem aus dem [[Griechische Sprache|griechischen]] {{lang|grc|ῥυσμός}} (Nebenform von {{lang|grc|ῥυθμός}}) in der Bedeutung „Zahl“ entlehnten Wortbestandteil ''-rismus'' interpretiert.

Algus, der vermutete Erfinder dieser Rechenkunst, wurde hierbei von einigen als Araber, von anderen als Grieche oder zumindest griechisch schreibender Autor, gelegentlich auch als „König von Kastilien“ (Johannes von Norfolk) betrachtet. In der volkssprachlichen Tradition erscheint dieser „Meister Algus“ dann zuweilen in einer Reihe mit großen antiken Denkern wie [[Platon]], [[Aristoteles]] und [[Euklid]], so im altfranzösischen ''[[Roman de la Rose]]'', während das altitalienische Gedicht ''[[Dante Alighieri#Fiore und Detto d’Amore|Il Fiore]]'' ihn sogar mit dem Erbauer des Schiffes [[Argo]] gleichsetzt, mit dem Jason sich auf die Suche nach dem Goldenen Vlies begab.

Auf der [[Volksetymologie|para-etymologischen]] Zurückführung des zweiten Bestandteils ''-rismus'' auf griech. {{lang|grc|ῥυσμός}}, {{lang|grc|ῥυθμός}} beruht dann auch die präzisierende lateinische Wortform ''algorithmus'', die seit der [[Frühe Neuzeit|Frühen Neuzeit]], anfangs auch mit der Schreibvariante ''algorythmus'', größere Verbreitung erlangte und zuletzt die heute übliche Wortbedeutung als Fachterminus für geregelte Prozeduren zur Lösung definierter Probleme annahm.

== Informatik und Mathematik {{Anker|Algorithmik}} ==
Algorithmen sind eines der zentralen Themen der [[Informatik]] und [[Mathematik]]. Sie sind Gegenstand einiger Spezialgebiete der [[Theoretische Informatik|Theoretischen Informatik]], der [[Komplexitätstheorie]] und der [[Berechenbarkeitstheorie]], mitunter ist ihnen ein eigener Fachbereich '''Algorithmik''' oder '''Algorithmentheorie''' gewidmet. In Form von [[Computerprogramm]]en und elektronischen [[Schaltkreis]]en steuern Algorithmen [[Computer]] und andere [[Maschine]]n.

=== Algorithmus und Programme ===
Für Algorithmen gibt es unterschiedliche formale Repräsentationen. Diese reichen vom Algorithmus als abstraktem Gegenstück zum konkret auf eine Maschine zugeschnittenen Programm (das heißt, die [[Abstraktion]] erfolgt hier im Weglassen der Details der realen Maschine, das Programm ist eine konkrete Form des Algorithmus, angepasst an die Notwendigkeiten und Möglichkeiten der realen Maschine) bis zur Ansicht, Algorithmen seien gerade die Maschinenprogramme von [[Turingmaschine]]n (wobei hier die Abstraktion in der Verwendung der Turingmaschine an sich erfolgt, das heißt, einer idealen [[Mathematische Maschine|mathematischen Maschine]]).

Algorithmen können in [[Programmablaufplan|Programmablaufplänen]] nach DIN 66001 oder [[ISO 5807]] grafisch dargestellt werden.

=== Erster Computeralgorithmus ===
Der erste für einen Computer gedachte Algorithmus (zur Berechnung von [[Bernoullizahlen]]) wurde 1843 von [[Ada Lovelace]] in ihren Notizen zu [[Charles Babbage]]s [[Analytical Engine]] festgehalten. Sie gilt deshalb als die erste [[Programmierer]]in. Weil Charles Babbage seine Analytical Engine nicht vollenden konnte, wurde Ada Lovelaces Algorithmus nie darauf implementiert.

=== Heutige Situation ===
[[Datei:Rete.svg|mini|Prinzipbild des [[Rete-Algorithmus]] für [[Expertensystem]]; veröffentlicht: 1979; [[gemeinfrei|frei]]]]

Algorithmen für Computer sind heute so vielfältig wie die Anwendungen, die sie ermöglichen sollen. Vom elektronischen [[Steuergerät]] für den Einsatz im KFZ über die Rechtschreib- und Satzbau-Kontrolle in einer [[Textverarbeitung]] bis hin zur Analyse von [[Aktienmarkt|Aktienmärkten]] finden sich tausende von Algorithmen. Hinsichtlich der Ideen und Grundsätze, die einem Computerprogramm zugrunde liegen, wird einem Algorithmus in der Regel [[Urheberrecht (Deutschland)|urheberrechtlicher Schutz]] versagt.<ref>Deutschland: {{§|69a|urhg|juris}} Abs. (2) UrhG.</ref> Je nach nationaler Ausgestaltung der Immaterialgüterrechte sind Algorithmen der Informatik jedoch dem [[Patent]]schutz zugänglich, so dass urheberrechtlich freie individuelle Werke, als Ergebnis eigener geistiger Schöpfung, wirtschaftlich trotzdem nicht immer frei verwertet werden können. Dies betrifft oder betraf z. B. Algorithmen, die auf der Mathematik der [[Hough-Transformation]] (Jahrzehnte alt, aber mehrfach aktualisiertes Konzept mit Neu-Anmeldung) aufbauen, Programme, die das Bildformat [[GIF]] lesen und schreiben wollten oder auch Programme im Bereich der Audio- und Video-Verarbeitung, da die zugehörigen Algorithmen, wie sie in den zugehörigen [[Codec]]s umgesetzt sind, oftmals nicht frei verfügbar sind. Die entsprechenden Einsparpotentiale für alle Anwender weltweit (für den [[Rete-Algorithmus]] wurde einst 1 Million USD auf [[DEC XCON]] genannt) dürften heute problemlos die Grenze von einer Milliarde USD im Jahr um ein zigfaches überschreiten.

== Definition ==
=== Turingmaschinen und Algorithmusbegriff ===
Die mangelnde mathematische Genauigkeit des Begriffs Algorithmus störte viele Mathematiker und Logiker des 19. und 20. Jahrhunderts, weswegen in der ersten Hälfte des 20. Jahrhunderts eine ganze Reihe von Ansätzen entwickelt wurde, die zu einer genauen Definition führen sollten. Formalisierungen des Berechenbarkeitsbegriffs sind die [[Turingmaschine]] ([[Alan Turing]]), [[Registermaschine]]n, der [[Lambda-Kalkül]] ([[Alonzo Church]]), [[rekursive Funktion]]en, Chomsky-Grammatiken (siehe [[Chomsky-Hierarchie]]) und [[Markow-Algorithmus|Markow-Algorithmen]].

Es wurde – unter maßgeblicher Beteiligung von Alan Turing selbst – gezeigt, dass all diese Methoden die gleiche Berechnungsstärke besitzen (gleich ''mächtig'' sind). Sie können durch eine Turingmaschine [[Emulation|emuliert]] werden, und sie können umgekehrt eine Turingmaschine emulieren.

Mit Hilfe des Begriffs der Turingmaschine kann folgende formale Definition des Begriffs formuliert werden:

''Eine Berechnungsvorschrift zur Lösung eines Problems heißt genau dann Algorithmus, wenn eine zu dieser Berechnungsvorschrift äquivalente Turingmaschine existiert, die für jede Eingabe, die eine Lösung besitzt, stoppt.''

Aus dieser Definition sind folgende Eigenschaften eines Algorithmus ableitbar:

# Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit).
# Jeder Schritt des Verfahrens muss tatsächlich ausführbar sein (Ausführbarkeit).
# Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit, siehe [[Platzkomplexität]]).
# Das Verfahren darf nur endlich viele Schritte benötigen ([[Terminiertheit|Terminierung]], siehe auch [[Zeitkomplexität]]).

Darüber hinaus wird der Begriff Algorithmus in praktischen Bereichen oft auf die folgenden Eigenschaften eingeschränkt:

# Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern ([[Determiniertheit (Algorithmus)|Determiniertheit]]).
# Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert ([[Determinismus (Algorithmus)|Determinismus]]).

=== Church-Turing-These ===
Die [[Church-Turing-These]] besagt, dass jedes intuitiv berechenbare Problem durch eine Turingmaschine gelöst werden kann. Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen, zu einer Turingmaschine äquivalenten Formalismus heran, insbesondere die Implementierbarkeit in einer [[Programmiersprache]] – die von Church verlangte [[Terminiertheit]] ist dadurch allerdings noch nicht gegeben.

Der Begriff der [[Berechenbarkeit]] ist dadurch dann so definiert, dass ein Problem [[Logische Äquivalenz|genau dann]] ''berechenbar'' ist, wenn es einen (terminierenden) Algorithmus zu dem Problem gibt, das heißt, wenn eine entsprechend programmierte Turingmaschine das Problem ''in endlicher Zeit'' lösen könnte.

=== Abstrakte Automaten ===
Turingmaschinen harmonieren gut mit den ebenfalls abstrakt-mathematischen [[Berechenbarkeit|berechenbaren Funktionen]], reale Probleme sind jedoch ungleich komplexer, daher wurden andere Maschinen vorgeschlagen.

Diese Maschinen weichen etwa in der Mächtigkeit der Befehle ab; statt der einfachen Operationen der Turingmaschine können sie teilweise mächtige Operationen, wie etwa [[Fourier-Transformation]]en, in einem Rechenschritt ausführen.

Oder sie beschränken sich nicht auf eine Operation pro Rechenschritt, sondern ermöglichen parallele Operationen, wie etwa die Addition zweier [[Vektor]]en in einem Schritt.

Ein Modell einer echten Maschine ist die ''{{lang|en|Sequential Abstract State Machine}}'' (kurz ''{{lang|en|seq. ASM}}'')<ref>[http://www.eecs.umich.edu/gasm/papers/seqthesis.html Sequential Abstract State Machine (seq. ASM)].</ref> mit folgenden Eigenschaften:

Ein Algorithmus einer seq. ASM soll
* durch einen endlichen Programmtext spezifiziert werden können
* schrittweise ausgeführt werden können
* für bestimmte Zustände terminieren, muss aber nicht immer terminieren (sinnvolle Gegenbeispiele für die Forderung, dass immer terminiert werden muss, wären etwa ein Programm, das fortgesetzt Primzahlen findet, oder ein Betriebssystem)
* nur begrenzt viele Zustände pro Schritt ändern können (Begrenzung der Parallelität)
* nur begrenzt viele Zustände pro Schritt inspizieren können (Begrenzung der Exploration).

== Eigenschaften ==
=== Determiniertheit ===
Ein Algorithmus ist [[Determiniertheit (Algorithmus)|determiniert]], wenn dieser bei jeder Ausführung mit gleichen Startbedingungen und Eingaben gleiche Ergebnisse liefert.

=== Determinismus ===
Ein Algorithmus ist [[Determinismus (Algorithmus)|deterministisch]], wenn zu jedem Zeitpunkt der Algorithmusausführung der nächste Handlungsschritt eindeutig definiert ist. Wenn an mindestens einer Stelle mehr als eine Möglichkeit besteht (ohne Vorgabe, welche zu wählen ist), dann ist der gesamte Algorithmus ''[[Nichtdeterminismus|nichtdeterministisch]]''.

Beispiele für deterministische Algorithmen sind [[Bubblesort]] und der [[Euklidischer Algorithmus|euklidische Algorithmus]]. Dabei gilt, dass jeder deterministische Algorithmus determiniert, während aber nicht jeder determinierte Algorithmus deterministisch ist. So ist [[Quicksort]] mit zufälliger Wahl des [[Pivotelement]]s ein Beispiel für einen determinierten, aber nicht deterministischen Algorithmus, da sein Ergebnis bei gleicher Eingabe und eindeutiger Sortierung immer dasselbe ist, der Weg dorthin jedoch zufällig erfolgt.

Nichtdeterministische Algorithmen können im Allgemeinen mit keiner realen Maschine (auch nicht mit [[Quantencomputer]]n) ''direkt'' umgesetzt werden.

Beispiel für einen nichtdeterministischen Algorithmus wäre ein Kochrezept, dass mehrere Varianten beschreibt. Es bleibt dem Koch überlassen, welche er durchführen möchte. Auch das Laufen durch einen [[Irrgarten]] lässt an jeder Verzweigung mehrere Möglichkeiten, und neben vielen Sackgassen können mehrere Wege zum Ausgang führen.

=== Finitheit ===
==== Statische Finitheit ====
Die Beschreibung des Algorithmus besitzt eine endliche Länge, der Quelltext muss also aus einer begrenzten Anzahl von Zeichen bestehen.

==== Dynamische Finitheit ====
Ein Algorithmus darf zu jedem Zeitpunkt seiner Ausführung nur begrenzt viel Speicherplatz benötigen.

==== Terminiertheit ====
Ein Algorithmus ‚[[Terminiertheit|terminiert überall]]‘ oder ‚ist terminierend‘, wenn er nach endlich vielen Schritten anhält (oder kontrolliert abbricht) – für jede mögliche Eingabe. Ein nicht-terminierender Algorithmus (somit zu keinem Ergebnis kommend) gerät (für manche Eingaben) in eine so genannte Endlosschleife.

Für manche Abläufe ist ein nicht-terminierendes Verhalten gewünscht: Z. B. Steuerungssysteme, Betriebssysteme und Programme, die auf Interaktion mit dem Benutzer aufbauen. Solange der Benutzer keinen Befehl zum Beenden eingibt, laufen diese Programme beabsichtigt endlos weiter. [[Donald E. Knuth]] schlägt in diesem Zusammenhang vor, nicht terminierende Algorithmen als rechnergestützte Methoden ''(Computational Methods)'' zu bezeichnen.

Darüber hinaus ist die Terminierung eines Algorithmus (das [[Halteproblem]]) nicht [[entscheidbar]]. Das heißt, das Problem, festzustellen, ob ein (beliebiger) Algorithmus mit einer beliebigen Eingabe terminiert, ist nicht durch einen Algorithmus lösbar.

=== Effektivität ===
Der Effekt jeder Anweisung eines Algorithmus muss eindeutig festgelegt sein.

=== Beispiele für (weitere) Eigenschaften von Algorithmen ===
* ''Einfache Grundoperation:'' „Öffne die Flasche Wein“ – hierbei wird das Wissen um das Öffnen vorausgesetzt.
* ''Sequentieller Algorithmus:'' „Bier auf Wein, lass das sein“ – beiden Operationen ist eine Reihenfolge vorgegeben.
* ''Nebenläufiger Algorithmus:'' „Schnaps und Bier“ – die Reihenfolge ist nicht vorgegeben und kann auch gleichzeitig erfolgen.
* ''Parallele Ausführung:'' „Mit Sekt anstoßen“ – dies kann nur gleichzeitig (parallel) ausgeführt werden und nicht hintereinander (sequentiell).
* ''Nichtdeterministischer/nichtdeterminierter Algorithmus:'' „Bier oder Wasser“ – das Ergebnis kann sich unterscheiden, je nachdem welches man wählt.

== Algorithmenanalyse ==
Die Erforschung und Analyse von Algorithmen ist eine Hauptaufgabe der Informatik, und wird meist theoretisch (ohne konkrete Umsetzung in eine Programmiersprache) durchgeführt. Sie ähnelt somit dem Vorgehen in anderen mathematischen Gebieten, in denen die Analyse eher auf die zugrunde liegenden Konzepte als auf konkrete Umsetzungen ausgerichtet ist. Algorithmen werden zur Analyse in eine stark formalisierte Form gebracht und mit den Mitteln der [[Formale Semantik|formalen Semantik]] untersucht.

Die Analyse unterteilt sich in verschiedene Teilgebiete. Beispielsweise wird das Verhalten von Algorithmen bezüglich Ressourcenbedarf wie [[Zeitkomplexität|Rechenzeit]] und Speicherbedarf in der [[Komplexitätstheorie]] behandelt; die Ergebnisse werden als [[asymptotische Laufzeit]]en angegeben. Der Ressourcenbedarf wird dabei in Abhängigkeit von der Länge der Eingabe ermittelt, das heißt, die angegebene Komplexität hängt davon ab, wie groß die Zahlen sind, deren [[größter gemeinsamer Teiler]] gesucht wird, oder wie viele Elemente [[Sortierverfahren|sortiert]] werden müssen etc.

Das Verhalten bezüglich der Terminierung, ob also der Algorithmus überhaupt jemals erfolgreich beendet werden kann, behandelt die [[Berechenbarkeitstheorie]].

== Typen und Beispiele ==
[[Datei:Tower of Hanoi.gif|miniatur|rechts|Die Lösung für das Spiel [[Türme von Hanoi]] mit drei Spielsteinen – ein einfacher Algorithmus]]

Der älteste bekannte nicht-triviale Algorithmus ist der [[Euklidischer Algorithmus|euklidische Algorithmus]]. Spezielle Algorithmus-Typen sind der [[Randomisierter Algorithmus|randomisierte Algorithmus]] (mit Zufallskomponente), der [[Approximationsalgorithmus]] (als Annäherungsverfahren), die [[Evolutionärer Algorithmus|evolutionären Algorithmen]] (nach biologischem Vorbild) und der [[Greedy-Algorithmus]].

Eine weitere Übersicht gibt die [[Liste von Algorithmen]] und die [[:Kategorie:Algorithmus|Kategorie Algorithmus]].

== Geschichte des Algorithmus ==
=== Antikes Griechenland ===
Obwohl der etymologische Ursprung des Wortes arabisch ist, entstanden die ersten Algorithmen im [[Antikes Griechenland|antiken Griechenland]]. Zu den wichtigsten Beispielen gehören das [[Sieb des Eratosthenes]] zum Auffinden von [[Primzahlen]], welches im Buch ''Einführung in die Arithmetik'' von [[Nikomachos von Gerasa|Nikomachos]] beschrieben wurde<ref>Roger L. Cooke: ''The History of Mathematics: A Brief Course'', Wiley 2005, S. 166.</ref> und der [[Euklidischer Algorithmus|euklidische Algorithmus]] zum Berechnen des [[Größter gemeinsamer Teiler|größten gemeinsamen Teilers]] zweier [[natürliche Zahl|natürlicher Zahlen]] aus dem Werk „[[Elemente (Euklid)|die Elemente]]“.<ref>http://aleph0.clarku.edu/~djoyce/elements/bookVII/propVII2.html</ref> Einer der ältesten Algorithmen, die sich mit einer [[reelle Zahl|reellen Zahl]] beschäftigen, ist der [[Auslöschung (numerische Mathematik)#Beispiel: Algorithmus des Archimedes zur Kreiszahlberechnung|Algorithmus des Archimedes]] zur Approximation von [[Kreiszahl|<math>\pi</math>]], was zugleich auch eines der ältesten [[numerische Mathematik|numerischen Verfahren]] ist.<ref>http://itech.fgcu.edu/faculty/clindsey/mhf4404/archimedes/archimedes.html.</ref>

=== Der Ursprung des Wortes ===
Das Wort Algorithmus stammt aus dem 9. Jahrhundert von dem [[Choresmier (Volk)|choresmischen]] Mathematiker [[Al-Chwarizmi]], der auf der Arbeit des aus dem 7. Jahrhundert stammenden indischen Mathematikers [[Brahmagupta]]<ref>http://www.andyborne.com/math/downloads/AL-Kwarazmi.pdf.</ref><ref>[http://www-groups.dcs.st-and.ac.uk/~history/Biographies/Brahmagupta.html Brahmagupta biography].</ref> aufbaute. In seiner ursprünglichen Bedeutung bezeichnete ein Algorithmus nur das Einhalten der [[arithmetik|arithmetischen Regeln]] unter Verwendung der [[Indische_Zahlschrift|indisch-arabischen Ziffern]]. Die ursprüngliche Definition entwickelte sich mit Übersetzung ins Lateinische weiter.<ref>{{Internetquelle|url=http://www.scriptol.com/programming/algorithm-history.php |titel=History of Algorithms and Algorithmics |werk=Scriptol.com |datum= |zugriff=2012-11-07}}</ref>

=== Mathematik im 19. und 20. Jahrhundert ===
Bedeutende Arbeit leisteten die Logiker des 19. Jahrhunderts.
[[George Boole]] der in seiner Schrift ''The Mathematical Analysis of Logic'' den ersten [[Kalkül|algebraischen Logikkalkül]] erschuf, begründete damit die moderne mathematische Logik, die sich von der traditionellen philosophischen Logik durch eine konsequente Formalisierung abhebt.<ref>[http://www.gutenberg.org/files/36884/36884-pdf.pdf?session_id=c32d51908145d828073340e0cf7c0d9a9290cd49 Project Gutenberg's The Mathematical Analysis of Logic, by George Boole].</ref>
[[Gottlob Frege]] entwickelte als erster eine [[formale Sprache]] und die daraus resultierenden [[Ableitung_(Logik)|formalen Beweise]].<ref>Gottlob Frege – Eine Einführung in sein Werk ([http://epub.uni-regensburg.de/12582/1/ubr05469_ocr.pdf PDF])</ref>
[[Giuseppe Peano]] reduzierte die Arithmetik auf eine Sequenz von Symbolen manipuliert von Symbolen. Er beschäftigte sich mit der Axiomatik der natürlichen Zahlen. Dabei entstanden die [[Peano-Axiome]].<ref>Peano: ''Arithmetices principia nova methodo exposita'', Turin 1889.</ref>

Die Arbeit von Frege wurde stark von [[Alfred North Whitehead]] und [[Bertrand Russell]] in ihrem Werk [[Principia Mathematica]] weiter ausgearbeitet und vereinfacht.<ref>http://name.umdl.umich.edu/AAT3201.0001.001 Principia Mathematica, 1. Auflage 1910-1913, in der Onlineversion der University of Michigan.</ref> Zuvor wurde von Bertrand Russell die berühmte [[russellsche Antinomie]] formuliert, was zum Einsturz der [[Naive Mengenlehre|naiven Mengenlehre]] führte. Das Resultat führte auch zur Arbeit [[Kurt Gödel]]s.

[[David Hilbert]] hat um 1928 das [[Entscheidungsproblem]] in seinem [[Hilbertprogramm|Forschungsprogramm]] präzise formuliert.<ref>Tapp, Christian: ''An den Grenzen des Endlichen. Das Hilbertprogramm im Kontext von Formalismus und Finitismus.'' Springer, Heidelberg 2013, ISBN 978-3-642-29654-3.</ref> [[Alan Turing]] und [[Alonzo Church]] haben für das Problem 1936 festgestellt, dass es unlösbar ist.<ref>cf. footnote in Alonzo Church 1936a in Davis 1965:90 and 1936b in Davis 1965:110.</ref>

== Literatur ==
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], [[Clifford Stein]]: ''Algorithmen. Eine Einführung.'' 2., korr. Auflage. Oldenbourg, München, Wien 2007, ISBN 3-486-58262-3 (Originaltitel: Introduction to algorithms. Übersetzt von Karen Lippert, Micaela Krieger-Hauwede).<br />Englischsprachige Originalausgabe: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7
* [[Christoph Drösser]]: ''Total berechenbar? Wenn Algorithmen für uns entscheiden'', [[Hanser-Verlag]], 2016, ISBN 978-3-44644-699-1.<ref>[[Dagmar Röhrlich]]: [http://www.deutschlandfunk.de/algorithmen-die-neue-weltmacht.740.de.html?dram:article_id=348892 ''Die neue Weltmacht.''] In: ''[[Deutschlandfunk.de]]'', ''[[Wissenschaft im Brennpunkt]]'', 20. März 2016, abgerufen am 28. März 2016</ref>
* {{BibISBN|3827370205}}
* [[Donald E. Knuth]]: ''[[The Art of Computer Programming]].'' Bd. 1–3. Addison Wesley, Reading (Mass.) 1998, ISBN 0-201-48541-9
* Anany Levitin: ''Introduction to The Design and Analysis of Algorithms.'' Addison Wesley, 2007, ISBN 0-321-36413-9
* Thomas Ottmann, Peter Widmayer: ''Algorithmen und Datenstrukturen.'' 4. Auflage. Spektrum Akademischer Verlag, Heidelberg 2002, ISBN 3-8274-1029-0
* Sebastian Stiller: ''Planet der Algorithmen – Ein Reiseführer''. [[Knaus-Verlag]], 2015. ISBN 978-3-641-16793-6
* Jochen Ziegenbalg, Oliver Ziegenbalg und Bernd Ziegenbalg: ''Zum Begriff des Algorithmus.'' In: ''Algorithmen von Hammurapi bis Gödel.'' 3. Auflage. Deutsch, Frankfurt 2010, ISBN 978-3-8171-1864-9, S. 24–31

== Externe Links ==
{{Wiktionary|Algorithmus}}
* [[Tom Schimmeck]]: [http://www.deutschlandfunk.de/algorithmen-im-us-justizsystem-schicksalsmaschinen.1247.de.html?dram:article_id=385478 ''Algorithmen im US-Justizsystem: Schicksalsmaschinen.''] In: ''[[deutschlandfunk.de]]'', 20. Juni 2017,
* [http://www-i1.informatik.rwth-aachen.de/~algorithmus/ Der Algorithmus der Woche] (Algorithmen anschaulich erklärt, herausgegeben vom Fakultätentag Informatik)
* [http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures] des [[NIST]] (englisch)
* [http://www.algo.informatik.tu-darmstadt.de/algorithmik/was-ist-algorithmik/ Was ist Algorithmik?] – Seite beim Fachbereich Informatik der ''[[Technische Universität Darmstadt|TU Darmstadt]]''
* [http://www.pnjb.de/uni/ws1011/hoehere-algorithmik.pdf Vorlesungsmitschrift Höhere Algorithmik der FU Berlin] (PDF; 1,9 MB)

== Einzelnachweise ==
<references responsive />

[[Kategorie:Algorithmus| ]]

← Nächstältere Version		Version vom 5. Mai 2018, 12:06 Uhr
Zeile 177:		Zeile 177:

	== Einzelnachweise ==		== Einzelnachweise ==
	<references ~~responsive~~ />		<references />

	[[Kategorie:Algorithmus\| ]]		[[Kategorie:Algorithmus\| ]]

Algorithmus - Versionsgeschichte

C1ph4 am 5. Mai 2018 um 10:06 Uhr

C1ph4: Die Seite wurde neu angelegt: „[[Al-Chwarizmi, der Namensgeber des ''Algorithmus'', auf einer sowjetischen…“