Algorithmusmathematik

Algorithmus, systematisches Verfahren, das in einer endlichen Anzahl von Schritten die Antwort auf eine Frage oder die Lösung eines Problems liefert. Der Name leitet sich von der lateinischen Übersetzung Algoritmi de numero Indorum der arithmetischen Abhandlung des muslimischen Mathematikers al-Khwarizmi aus dem 9. Jahrhundert „Al-Khwarizmi über die hinduistische Kunst der Abrechnung“ ab.

Informatik: Algorithmen und Komplexität

Ein Algorithmus ist ein spezifisches Verfahren zur Lösung eines genau definierten Rechenproblems. Die Entwicklung und Analyse von Algorithmen ist von grundlegender Bedeutung

Für Fragen oder Probleme mit nur einer endlichen Menge von Fällen oder Werten existiert immer ein Algorithmus (zumindest im Prinzip); Es besteht aus einer Wertetabelle der Antworten. Im Allgemeinen ist es kein so triviales Verfahren, Fragen oder Probleme zu beantworten, bei denen unendlich viele Fälle oder Werte zu berücksichtigen sind, z. B. „Ist die natürliche Zahl (1, 2, 3, …) eine Primzahl?“. oder "Was ist der größte gemeinsame Teiler der natürlichen Zahlen a und b?" Die erste dieser Fragen gehört zu einer Klasse, die als entscheidbar bezeichnet wird. Ein Algorithmus, der eine Ja- oder Nein-Antwort liefert, wird als Entscheidungsverfahren bezeichnet. Die zweite Frage gehört zu einer Klasse namens berechenbar; Ein Algorithmus, der zu einer bestimmten Zahlenantwort führt, wird als Berechnungsverfahren bezeichnet.

Algorithmen existieren für viele solcher unendlichen Klassen von Fragen; Euklids Elemente, die um 300 v. Chr. Veröffentlicht wurden, enthielten eines, um den größten gemeinsamen Teiler zweier natürlicher Zahlen zu finden. Jeder Grundschüler wird in einer langen Teilung gebohrt. Dies ist ein Algorithmus für die Frage: "Was sind der Quotient und der Rest, wenn eine natürliche Zahl a durch eine andere natürliche Zahl b geteilt wird?" Die Verwendung dieses Berechnungsverfahrens führt zur Antwort auf die entscheidbare Frage „Teilt b a?“. (Die Antwort lautet ja, wenn der Rest Null ist). Die wiederholte Anwendung dieser Algorithmen liefert schließlich die Antwort auf die entscheidende Frage „Ist eine Primzahl?“. (Die Antwort lautet nein, wenn a durch eine kleinere natürliche Zahl neben 1 teilbar ist).

Manchmal kann es keinen Algorithmus zum Lösen einer unendlichen Klasse von Problemen geben, insbesondere wenn die akzeptierte Methode weiter eingeschränkt wird. Zum Beispiel wurden zwei Probleme aus Euklids Zeit, die nur die Verwendung eines Kompasses und eines Lineals (nicht markiertes Lineal) erforderten - das Trennen eines Winkels und das Konstruieren eines Quadrats mit einer Fläche, die einem bestimmten Kreis entspricht - jahrhundertelang verfolgt, bevor sich herausstellte, dass sie unmöglich waren. Um die Wende des 20. Jahrhunderts schlug der einflussreiche deutsche Mathematiker David Hilbert 23 Probleme vor, die die Mathematiker im kommenden Jahrhundert lösen sollten. Das zweite Problem auf seiner Liste verlangte nach einer Untersuchung der Konsistenz der Axiome der Arithmetik. Die meisten Mathematiker hatten wenig Zweifel an der möglichen Erreichung dieses Ziels, bis der in Österreich geborene Logiker Kurt Gödel 1931 das überraschende Ergebnis zeigte, dass es arithmetische Sätze (oder Fragen) geben muss, die nicht bewiesen oder widerlegt werden können. Im Wesentlichen führt ein solcher Vorschlag zu einem Bestimmungsverfahren, das niemals endet (eine Bedingung, die als Stoppproblem bekannt ist). In dem erfolglosen Versuch, zumindest festzustellen, welche Sätze unlösbar sind, definierte der englische Mathematiker und Logiker Alan Turing das lose verstandene Konzept eines Algorithmus rigoros. Obwohl Turing letztendlich bewies, dass es unentscheidbare Aussagen geben muss, wurde seine Beschreibung der wesentlichen Merkmale einer Allzweckalgorithmusmaschine oder Turingmaschine zur Grundlage der Informatik. Heutzutage sind die Fragen der Entscheidbarkeit und Berechenbarkeit von zentraler Bedeutung für den Entwurf eines Computerprogramms - eines speziellen Algorithmus.