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 et chémoinformatique
• 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
• Apprentissage
• Listes, tableaux et arborescences
• Recherche
• Classement
• Fusion
• Mathématiques
• Algèbre
• Arithmétique
• Logarithme discret
• Factorisation entière
• Test de nombre premier
• Numérique
• Statistiques
• Matrices
• Optique
• Optimisation et recherche opérationnelle
• 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 et chémoinformatique

• Needleman-Wunsch. Accomplit un alignement global sur deux séquences, pour des protéines ou nucléotides.
• Smith-Waterman. Variation de Needleman-Wunsch.
• Algorithme de Ullmann pour résoudre le problème d'isomorphisme de sous-graphe (subgraph isomorphism) solving. (1976). Détermine deux graphes ont un sous-graphe isomorphiques.
  Le problème des plus grands sous-graphes isomorphiques se résoudre avec un graphe de composition modulaire.

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.
• Zopfli. Par Google, compression d'usage général efficace mais lente. Le nom signifie petit pain en allemand suisse.
• Brotli. Par Google, successeur de Zopfli plus rapide, basé sur LZ 77, codage par entropie et modelage contextuel.

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 et décryptage

• Algorithme de Shor. Algorithme quantique supposé capable de décrypter un code basé sur les fonctions asymétriques tel que RSA.
• 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

• A* tree search. Recherche le chemin optimal entre deux noeuds sur un graphe. Amélioration du best-first utilisant une heuristique pour accélérer la recherche.
• Bellman-Ford. Calcule les plus courts chemins dans un graphe valué (ou des arcs peuvent avoir un poids négatif).
• Canonisation de graphes. Consiste à trouver la forme canonique d'un graphe de sorte qu'il soit isomorphique à un autre graphe. S'utilise en chémoinformatique.
• Dijkstra's algorithm. Calcule les plus courts chemins dans un graphe sans arc de valeur négative.
• Perturbation methods. Calcule 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.
• Hopcroft–Karp algorithm. A partir d'un graphe bipartie, retourne le maximum de cotés sans points communs. Les alternatives sont  les algos breadth-first et depth-first.
• Johnson. Plus court chemin dans un graphe orienté valué.
• Kruskal. Trouve l'arbre de parcours minimum d'un graphe.
• Prim. L'algorithme de Robert Prim trouve l'arbre de parcours minimum d'un graphe. Aussi appelé DJP , Jarník ou Prim–Jarník.
• 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.
• Colorisation. Procédé pour colorer une image ou une vidéo en noir et blanc, avec quelques traits pour marquer les couleurs. Exemples.
• Depixélisation. Sous le nom original de "Depixelizing Pixel Art", cet algorithme de lissage convertit une image en pixels grossiers en une image réaliste. (Johannes Kopf et Dani Lischinski). Démonstration. Archive des démos. Implémentation en C++ .
• HDR. Il y a de nombreux algorithmes pour contraster les photos.
• 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.
• 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.
• Resynthesizer. Enlève un objet sur une photo en reconstituant le fond. Utilisé par Photoshop et The Gimp. Tutoriel resynthesizer.
• 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. Algo basique utilisé pour la recherche du meilleur coup dans un jeu de tableau notamment (échec, dame, reversi).
• Analyse des syntiments. En fait une combinaison des algorithmes de Bayes, entropie maximale et SVM (machine à support de vecteur).
• Colonies de fourmis. Ensemble d'algorithmes basés sur le comportement des fourmis qui parviennent à une optimisation pour résoudre un problème.
• CLA. Cortical Learning Algorithm. Pour l'apprentissage robotique, basé sur trois propriétés, les représentations distribuées clairsemées, l'inférence temporelle, l'apprentissage en ligne. Code disponible dans le projet NuPic de Numenta.
• DE (Differential evolution). Résoud le problème polynomial de Chebyshev, qui s'applique aux filtres électroniques.
• Semi-Supervised Recognition of Sarcastic Sentences in Online Product Reviews.
  Un algorithme qui reconnaît le sacarsme ou l'ironie dans un tweet ou un document en ligne. Un tel algorithme sera aussi essentiel pour la programmation des robots humanoïdes.

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.
• Deep Dense Face Detector. Farafade, Saberian et Li. Capable de reconnaître des visages sous différents angles.
• Evolution-Constructed Features. Brigham Young University. Pour la capacité d'identifier des objets connus et ajouter de nouveaux objets à la base de connaissance sans intervention humaine.
• 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.
• Tracking-Learning Detection. Détecte des objets en mouvement et les suit.
• Viola-Jones, framework de détection d'objets simple et rapide. Il est capable de reconnaître les visages et est implémenté dans OpenCV.

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.

Apprentissage

• PAVA (Pool-Adjacent-Violators Algorithm). Leeuw, Hornik, Mair. Améliore une fonction pour un ensemble de points. Optimize la régression isotonique. Code C++.
• Poids Multiplicatifs. Attribue des poids à différentes stratégie pour prendre une décision. Cela s'applique à la reconnaissances des formes et se retrouve dans la génétique naturelle.

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

• Arbre retourné (Splay tree). Arbre binaire avec une fonction de retournement pour placer un noeud à la racine et réorganiser les autres en conséquence.
• 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é.
• Ensemble disjoint ou recherche-union (union-find). Avec pour application la création d'un labyrinthe.
• 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.
• Skip list. Structure composée de listes chaînée pour un accès plus rapide, et algorithme de recherche/insertion.
• Médiane. Recherche de la médiane dans une liste de nombres non ordonnée. L'algo de Torben est moins rapide mais ne modifie pas le tableau.

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.
• Tim sort. Analyse la liste à classer avant de choisir la procédure optimale. Sans doute le plus rapide et ne dépend pas de la taille de la liste. Utilise en interne par Java, Python, C++.
• 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).
• Tri par base ou tri radix. (Radix sort). Classe les clés associées aux éléments d'une liste ou des entiers à partir des digits.
• 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.

Statistiques

• 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 et recherche opérationnelle

Voir aussi Graphes.

• Agencement optimal. Placer le plus grand nombre de d'objets sur une surface limitée.
• Ant colony optimization. Technique probabiliste de résolution de problèmes 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'optimisation non linéaire sans contrainte.
• Bellman-Ford. (1955). Calcule le chemin le plus court entre un sommet et tous les autres sommet sur un graphe orienté. Supporte les valeurs négatives au contraire de l'algo de Dijkstra.
• Branch and bound. (Séparation et évaluation.) 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.
• Flux Maximal Presque Linéaire. Un algorithme par Kelner, Tat Lee, Orecchia, Sidford pour obtenir un flux maximal en considérant tous les chemins simultanément.
• 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 proportionnels 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.
• Hongrois (Kuhn-Munkre). Optimise l'affectation de ressources ou de postes de travail pour le moindre coût.
• 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.
• Problème des mariages stables. On l'utilise en économie, mathématique, biologie et autres sciences. On veut accoupler un ensemble x d'éléments incompatibles entre eux et un ensemble y d'éléments incompatibles entre eux de sorte que chaque x trouve l'y qui lui convient le mieux et inversement. Source JavaScript.
• Nelder-Mead method (downhill simplex). Optimisation non linéaire.
• Newton's method in optimization. Le même algorithme qui trouve les racines d'équations à une ou plusieurs dimensions peut aussi servir à trouver les minimum et maximum locaux de fonctions.
• Paxos. Ensemble d'algorithmes distribués pour atteindre un consensus parmi plusieurs propositions et de nombreux facteurs.
• 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.
• Shazam. Reconnaissance d'un morceau musical par comparaison du signal et définition de sa spécificité.

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é.
• Burrows Wheeler transform. Transformation de chaîne que l'on peut utiliser pour faire une recherche de mots plus rapide dans un texte.
• 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

• Latent Dirichlet Allocation (LDA). Analyse des documents pour associer le contenu à un contexte. Utilisé par les moteurs de recherche.
• Latent Semantic Indexing (LSI) . Ou indexation sémantique latente. Automatisation de méthodes pour rattacher un texte à un contexte à partir mots apparaissant communément dans ce contexte.
• 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.
• Forme des feuilles. A partir de 28 paramètres, cet algorithme retrouve la forme de toutes les feuilles produites par la nature.
• Hypertext Induced Topic Selection (HITS, brevet de 1997). Algorithme de calcul de score de pages Web par Jon Kleinberg. Un score dépends des liens entrants et l'autre des liens sortants.
• PageRank. (1998) Algorithme de score de pages par Larry Page and Sergey Brin (Google) basé sur les liens entrants et sortants. Le score dépend de nombreux autres critères également, voir Brevet Google de score de pages.
• 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

• Algorithmes pour transformer les images,

Dernière mise à jour: 16 mars 2021.

Légal: Vous pouvez librement imprimer cette page. Ne l'utilisez pas sur un autre site, placez plutôt un lien vers cette page.

Algorithmes

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

© 2006-2021 Scriptol.fr