Liste des algorithmes

La liste complète de tous les principaux algorithmes (300), dans tous les domaines. Avec pour but de fournir un programme prêt à tourner pour chacun, ou une description de l'algorithme. Les langages de programmation incluent Java, JavaScript, et PHP, C ou C++ soit sous forme directe, soit générés à partir d'un source en Scriptol.

• Automate
• Bioinformatique
• Compression
• Compression sans perte
• Compression avec perte d'information
• Cryptographie
• Générateur de nombre aléatoire
• Génie logiciel
• Allocation de mémoire
• Systèmes distribués
• Système d'exploitation (disque, plannification...)
• Géometrie
• Graphes
• Graphisme
• Intelligence artificielle
• Vision par ordinateur
• Algorithmes génétiques
• Réseau de neurones
• Listes, tableaux et arborescences
• Recherche
• Classement
• Fusion
• Mathématiques
• Algèbre
• Arithmétique
• Logarithme discret
• Factorisation entière
• Test de nombre premier
• Numérique
• Matrices
• Optique
• Optimisation
• Parsing
• Prédiction (statistique)
• Programmation logique
• Quantum
• Sciences
• Astronomie
• Médical
• (Traitement du) Signal
• Textes
• Recherche
• Reconnaissance avec approximation
• Traitement de mots
• Utilitaires
• Divers

Automate

• Powerset construction. Algorithme pour convertir un automate non déterministe en automate déterministe.
• Todd-Coxeter algorithm. Procédure pour générer des cosets.

Bioinformatique

• Needleman-Wunsch. Accomplit un alignement global sur deux séquences, pour des protéines ou nucléotides.
• Smith-Waterman. Variation de Needleman-Wunsch.

Compression

Compression sans perte

• Burrows-Wheeler transform. Pré-traitement permettant d'améliorer la compression.
• Deflate. Compression de données, utilisée par ZIP.
• Delta encoding. Aide pour comprimer des données où des séquences apparaissent fréquemment.
• Incremental encoding. Delta encoding appliqué à des séquences de chaînes.
• LZW. (Lempel-Ziv-Welch). Successeur de LZ78. Construit une table de translation ç partir des données à compresser. Est utilisé par le format graphique GIF.
• LZ77 et 78. La base des déclinaisons à venir en LZ (LZW, LZSS, ...). Toutes utilisent un codage à l'aide d'un dictionnaire.
• LZMA. Initiales de Lempel-Ziv-Markov chain-Algorithm.
• LZO. Algorithme axé sur la vitesse.
• PPM. (Prediction by Partial Matching). Prédiction par correspondance partielle. Technique de compression adaptative et statistique.
• Shannon-Fano coding. Construit des codes préfixes basés sur un ensemble de symboles et leur probalilité.
• Truncated binary encoding. Un encodage normalement utilisé pour une distribution uniforme avec un alphabet fini. Améliore le codage binaire.
• Run-length encoding. Algorithme primaire remplaçant une séquence uniforme par le nombre d'occurences..
• Sequitur. Utilise une grammaire incrémentale sur une chaîne.
• EZW (Embedded Zerotree Wavelet). Codage progressif pour comprimer une image en une suite de bits, avec une précision progressive. Peut être utilisé en compression avec perte pour un résultat plus spectactulaire.

Codage par entropie

Principe d'encodage qui assigne des codes aux symboles de sorte que la longueur des codes corresponde à la probabilité des symboles.

• Huffman coding. Utilise la fréquence relative des caractères.
• Adaptive Huffman coding. Technique d'encodage adaptative basé sur l'algorithme de Huffman.
• Arithmetic coding. Encodage élaboré.
• Range encoding. Même princique que le codage arithmétique, mais avec un procédé différent.
• Unary coding. Représente un nombre n avec n autres suivis par un zéro.
• Elias delta, gamma, omega coding. Encodage universel des entiers positifs.
• Fibonacci coding. Encodage d'entiers positifs en mots binaires.
• Golomb coding. Codage optimal pour les alphabets suivant une distribution géométrique.
• Rice coding. Comme Golomb.

Compression avec perte d'information

• Linear predictive coding. Utilise l'enveloppe spectrale sous forme compressée du signal digital de la voix.
• A-law algorithm.
• Mu-law algorithm. Compression de signal analogique.
• Fractal compression. Compression d'images utilisant les fractales.
• Transform coding. Utilisé pour les données de type audio ou photos.
• Vector quantization. Technique utilisée dans la compression avec perte.
• Wavelet compression. Type de compression convenant bien aux images et à l'audio.

Cryptographie

Cryptage à clé secrète (symétrique)

Utilise une clé secrète (ou une paire de clés directement liées), à la fois pour l'encryptage et le décryptage.

• Advanced Encryption Standard (AES), connu aussi sous le nom de Rijndael.
• Blowfish. Conçu par Schneir comme algorithme d'usage général, pour remplacer le DE vieillissant.
• Data Encryption Standard (DES). Anciennement DE Algorithm.
• IDEA (International Data Encryption Algorithm). Anciennement IPES (Improved PES), remplace aussi DES. Utilisé par PGP (Pretty Good Privacy). Effectue des transformations sur les données découpées en bloc, en utilisant une clé.
• RC4 (or ARC4). Chiffrage de flux très utilisé, notamment par le protocole SSL pour le traffic Internet et WEP pour les réseaux sans fil.
• Tiny Encryption Algorithm. Algorithme sur blocs de données facile à implémenter, utilisant quelques formules.
• PES (Proposed Encryption Standard). Nom précédent de IDEA.

Cryptage à clé publique (asymétrique)

Utilise une paire de clés, dites clé publique et clé privée. La clé publique crypte le message, seule la clé privée permet de le décrypter.

• DSA (Digital Signature Algorithm). Génère des clés avec des nombres premier et aléatoires. Etait utilisée par les agences US, et maintenant dans le domaine public.
• ElGamal. Basé sur Diffie-Hellman, utilisé par GNU Privacy Guard software, PGP, et autres systèmes de cryptographie.
• RSA(Rivest, Shamir, Adleman). Largement utilisé dans le commerce éléctronique. Utilise des nombres premiers.
• Diffie-Hellman (Merkle) key exchange (ou échange exponentiel key). Méthode et algorithme pour échanger du contenu secret par un canal de communication non protégé. Utilisé par RSA.
• NTRUEncrypt. Utilise des anneaux polynomiaux avec multiplications convolutives.

Générateur de code de contrôle

Génére un code à partir de l'encryptage d'un message ou d'un fichier de taille quelconque.

• MD5. Utilisé pour tester les images ISO des CD ou DVD.
• RIPEMD (RACE Integrity Primitives Evaluation Message Digest). Basé sur les principes de MD4 et similaire à to SHA-1.
• SHA-1 (Secure Hash Algorithm 1). Le plus utilisé dans l'ensemble des fonctions de hachâge cryptographique SHA. A été conçu par l'agence américaine NSA.
• HMAC. Authentication de message par clés de hachage.
• Tiger (TTH). Utilisé dans le hachage "Tiger tree".

Cryptage sécurisé utilisant des nombres aléatores

• Voir. Générateur de nombres aléatoires

Techniques de cryptographie

Secret sharing, Secret Splitting, Key Splitting, M of N.

• Shamir's secret sharing scheme. C'est une formule basée sur une interpolation polynomiale.
• Blakley's secret sharing scheme. Est géométrique, le secret est un point dans un espace à m dimensions.

Autres techniques

• Subset sum. Un ensemble d'entiers étant donné, y a-t'il un sous-ensemble dont la somme fasse zéro? Utilisé en cryptographie.

(Pseudo) Générateurs de nombres aléatoires

• Blum Blum Shub. Basé sur une formule utilisant des nombres premiers.
• Mersenne twister. Par Matsumoto Nishimura, rapide, a une périodicité très longue.
• Lagged Fibonacci generator. Améliore le générateur à congruence linéaire en utilisant la séquence de Fibonacci.
• Linear congruential generator. Un des plus anciens, non le meilleur, génère une séquence à partir de trois nombres.
• Yarrow algorithm. Par Bruce Schneier, John Kelsey, and Niels Ferguson. Générateur cryptographiquement sûr, peut être utilisé pour générer des nombres réellement aléatoires à partir d'entrées de périphériques analogiques.
• Fortuna. Présenté comme une amélioration de l'algorithem de Yarrow.
• Linear feedback shift register. Registre à décalage dont l'entrée est une fonction linéaire de son contenu précédent. Le contenu initial est le "seed" (grain).

Génie logiciel

• Algorithms for Recovery and Isolation Exploiting Semantics.
• Unicode Collation. Fournit un moyen standard de placer des noms, mots ou chaines de caractères dans une séquence donnée.
• CHS conversion. Conversion entre les systèmes d'addressages sur disques.
• Cyclic redundancy check. Calcul de mots de contrôle.
• Parity control. Technique de detection d'erreur élémentaire. un nombre est-il pair ou impair?

Allocation de mémoire

• Boehm garbage collector. Gestionnaire de mémoire.
• Buddy memory allocation. Allocation de mémoire en réduisant la fragmentation.
• Generational garbage collector. Gestionnaire de mémoire rapide qui se base sur l'ancienneté des enregistrements.
• Mark and sweep.
• Reference counting. Gestionnaire d'allocation simple qui compte le nombre de liens sur une donnée et récupère l'espace quand il vaut zéro.

Systèmes distribués

• Lamport ordering. Un ordonnateur d'évènement basé sur la relation happened-before (arrivé avant).
• Snapshot. C'est la sauvegarde de l'état global du système.
• Vector clocks. Ordonnancement total des évènements.
• Marzullo. Synchronisation distribuée selon le temps alloué.
• Intersection. Autre algorithm basé sur le temps alloué.

Systèmes d'exploitation

• Banker. Algorithme pour éviter les plantages.
• Page replacement. Sélection de pages à sacrifier quand la mémoire manque.
• Bully. Sélection d'un poste prioritaire.

Algorithmes de contrôle de disque.

• Elevator. Planification de disque fonctionnant comme un ascenceur.
• Shortest seek first. Planification du disque pour réduire le temps d'accès.

Algorithmes de synchonization de processus.

• Peterson. Permet à deux processus de partager une même ressource sans conflit, grâce à l'emploi d'une mémoire commune pour communiquer.
• Lamport's Bakery. Améliore la robustesse de la gestion de plusieurs processus en multi-tâches au moyen d'exclusions mutuelles.
• Dekker. Autre algorithme de programmation concurrente comme celui de Peterson.

Algorithmes de minutage (scheduling)

• Earliest deadline first scheduling. Quand un évènement survient (fin de tâche, nouvelle tâche, etc...) on recherche dans la liste le processus à terminer au plus tôt.
• Fair-share scheduling. Partage le temps processeur entre les groupes ou utilisateurs. On appelle récursivement pour cela un autre algorithme pour gérer le partage entre processus.
• Least slack time scheduling ou Least Laxity First. Affecte les priorités selon les différences temporelles pour les processus. date limite, le moment où on est prêt, le temps d'exécution.
• List scheduling. A partir d'une liste de processus dotés de priorités, affecte d'abord aux plus prioritaires les ressources disponibles. Stratégies possibles. chemin critique, plus long chemin, plus haut niveau d'abord, plus long temps de traitement.
• Multi level feedback queue.
• Rate-monotonic scheduling. Algorithme optimal, préemptif, à priorité statique. Priorité donnée selon un principe de taux monotonique (le premier à finir est le premier traité).
• Round-Robin scheduling. Le plus simple, assigne des tranches de temps à chaque processus sans priorité.
• Shortest job next (or first). Exécute ensuite le processus en attente qui a le temps d'exécution le plus court, sans préemption.
• Shortest remaining time. Une version de minutage du plus court processus à venir, qui termine la tâche en court avant d'en choisir une autre.

Geométrie

• Gift wrapping. Détermine l'enveloppe convexe d'un ensemble de points.
• Gilbert-Johnson-Keerthi distance. Trouve la plus courte distance entre deux formes convexes.
• Graham scan. Détermine l'enveloppe convexe d'un ensemble de points sur un plan.
• Line segment intersection. Trouve quelles lignes sont en intersection avec une ligne imaginaire.
• Points dans un polygone.
• Ray/Plane intersection. Intersection de rayons avec un plan.
• Line/Triangle intersection. Cas particulier de Ray/Plane.
• Polygonisation de surfaces implicites. Approxime une surface implicite par une représentation en polygones.
• Triangulation. Méthode pour évaluer une distance ou déterminer les propriétés d'un espace topologique.

Graphes

• Bellman-Ford. Calcule les plus courts chemins dans un graphe valué (ou des arcs peuvent avoir un poids négatif).
• Dijkstra's algorithm. Calcule les plus courts chemins dans un graphe sans arc de valeur négative.
• Perturbation methods. Calcules les plus courts chemins dans un graphe.
• Floyd-Warshall. Résoud le problème de plus court chemin dans un graphe orienté et valué.
• Floyd's cycle-finding. Algorithme itératif qui détecte les cycles.
• Johnson. Plus court chemin dans un graphe orienté valué.
• Kruskal. Trouve l'arbre de parcours minimum d'un graphe.
• Prim. Comme Kruskal.
• Boruvka. Comme Kruskal.
• Ford-Fulkerson. Calcule le flot maximum passant dans un graphe.
• Edmonds-Karp. Implémentation de Ford-Fulkerson.
• Nonblocking Minimal Spanning Switch. Echanges téléphoniques.
• Woodhouse-Sharp. Trouve l'arbre de parcours minimum d'un graphe.
• Spring based. Algorithme de dessin de graphe.
• Hungarian. Trouve une correspondance parfaite.
• Coloring. Coloration d'un graphe.
• Nearest neighbour. Recherche du plus proche voisin.
• Topological sort. Classement d'un graphe orienté acyclique de façon que chaque noeud précède les noeuds auxquels il est lié (selon le sens des arcs).
• Tarjan's off-line least common ancestors algorithm. Calcule les ancêtres communs les plus proches à des paires de noeuds dans un arbre.

Graphisme

• Bresenham's line. Utilise des variables de décision pour afficher un ligne entre deux points.
• Landscape. Dessine un décor en trois dimensions..
• DDA line algorithm. Utilise les mathématiques en virgule-flottante pour dessiner une ligne entre deux points.
• Flood fill. Colorie une zone délimitée par par une ligne fermée.
• Image Restoring. Restore des photos, améliore des images.
• Xiaolin Wu's line algorithm. Algorithm d'anti-aliasing de ligne.
• Painter's algorithm. Détecte les parties visibles d'une scène en 3D.
• Ray tracing. "Rendering", tracé d'image réaliste.
• Phong shading. En 3D, crée un éclairage.
• Gouraud shading. Simule les effets de liumière et couleurs sur la surface d'un objet en 3D.
• Scanline rendering. Construit une image en déplaçant une ligne imaginaire.
• Global illumination. Reconstitue l'éclairage direct et réfléchi par d'autres objets.
• Interpolation. Construit de nouveau point sur une image agrandie.
• Slope-intercept algorithm. C'est une implémentation de la formule slope-intercept pour dessiner une ligne.
• Spline interpolation. Réduit les erreurs avec le phénomène de Runge.
• 3D Surface Tracker Technology. Procédé pour ajouter des images sur les murs dans une vidéo en tenant compte des surfaces cachées.

Intelligence artificielle

• Alpha-beta. Alpha max plus beta min. Utilisé pour les jeux de tableaux notamment.
• DE (Differential evolution). Résoud le problème polynomial de Chebyshev.

Vision par ordinateur

• Epitome. Représente une image ou une vidéo par une plus petite.
• Compte d'objets dans une image. Utilise l'algorithme des composants connectés pour définir d'abord chaque objet, et compter les objets.
• Algorithme de O'Carroll. A partir d'une conversion en mathématique de la vision des insecte, cet algorithme évalue comment se déplacer en évitant les objets.

Algorithmes génétiques

Ils utilisent trois opérateurs. sélection (choisir une solution), reproduction (utiliser la solution choisie pour en construire d'autres), remplacement (remplace la solution avec une meilleure).

• Fitness proportionate selection. Nommé aussi roulette, sélectionne des solutions.
• Truncation selection. Sélectionne des solutions classées par pertinence.
• Tournament selection. Sélectionne la meilleur solution par une sorte de tournoi.
• Stochastic universal sampling. Les individus sont associés aux éléments contigus d'une ligne de sorte que chacun ait une taille qui lui corresponde.

Réseaux de neurones

• Réseau de Hopfield. Réseau neuronal récurrent qui fonctionne comme une mémoire adressable binaire. Il converge vers un état stable.
• Backpropagation. Technique d'apprentissage aidée pour entraîner des réseaux de neurones artificiels.
• Self-organizing map (Kohonen map). Réseaux de neurones entraînés en utilisant un apprentissage autonome pour produire une représentation en basse dimensions (2D, 3D) des exemples donnés à apprendre.

Listes, tableaux et arborescences

Recherche

• Dictionary search. Voir recherche prédictive.
• Selection algorithm. Trouve l'élément le plus grand de niveau k dans une liste.
• Recherche dichotomique (binary search). Trouve un objet dans une liste ordonnée.
• Breadth-first search. Traverse un graphe niveau par niveau.
• Depth-first search. Traverse un graphe branche par branche.
• Best-first search. Traverse un graphe dans l'ordre d'importance probable en utilisant une file de priorité.
• A* tree search. Amélioration du best-first utilisant une heuristique pour accélérer la recherche.
• Uniform-cost search. Recherche en arbre qui trouve les moindre coûts si les coûts varient.
• Predictive search. Sorte de recherche dichotomique.
• Hash table. Associe des clés aux éléments pour rechercher dans une liste non classée avec une durée linéaire.
• Interpolated search. Voir la recherche prédictive.

Classement

• Binary tree sort. Classement d'un arbre binaire, incrémental, similaire au tri par insertion.
• Bogosort. Classement inefficace d'une pile de carte par sélection au hasard.
• Tri à bulle. Pour chaque paire d'indices interverti les éléments qui ne sont pas dans l'ordre.
• Bucket sort. Découpe une liste en paquets, et les trie individuellement. Généralise pigeonhole.
• Cocktail sort (ou tri à bulle bi-directionnel). Tri dans deux directions à la fois.
• Comb sort. Tri à bulle efficace qui élimine les petites valeurs à la fin du tri, et se sert des espaces entre les valeurs.
• Counting sort. Utilise les intervalles entre les nombres de la liste A pour créer la liste B. Les index de B sont utiliser pour connaître les valeurs de A inférieures à un nombre i.
• Gnome sort. Comme le tri par insertion, mais le déplacement à la bonne place se fait par une série d'inversion comme en tri à bulles.
• Heapsort. Convertit la liste en pile, en supprime l'élément le plus grand et l'ajoute à la fin de liste.
• Tri par insertion. Détermine ou l'élément courant se place dans la liste classée et l'y place.
• Introsort ou Introspective sort. Démarre en quicksort et bascule en heapsort quand un certain niveau de récursion est atteint.
• Merge sort. Classe la première et seconde moitié de liste séparément et les fusionne (récursivement).
• Pancake sort. Intervertit les élément d'un préfix quelconque dans une séquence.
• Pigeonhole sort. Remplit un tableau vide au départ avec les éléments à classer dans un autre tableau, dans l'ordre.
• Postman sort. Variation du tri par paquets, hiérarchisée, utilisée par les bureaux de poste pour le courrier.
• Quicksort. Sépare la liste en deux, tous les éléments de la première étant inférieurs à ceux de la seconde et les classe (récursivement).
• Radix sort. Classe les clés associées aux élément d'une liste.
• Selection sort. Prend le dernier élément restant et l'ajoute à la fin de la liste classée.
• Shell sort. Amélioration du tri par insertion en utilisant l'intervalle entre les valeurs.
• Smoothsort. Voir heapsort.
• Stochastic sort. Voir bogosort.

Fusion

• Simple Merge. Fusionne n flux triés en un seul. Les flux sont comparés, la entrées les plus petites de chacun sont envoyées au flux sortant.
• Tri k-way Merge (ou p-way). Tri un flux de données par fusions répétitives.

Mathématiques

Algèbre

• Buchberger's algorithm. Trouve une base de Gräbner.
• Eigenvalue algorithm.
• Extended Euclidean algorithm. Résoud l'équation ax+by= c.
• Fourier transform multiplication. Pour de très grand nombres, calculer la transformation rapide de Fourier pour deux nombres et multiplier les deux résultats élément par élément.
• Gram-Schmidt process. Orthogonalise un ensemble de vecteurs.
• Gauss-Jordan elimination. Résoud un système d'équations linéaires.
• Karatsuba multiplication. Algorithme récursif efficace pour de grands nombres. Dérivé de Toom-Cook.
• Knuth-Bendix completion. Pour réécrire un système de règles.
• Multivariate division. Polynomes selon plusieurs indéterminations.
• Risch algorithm. Traduit une intégrale indéfinié en problème algébrique.
• Toom-Cook (Toom3). Décompose chaque nombre à multiplier en plusieurs parties.

Eigenvalue algorithm

Algorithmes pour trouver les "Eigenvalue" (valeurs propres) et/ou Eigenvector (vecteur propre) d'une matrice.

• QR algorithm. Une méthode populaire basée sur la décomposition QR.
• Inverse iteration. Algorithme itératif.
• Rayleigh quotient iteration. Etend le principe d'itération inverse en utlisant le quotient de Rayleigh pour obtenir progressivement des estimations d'eigenvalue suffisantes.
• Arnoldi iteration. Calcule les eigenvalue de la projection orthogonale de A dans le sous-espace de Krylov.
• Lanczos iteration. Méthode pour trouver le vercteur zéro dans le processus du crible quadratique.
• Jacobi method. Procédure numérique pour le calcul des eigenvalues et eignenvectors d'une matrice symétrique réelle.
• Bisection.
• Divide-and-conquer. S'utilise sur les matrices symétriques réelles.

Algorithms eigenvector

• Richardson eigenvector algorithm.
• Max-Plus eigenvector algorithm. Pour contrôle H1 non-linéraire.
• Abrams and Lloyd eigenvector algorithm.

Arithmétique

• PGCD binaire. Calcul du plus grand diviseur commun rapidemment.
• Booth's multiplication. Multiplie deux nombres entiers en utilisant le complément à 2.
• Euclidean algorithm. Calcule le PGCD.
• Multiplication binaire (ou égyptienne). On décompose le plus grand multiplicande en une somme de puissance de deux, et on crée une table des puissances de deux du second.

Logarithme discret dans le théorie des groupes

• Baby-step giant-step. C'est une série d'étapes connues pour calculer le logarithme.
• Pollard's rho algorithm for logarithms. Analogue à l'algorithme de même nom pour la factorisation entière, qui peut s'appliquer aussi au calcul du logarithme discret.
• Pohlig-Hellman algorithm. Résoud le problème pour un groupe multiplicatif dont l'ordre est un entier. Basé sur le théorème chinois du reste, et s'exécute en une durée polynomiale.
• Index calculus algorithm. Algorithme bien connu pour certains groupes comme le groupe multiplicatif modulo m.

Factorisation entière

Décomposer un entier en facteurs premiers.

• Fermat's factorization method. Une représentation d'un entier pair comme comme la différence de deux carrés.
• Trial division. L'algorithme le plus simple. essai de diviser un entier par les nombres premiers successifs.
• Lenstra elliptic curve factorization ou elliptic curve factorization method (ECM). Rapide, nécessitant une durée sous-exponentielle emploi des courbes elliptiques.
• Pollard's rho. Variation de Pollard's p-1 efficace pour décomposer des nombres en un petit nombre de facteurs.
• Pollard's p-1. Algorithme sépcialisé qui convient seulement pour des entiers avec certains types de facteurs.
• Congruence of squares. Trouver une congruence de carrés modulo n est un moyen de factoriser l'entier n.
• Quadratic sieve. Utilise l'idée de le méthode de Dixon. C'est un algorithme qui est plus simple que "number field sieve" et le plus rapide pour les entiers de moins de 100 chiffres.
• Dixon. Méthode de factorisation d'utilisation générale.
• Special number field sieve. Algorithme spécialisé idéal pour factoriser les nombres de Fermat.
• General number field sieve (GNS). Dérivé de "special number field sieve". Efficace pour les grand nombres. Procède par étapes.

Test de nombre premier

Déterminer si un nombre donné est premier.

• AKS primality test (Agrawal-Kayal-Saxena). Le premier algorithme publié qui soit à la fois polynomial, déterministe et inconditionnel. Généralisation du théorème de Fermat, étendu aux polynômes.
• Fermat primality test. Tient à une égalité ou un ensemble d'égalités vraies pour les valeurs premières, pour voir ensuite si elles contiennent ou nom le nombre à tester.
• Miller-Rabin primality test. Similaire au test de Fermat. Algorithme inconditionel et probabiliste.
• Crible d'Eratosthènes. Ancient algorithme pour trouver les nombres premiers jusqu'è un nombre entier donné.
• Sieve of Atkin. Version optimisée du crible d'Eratosthenes.
• Solovay-Strassen primality test. Même principe que le test de Fermat.

Numérique

• Fibonacci. Calcul de la séquence de Fibonacci.
• Biconjugate gradient method. Résolution d'équations linaires.
• Dancing Links. Trouve toutes les solutions au problème de couverture exacte.
• De Boor algorithm. Calculs de courbes.
• De Casteljau's algorithm. Calcule les courbes de Bezier.
• False position method. Approximation des racines d'une fonction.
• Gauss-Legendre. Calcul des décimales de pi.
• Kahan summation. Addition de nombres en virgule flottante efficace.
• MISER. Intégration numérique, simulation de Monte Carlo.
• Newton's method. Trouve les valeurs zéro de fonctions.
• Rounding functions. Arrondi classique de nombres entiers.
• Secant method. Approximation des racines d'une fonction.
• Shifting nth-root. Extraction de racine chiffre par chiffre.
• Square root. Approximation de la racine carrée d'un nombre.
• Borwein's algorithm. Calcule la valeur de 1/e.
• Metropolis-Hastings. Génère une séquence d'échantillons pour la distribution probable d'une variable ou plus.

Matrices

Calcul matriciel ou optimisation.

• Exponentiating by squaring. Calcule la puissance de matrices.
• Rutishauser. Tridiagonalisation de matrices.
• Strassen algorithm. Multiplication rapide de matrices.
• Décomposition symbolique de Cholesky. Stockage efficace de matrices.
• Zha's algorithm. Améliore Rutishauser pour la tridiagonalisation de matrices orientées.
• Chain matrix multiplication. Optimization de la multiplication d'une séquence de matrices par le moyen le plus efficace en utilisant la programmation dynamique.

Optique

• Gerchberg Saxton. Détermination de phase à partir d'image et de plans de diffraction.

Optimisation

• Ant colony optimization. Technique probabiliste de résolution de problems qui se réduisent à trouver le bon chemin sur un graphe.
• BFGS (méthode de Broyden-Fletcher-Goldfarb-Shanno). Résoud un problème d'optimisaton non linéaire sans contrainte.
• Branch and bound. Méthode pour trouver la solution optimale de problèmes d'optimisation discrets et combinatoires.
• Conjugate gradient method. Algorithme itératif pour la solution numérique de systèmes d'équations linéaires, dont la matrice est symétrique et positive.
• Evolution strategy. Technique d'optimisation basée sur l'idée d'adaptation et d'évolution. Les opérateurs sont. sélection, recombinaison, mutation, selection environnementale...
• Gauss-Newton. Résoud le problème de moindre carré non linéaire.
• Gradient descent. Approche le minimum local d'une fonction par des pas proportionels au négatif du gradient (ou approché) de la fonction au point actuel.
• Gradient ascent. Approche le maximum local d'une function, comme "gradient descent", avec des pas directement proportionels au gradient.
• Levenberg-Marquardt. Comme Gauss-Newton.
• Line search. Approche par itération, pour trouver le minimum local d'une fonction en optimisation sans contrainte.
• Local search. Méta-heuristique pour résoudre de difficiles problèmes d'optimisation, tel que maximiser un critère parmi plusieurs solutions candidates.
• Nelder-Mead method (downhill simplex). Optimisation non linéaire.
• Newton's method in optimization. Le même algorithme qui trouve les racines d'équation à une ou plusieurs dimensions peut aussi servir à trouver les minimum et maximum locaux de fonctions.
• PSO, Particle Swarm Optimization (essaim de particules). L'intelligence d'un essaim modelisée par des particules dans un espace multidimensionel, avec une position et une vitesse.
• Random-restart hill climbing. Méta-algorithme construit par dessus l'algorithme "hill climbing optimization".
• Simplexe. Résolution du problème de programmation linéaire.
• Simulated annealing. Méta-algorithme générique et probabiliste pour le problème d'optimisation global, s'inspire du principe de recuit en métallurgie.
• Steepest descent. voir gradient descent.
• Stochastic tunneling. Approche pour minimiser une fonction basée sur la méthode d'échantillonage Monte Carlo.
• Tabu search. Optimise une recherche en utilisant des structures de mémorisation.
• Trust search. Une autre approche par itérations pour trouver le minimum local d'une fonction en optimisation sans contrainte.

Parsing

• CYK algorithm. Un algorithme O(n³) efficace pour toute grammaire non contextuelle.
• Earley's algorithm. Autre algorithme O(n³) pour grammaires non contextuelles.
• Inside-outside. Algorithme O(n³) pour réestimer la probabilité des productions dans des grammaires probabilistiques non contextuelles.

Parsers LL

Parse une grammaire non contextuelle de haut en bas, de gauche à droite. Comme le fait ANTLR qui est LL(*).

Parsers LR

Parse une grammaire non contextuelle de bas en haut, donc en commençant par les derniers descendants de chaque branche.

• Dijkstra's shunting yard algorithm. Couramment utilisé pour implémenter les parseurs à précédence d'opérateur qui font la conversion entre la notation infixe et la notation polonaise inversée.
• LALR (Look-Ahead LR). Procèdent de gauche à droite avec lecture d'un seul token à venir. Yacc et Bison sont des parsers LALR(1). Supérieurs aux SLR.
• SLR (Simple LR) parser. Parseur LR(0) modifié pour prévenir les conflits shift-reduce et reduce-reduce. Reste inférieur à LR(1).
• Canonical LR parser ou LR(1). Voit un token à l'avance.
• GLR. (Generalyzed LR parser) par Masaru Tomita. Une extension à LR pour gérer les grammaires non déterministes ou ambigües. Il est efficace pour le langage natural.

Parsers descendant récursifs

Parsers LL construits à partir d'un ensemble de procédures s'excluant mutuellement qui représentent les règles de production de la grammaire.

• Packrat. Algorithme à durée linéaire pour les grammaires non contextuelles LL(k). Utilise la copie et la mémorisation des choix pour éviter la non termination.

Prédiction (statistique)

• Baum-Welch. Trouve les paramètres inconnus d'un modèle de Markov caché (HMM) en utilisant un algorithme d'avance-recul.
• Viterbi. Calcule le chemin de Viterbi (Viterbi path), une séquence d'état qui a la plus grande probabilité d'apparition dans une suite d'évènements.

Programmation logique

• Algorithme de Davis–Putnam. Teste la validité d'une assertion du premier ordre.

Quantum

Application des calculs de quantum à des problèmes variés

• Grover's algorithm. Fournit une accélération quadratique à plusieurs problèmes de recherche.
• Shor's algorithm. Fournit une accélération exponentielle pour factoriser un nombre.
• Deutsch-Jozsa. Critère de balance pour une fonction booléenne.

Sciences

Astronomie

• Ephémérides.
• Positions de la lune et autres objets célestes.
• Jour julien. Nombre de jours qui ont passé depuis le lundi 1 janvier, 4713 avant JC dans le calendrier julien proleptique. L'algorithme est une formule. On a des variations. jour julien héliocentrique, chronologique, modifié, réduit, tronqué, de Dublin, de Lilian.
• Date julienne. Le jour julien non arroundi, avec une fraction décimale.

Médical

• Calculs pour médications.
• Aide au diagnostic.

(Traitement du) Signal

• CORDIC. Fonction trigonométrique rapide.
• Rainflow-counting. Réduit l'historique de stree complexe à un compte de d'inversion de stree élémentaire.
• Osem. Traitement d'images médicales.
• Goertzel algorithm. Peut s'utiliser pour décoder le DTMF.
• Discrete Fourier transform. Détermine les fréquence dans un segment de signal.
  • Fast Fourier transform
  • Cooley-Tukey FFT
  • Rader's FFT
  • Bluestein's FFT
  • Bruun's FFT
  • Prime-factor FFT
• Richardson-Lucy deconvolution. Algorithme de de-blurring d'image.
• Elser Difference-Map. Diffraction microscopique de rayons X.

Textes

Recherche

• Aho-Corasick. Recherche dans un texte en construisant une table à partir des mots.
• Bitap (ou shift-or, shift-and, Baeza-Yates-Gonnet). Algorithme de recherche floue développé par Udi Manber and Sun Wu.
• Boyer-Moore string search. Recherche dans un texte en sautant les sous-chaînes qui ne contiennent par les lettres du mot recherché.
• Knuth-Morris-Pratt. Construit une table pendant la recherche pour sauter des sous-chaînes.
• Problème de la plus longue sous-séquence commune. (Algorithme de Haskell). A deux séquences.
• Plus longue sous-séquence augmentant. Commune à deux séquences. Cela se ramène à trouver le plus long chemin dans un graphe orienté sans cycles.
• La plus courte super-séquence commune. A deux séquences.
• Rabin-Karp string search. Utilise le hachage pour des recherches multiples.
• Horspool. Simplification de l'algorithme de Boyer-Moore. O(mn).

Comparaison avec approximation

• Distance de Levenshtein (ou distance d'édition). Nombre d'opérations (insertion, suppression, remplacement) minimal pour transformer un mot en un autre mot.
• Soundex. Algorithme phonétique pour indexer des mots selon leur son (en anglais).
• Metaphone.Indexation de mots selon le son (en anglais).
• NYSIIS. (New York State Identification and Intelligence System). Algorithme phonétique qui améliore soundex.

Traitement de mots

• Stemming. Méthode de réduction des mots à leurs stèmes ou racine.

Utilitaires

• Doomsday. Jour de la semaine.
• Xor swap. Intervertit les valeurs de deux variable sans variable intermédiaire.
• Hamming weight. Trouve le nombre de bits 1 dans un mot binaire.
• Luhn. Méthode de validation de numéros d'identification.
• Create bit mask. Algorithme de manipulation de bits.

Divers

• BrowseRank. Alternative au PageRank qui se base sur le comportement des utilisateurs.
• Hypertext Induced Topic Selection (HITS). Algorithme de calcul de score de pages Web par Jon Kleiberg. Un score dépends des liens entrants et l'autre des liens sortants.
• PageRank. Algorithme de score de pages de Google basé sur les liens entrants et sortants. Le score dépend de nombreux autres critères également. Références.
• Schreier-Sims. Permutation de groupes. Méthode pour calcule les BSGS (Base and Strong Generating Set). Utilisé par des algorithmes algébriques.
• Robinson-Schensted. Algorithme combinatoire.

Liens

• Le répertoire des algorithmes sur dmoz.org (en).

Algorithmes

Définition du mot algorithme - Classification - Histoire de l'algorithmique - Liste des algorithmes - Crible d'Eratosthenes - Nombre de Fibonacci