Liste von Algorithmen

Grundlegende Einteilungen

Die Seite ist eine Übersicht über Artikel zu Algorithmen, also genau festgelegten Verfahren zur Lösung von Problemen. Sie ordnet Algorithmen nach verschiedenen Gesichtspunkten.

Bei der Komplexität wird zwischen Platzkomplexität und Zeitkomplexität unterschieden. Die Platzkomplexität beschreibt den benötigten Speicher, die Zeitkomplexität den benötigten Rechenaufwand. Genannt werden jeweils linear, logarithmisch, polynomial und exponentiell platz- beziehungsweise zeitbeschränkte Algorithmen.

Nach den Maschinenfähigkeiten gibt es deterministische und nicht-deterministische Algorithmen, quantenmechanische und randomisierte Algorithmen. Bei randomisierten Verfahren werden unter anderem Las-Vegas-, Monte-Carlo- und Latin-Hypercube-Algorithmen aufgeführt.

Nach der Problemstellung unterscheidet die Liste Entscheidungsalgorithmen, die eine Entscheidung liefern, und Optimierungsalgorithmen, die eine möglichst gute Lösung suchen. Zu den Verfahren gehören Approximationsalgorithmen, Backtracking, dynamische und evolutionäre Algorithmen, Greedy-Algorithmen, probabilistische Verfahren sowie Teile-und-herrsche-Verfahren.

Geometrie, Graphen und Kalenderrechnung

In der Geometrie und Computergrafik behandelt die Liste Verfahren zur Rasterung von Linien, Polygonen und Kreisen. Beispiele sind der Bresenham-Algorithmus, der De-Casteljau-Algorithmus, Floodfill, Marching Cubes und Parabolic Blending. Außerdem werden die Delaunay-Triangulierung, Voronoi-Diagramme und Verfahren zur Berechnung der konvexen Hülle genannt, darunter QuickHull, Graham Scan, Gift-Wrapping-Algorithmus (Jarvis March) und Chans Algorithmus.

Die Graphentheorie umfasst Algorithmen für kürzeste Wege, minimale Spannbäume, maximale Flüsse und das Steinerbaumproblem. Zu den kürzesten-Wege-Verfahren gehören A*, Bellman-Ford, Dijkstra, der Min-Plus-Matrixmultiplikations-Algorithmus sowie der Algorithmus von Floyd und Warshall. Für minimale Spannbäume werden unter anderem Kruskal, Prim, Borůvka und Tarjan aufgeführt. Maximale Flüsse berechnen Ford und Fulkerson, Edmonds und Karp, Dinic sowie Goldberg-Tarjan. Für das Steinerbaumproblem nennt die Liste den KMB-Algorithmus und den Algorithmus von Mehlhorn.

Weitere graphentheoretische Verfahren sind Ameisenalgorithmen, der relative Greedy-Algorithmus und der Loss-Kontraktions-Algorithmus. Zur Suche in Graphen gehören Breitensuche sowie Tiefensuche und iterative Tiefensuche. Für das Problem des Handlungsreisenden werden die Christofides-Heuristik, MST-Heuristik, Nächster-Nachbar-Heuristik, FARIN, NEARIN, RANDIN und Sukzessive Einbeziehung genannt.

Für Kalenderberechnungen enthält die Übersicht die Gaußsche und Spencers Osterformel, die Berechnung von Schaltjahren und Zellers Kongruenz.

Bioinformatik, Kompression und Klassifikation

In der Bioinformatik werden Verfahren zum Vergleich und zur Analyse biologischer Sequenzen aufgeführt. Dazu gehören BLAST, FASTA, der Center-Star-Algorithmus, der Fitch-Algorithmus, Needleman-Wunsch, Smith-Waterman und UPGMA.

Die Kompression umfasst Verfahren zur Verringerung der Datenmenge, darunter Audiodatenkompression, Entropiekodierung, arithmetisches Kodieren, Shannon-Fano-, Huffman- und Tunstall-Kodierung, Lauflängenkodierung, LZ77, Lempel-Ziv-Welch (LZW), Deflate, Sequitur und die Wavelet-Transformation.

Bei der Klassifikation werden Daten Kategorien zugeordnet. Genannt werden Abstandsklassifikator, Bayes-Klassifikator, Clusterverfahren, Entscheidungsbaum, Fuzzy-Klassifikator, künstliches neuronales Netz, Mahalanobis-Distanz-Klassifikator, Multi-Layer-Perzeptron, Nächste-Nachbarn-Klassifikation, Perzeptron, Polynomklassifikator, Quader-Klassifikator, Radial-Basis-Funktionen und Support-Vector-Maschinen.

Die Clusteranalyse ordnet Daten nach ihrer Struktur oder Ähnlichkeit. Die Liste nennt DBSCAN (Density-Based Spatial Clustering of Applications with Noise), den EM-Algorithmus, K-Means und OPTICS (Ordering Points To Identify the Clustering Structure).

Kryptographie und Prüfsummen

Die Kryptographie umfasst Verfahren zur Verschlüsselung. Symmetrische Verschlüsselungsalgorithmen verwenden Secret-Key-Kryptologiesysteme. Dazu zählen monoalphabetische Substitution, Verschiebechiffre, Atbash, homophone Verschlüsselung, Polybios-Chiffre, Blockchiffren und Stromchiffren. Als Blockchiffren werden unter anderem AES (Advanced Encryption Standard, Rijndael), Anubis, Blowfish, CAST, DES/3DES, IDEA, Magenta, MARS, MISTY1, Serpent, Skipjack und Twofish genannt. Zu den Stromchiffren gehören A5/1, A5/2, A5/3 und A5/4, HC-256, Rabbit, RC4, Salsa20, SEAL, SOSEMANUK und Trivium.

Weitere symmetrische Verfahren sind polyalphabetische Substitution, Vigenère-Chiffre, One-Time-Pad, Enigma und Transposition. Asymmetrische Verschlüsselungsalgorithmen beziehungsweise Public-Key-Kryptologiesysteme umfassen RSA, Diffie-Hellman, Elgamal, das Rabin-Kryptosystem, GMR und Elliptic Curve Cryptography. Hybridverfahren verbinden unterschiedliche Verschlüsselungsarten. Als spezielle Anwendungen nennt die Liste CSS (Content Scramble System) für DVDs und CSA (Common-Scrambling-Algorithmus) für DVB-Pay-TV.

Prüfsummenverfahren dienen der Erkennung von Übertragungs- oder Speicherfehlern. Aufgeführt werden Adler-32, der Hamming-Code und ZRP beziehungsweise CRC (Zyklische Redundanzprüfung, Cyclic Redundancy Check).

Sortieren und Suchen

Die Sortieralgorithmen umfassen unter anderem Binary Tree Sort, Bogosort, Bubblesort, Bucketsort, Combsort, Countingsort, Gnomesort, Heapsort, Hybridsort, Insertionsort, Merge Insertion, Mergesort, Quicksort, Radixsort, Selectionsort, Shakersort, Shellsort, Simplesort, Slowsort, Smoothsort, Stoogesort, Swap-Sort und Timsort. Introsort wird als verbesserter Quicksort-Algorithmus bezeichnet, der auch im Worst Case eine Laufzeit von O(n\log n) hat.

Für Listen und Arrays nennt die Übersicht lineare Suche, binäre Suche und Interpolationssuche. Die Intervallsuche, auch Interpolarsuche genannt, sucht durch Abschätzung der Position des gesuchten Elements. Für Graphen und Bäume werden Breitensuche, Tiefensuche, iterative Tiefensuche und A*-Suche aufgeführt.

Zur Textsuche gehören der Boyer-Moore-, Boyer-Moore-Horspool-, Knuth-Morris-Pratt-, Aho-Corasick-, Rabin-Karp- und Sunday-Algorithmus sowie Skip-Search, Shift-And, PATRICIA-Trie und Suffixbaum. Weitere Suchverfahren sind Lazy Select, ein stochastischer Algorithmus, und Verfahren zur Suche nach Funktionsoptima.

Weitere mathematische, spielbezogene und sonstige Verfahren

Die Numerik verweist auf eine eigene Liste numerischer Verfahren. In der Zahlentheorie bestimmt der Euklidische Algorithmus den größten gemeinsamen Teiler (ggT) zweier natürlicher Zahlen A und B. Das Sieb des Eratosthenes bestimmt alle Primzahlen kleiner oder gleich einer vorgegebenen Zahl. CORDIC dient zur Berechnung elementarer trigonometrischer und hyperbolischer Funktionen. Der Steinhaus-Johnson-Trotter-Algorithmus erzeugt alle möglichen Permutationen von n Objekten mittels Vertauschung von Elementen; der Heap-Algorithmus erzeugt dieselben Permutationen mittels optimierter Vertauschung von Elementen.

In der linearen Algebra lösen das Gaußsche Eliminationsverfahren und der Gauß-Jordan-Algorithmus lineare Gleichungssysteme. Der Berlekamp-Algorithmus dient der Faktorisierung von Polynomen über endlichen Körpern.

Für Taktik- und Strategiespiele nennt die Liste den Minimax-Algorithmus, die Alpha-Beta-Suche und die Proof-Number-Suche. Weitere Algorithmen sind binäre Exponentiation, der Extraktionsalgorithmus nach Luhn, der Zassenhaus-Algorithmus, ein epidemischer Algorithmus, Local Outlier Factor zur Ausreißererkennung im Data-Mining, Quickselect und die Ungarische Methode.