In der Mathematik und Informatik ist ein Algorithmus AL-gə-ridh-əm eine eindeutige Spezifikation zur Lösung einer Klasse von Problemen. Algorithmen können Berechnungen, Datenverarbeitung und automatisierte logische Aufgaben durchführen.

Als eine effektive Methode kann ein Algorithmus innerhalb einer endlichen Menge von Raum und Zeit und in einer wohldefinierten formalen Sprache zum Berechnen einer Funktion ausgedrückt werden. Ausgehend von einem Anfangszustand und einer Anfangseingabe (vielleicht leer) beschreiben die Anweisungen eine Berechnung, die, wenn sie ausgeführt wird, eine endliche Anzahl wohldefinierter aufeinanderfolgender Zustände durchläuft, die schließlich „Ausgabe“ erzeugt und bei einem endgültigen Endzustand endet. Der Übergang von einem Zustand zum nächsten ist nicht unbedingt deterministisch; Einige Algorithmen, die als randomisierte Algorithmen bekannt sind, enthalten Zufallseingaben.

Das Konzept des Algorithmus existiert seit Jahrhunderten und die Verwendung des Konzeptes kann griechischen Mathematikern zugeschrieben werden, zB das Sieb von Eratosthenes und Euklids Algorithmus; Der Begriff Algorithmus selbst stammt von dem Mathematiker Muḥammad ibn Mūsā al’Khwārizmī aus dem 9. Jahrhundert, latinisiert „Algoritmi“. Eine partielle Formalisierung dessen, was der moderne Algorithmusbegriff werden sollte, begann mit Versuchen, das Entscheidungsproblem von David Hilbert aus dem Jahr 1928 zu lösen. Nachfolgende Formalisierungen wurden als Versuche definiert, „effektive Berechenbarkeit“ oder „effektive Methode“ zu definieren. ; Zu diesen Formalisierungen gehörten die rekursiven Funktionen von Gödel-Herbrand-Kleene von 1930, 1934 und 1935, der Lambda-Kalkül von Alonzo Church von 1936, Emil Posts Formulierung 1 von 1936 und Alan Turings Turing-Maschinen von 1936-7 und 1939.

Etymologie
Das Wort „Algorithmus“ hat seinen Ursprung in der Latinisierung des Namens von Muhammad ibn Musa al-Khwarizmi in einem ersten Schritt zum Algorismus. Al-Khwārizmī (persisch: خوارزمی, ca. 780-850) war ein persischer Mathematiker, Astronom, Geograph und Gelehrter im Haus der Weisheit in Bagdad, dessen Name „der Eingeborene von Khwarezm“ bedeutet, eine Region, die Teil von Größerer Iran und ist jetzt in Usbekistan.

Um 825 verfasste Al-Khwarizmi eine arabischsprachige Abhandlung über das hindu-arabische Zahlensystem, die im 12. Jahrhundert unter dem Titel Algoritmi de numero Indorum ins Lateinische übersetzt wurde. Dieser Titel bedeutet „Algoritmi über die Zahlen der Indianer“, wobei „Algoritmi“ die Latinisierung des Übersetzers von Al-Khwarizmi war. Al-Khwarizmi war im späten Mittelalter der meistgelesene Mathematiker in Europa, vor allem durch ein anderes seiner Bücher, die Algebra. Im spätmittelalterlichen Latein bedeutete Algorismus, der englische „Algorismus“, die Verfälschung seines Namens, einfach das „Dezimalsystem“. Im 15. Jahrhundert, unter dem Einfluss des griechischen Wortes ἀριθμός „Zahl“ (vgl. „Arithmetik“), wurde das lateinische Wort in algorithmus geändert, und der entsprechende englische Begriff „Algorithmus“ wird erstmals im 17. Jahrhundert attestiert; Der moderne Sinn wurde im 19. Jahrhundert eingeführt.

In Englisch wurde es zuerst in ungefähr 1230 und dann von Chaucer 1391 verwendet. Englisch adoptierte den französischen Ausdruck, aber es war nicht bis Ende des 19. Jahrhunderts, dass „Algorithmus“ die Bedeutung nahm, die es im modernen Englisch hat.

Eine andere frühe Verwendung des Wortes ist von 1240, in einem Handbuch mit dem Titel Carmen de Algorismo von Alexandre de Villedieu komponiert. Es beginnt damit:

Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.

was übersetzt wie folgt:

Der Algorismus ist die Kunst, mit der wir zur Zeit die indischen Zahlen verwenden, die zwei mal fünf sind.

Das Gedicht ist ein paar hundert Zeilen lang und fasst die Kunst des Rechnens mit dem neuen Stil indischer Würfel oder Talibus Indorum oder Hindu-Zahlen zusammen.

Informelle Definition
Eine detaillierte Darstellung der verschiedenen Standpunkte zur Definition von „Algorithmus“ finden Sie unter Algorithmus-Charakterisierungen.
Eine informelle Definition könnte „eine Reihe von Regeln sein, die eine Abfolge von Operationen genau definieren“. Dazu gehören alle Computerprogramme, einschließlich Programme, die keine numerischen Berechnungen durchführen. Im Allgemeinen ist ein Programm nur ein Algorithmus, wenn es schließlich stoppt.

Ein prototypisches Beispiel für einen Algorithmus ist der Euklidische Algorithmus zur Bestimmung des maximalen gemeinsamen Teilers von zwei ganzen Zahlen; Ein Beispiel (es gibt andere) wird durch das obige Flussdiagramm und als ein Beispiel in einem späteren Abschnitt beschrieben.

Boolos, Jeffrey & 1974, 1999 bieten eine informelle Bedeutung des Wortes in dem folgenden Zitat:

Kein Mensch kann schnell genug schreiben, oder lang genug, oder klein genug † († „kleiner und kleiner ohne Grenzen … du würdest versuchen, auf Moleküle, auf Atome, auf Elektronen zu schreiben“), um alle Mitglieder eines aufzählbar unendlich setzen, indem sie ihre Namen nacheinander in einer Notation ausschreiben. Aber Menschen können etwas ebenso Nützliches tun, im Falle bestimmter aufzählbar unendlicher Mengen: Sie können explizite Anweisungen geben, um das n-te Mitglied der Menge für beliebige endliche n zu bestimmen. Solche Anweisungen sind in einer Form, in der sie von einer Rechenmaschine befolgt werden können, oder von einem Menschen, der in der Lage ist, nur sehr elementare Operationen an Symbolen durchzuführen, ganz explizit zu geben.

Eine „aufzählbar unendliche Menge“ ist eine, deren Elemente in Eins-zu-Eins-Entsprechung mit den ganzen Zahlen gesetzt werden können. So sagen Boolos und Jeffrey, dass ein Algorithmus Anweisungen für einen Prozess impliziert, der ausgegebene Ganzzahlen aus einer beliebigen „Eingabe“ -Integer oder ganzen Zahlen „erzeugt“, die theoretisch beliebig groß sein können. Somit kann ein Algorithmus eine algebraische Gleichung sein, wie etwa y = m + n – zwei beliebige „Eingangsvariablen“ m und n, die eine Ausgabe y erzeugen. Aber die Versuche verschiedener Autoren, den Begriff zu definieren, weisen darauf hin, dass das Wort viel mehr als das beinhaltet, etwas in der Größenordnung von (für das zusätzliche Beispiel):

Präzise Anweisungen (in Sprache, die von „dem Computer“ verstanden wird) für einen schnellen, effizienten, „guten“ Prozess, der die „Bewegungen“ des „Computers“ (Maschine oder Mensch, ausgestattet mit den notwendigen intern enthaltenen Informationen und Fähigkeiten) festlegt , dekodiere und verarbeite dann willkürliche eingegebene ganze Zahlen / Symbole m und n, Symbole + und = … und „produziere“ effektiv „output-integer y“ in einer „vernünftigen“ Zeit an einer spezifizierten Stelle und in einem spezifizierten Format.
Das Konzept des Algorithmus wird auch verwendet, um den Begriff der Entscheidungsfähigkeit zu definieren. Dieser Begriff ist von zentraler Bedeutung für die Erklärung, wie formale Systeme ausgehend von einer kleinen Anzahl von Axiomen und Regeln entstehen. In der Logik kann die Zeit, die ein Algorithmus benötigt, um zu vervollständigen, nicht gemessen werden, da er nicht offensichtlich mit unserer üblichen physischen Dimension verbunden ist. Aus solchen Unsicherheiten, die die laufende Arbeit kennzeichnen, ergibt sich die Nichtverfügbarkeit einer Definition des Algorithmus, die sowohl für die konkrete (in gewissem Sinne) als auch für die abstrakte Verwendung des Begriffs geeignet ist.

Formalisierung
Algorithmen sind essentiell für die Art und Weise, wie Computer Daten verarbeiten. Viele Computerprogramme enthalten Algorithmen, die die spezifischen Anweisungen aufführen, die ein Computer (in einer bestimmten Reihenfolge) ausführen soll, um eine bestimmte Aufgabe auszuführen, wie zum Beispiel die Gehaltsschecks der Angestellten zu berechnen oder die Zeugniskarten der Schüler auszudrucken. Somit kann ein Algorithmus als eine beliebige Abfolge von Operationen betrachtet werden, die von einem Turing-vollständigen System simuliert werden können. Autoren, die diese These behaupten, sind Minsky (1967), Savage (1987) und Gurevich (2000):

Minsky: „Aber wir werden auch mit Turing behaupten, dass jede Prozedur, die“ natürlich „als effektiv bezeichnet werden könnte, tatsächlich durch eine (einfache) Maschine realisiert werden kann. Obwohl dies extrem erscheinen mag, sind die Argumente seine Bevorzugung ist schwer zu widerlegen „.

Gurevich: „… Turings informelles Argument für seine These rechtfertigt eine stärkere These: Jeder Algorithmus kann durch eine Turing-Maschine simuliert werden … Laut Savage [1987] ist ein Algorithmus ein rechnerischer Prozess, der durch eine Turing-Maschine definiert wird“ .

Wenn ein Algorithmus mit Verarbeitungsinformationen verknüpft ist, können Daten typischerweise von einer Eingabequelle gelesen, in eine Ausgabevorrichtung geschrieben und für die weitere Verarbeitung gespeichert werden. Gespeicherte Daten werden als Teil des internen Zustands der Entität betrachtet, die den Algorithmus ausführt. In der Praxis wird der Zustand in einer oder mehreren Datenstrukturen gespeichert.

Für einen solchen Berechnungsprozess muss der Algorithmus streng definiert werden: spezifiziert in der Art und Weise, wie er in allen möglichen Umständen, die auftreten können, anwendbar ist. Das heißt, alle konditionellen Schritte müssen von Fall zu Fall systematisch behandelt werden; Die Kriterien für jeden Fall müssen klar (und berechenbar) sein.

Da ein Algorithmus eine präzise Liste präziser Schritte ist, ist die Reihenfolge der Berechnung immer entscheidend für das Funktionieren des Algorithmus. Es wird normalerweise angenommen, dass Anweisungen explizit aufgelistet werden und als „von oben“ und „nach unten“ beginnend beschrieben werden, eine Idee, die formaler durch den Kontrollfluss beschrieben wird.

Bis jetzt hat die Diskussion der Formalisierung eines Algorithmus die Prämissen der imperativen Programmierung angenommen. Dies ist die gebräuchlichste Konzeption, und sie versucht, eine Aufgabe in diskreten, „mechanischen“ Mitteln zu beschreiben. Einzigartig an dieser Konzeption von formalisierten Algorithmen ist die Zuweisungsoperation, die den Wert einer Variablen festlegt. Es kommt von der Intuition des „Gedächtnisses“ als Notizblock. Es gibt ein Beispiel für eine solche Aufgabe.

Für einige alternative Konzepte dessen, was einen Algorithmus ausmacht, siehe funktionale Programmierung und logische Programmierung.

Algorithmen ausdrücken
Algorithmen können in vielen Arten von Notationen ausgedrückt werden, einschließlich natürlicher Sprachen, Pseudocode, Flussdiagrammen, Drakon-Charts, Programmiersprachen oder Steuertabellen (die von Interpretern verarbeitet werden). Ausdrücke in natürlicher Sprache von Algorithmen tendieren dazu, ausführlich und mehrdeutig zu sein und werden selten für komplexe oder technische Algorithmen verwendet. Pseudocode, Flussdiagramme, Drakon-Diagramme und Steuertabellen sind strukturierte Wege, um Algorithmen auszudrücken, die viele der Mehrdeutigkeiten vermeiden, die in Aussagen natürlicher Sprache üblich sind. Programmiersprachen sind in erster Linie dazu gedacht, Algorithmen in einer Form auszudrücken, die von einem Computer ausgeführt werden kann, aber oft dazu verwendet wird, Algorithmen zu definieren oder zu dokumentieren.

Es ist eine Vielzahl von Darstellungen möglich, und man kann ein gegebenes Turing-Maschinenprogramm als eine Abfolge von Maschinentabellen (siehe mehr in Zustandsmaschine, Zustandsübergangstabelle und Steuertabelle), als Flussdiagramme und Drakon-Diagramme (siehe mehr unter Zustandsdiagramm) oder als eine Form von rudimentärem Maschinencode oder Assemblercode, die „Vierergruppen“ genannt werden (siehe mehr bei Turingmaschine).

Repräsentationen von Algorithmen können in drei akzeptierte Ebenen der Turing Maschinenbeschreibung eingeteilt werden:

1 Beschreibung auf hoher Ebene
„… Prosa, um einen Algorithmus zu beschreiben, die Implementierungsdetails ignorierend. Auf dieser Ebene müssen wir nicht erwähnen, wie die Maschine ihr Band oder ihren Kopf verwaltet.“
2 Beschreibung der Implementierung
„… Prosa definierte die Art und Weise, wie die Turing-Maschine ihren Kopf benutzt und wie sie Daten auf ihrem Band speichert. Auf dieser Ebene geben wir keine Details über Zustände oder Übergangsfunktionen an.“
3 Formale Beschreibung
Am detailliertesten, „niedrigste Ebene“, gibt die Turing-Maschine „Zustandstabelle“ an.
Für ein Beispiel des einfachen Algorithmus „Add m + n“, der in allen drei Ebenen beschrieben wird, siehe Algorithmus # Beispiele.

Implementierung
Die meisten Algorithmen sollen als Computerprogramme implementiert werden. Algorithmen werden jedoch auch auf andere Weise implementiert, beispielsweise in einem biologischen neuronalen Netzwerk (beispielsweise dem menschlichen Gehirn, das Arithmetik oder ein Insekt, das nach Nahrung sucht), in einem elektrischen Schaltkreis oder in einer mechanischen Vorrichtung.

Computeralgorithmen
In Computersystemen ist ein Algorithmus im Grunde eine Instanz von Logik, die von Softwareentwicklern in Software geschrieben wird, um für den / die beabsichtigten „Zielcomputer“ wirksam zu sein, Ausgabe von gegebener (möglicherweise Null) Eingabe zu erzeugen. Ein optimaler Algorithmus, der sogar in alter Hardware läuft, würde schnellere Ergebnisse liefern als ein nicht optimaler Algorithmus (höhere Zeitkomplexität) für denselben Zweck, der in effizienterer Hardware läuft; Aus diesem Grund gelten Algorithmen wie Computerhardware als Technologie.

„Elegante“ (kompakte) Programme, „gute“ (schnelle) Programme: Der Begriff „Einfachheit und Eleganz“ erscheint informell in Knuth und genau in Chaitin:

Knuth: „… Wir wollen gute Algorithmen in einem locker definierten ästhetischen Sinn. Ein Kriterium … ist die Länge der Zeit, die zur Ausführung des Algorithmus benötigt wird.“ Andere Kriterien sind die Anpassungsfähigkeit des Algorithmus an Computer, seine Einfachheit und Eleganz , etc“
Chaitin: „… ein Programm ist, elegant ‚, womit ich meine, dass es das kleinstmögliche Programm ist, um den Output zu produzieren, den es leistet.“
Chaitin stellt seiner Definition vor: „Ich werde zeigen, dass man nicht beweisen kann, dass ein Programm, elegant ‚ist“ – ein solcher Beweis würde das Halting-Problem lösen (ebd.).

Algorithmus gegen Funktion berechenbar durch einen Algorithmus: Für eine gegebene Funktion können mehrere Algorithmen existieren. Dies ist auch dann der Fall, wenn der verfügbare Befehlssatz für den Programmierer nicht erweitert wird. Rogers beobachtet, dass „es wichtig ist, zwischen dem Begriff des Algorithmus, dh der Prozedur, und dem Begriff der durch den Algorithmus berechenbaren Funktion zu unterscheiden, dh der Kartierung, die durch die Prozedur erzeugt wird. Die gleiche Funktion kann mehrere verschiedene Algorithmen haben.“

Leider kann es einen Kompromiss zwischen Güte (Geschwindigkeit) und Eleganz (Kompaktheit) geben – ein elegantes Programm kann mehr Schritte erfordern, um eine Berechnung zu vervollständigen als eine weniger elegant. Ein Beispiel, das den Euklid-Algorithmus verwendet, wird unten angezeigt.

Computer (und Computer), Modelle der Berechnung: Ein Computer (oder menschlicher „Computer“) ist eine eingeschränkte Art von Maschine, eine „diskrete deterministische mechanische Vorrichtung“, die blind ihren Anweisungen folgt. Melzaks und Lambeks primitive Modelle reduzierten diese Vorstellung auf vier Elemente: (i) diskrete, unterscheidbare Orte, (ii) diskrete, nicht unterscheidbare Zähler (iii) einen Agenten und (iv) eine Liste von Anweisungen, die relativ zur Fähigkeit des Agent.

Simulation eines Algorithmus: Computersprache (Computersprache): Knuth weist den Leser darauf hin, dass „der beste Weg, einen Algorithmus zu lernen, darin besteht, es zu versuchen … sofort Stift und Papier zu nehmen und ein Beispiel durchzuarbeiten“. Aber was ist mit einer Simulation oder Ausführung der realen Sache? Der Programmierer muss den Algorithmus in eine Sprache übersetzen, die der Simulator / Computer / Computer effektiv ausführen kann. Stone gibt ein Beispiel dafür: Wenn man die Wurzeln einer quadratischen Gleichung berechnet, muss der Computer-Experte wissen, wie man eine Quadratwurzel nimmt. Wenn dies nicht der Fall ist, muss der Algorithmus, um effektiv zu sein, einen Satz von Regeln zum Extrahieren einer Quadratwurzel bereitstellen.

Dies bedeutet, dass der Programmierer eine „Sprache“ kennen muss, die relativ zum Zielrechenagenten (Computer / Computer) wirksam ist.

Algorithmische Analyse
Es ist häufig wichtig zu wissen, wie viel von einer bestimmten Ressource (wie Zeit oder Speicher) theoretisch für einen bestimmten Algorithmus benötigt wird. Es wurden Methoden für die Analyse von Algorithmen entwickelt, um solche quantitativen Antworten (Schätzungen) zu erhalten. Zum Beispiel hat der obige Sortieralgorithmus eine Zeitanforderung von O (n), wobei die große O-Notation mit n als Länge der Liste verwendet wird. Der Algorithmus muss sich immer nur zwei Werte merken: die bisher größte und die aktuelle Position in der Eingabeliste. Daher wird gesagt, dass es einen Platzbedarf von O (1) hat, wenn der Platz, der benötigt wird, um die eingegebenen Zahlen zu speichern, nicht gezählt wird, oder O (n), wenn er gezählt wird.

Formal gegen empirisch
Die Analyse und das Studium von Algorithmen ist eine Disziplin der Informatik und wird oft abstrakt ohne den Gebrauch einer spezifischen Programmiersprache oder Implementierung praktiziert. In diesem Sinne ähnelt die Algorithmusanalyse anderen mathematischen Disziplinen insofern, als sie sich auf die zugrundeliegenden Eigenschaften des Algorithmus und nicht auf die Besonderheiten einer bestimmten Implementierung konzentriert. Normalerweise wird Pseudocode für die Analyse verwendet, da es die einfachste und allgemeinste Darstellung ist. Letztlich werden die meisten Algorithmen jedoch üblicherweise auf bestimmten Hardware / Software-Plattformen implementiert und ihre algorithmische Effizienz wird schließlich unter Verwendung von echtem Code auf den Prüfstand gestellt. Für die Lösung eines „Einmal“ -Problems mag die Effizienz eines bestimmten Algorithmus keine signifikanten Konsequenzen haben (es sei denn, n ist extrem groß), aber für Algorithmen, die für eine schnelle interaktive, kommerzielle oder lange Lebensdauer ausgelegt sind, kann es kritisch sein. Die Skalierung von kleinen n zu großen n legt häufig ineffiziente Algorithmen offen, die ansonsten gutartig sind.

Effizienz bei der Ausführung
Um die möglichen Verbesserungen, die selbst in gut etablierten Algorithmen möglich sind, zu veranschaulichen, kann eine kürzliche signifikante Innovation, die sich auf FFT-Algorithmen (im Bereich der Bildverarbeitung) bezieht, die Verarbeitungszeit für Anwendungen wie die medizinische Bildgebung um bis zu 1000 reduzieren. Im Allgemeinen hängen Geschwindigkeitsverbesserungen von speziellen Eigenschaften des Problems ab, die in praktischen Anwendungen sehr häufig sind. Beschleunigungen dieser Größenordnung ermöglichen es Computern, die die Bildverarbeitung ausgiebig nutzen (wie Digitalkameras und medizinische Geräte), weniger Strom zu verbrauchen.

Einstufung
Es gibt verschiedene Möglichkeiten, Algorithmen mit jeweils eigenen Vorteilen zu klassifizieren.

Durch die Implementierung
Eine Möglichkeit, Algorithmen zu klassifizieren, sind Implementierungsmittel.

Rekursion
Ein rekursiver Algorithmus ist einer, der sich selbst wiederholt aufruft (sich darauf bezieht), bis eine bestimmte Bedingung (auch als Beendigungsbedingung bekannt) übereinstimmt, die eine für die funktionale Programmierung übliche Methode ist. Iterative Algorithmen verwenden repetitive Konstrukte wie Schleifen und manchmal zusätzliche Datenstrukturen wie Stapel, um die gegebenen Probleme zu lösen. Einige Probleme sind natürlich für die eine oder die andere Implementierung geeignet. Zum Beispiel ist Türme von Hanoi gut verstanden unter Verwendung rekursiver Implementierung. Jede rekursive Version hat eine äquivalente (aber möglicherweise mehr oder weniger komplexe) iterative Version und umgekehrt.

Logisch
Ein Algorithmus kann als kontrollierte logische Ableitung angesehen werden. Dieser Begriff kann ausgedrückt werden als: Algorithmus = Logik + Kontrolle. Die Logikkomponente drückt die Axiome aus, die bei der Berechnung verwendet werden können, und die Steuerkomponente bestimmt die Art und Weise, in der die Ableitung auf die Axiome angewendet wird. Dies ist die Grundlage für das Logikprogrammierungsparadigma. In reinen Logik-Programmiersprachen ist die Steuerungskomponente festgelegt und Algorithmen werden spezifiziert, indem nur die Logikkomponente bereitgestellt wird. Die Attraktivität dieses Ansatzes ist die elegante Semantik: Eine Änderung der Axiome hat eine wohldefinierte Veränderung des Algorithmus.

Seriell, parallel oder verteilt
Algorithmen werden normalerweise mit der Annahme diskutiert, dass Computer jeweils einen Befehl eines Algorithmus ausführen. Diese Computer werden manchmal als serielle Computer bezeichnet. Ein für eine solche Umgebung entwickelter Algorithmus wird im Gegensatz zu parallelen Algorithmen oder verteilten Algorithmen als serieller Algorithmus bezeichnet. Parallele Algorithmen nutzen Computerarchitekturen, bei denen mehrere Prozessoren gleichzeitig an einem Problem arbeiten können, während verteilte Algorithmen mehrere mit einem Computernetzwerk verbundene Maschinen verwenden. Parallele oder verteilte Algorithmen teilen das Problem in mehr symmetrische oder asymmetrische Teilprobleme auf und sammeln die Ergebnisse wieder zusammen. Der Ressourcenverbrauch in solchen Algorithmen ist nicht nur Prozessorzyklen auf jedem Prozessor, sondern auch der Kommunikationsaufwand zwischen den Prozessoren. Einige Sortieralgorithmen können effizient parallelisiert werden, aber ihr Kommunikationsaufwand ist teuer. Iterative Algorithmen sind im Allgemeinen parallelisierbar. Einige Probleme haben keine parallelen Algorithmen und werden inhärent serielle Probleme genannt.

Deterministisch oder nicht-deterministisch
Deterministische Algorithmen lösen das Problem mit einer genauen Entscheidung bei jedem Schritt des Algorithmus, während nicht-deterministische Algorithmen Probleme durch Raten lösen, obwohl typische Annahmen durch die Verwendung von Heuristiken genauer gemacht werden.

Genau oder ungefähr
Während viele Algorithmen eine exakte Lösung erreichen, suchen Approximationsalgorithmen nach einer Approximation, die näher an der wahren Lösung liegt. Die Annäherung kann entweder durch Verwendung einer deterministischen oder einer zufälligen Strategie erreicht werden. Solche Algorithmen haben praktischen Wert für viele schwierige Probleme. Eines der Beispiele für einen ungefähren Algorithmus ist das Knapsack-Problem. Das Knapsack-Problem ist ein Problem, bei dem bestimmte Elemente vorhanden sind. Das Ziel des Problems ist, den Rucksack zu packen, um den maximalen Gesamtwert zu erhalten. Jeder Gegenstand hat ein gewisses Gewicht und einen gewissen Wert. Das Gesamtgewicht, das wir tragen können, ist nicht mehr als eine feste Zahl X. Also müssen wir Gewichtungen von Gegenständen sowie ihren Wert berücksichtigen.

Quantenalgorithmus
Sie laufen auf einem realistischen Modell der Quantenberechnung. Der Begriff wird normalerweise für jene Algorithmen verwendet, die von Natur aus Quanten sind, oder ein wesentliches Merkmal der Quantenberechnung wie Quantenüberlagerung oder Quantenverschränkung verwenden.

Nach dem Design-Paradigma
Eine andere Möglichkeit, Algorithmen zu klassifizieren, ist ihre Entwurfsmethodik oder ihr Paradigma. Es gibt eine gewisse Anzahl von Paradigmen, die sich voneinander unterscheiden. Darüber hinaus enthält jede dieser Kategorien viele verschiedene Arten von Algorithmen. Einige gängige Paradigmen sind:

Brute-Force oder erschöpfende Suche
Dies ist die naive Methode, jede mögliche Lösung auszuprobieren, um zu sehen, welches das beste ist.

Teilen und erobern
Ein Divide and Conquer-Algorithmus reduziert wiederholt eine Instanz eines Problems auf eine oder mehrere kleinere Instanzen des gleichen Problems (normalerweise rekursiv), bis die Instanzen klein genug sind, um sie leicht zu lösen. Ein solches Beispiel für „Teile und herrsche“ ist die Mergesortierung. Die Sortierung kann für jedes Datensegment durchgeführt werden, nachdem Daten in Segmente unterteilt wurden, und das Sortieren von ganzen Daten kann in der Eroberungsphase durch Zusammenführen der Segmente erhalten werden. Eine einfachere Variante von Divide and Conquer nennt man einen Sink and Conquer-Algorithmus, der ein identisches Teilproblem löst und die Lösung dieses Teilproblems nutzt, um das größere Problem zu lösen. Divide and Conquer teilt das Problem in mehrere Teilprobleme auf, und so ist die Phase des Eroberens komplexer als Algorithmen zum Verringern und Überwinden. Ein Beispiel für den Algorithmus zum Verringern und Überwinden ist der binäre Suchalgorithmus.

Suche und Aufzählung
Viele Probleme (wie Schach spielen) können als Probleme in Graphen modelliert werden. Ein Graph-Explorationsalgorithmus spezifiziert Regeln zum Bewegen um einen Graphen und ist für solche Probleme nützlich. Diese Kategorie umfasst auch Suchalgorithmen, Verzweigungs- und Begrenzungsaufzählung und Rückverfolgung.
Randomisierter Algorithmus

Reduzierung der Komplexität
Diese Technik beinhaltet die Lösung eines schwierigen Problems, indem es in ein bekannteres Problem transformiert wird, für das wir (hoffentlich) asymptotisch optimale Algorithmen haben. Ziel ist es, einen Reduktionsalgorithmus zu finden, dessen Komplexität nicht von den resultierenden reduzierten Algorithmen dominiert wird. Zum Beispiel beinhaltet ein Auswahlalgorithmus zum Auffinden des Medians in einer unsortierten Liste zuerst das Sortieren der Liste (des teuren Teils) und dann das Herausziehen des mittleren Elements in der sortierten Liste (des billigen Teils). Diese Technik wird auch als transform and conquer bezeichnet.

Optimierungsprobleme
Für Optimierungsprobleme gibt es eine spezifischere Klassifizierung von Algorithmen; Ein Algorithmus für solche Probleme kann in eine oder mehrere der oben beschriebenen allgemeinen Kategorien sowie in eine der folgenden fallen:

Lineares Programmieren
Bei der Suche nach optimalen Lösungen für eine lineare Funktion, die an lineare Gleichheits- und Ungleichheitsbedingungen gebunden ist, können die Einschränkungen des Problems direkt bei der Erzeugung der optimalen Lösungen verwendet werden. Es gibt Algorithmen, die jedes Problem in dieser Kategorie lösen können, wie zum Beispiel der populäre Simplex-Algorithmus. Probleme, die mit linearer Programmierung gelöst werden können, umfassen das maximale Strömungsproblem für gerichtete Graphen. Wenn ein Problem zusätzlich erfordert, dass eine oder mehrere der Unbekannten eine ganze Zahl sein müssen, wird sie in ganzzahlige Programmierung klassifiziert. Ein linearer Programmieralgorithmus kann ein solches Problem lösen, wenn bewiesen werden kann, dass alle Beschränkungen für ganzzahlige Werte oberflächlich sind, dh die Lösungen diese Beschränkungen auf jeden Fall erfüllen. Im allgemeinen Fall wird ein spezieller Algorithmus oder ein Algorithmus, der ungefähre Lösungen findet, abhängig von der Schwierigkeit des Problems verwendet.
Dynamische Programmierung

Wenn ein Problem optimale Substrukturen zeigt – dh die optimale Lösung eines Problems kann aus optimalen Lösungen für Teilprobleme aufgebaut werden – und überlappende Teilprobleme, dh dieselben Subprobleme werden zur Lösung vieler verschiedener Problemfälle verwendet, vermeidet ein schnellerer Ansatz namens dynamische Programmierung die Neuberechnung von Lösungen wurden bereits berechnet. Zum Beispiel kann der Floyd-Warshall-Algorithmus den kürzesten Weg zu einem Ziel von einem Eckpunkt in einem gewichteten Graphen finden, indem der kürzeste Pfad zum Ziel von allen benachbarten Eckpunkten verwendet wird. Dynamische Programmierung und Memoisierung gehören zusammen. Der Hauptunterschied zwischen dynamischer Programmierung und Teile und herrsche ist, dass Teilprobleme mehr oder weniger unabhängig voneinander sind, während Teilprobleme sich in der dynamischen Programmierung überschneiden. Der Unterschied zwischen dynamischer Programmierung und einfacher Rekursion liegt im Caching oder Memoisieren rekursiver Aufrufe. Wenn Teilprobleme unabhängig sind und es keine Wiederholung gibt, hilft Memoisierung nicht; Daher ist dynamische Programmierung keine Lösung für alle komplexen Probleme. Durch die Verwendung von Memoization oder die Beibehaltung einer Tabelle von bereits gelösten Teilproblemen reduziert die dynamische Programmierung die exponentielle Natur vieler Probleme auf die Polynomkomplexität.

Die gierige Methode
Ein Greedy-Algorithmus ähnelt insofern einem dynamischen Programmieralgorithmus, als er Substrukturen untersucht, in diesem Fall nicht das Problem, sondern eine gegebene Lösung. Solche Algorithmen beginnen mit einer Lösung, die gegeben oder konstruiert worden ist, und verbessern sie durch kleine Modifikationen. Für einige Probleme können sie die optimale Lösung finden, während sie für andere bei lokalen Optima stehen, dh bei Lösungen, die nicht durch den Algorithmus verbessert werden können, aber nicht optimal sind. Die beliebteste Verwendung von Greedy-Algorithmen besteht darin, den minimalen Spannbaum zu finden, bei dem das Finden der optimalen Lösung mit dieser Methode möglich ist. Huffman Tree, Kruskal, Prim, Sollin sind gierige Algorithmen, die dieses Optimierungsproblem lösen können.

Die heuristische Methode
Bei Optimierungsproblemen können heuristische Algorithmen verwendet werden, um eine Lösung zu finden, die der optimalen Lösung nahe kommt, wenn das Finden der optimalen Lösung unpraktisch ist. Diese Algorithmen arbeiten, indem sie bei ihrem Fortschreiten immer näher zur optimalen Lösung kommen. Wenn sie für eine unbegrenzte Zeit laufen, finden sie im Prinzip die optimale Lösung. Ihr Vorteil ist, dass sie in relativ kurzer Zeit eine Lösung finden, die der optimalen Lösung sehr nahe kommt. Solche Algorithmen umfassen lokale Suche, Tabu-Suche, simuliertes Annealing und genetische Algorithmen. Einige von ihnen, wie Simulated Annealing, sind nicht-deterministische Algorithmen, während andere, wie die Tabu-Suche, deterministisch sind. Wenn eine Grenze für den Fehler der nicht optimalen Lösung bekannt ist, wird der Algorithmus weiter als Approximationsalgorithmus kategorisiert.

Nach Studienrichtung
Jedes Wissenschaftsgebiet hat seine eigenen Probleme und braucht effiziente Algorithmen. Verwandte Probleme in einem Bereich werden oft zusammen untersucht. Einige Beispielklassen sind Suchalgorithmen, Sortieralgorithmen, Mischalgorithmen, numerische Algorithmen, Graphalgorithmen, Stringalgorithmen, computergestützte geometrische Algorithmen, kombinatorische Algorithmen, medizinische Algorithmen, maschinelles Lernen, Kryptographie, Datenkomprimierungsalgorithmen und Analysetechniken.

Felder tendieren dazu, einander zu überlappen, und Algorithmusfortschritte in einem Feld können diejenigen von anderen, manchmal völlig nicht verwandten Feldern verbessern. Zum Beispiel wurde die dynamische Programmierung für die Optimierung des Ressourcenverbrauchs in der Industrie erfunden, wird aber nun verwendet, um eine breite Palette von Problemen in vielen Bereichen zu lösen.

Durch Komplexität
Algorithmen können nach der Zeit klassifiziert werden, die sie im Vergleich zu ihrer Eingabegröße benötigen:

Konstante Zeit: Wenn die vom Algorithmus benötigte Zeit gleich ist, unabhängig von der Eingabegröße. ZB ein Zugriff auf ein Array-Element.
Linearzeit: wenn die Zeit proportional zur Eingabegröße ist. ZB der Durchlauf einer Liste.
Logarithmische Zeit: wenn die Zeit eine logarithmische Funktion der Eingabegröße ist. ZB binärer Suchalgorithmus.
Polynomialzeit: Wenn die Zeit eine Potenz der Eingabegröße ist. ZB hat der Blasensortieralgorithmus eine quadratische Zeitkomplexität.
Exponentialzeit: Wenn die Zeit eine Exponentialfunktion der Eingabegröße ist. ZB Brute-Force-Suche.
Einige Probleme können mehrere Algorithmen unterschiedlicher Komplexität aufweisen, während andere Probleme keine Algorithmen oder keine bekannten effizienten Algorithmen aufweisen. Es gibt auch Zuordnungen von einigen Problemen zu anderen Problemen. Aufgrund dessen wurde gefunden, dass es besser ist, die Probleme selbst anstelle der Algorithmen in Äquivalenzklassen zu klassifizieren, basierend auf der Komplexität der bestmöglichen Algorithmen für sie.

Kontinuierliche Algorithmen
Das Adjektiv „fortlaufend“, wenn es auf das Wort „Algorithmus“ angewendet wird, kann bedeuten:

Ein Algorithmus, der mit Daten arbeitet, die kontinuierliche Größen darstellen, obwohl diese Daten durch diskrete Näherungen dargestellt werden – solche Algorithmen werden in der numerischen Analyse untersucht; oder
Ein Algorithmus in Form einer Differentialgleichung, die kontinuierlich auf den Daten läuft und auf einem analogen Computer läuft.