Was ist eine Liste der acht Arten von Algorithmen?

Beste Antwort

Klassifizierung nach Zweck

Jeder Algorithmus hat ein Ziel. Der Zweck des Schnellsortierungsalgorithmus besteht beispielsweise darin, Daten in aufsteigender oder absteigender Reihenfolge zu sortieren. Die Anzahl der Ziele ist jedoch unendlich, und wir müssen sie nach verschiedenen Zwecken gruppieren.

Klassifizierung nach Implementierung

Ein Algorithmus kann nach verschiedenen Grundprinzipien implementiert werden.

• Rekursiv oder iterativ Ein rekursiver Algorithmus ruft sich wiederholt auf, bis eine bestimmte Bedingung erfüllt ist. Es ist eine Methode, die der funktionalen Programmierung gemeinsam ist. Iterative Algorithmen verwenden sich wiederholende Konstrukte wie Schleifen. Einige Probleme eignen sich besser für die eine oder andere Implementierung. Zum Beispiel sind die Türme des Hanoi-Problems in der rekursiven Implementierung gut verstanden. Jede rekursive Version hat ein iteratives Äquivalent iterativ und umgekehrt.
• Logisch oder prozedural Ein Algorithmus kann als kontrollierte logische Ableitung angesehen werden. Eine Logikkomponente drückt die Axiome aus, die bei der Berechnung verwendet werden können, und eine Steuerkomponente bestimmt die Art und Weise, wie der Abzug auf die Axiome angewendet wird. Dies ist die Basis der Logikprogrammierung. In reinen Logikprogrammiersprachen ist die Steuerkomponente fest und Algorithmen werden nur durch Angabe der Logikkomponente angegeben.
• Seriell oder parallele Algorithmen werden normalerweise unter der Annahme diskutiert, dass Computer jeweils einen Befehl eines Algorithmus ausführen. Dies ist ein serieller Algorithmus im Gegensatz zu parallelen Algorithmen, die Computerarchitekturen nutzen, um mehrere Anweisungen gleichzeitig zu verarbeiten. Sie unterteilen das Problem in Unterprobleme und geben sie an mehrere Prozessoren weiter. Iterative Algorithmen sind im Allgemeinen parallelisierbar. Sortieralgorithmen können effizient parallelisiert werden.
• Deterministisch oder nicht deterministisch Deterministische Algorithmen lösen das Problem mit einem vordefinierten Prozess, während nicht deterministische Algorithmen bei jedem Schritt mithilfe der Heuristik die beste Lösung erraten müssen.

Klassifizierung nach Entwurfsparadigma

Ein Entwurfsparadigma ist eine Domäne in der Forschung oder in einer Klasse von Problemen, die einen speziellen Algorithmus erfordert:

• Teilen und Erobern Ein Algorithmus zum Teilen und Erobern reduziert eine Instanz eines Problems wiederholt auf eine oder mehrere kleinere Instanzen desselben Problems (normalerweise rekursiv), bis die Instanzen klein genug sind leicht zu lösen. Ein solches Beispiel für Teilen und Erobern ist das Zusammenführen von Sortierungen. Das Sortieren kann für jedes Datensegment erfolgen, nachdem die Daten in Segmente unterteilt wurden, und das Sortieren ganzer Daten kann in der Eroberungsphase durch Zusammenführen dieser Daten erfolgen. Der binäre Suchalgorithmus ist ein Beispiel für eine Variante von Teilen und Erobern mit dem Namen Verringern und Erobern des Algorithmus , die ein identisches Teilproblem löst und die Lösung dieses Teilproblems zur Lösung verwendet das größere Problem.
• Dynamische Programmierung Der kürzeste Pfad in einem gewichteten Diagramm kann gefunden werden, indem der kürzeste Pfad zum Ziel von allen Nachbarn verwendet wird Eckpunkte. Wenn die optimale Lösung für ein Problem aus optimalen Lösungen für Teilprobleme konstruiert werden kann, wird durch die Verwendung der dynamischen Programmierung vermieden, dass bereits berechnete Lösungen neu berechnet werden. – Der Hauptunterschied zum „Teilen und Erobern“ -Ansatz besteht darin, dass Teilprobleme beim Teilen und Erobern unabhängig sind, wobei die Überlappung von Teilproblemen bei der dynamischen Programmierung auftritt. – Dynamische Programmierung und Memoisierung gehören zusammen. Der Unterschied zur einfachen Rekursion besteht im Zwischenspeichern oder Speichern von rekursiven Aufrufen. Wenn Teilprobleme unabhängig sind, ist dies nutzlos. Durch die Verwendung von Memoization oder die Pflege einer Tabelle bereits gelöster Teilprobleme reduziert die dynamische Programmierung die Exponentialität vieler Probleme auf die Polynomkomplexität.
• Die gierige Methode Ein Greedy-Algorithmus ähnelt einem dynamischen Programmieralgorithmus, der Unterschied besteht jedoch darin, dass Lösungen für die Teilprobleme nicht in jeder Phase bekannt sein müssen. Stattdessen kann eine „gierige“ Wahl getroffen werden, welche für den Moment die beste Lösung darstellt. Der beliebteste gierige Algorithmus ist das Finden des von Kruskal angegebenen minimalen Spannbaums.
• Lineare Programmierung Das Problem wird als linearer Satz ausgedrückt Ungleichungen und dann wird versucht, die Eingaben zu maximieren oder zu minimieren. Dies kann viele Probleme lösen, wie beispielsweise den maximalen Fluss für gerichtete Graphen, insbesondere unter Verwendung des Simplex-Algorithmus.Eine komplexe Variante der linearen Programmierung wird als Ganzzahlprogrammierung bezeichnet, bei der der Lösungsraum auf alle Ganzzahlen beschränkt ist.
• Reduktion wird auch als transformieren und erobern Lösen Sie ein Problem, indem Sie es in ein anderes Problem umwandeln. Ein einfaches Beispiel: Wenn Sie den Median in einer unsortierten Liste finden, wird dieses Problem zunächst in ein Sortierproblem übersetzt und das mittlere Element in einer sortierten Liste gefunden. Das Hauptziel der Reduzierung besteht darin, eine möglichst einfache Transformation zu finden.
• Verwenden von Diagrammen Viele Probleme, wie z. B. Schach spielen, können als Probleme modelliert werden auf Grafiken. Es werden Algorithmen zur Exploration von Graphen verwendet. Diese Kategorie umfasst auch die Suchalgorithmen und das Backtracking.
• Das probabilistische und heuristische Paradigma Probabilistisch Diejenigen, die zufällig eine Auswahl treffen. Genetic Versuchen Sie, Lösungen für Probleme zu finden, indem Sie biologische Evolutionsprozesse nachahmen, wobei ein Zyklus zufälliger Mutationen aufeinanderfolgende Generationen von „Lösungen“ ergibt. So emulieren sie die Fortpflanzung und das „Überleben der Stärksten“. Heuristik Der allgemeine Zweck besteht nicht darin, eine optimale Lösung zu finden, sondern eine ungefähre Lösung, bei der die Zeit oder die Ressourcen für die Suche nach einer perfekten Lösung nicht praktikabel sind.

Klassifizierung nach Komplexität

Einige Algorithmen werden in linearer Zeit und andere in exponentieller Zeit abgeschlossen Einige werden nie abgeschlossen.

Quelle: Klassifizierung von Algorithmen

Überwachtes Lernen: Klassifizierung

Antwort

Das Folgende ist eine andere Möglichkeit, Algorithmen zu klassifizieren.

Bei der Wettbewerbsprogrammierung gibt es 4 Hauptprobleme: Lösen von Paradigmen.

Mit anderen Worten, angesichts eines Problems sind hier die verschiedenen Ansätze / Werkzeuge aufgeführt, die Sie zur Lösung des Problems verwenden sollten.

1. Brute Force / Vollständige Suche: Eine Methode, die alle Möglichkeiten untersucht und die beste Lösung auswählt.
2. Vorteile: einfach, sollte immer die Lösung finden, da Sie alle Möglichkeiten prüfen.
3. Nachteile : als undurchführbar Die Anzahl der Möglichkeiten nimmt exponentiell zu, wenn die Anzahl der Elemente zunimmt.
4. Teilen und Erobern: Methode, die das Problem in kleinere Teile unterteilt und diese dann löst Teile. Denken Sie an die binäre Suche.
5. Gieriger Ansatz: Methode, die zum gegenwärtigen Zeitpunkt die beste Option auswählt, ohne Rücksicht auf die Zukunft.
6. Vorteile: schnell, einfach, kann die beste Lösung erhalten oder ein bisschen näher kommen
7. Nachteile: Meistens erhalten wir nicht die beste Lösung
8. Dynamische Programmierung: Methode, die unter Verwendung zuvor gefundener Unterlösungen zu einer Lösung aufbaut. Auf jeden Fall eine der fortschrittlicheren Techniken, aber äußerst leistungsfähig und anwendbar.
9. Vorteile: findet die optimale Lösung für viele Probleme in der Polynomzeit ( während Brute Force exponentiell sein würde)
10. Nachteile : schwer zu erfassen und anzuwenden, braucht Zeit, um die verschiedenen Zustände und Wiederholungen zu verstehen

Quellen

Halim, Steven und Felix Halim. Wettbewerbsfähige Programmierung: Die neue Untergrenze von Programmierwettbewerben . Lulu, 2013.