Liste des algorithmes - List of algorithms

Ce qui suit est une liste d' algorithmes avec des descriptions d'une ligne pour chacun.

Planification automatisée

Algorithmes combinatoires

Algorithmes combinatoires généraux

• Algorithme de Brent : trouve un cycle dans les itérations de valeurs de fonction en utilisant seulement deux itérateurs
• Algorithme de recherche de cycle de Floyd : trouve un cycle dans les itérations de la valeur de la fonction
• Algorithme Gale-Shapley : résout le problème du mariage stable
• Générateurs de nombres pseudo- aléatoires (répartis uniformément - voir aussi Liste des générateurs de nombres pseudo-aléatoires pour d'autres PRNG avec divers degrés de convergence et de qualité statistique variable) :
  • Générateur GLAND
  • Blum Blum Shub
  • Générateur de Fibonacci retardé
  • Générateur linéaire congruentiel
  • Tornade Mersenne

Algorithmes de graphes

• Algorithme de coloration : Algorithme de coloration de graphe.
• Algorithme Hopcroft–Karp : convertit un graphe bipartite en une correspondance de cardinalité maximale
• Algorithme hongrois : algorithme pour trouver une correspondance parfaite
• Codage de Prüfer : conversion entre un arbre étiqueté et sa séquence de Prüfer
• Algorithme d'ancêtres communs les plus bas hors ligne de Tarjan : calcule les ancêtres communs les plus bas pour les paires de nœuds dans un arbre
• Tri topologique : recherche l'ordre linéaire des nœuds (par exemple les jobs) en fonction de leurs dépendances.

Dessin de graphique

• Algorithmes basés sur la force (également appelés algorithmes dirigés par la force ou algorithme à ressort)
• Disposition spectrale

Théorie des réseaux

• Analyse de réseau
  • Analyse des liens
    • Algorithme de Girvan-Newman : détecter les communautés dans les systèmes complexes
    • Analyse de liens Web
      • Recherche de sujet induite par hyperlien (HITS) (également connue sous le nom de hubs et autorités )
      • Classement
      • Classement de confiance
• Réseaux de flux
  • Algorithme de Dinic : est un algorithme fortement polynomial pour calculer le débit maximum dans un réseau de débit .
  • Algorithme Edmonds-Karp : implémentation de Ford-Fulkerson
  • Algorithme Ford-Fulkerson : calcule le débit maximum dans un graphe
  • Algorithme de Karger : une méthode de Monte Carlo pour calculer la coupe minimale d'un graphe connexe
  • Algorithme push–relabel : calcule un flux maximum dans un graphe

Routage pour les graphiques

• Algorithme d'Edmonds (également connu sous le nom d' algorithme de Chu-Liu/Edmonds) : trouver les branchements maximum ou minimum
• Arbre couvrant minimum euclidien : algorithmes de calcul de l'arbre couvrant minimum d'un ensemble de points dans le plan
• Problème du plus court chemin euclidien : trouver le chemin le plus court entre deux points qui ne coupe aucun obstacle
• Problème du plus long chemin : trouver un chemin simple de longueur maximale dans un graphe donné
• Arbre couvrant minimal
  • Algorithme de Borůvka
  • L'algorithme de Kruskal
  • L'algorithme de Prim
  • Algorithme de suppression inversée
• Commutateur à portée minimale non bloquante , par exemple, pour un central téléphonique
• Problème de chemin le plus court
  • Algorithme de Bellman-Ford : calcule les chemins les plus courts dans un graphique pondéré (où certains des poids de bord peuvent être négatifs)
  • Algorithme de Dijkstra : calcule les chemins les plus courts dans un graphe avec des poids de bord non négatifs
  • Algorithme Floyd-Warshall : résout le problème du plus court chemin de toutes les paires dans un graphe orienté pondéré
  • Algorithme de Johnson : Algorithme du chemin le plus court de toutes les paires dans un graphe orienté pondéré clairsemé
• Problème de fermeture transitive : trouver la fermeture transitive d'une relation binaire donnée
• Problème de voyageur de commerce
  • Algorithme Christofides
  • Algorithme du plus proche voisin
• Règle de Warnsdorff : Une méthode heuristique pour résoudre le problème de la tournée du chevalier .

Recherche graphique

• A* : cas particulier de la recherche best-first qui utilise des heuristiques pour améliorer la vitesse
• B* : un algorithme de recherche de graphe best-first qui trouve le chemin le moins coûteux d'un nœud initial donné à n'importe quel nœud d'objectif (parmi un ou plusieurs objectifs possibles)
• Backtracking : abandonne les solutions partielles lorsqu'elles s'avèrent ne pas satisfaire une solution complète
• Beam search : est un algorithme de recherche heuristique qui est une optimisation de la recherche best-first qui réduit ses besoins en mémoire
• Recherche de pile de faisceaux : intègre le backtracking avec la recherche de faisceau
• Meilleure recherche en premier : parcourt un graphique dans l'ordre d'importance probable en utilisant une file d'attente prioritaire
• Recherche bidirectionnelle : trouver le chemin le plus court d'un sommet initial à un sommet cible dans un graphe orienté
• Recherche en largeur d'abord : parcourt un graphe niveau par niveau
• Recherche par force brute : Une méthode de recherche exhaustive et fiable, mais inefficace du point de vue informatique dans de nombreuses applications.
• D* : un algorithme de recherche heuristique incrémentale
• Recherche en profondeur : parcourt un graphe branche par branche
• Algorithme de Dijkstra : Un cas particulier de A* pour lequel aucune fonction heuristique n'est utilisée
• General Problem Solver : un algorithme de démonstration de théorème fondamental destiné à fonctionner comme une machine universelle de résolution de problèmes.
• Recherche itérative en profondeur d'abord (IDDFS) : une stratégie de recherche dans l'espace d'état
• Recherche de point de saut : Une optimisation vers A* qui peut réduire le temps de calcul d'un ordre de grandeur en utilisant des heuristiques supplémentaires.
• Recherche lexicographique en largeur d'abord (également connue sous le nom de Lex-BFS) : un algorithme de temps linéaire pour ordonner les sommets d'un graphe
• Recherche à coût uniforme : une recherche arborescente qui trouve l'itinéraire le moins cher où les coûts varient
• SSS* : recherche dans l'espace d'états traversant un arbre de jeu selon un mode best-first similaire à celui de l'algorithme de recherche A*
• F* : Algorithme spécial pour fusionner les deux tableaux

Sous-graphes

• Les cliques
  • Algorithme de Bron-Kerbosch : une technique pour trouver des cliques maximales dans un graphe non orienté
  • Algorithme de clique maximum MaxCliqueDyn : trouver une clique maximum dans un graphe non orienté
• Composants fortement connectés
  • Algorithme de composant fort basé sur le chemin
  • L'algorithme de Kosaraju
  • Algorithme des composants fortement connectés de Tarjan
• Problème d'isomorphisme de sous-graphe

Algorithmes de séquence

Correspondance de séquence approximative

• Algorithme Bitap : algorithme flou qui détermine si les chaînes sont approximativement égales.
• Algorithmes phonétiques
  • Daitch–Mokotoff Soundex : un raffinement Soundex qui permet l'appariement des patronymes slaves et germaniques
  • Double Metaphone : une amélioration sur Metaphone
  • Approche par correspondance : un algorithme phonétique développé par Western Airlines
  • Metaphone : un algorithme pour indexer les mots par leur son, lorsqu'ils sont prononcés en anglais
  • NYSIIS : algorithme phonétique , améliore Soundex
  • Soundex : un algorithme phonétique pour indexer les noms par le son, tel qu'il se prononce en anglais
• Métriques de chaîne : calcule un score de similarité ou de dissemblance (distance) entre deux paires de chaînes de texte
  • Distance Damerau–Levenshtein : calcule une mesure de distance entre deux cordes, améliore la distance de Levenshtein
  • Coefficient de Dice (également appelé coefficient de Dice) : une mesure de similarité liée à l' indice Jaccard
  • Distance de Hamming : somme du nombre de positions différentes
  • Distance Jaro-Winkler : est une mesure de similarité entre deux cordes
  • Distance d'édition de Levenshtein : calcule une métrique pour la quantité de différence entre deux séquences
• Recherche de trigramme : recherche de texte lorsque la syntaxe ou l'orthographe exacte de l'objet cible n'est pas connue avec précision

Algorithmes de sélection

• Sélection rapide
• Introsélection

Recherche de séquence

• Recherche linéaire : localise un élément dans une séquence non triée
• Algorithme de sélection : trouve le k ème plus grand élément d'une séquence
• Recherche ternaire : une technique pour trouver le minimum ou le maximum d'une fonction qui est soit strictement croissante puis strictement décroissante ou vice versa
• Listes triées
  • Algorithme de recherche binaire : localise un élément dans une séquence triée
  • Technique de recherche de Fibonacci : recherchez une séquence triée à l'aide d'un algorithme de division pour régner qui réduit les emplacements possibles à l'aide de nombres de Fibonacci
  • Recherche par saut (ou recherche par bloc) : recherche linéaire sur un sous-ensemble plus petit de la séquence
  • Recherche prédictive : recherche de type binaire qui prend en compte l' ampleur du terme de recherche par rapport aux valeurs hautes et basses de la recherche. Parfois appelée recherche par dictionnaire ou recherche interpolée.
  • Recherche binaire uniforme : une optimisation de l'algorithme de recherche binaire classique

Fusion de séquences

• Algorithme de fusion simple
• algorithme de fusion k-way
• Union (fusion, avec des éléments sur la sortie non répétés)

Permutations de séquences

• Fisher-Yates shuffle (également connu sous le nom de Knuth shuffle) : mélangez au hasard un ensemble fini
• Algorithme de Schensted : construit une paire de tableaux de Young à partir d'une permutation
• Algorithme Steinhaus-Johnson-Trotter (également connu sous le nom d'algorithme Johnson-Trotter) : génère des permutations en transposant des éléments
• Algorithme de génération de permutation de Heap : échanger des éléments pour générer la prochaine permutation

Combinaisons de séquences

Alignement de séquence

• Déformation temporelle dynamique : mesure la similarité entre deux séquences qui peuvent varier en temps ou en vitesse
• Algorithme de Hirschberg : trouve l' alignement de séquence le moins coûteux entre deux séquences, tel que mesuré par leur distance de Levenshtein
• Algorithme Needleman–Wunsch : trouver l'alignement global entre deux séquences
• Algorithme de Smith-Waterman : trouver l'alignement local des séquences

Tri de séquence

• Échanger des tris
  • Tri à bulles : pour chaque paire d'indices, échanger les éléments en cas de désordre
  • Tri par shaker ou tri à bulles bidirectionnel, un tri à bulles parcourant la liste alternativement d'avant en arrière et d'arrière en avant
  • Tri en peigne
  • Trier les gnomes
  • Tri impair-pair
  • Tri rapide : divisez la liste en deux, avec tous les éléments de la première liste avant tous les éléments de la deuxième liste. ; puis triez les deux listes. Souvent la méthode de choix
• Humoristique ou inefficace
  • Bogosort
  • Trier les Stooges
• Hybride
  • Tri Flash
  • Introsort : commencer par quicksort et passer au heapsort lorsque la profondeur de récursivité dépasse un certain niveau
  • Timsort : algorithme adaptatif dérivé du tri par fusion et du tri par insertion. Utilisé dans Python 2.3 et supérieur, et Java SE 7.
• Tris par insertion
  • Tri par insertion : détermine où appartient l'élément courant dans la liste des éléments triés, et l'y insère
  • Tri de la bibliothèque
  • Tri de patience
  • Shell sort : une tentative d'amélioration du tri par insertion
  • Tri d'arbres ( tri d'arbres binaires) : construisez un arbre binaire, puis parcourez-le pour créer une liste triée
  • Tri par cycle : en place avec un nombre d'écritures théoriquement optimal
• Fusionner les tris
  • Fusionner le tri : trier séparément la première et la seconde moitié de la liste, puis fusionner les listes triées
  • Tri lent
  • Tri des brins
• Tris sans comparaison
  • Tri de perles
  • Tri par godet
  • Burstsort : créez un trie de rafale compact et efficace en cache, puis parcourez-le pour créer une sortie triée
  • Tri par comptage
  • Trier les pigeonniers
  • Tri Postman : variante du tri Bucket qui profite de la structure hiérarchique
  • Tri par base : trie les chaînes lettre par lettre
• Tris par sélection
  • Heapsort : convertit la liste en un tas, continue de supprimer le plus gros élément du tas et de l'ajouter à la fin de la liste
  • Tri par sélection : choisissez le plus petit des éléments restants, ajoutez-le à la fin de la liste triée
  • Tri lisse
• Autre
  • Trieur bitonique
  • Tri des crêpes
  • Trier les spaghettis
  • Tri topologique
• Classe inconnue
  • Tri d'échantillons

Sous-séquences

• Algorithme de Kadane : trouve le sous-tableau maximum de n'importe quelle taille
• Problème de sous -séquence commune la plus longue : Trouver la sous-séquence la plus longue commune à toutes les séquences dans un ensemble de séquences
• Problème de la plus longue sous-suite croissante : Trouver la plus longue sous-suite croissante d'une séquence donnée
• Problème de super-séquence commune la plus courte : Trouvez la super-séquence la plus courte qui contient deux ou plusieurs séquences comme sous-séquences

Sous-chaînes

• Problème de sous-chaîne commune la plus longue : trouvez la ou les chaînes les plus longues qui sont une sous-chaîne (ou sont des sous-chaînes) de deux ou plusieurs chaînes
• Recherche de sous-chaîne
  • Algorithme de correspondance de chaînes Aho-Corasick : algorithme basé sur un trie pour trouver toutes les correspondances de sous-chaînes avec l'un des ensembles finis de chaînes
  • Boyer-Moore algorithme chaîne de recherche : linéaire amorti ( sous - linéaire algorithme dans la plupart du temps) pour la recherche substring
  • Algorithme Boyer–Moore–Horspool : Simplification de Boyer–Moore
  • Algorithme de Knuth–Morris–Pratt : recherche de sous-chaîne qui contourne le réexamen des caractères appariés
  • Algorithme de recherche de chaîne Rabin-Karp : recherche efficacement plusieurs modèles
  • Algorithme de correspondance de chaînes Zhu-Takaoka : une variante de Boyer-Moore
• L'algorithme de Ukkonen : un temps linéaire , algorithme en ligne pour la construction d' arbres suffixe
• Caractères génériques correspondants
  • Rich Salz ' wildmat : un algorithme récursif open source largement utilisé
  • Algorithme de correspondance de caractères génériques de Krauss : un algorithme non récursif open source

Mathématiques computationnelles

Algèbre abstraite

• Chien search : un algorithme récursif pour déterminer les racines de polynômes définis sur un corps fini
• Algorithme de Schreier-Sims : calcul d'un ensemble générateur de base et fort (BSGS) d'un groupe de permutation
• Algorithme de Todd–Coxeter : Procédure de génération des cosets .

Calcul formel

• Algorithme de Buchberger : trouve une base de Gröbner
• Algorithme de Cantor–Zassenhaus : factoriser des polynômes sur des corps finis
• Algorithme Faugère F4 : trouve une base de Gröbner (mentionne aussi l'algorithme F5)
• Algorithme de Gosper : trouver des sommes de termes hypergéométriques qui sont eux-mêmes des termes hypergéométriques
• Algorithme de complétion Knuth-Bendix : pour la réécriture des systèmes de règles
• Algorithme de division multivariée : pour les polynômes à plusieurs indéterminés
• Algorithme kangourou de Pollard (également connu sous le nom d'algorithme lambda de Pollard ): un algorithme pour résoudre le problème du logarithme discret
• Division longue polynomiale : un algorithme pour diviser un polynôme par un autre polynôme de même degré ou de degré inférieur
• Algorithme de Risch : un algorithme pour l'opération de calcul d'intégration indéfinie (c'est-à-dire trouver des primitives )

Géométrie

• Problème de paire la plus proche : trouver la paire de points (à partir d'un ensemble de points) avec la plus petite distance entre eux
• Algorithmes de détection de collision : vérifiez la collision ou l'intersection de deux solides donnés
• Algorithme de cône : identifier les points de surface
• Algorithmes d'enveloppe convexe : détermination de l' enveloppe convexe d'un ensemble de points
  • Numérisation de Graham
  • coque rapide
  • Algorithme d'emballage cadeau ou Jarvis mars
  • Algorithme de Chan
  • Algorithme de Kirkpatrick-Seidel
• Transformée de distance euclidienne : calcule la distance entre chaque point d'une grille et une collection discrète de points.
• Hachage géométrique : une méthode pour trouver efficacement des objets bidimensionnels représentés par des points discrets ayant subi une transformation affine
• Algorithme de distance Gilbert–Johnson–Keerthi : détermination de la plus petite distance entre deux formes convexes .
• Algorithme Jump-and-Walk : un algorithme de localisation de points dans les triangulations
• Lissage laplacien : un algorithme pour lisser un maillage polygonal
• Intersection de segment de ligne : rechercher si les lignes se coupent, généralement avec un algorithme de ligne de balayage
  • Algorithme de Bentley-Ottmann
  • Algorithme de Shamos-Hoey
• Algorithmes de la boîte englobante minimale : trouver la boîte englobante minimale orientée englobant un ensemble de points
• Recherche du voisin le plus proche : recherchez le ou les points les plus proches d'un point de requête
• Algorithmes de point dans un polygone : teste si un point donné se trouve dans un polygone donné
• Algorithmes d' enregistrement d'ensembles de points : recherche la transformation entre deux ensembles de points pour les aligner de manière optimale.
• Pieds à coulisse rotatifs : déterminez toutes les paires antipodales de points et de sommets sur un polygone convexe ou une enveloppe convexe .
• Algorithme Shoelace : déterminer l'aire d'un polygone dont les sommets sont décrits par paires ordonnées dans le plan
• Triangulation
  • Triangulation de Delaunay
    • Algorithme de Ruppert (également appelé raffinement de Delaunay) : créer des triangulations de Delaunay de qualité
    • Deuxième algorithme de Chew : créer des triangulations de Delaunay sous contraintes de qualité
  • Triangles en marche : reconstruire la géométrie de surface bidimensionnelle à partir d'un nuage de points non structuré
  • Algorithmes de triangulation de polygones : décomposer un polygone en un ensemble de triangles
  • Diagrammes de Voronoï , dual géométrique de la triangulation de Delaunay
    • Algorithme Bowyer–Watson : créer un diagramme de Voronoi dans un nombre quelconque de dimensions
    • Algorithme de Fortune : créer un diagramme de Voronoi
  • Quasitriangulation

Algorithmes de la théorie des nombres

• Algorithme binaire GCD : Moyen efficace de calculer GCD.
• Algorithme de multiplication de Booth
• Méthode Chakravala : un algorithme cyclique pour résoudre des équations quadratiques indéterminées, dont l'équation de Pell
• Logarithme discret :
  • Pas de bébé pas de géant
  • Algorithme de calcul d'index
  • Algorithme rho de Pollard pour les logarithmes
  • Algorithme de Pohlig-Hellman
• Algorithme euclidien : calcule le plus grand diviseur commun
• Algorithme euclidien étendu : résout également l'équation ax  +  by  =  c .
• Factorisation d'entiers : décomposer un entier en ses facteurs premiers
  • Congruence des carrés
  • Algorithme de Dixon
  • La méthode de factorisation de Fermat
  • Tamis de champ numéroté général
  • Factorisation de la courbe elliptique de Lenstra
  •  Algorithme p − 1 de Pollard
  • Algorithme rho de Pollard
  • algorithme de factorisation en nombres premiers
  • Tamis quadratique
  • Algorithme de Shor
  • Tamis de champ numéro spécial
  • Section de première instance
• Algorithmes de multiplication : multiplication rapide de deux nombres
  • Algorithme de Karatsuba
  • Algorithme de Schönhage-Strassen
  • Multiplication Toom-Cook
• Racine carrée modulaire : calcul des racines carrées modulo un nombre premier
  • Algorithme de Tonelli-Shanks
  • Algorithme de Cipolla
  • Algorithme de recherche de racine de Berlekamp
• Algorithme d'Odlyzko–Schönhage : calcule les zéros non triviaux de la fonction zêta de Riemann
• Algorithme de Lenstra–Lenstra–Lovász (également connu sous le nom d'algorithme LLL) : trouver une base de réseau courte et presque orthogonale en temps polynomial
• Tests de primalité : déterminer si un nombre donné est premier
  • Test de primalité AKS
  • Test de primalité Baillie-PSW
  • Test de primalité de Fermat
  • Test de primalité de Lucas
  • Test de primalité de Miller-Rabin
  • Tamis d'Atkin
  • Tamis d'Eratosthène
  • Tamis de Sundaram

Algorithmes numériques

Résolution d'équation différentielle

• Méthode d'Euler
• Méthode d'Euler en amont
• Règle trapézoïdale (équations différentielles)
• Méthodes linéaires à plusieurs étapes
• Méthodes Runge-Kutta
  • Intégration d'Euler
• Méthodes multigrilles ( méthodes MG), un groupe d'algorithmes pour résoudre des équations différentielles en utilisant une hiérarchie de discrétisations
• Equation aux dérivées partielles :
  • Méthode des différences finies
  • Méthode Crank-Nicolson pour les équations de diffusion
  • Lax–Wendroff pour les équations d'onde
• Intégration Verlet ( prononciation française: [vɛʁlɛ] ): intégrer les équations du mouvement de Newton

Fonctions élémentaires et spéciales

• Calcul de :
  • Algorithme de Borwein : un algorithme pour calculer la valeur de 1/π
  • Algorithme de Gauss–Legendre : calcule les chiffres de pi
  • Algorithme de Chudnovsky : Une méthode rapide pour calculer les chiffres de π
  • Formule de Bailey-Borwein-Plouffe : (formule BBP) un algorithme de spigot pour le calcul du nième chiffre binaire de π
• Algorithmes de division : pour calculer le quotient et/ou le reste de deux nombres
  • Division longue
  • Division restauration
  • Division sans restauration
  • Division SRT
  • Division Newton-Raphson : utilise la méthode de Newton pour trouver l' inverse de D, et multiplie cette réciproque par N pour trouver le quotient final Q.
  • Division Goldschmidt
• Fonctions hyperboliques et trigonométriques :
  • Algorithme BKM : calcule des fonctions élémentaires à l' aide d'une table de logarithmes
  • CORDIC : calcule des fonctions hyperboliques et trigonométriques à l'aide d'une table d'arctangentes
• Exponentiation :
  • Exponentiation en chaîne d'addition : exponentiation par des puissances entières positives qui nécessite un nombre minimal de multiplications
  • L'exponentiation par élévation au carré : un algorithme utilisé pour le calcul rapide de grandes puissances entières d'un nombre
• Réduction de Montgomery : un algorithme qui permet d'effectuer efficacement l'arithmétique modulaire lorsque le module est grand
• Algorithmes de multiplication : multiplication rapide de deux nombres
  • Algorithme de multiplication de Booth : un algorithme de multiplication qui multiplie deux nombres binaires signés en notation complémentaire à deux
  • Algorithme de Fürer : un algorithme de multiplication d'entiers pour de très grands nombres possédant une complexité asymptotique très faible
  • Algorithme de Karatsuba : une procédure efficace pour multiplier de grands nombres
  • Algorithme de Schönhage-Strassen : un algorithme de multiplication asymptotiquement rapide pour les grands entiers
  • Multiplication Toom–Cook : (Toom3) un algorithme de multiplication pour les grands entiers
• Algorithmes inverses multiplicatifs : pour calculer l'inverse multiplicatif d'un nombre (réciproque).
  • La méthode de Newton
• Fonctions d'arrondi : les manières classiques d'arrondir les nombres
• Algorithme Spigot : Un moyen de calculer la valeur d'une constante mathématique sans connaître les chiffres précédents
• Racine carrée et nième d'un nombre :
  • Algorithme Alpha max plus beta min : une approximation de la racine carrée de la somme de deux carrés
  • Méthodes de calcul des racines carrées
  • n ième algorithme racine
  • Algorithme de décalage de racine n : extraction de racine chiffre par chiffre
• Addition:
  • Le découpage binaire : une technique diviser pour régner qui accélère l'évaluation numérique de nombreux types de séries avec des termes rationnels
  • Algorithme de sommation de Kahan : une méthode plus précise de sommation de nombres à virgule flottante
• Algorithme illimité

Géométrique

• Rétroprojection filtrée : calcule efficacement la transformée de Radon bidimensionnelle inverse .
• Level set method (LSM) : une technique numérique pour le suivi des interfaces et des formes

Interpolation et extrapolation

• Interpolation de Birkhoff : une extension de l'interpolation polynomiale
• Interpolation cubique
• Interpolation Hermite
• Interpolation de Lagrange : interpolation à l'aide de polynômes de Lagrange
• Interpolation linéaire : une méthode d'ajustement de courbe utilisant des polynômes linéaires
• Interpolation cubique monotone : une variante de l'interpolation cubique qui préserve la monotonie de l'ensemble de données interpolé.
• Interpolation multivariée
  • Interpolation bicubique , une généralisation de l' interpolation cubique à deux dimensions
  • Interpolation bilinéaire : une extension de l'interpolation linéaire pour interpoler les fonctions de deux variables sur une grille régulière
  • Le rééchantillonnage de Lanczos ("Lanzosh") : une méthode d'interpolation multivariée utilisée pour calculer de nouvelles valeurs pour toutes les données échantillonnées numériquement
  • Interpolation du plus proche voisin
  • Interpolation tricubique , une généralisation de l' interpolation cubique à trois dimensions
• Interpolation de Pareto : méthode d'estimation de la médiane et d'autres propriétés d'une population qui suit une distribution de Pareto .
• Interpolation polynomiale
  • L'algorithme de Neville
• Interpolation spline : Réduit l'erreur avec le phénomène de Runge .
  • Algorithme de De Boor : B-splines
  • Algorithme de De Casteljau : courbes de Bézier
• Interpolation trigonométrique

Algèbre linéaire

• Algorithmes de valeurs propres
  • Itération d'Arnoldi
  • Itération inverse
  • Méthode Jacobi
  • Itération de Lanczos
  • Itération de puissance
  • Algorithme QR
  • Itération du quotient de Rayleigh
• Processus de Gram–Schmidt : orthogonalise un ensemble de vecteurs
• Algorithmes de multiplication matricielle
  • Algorithme de Cannon : un algorithme distribué de multiplication matricielle particulièrement adapté aux ordinateurs disposés dans un maillage N × N
  • Algorithme Coppersmith–Winograd : multiplication matricielle carrée
  • Algorithme de Freivalds : un algorithme aléatoire utilisé pour vérifier la multiplication matricielle
  • Algorithme de Strassen : multiplication matricielle plus rapide

• Résolution de systèmes d'équations linéaires
  • Méthode du gradient biconjugué : résout des systèmes d'équations linéaires
  • Gradient conjugué : un algorithme pour la résolution numérique de systèmes particuliers d'équations linéaires
  • Élimination gaussienne
  • Elimination de Gauss-Jordan : résout des systèmes d'équations linéaires
  • Méthode de Gauss–Seidel : résout les systèmes d'équations linéaires de manière itérative
  • Récursion de Levinson : résout une équation impliquant une matrice de Toeplitz
  • La méthode de Stone : également connue sous le nom de procédure fortement implicite ou SIP, est un algorithme permettant de résoudre un système d'équations linéaires creux
  • Sur-relaxation successive (SOR) : méthode utilisée pour accélérer la convergence de la méthode de Gauss-Seidel
  • Algorithme matriciel tridiagonal ( algorithme de Thomas) : résout des systèmes d'équations tridiagonales
• Algorithmes de matrice creuse
  • Algorithme Cuthill–McKee : réduire la bande passante d'une matrice creuse symétrique
  • Algorithme de degré minimum : permuter les lignes et les colonnes d'une matrice creuse symétrique avant d'appliquer la décomposition de Cholesky
  • Décomposition symbolique de Cholesky : moyen efficace de stocker une matrice creuse

monte Carlo

• Échantillonnage de Gibbs : génère une séquence d'échantillons à partir de la distribution de probabilité conjointe de deux ou plusieurs variables aléatoires
• Hybrid Monte Carlo : génère une séquence d'échantillons en utilisant la chaîne de Markov pondérée hamiltonienne Monte Carlo , à partir d'une distribution de probabilité difficile à échantillonner directement.
• Algorithme Metropolis–Hastings : utilisé pour générer une séquence d'échantillons à partir de la distribution de probabilité d'une ou plusieurs variables
• Algorithme de Wang et Landau : une extension de l' échantillonnage de l' algorithme de Metropolis-Hastings

Intégration numérique

• Algorithme MISER : simulation Monte Carlo, intégration numérique

Recherche de racine

• Méthode de bissection
• Méthode des fausses positions : approxime les racines d'une fonction
• Méthode ITP : convergence optimale minmax et superlinaire simultanément
• Méthode de Newton : trouve les zéros des fonctions avec le calcul
• Méthode de Halley : utilise les dérivées premières et secondes
• Méthode sécante : 2 points, 1 côté
• Méthode des fausses positions et méthode de l' Illinois : 2 points, bracketing
• Méthode de Ridder : 3 points, mise à l'échelle exponentielle
• Méthode de Muller : 3 points, interpolation quadratique

Algorithmes d'optimisation

• Élagage alpha-bêta : recherche pour réduire le nombre de nœuds dans l'algorithme minimax
• Branché et lié
• Algorithme de Bruss : voir algorithme de cotes
• Multiplication matricielle en chaîne
• Optimisation combinatoire : problèmes d'optimisation où l'ensemble des solutions réalisables est discret
  • Procédure de recherche adaptative randomisée gloutonne (GRASP) : constructions successives d'une solution randomisée gloutonne et améliorations itératives ultérieures de celle-ci grâce à une recherche locale
  • Méthode hongroise : un algorithme d'optimisation combinatoire qui résout le problème d'affectation en temps polynomial
• Satisfaction des contraintes
  • Algorithmes généraux pour la satisfaction de contraintes
    • Algorithme AC-3
    • Algorithme de carte de différence
    • Algorithme de conflits minimum
  • Algorithme Chaff : un algorithme pour résoudre des instances du problème de satisfiabilité booléenne
  • Algorithme de Davis-Putnam : vérifier la validité d'une formule logique du premier ordre
  • Algorithme Davis-Putnam-Logemann-Loveland (DPLL): un algorithme pour décider de la satisfaisabilité de la formule logique propositionnelle en forme normale conjonctive , soit pour résoudre le CNF-SAT problème
  • Problème de couverture exacte
    • Algorithme X : un algorithme non déterministe
    • Dancing Links : une implémentation efficace de l'algorithme X
• Méthode d'entropie croisée : une approche générale de Monte Carlo pour l'optimisation multi-extrémale combinatoire et continue et l' échantillonnage d'importance
• Évolution différentielle
• Programmation dynamique : problèmes présentant les propriétés de sous - problèmes superposés et de sous - structure optimale
• Méthode ellipsoïde : est un algorithme pour résoudre des problèmes d'optimisation convexe
• Calcul évolutif : optimisation inspirée des mécanismes biologiques de l'évolution
  • Stratégie d'évolution
  • Programmation de l'expression génique
  • Algorithmes génétiques
    • Sélection proportionnelle de la condition physique – également connue sous le nom de sélection de la roulette
    • Échantillonnage universel stochastique
    • Sélection de troncature
    • Sélection du tournoi
  • Algorithme mémétique
  • L'intelligence en essaim
    • Optimisation des colonies de fourmis
    • Algorithme des abeilles : un algorithme de recherche qui imite le comportement de recherche de nourriture d'essaims d'abeilles mellifères
    • Essaim de particules
• Algorithme de Frank-Wolfe : un algorithme d'optimisation du premier ordre itératif pour l'optimisation convexe sous contraintes
• Recherche par section d'or : un algorithme pour trouver le maximum d'une fonction réelle
• Descente graduelle
• Recherche de grille
• Recherche d'harmonie (HS) : un algorithme métaheuristique imitant le processus d'improvisation des musiciens
• Méthode du point intérieur
• Programmation linéaire
  • Algorithme de Benson : un algorithme pour résoudre des problèmes d' optimisation vectorielle linéaire
  • Décomposition de Dantzig-Wolfe : un algorithme pour résoudre des problèmes de programmation linéaire avec une structure spéciale
  • Génération de colonne retardée
  • Programmation linéaire en nombres entiers : résoudre des problèmes de programmation linéaire où certaines ou toutes les inconnues sont restreintes à des valeurs entières
    • Brancher et couper
    • Méthode du plan de coupe
  • Algorithme de Karmarkar : Le premier algorithme raisonnablement efficace qui résout le problème de programmation linéaire en temps polynomial .
  • Algorithme simplex : Un algorithme pour résoudre des problèmes de programmation linéaire
• Recherche de ligne
• Recherche locale : une métaheuristique pour résoudre des problèmes d'optimisation informatiquement difficiles
  • Escalade à redémarrage aléatoire
  • Recherche tabou
• Minimax utilisé dans la programmation de jeux
• Recherche du voisin le plus proche (NNS) : recherchez les points les plus proches dans un espace métrique
  • Best Bin First : trouver une solution approximative au problème de recherche du voisin le plus proche dans des espaces de très grande dimension
• La méthode de Newton en optimisation
• Optimisation non linéaire
  • Méthode BFGS : Un algorithme d' optimisation non linéaire
  • Algorithme de Gauss-Newton : Un algorithme pour résoudre les problèmes des moindres carrés non linéaires .
  • Algorithme de Levenberg-Marquardt : Un algorithme pour résoudre les problèmes des moindres carrés non linéaires .
  • Méthode de Nelder-Mead ( méthode du simplex en descente) : un algorithme d' optimisation non linéaire
• Algorithme de cotes ( algorithme de Bruss) : trouve la stratégie optimale pour prédire un dernier événement spécifique dans un événement de séquence aléatoire
• Recherche aléatoire
• Recuit simulé
• Tunnellisation stochastique
• Algorithme de somme de sous-ensemble

Science informatique

Astronomie

• Algorithme Doomsday : jour de la semaine
• La congruence de Zeller est un algorithme pour calculer le jour de la semaine pour n'importe quelle date du calendrier julien ou grégorien
• divers algorithmes de Pâques sont utilisés pour calculer le jour de Pâques

Bioinformatique

• Outil de recherche d'alignement local de base également connu sous le nom de BLAST : un algorithme pour comparer les informations de séquence biologique primaire
• Algorithme de Kabsch : calcul de l'alignement optimal de deux ensembles de points afin de calculer l' écart quadratique moyen entre deux structures protéiques.
• Velvet : un ensemble d'algorithmes manipulant des graphes de Bruijn pour l' assemblage de séquences génomiques
• Tri par renversements signés : un algorithme pour comprendre l'évolution génomique.
• Parcimonie maximale (phylogénétique) : un algorithme pour trouver l'arbre phylogénétique le plus simple pour expliquer une matrice de caractères donnée.
• UPGMA : un algorithme de construction d'arbres phylogénétiques basé sur la distance.

Géosciences

• Les formules de Vincenty : un algorithme rapide pour calculer la distance entre deux points de latitude/longitude sur un ellipsoïde
• Geohash : un algorithme du domaine public qui code une paire latitude/longitude décimale sous forme de chaîne de hachage

Linguistique

• Algorithme Lesk : désambiguïsation du sens des mots
• Algorithme de racine : une méthode de réduction des mots à leur forme radicale, base ou racine
• Algorithme de Sukhotin : un algorithme de classification statistique pour classer les caractères d'un texte en voyelles ou en consonnes

Médicament

• Algorithme ESC pour le diagnostic de l'insuffisance cardiaque
• Critères de Manning pour le syndrome du côlon irritable
• Algorithmes de diagnostic de l' embolie pulmonaire
• Projet d'algorithme de médicament du Texas

La physique

• Algorithme de contraintes : une classe d'algorithmes pour satisfaire des contraintes pour les corps qui obéissent aux équations du mouvement de Newton
• Algorithme Demon : une méthode de Monte Carlo pour échantillonner efficacement les membres d'un ensemble microcanonique avec une énergie donnée
• Algorithme de Featherstone : calcule les effets des forces appliquées à une structure de joints et de liens
• Approximation de l' état fondamental
  • Méthode variationnelle
    • Méthode Ritz
• n -problèmes de corps
  • Simulation de Barnes-Hut : résout le problème à n corps d'une manière approximative qui a l'ordre O( n log n ) au lieu de O( n ² ) comme dans une simulation à somme directe.
  • Méthode multipolaire rapide (FMM) : accélère le calcul des forces à longue distance
• Algorithme de comptage de Rainflow : réduit un historique de contraintes complexe à un nombre d'inversions de contraintes élémentaires à utiliser dans l' analyse de fatigue
• Sweep and prune : un algorithme de phase large utilisé lors de la détection de collision pour limiter le nombre de paires de solides qui doivent être vérifiés pour la collision
• Algorithme VEGAS : une méthode pour réduire l'erreur dans les simulations de Monte Carlo
• Dynamique de Glauber : une méthode pour simuler le modèle d'Ising sur un ordinateur

Statistiques

• Algorithmes de calcul de la variance : éviter l'instabilité et le débordement numérique
• Algorithme de comptage approximatif : Permet de compter un grand nombre d'événements dans un petit registre
• Statistiques bayésiennes
  • Algorithme d'échantillonnage imbriqué : une approche computationnelle du problème de comparaison de modèles en statistique bayésienne
• Algorithmes de clustering
  • Clustering à liaison moyenne : un algorithme de clustering agglomérateur simple
  • Algorithme de clustering Canopy : un algorithme de pré-clustering non supervisé lié à l'algorithme K-means
  • Clustering à liaison complète : un algorithme de clustering agglomérateur simple
  • DBSCAN : un algorithme de clustering basé sur la densité
  • Algorithme de maximisation des attentes
  • Clustering flou : une classe d'algorithmes de clustering où chaque point a un degré d'appartenance à des clusters
    • C-moyen flou
    • Clustering FLAME (Fuzzy clustering by Local Approximation of MEmberships) : définissez des clusters dans les parties denses d'un ensemble de données et effectuez une affectation de cluster uniquement en fonction des relations de voisinage entre les objets
  • Algorithme de clustering KHOPCA : un algorithme de clustering local, qui produit des clusters hiérarchiques multi-sauts dans des environnements statiques et mobiles.
  • clustering k-means : regrouper des objets basés sur des attributs dans des partitions
  • k-means++ : une variante de ceci, en utilisant des graines aléatoires modifiées
  • k-medoids : similaire à k-means, mais choisit des points de données ou des medoids comme centres
  • Algorithme de Linde–Buzo–Gray : un algorithme de quantification vectorielle pour dériver un bon livre de codes
  • Algorithme de Lloyd (itération ou relaxation de Voronoi) : regrouper les points de données dans un nombre donné de catégories, un algorithme populaire pour le clustering k-means
  • OPTIQUE : un algorithme de clustering basé sur la densité avec une méthode d'évaluation visuelle
  • Clustering à liaison unique : un algorithme de clustering agglomérateur simple
  • SUBCLU : un algorithme de clustering de sous-espace
  • Méthode de Ward : un algorithme de clustering agglomératif, étendu à des algorithmes plus généraux de Lance-Williams
  • Algorithme de clustering WACA : un algorithme de clustering local avec des structures potentiellement multi-sauts ; pour les réseaux dynamiques
• Théorie de l'estimation
  • Algorithme de maximisation des attentes Une classe d'algorithmes connexes pour trouver des estimations de vraisemblance maximale de paramètres dans des modèles probabilistes
    • La maximisation de l' espérance de sous - ensemble ordonné (de OSEM): utilisé dans l' imagerie médicale pour la tomographie par émission de positrons , tomographie d'émission monophotonique et des rayons X tomographie assistée par ordinateur.
  • Algorithme de cotes ( algorithme de Bruss) Recherche en ligne optimale pour une valeur distinctive dans une entrée aléatoire séquentielle
  • Filtre de Kalman : estimer l'état d'un système dynamique linéaire à partir d'une série de mesures bruitées
• L'algorithme du faux voisin le plus proche (FNN) estime la dimension fractale
• Modèle de Markov caché
  • Algorithme Baum-Welch : calcule des estimations de vraisemblance maximale et des estimations de mode postérieur pour les paramètres d'un modèle de Markov caché
  • Algorithme forward-backward : un algorithme de programmation dynamique pour calculer la probabilité d'une séquence d'observation particulière
  • Algorithme de Viterbi : trouver la séquence d'états cachés la plus probable dans un modèle de Markov caché
• Régression des moindres carrés partiels : trouve un modèle linéaire décrivant certaines variables prédites en termes d'autres variables observables
• Théorie des files d'attente
  • Algorithme de Buzen : un algorithme pour calculer la constante de normalisation G(K) dans le théorème de Gordon-Newell
• RANSAC (abréviation de " RANdom SAmple Consensus ") : une méthode itérative pour estimer les paramètres d'un modèle mathématique à partir d'un ensemble de données observées contenant des valeurs aberrantes
• Algorithme de notation : est une forme de la méthode de Newton utilisée pour résoudre numériquement les équations du maximum de vraisemblance
• Méthode Yamartino : calcule une approximation de l'écart type σθ de la direction du vent θ lors d'un seul passage à travers les données entrantes
• Algorithme Ziggurat : génère des nombres aléatoires à partir d'une distribution non uniforme

L'informatique

L'architecture des ordinateurs

• Algorithme Tomasulo : permet à des instructions séquentielles qui seraient normalement bloquées en raison de certaines dépendances de s'exécuter de manière non séquentielle

Infographie

• Coupure
  • Coupure de ligne
    • Cohen–Sutherland
    • Cyrus–Beck
    • Clipping rapide
    • Liang-Barsky
    • Nicholl–Lee–Nicholl
  • Découpage de polygone
    • Sutherland–Hodgman
    • Vatti
    • Weiler–Atherton
• Lignes de contour et isosurfaces
  • Marching cubes : extraire un maillage polygonal d'une isosurface à partir d'un champ scalaire tridimensionnel (parfois appelé voxels)
  • Carrés de marche : génère des courbes de niveau pour un champ scalaire bidimensionnel
  • Les tétraèdres de marche : une alternative aux cubes de marche
• Théorème de Green discret : est un algorithme de calcul d'intégrale double sur un domaine rectangulaire généralisé en temps constant. C'est une extension naturelle de l'algorithme de la table des aires sommées
• Remplissage d'inondation : remplit une région connectée d'un tableau multidimensionnel avec un symbole spécifié
• Algorithmes d' illumination globale : prend en compte l'illumination directe et la réflexion d'autres objets.
  • Occlusion ambiante
  • Traçage de faisceau
  • Traçage du cône
  • Éclairage basé sur l'image
  • Transports légers de la métropole
  • Traçage de chemin
  • Cartographie des photons
  • Radiosité
  • tracé laser
• Élimination des surfaces cachées ou détermination visuelle de la surface
  • Algorithme de Newell : éliminer les cycles de polygones dans le tri en profondeur requis dans l'élimination des surfaces cachées
  • Algorithme de Painter : détecte les parties visibles d'un décor en 3 dimensions
  • Rendu Scanline : construit une image en déplaçant une ligne imaginaire sur l'image
  • Algorithme de Warnock
• Line Drawing : algorithme graphique d'approximation d'un segment de ligne sur des supports graphiques discrets.
  • Algorithme de ligne de Bresenham : trace les points d'un tableau à 2 dimensions pour former une ligne droite entre 2 points spécifiés (utilise des variables de décision)
  • Algorithme de ligne DDA : trace les points d'un tableau à 2 dimensions pour former une ligne droite entre 2 points spécifiés (utilise des calculs à virgule flottante)
  • Algorithme de ligne de Xiaolin Wu : algorithme d'anticrénelage de ligne.
• Algorithme du cercle médian : un algorithme utilisé pour déterminer les points nécessaires pour tracer un cercle
• Algorithme de Ramer-Douglas-Peucker : Étant donné une "courbe" composée de segments de ligne pour trouver une courbe pas trop dissemblable mais qui a moins de points
• Ombres
  • Ombrage Gouraud : un algorithme pour simuler les différents effets de lumière et de couleur sur la surface d'un objet en infographie 3D
  • Phong shading : un algorithme pour interpoler les vecteurs normaux de surface pour l'ombrage de surface en infographie 3D
• Slerp (interpolation linéaire sphérique) : interpolation de quaternions dans le but d'animer la rotation 3D
• Table des aires sommées (également appelée image intégrale) : un algorithme pour calculer la somme des valeurs dans un sous-ensemble rectangulaire d'une grille en temps constant

Cryptographie

• Cryptage asymétrique (clé publique) :
  • ElGamal
  • Cryptographie à courbe elliptique
  • MAE1
  • NTRUcrypter
  • RSA
• Signatures numériques (authentification asymétrique) :
  • DSA , et ses variantes :
    • ECDSA et ECDSA déterministe
    • EdDSA (Ed25519)
  • RSA
• Fonctions de hachage cryptographique (voir également la section sur les codes d'authentification des messages) :
  • BLAKE
  • MD5 – Notez qu'il existe maintenant une méthode de génération de collisions pour MD5
  • RIPEMD-160
  • SHA-1 – Notez qu'il existe désormais une méthode de génération de collisions pour SHA-1
  • SHA-2 (SHA-224, SHA-256, SHA-384, SHA-512)
  • SHA-3 (SHA3-224, SHA3-256, SHA3-384, SHA3-512, SHAKE128, SHAKE256)
  • Tiger (TTH), généralement utilisé dans les hachages d'arbres Tiger
  • TOURBILLON
• Générateurs de nombres pseudo-aléatoires sécurisés cryptographiquement
  • Blum Blum Shub – basé sur la dureté de la factorisation
  • Fortuna , conçu comme une amélioration de l' algorithme Yarrow
  • Registre à décalage à rétroaction linéaire (remarque : de nombreux algorithmes basés sur LFSR sont faibles ou ont été brisés)
  • Algorithme de millefeuille
• Échange de clés
  • Échange de clés Diffie–Hellman
  • Courbe elliptique Diffie–Hellman (ECDH)
• Fonctions de dérivation de clé , souvent utilisées pour le hachage de mot de passe et l' extension de clé
  • bcrypt
  • PBKDF2
  • crypter
  • Argon2
• Codes d'authentification des messages (algorithmes d'authentification symétrique, qui prennent une clé en paramètre) :
  • HMAC : authentification par message de hachage à clé
  • Poly1305
  • SipHash
• Partage de secret, partage de secret, partage de clé, algorithmes M of N
  • Le schéma de Blakey
  • Le schéma de Shamir
• Cryptage symétrique (clé secrète) :
  • Advanced Encryption Standard (AES), lauréat du concours NIST , également connu sous le nom de Rijndael
  • Poisson-globe
  • Deux Poisson
  • Trois poissons
  • Data Encryption Standard (DES), parfois DE Algorithm, lauréat du concours de sélection NBS, remplacé par AES dans la plupart des cas
  • IDÉE
  • RC4 (chiffre)
  • Minuscule algorithme de cryptage (TEA)
  • Salsa20 , et sa variante mise à jour ChaCha20
• Cryptographie post-quantique
• Algorithmes de preuve de travail

Logique numérique

• Minimisation booléenne
  • Algorithme de Quine-McCluskey : Aussi appelé algorithme QM, méthode programmable pour simplifier les équations booléennes.
  • Méthode de Petrick : Un autre algorithme de simplification booléenne.
  • Minimiseur logique heuristique expresso : Algorithme rapide pour la minimisation des fonctions booléennes.

Apprentissage automatique et classification statistique

• ALOPEX : un algorithme d'apprentissage automatique basé sur la corrélation
• Apprentissage des règles d'association : découvrez des relations intéressantes entre variables, utilisées dans l'exploration de données
  • Algorithme a priori
  • Algorithme Éclat
  • Algorithme de croissance FP
  • Règle à un attribut
  • Règle d'attribut zéro
• Boosting (méta-algorithme) : Utilisez de nombreux apprenants faibles pour augmenter l'efficacité
  • AdaBoost : boost adaptatif
  • BrownBoost : un algorithme de boost qui peut être robuste aux jeux de données bruités
  • LogitBoost : booster la régression logistique
  • LPBoost : boost de programmation linéaire
• Agrégation bootstrap (bagging) : technique pour améliorer la stabilité et la précision de la classification
• Vision par ordinateur
  • Grabcut basé sur des coupes graphiques
• Arbres de décision
  • Algorithme C4.5 : une extension à ID3
  • Algorithme ID3 (Iterative Dichotomiser 3) : utiliser l'heuristique pour générer de petits arbres de décision
• Clustering : une classe d' algorithmes d' apprentissage non supervisé pour le regroupement et le bucketing des vecteurs d'entrée liés.
  • k-nearest voisins (k-NN) : une méthode de classification des objets basée sur les exemples d'apprentissage les plus proches dans l' espace des caractéristiques
• Algorithme de Linde–Buzo–Gray : un algorithme de quantification vectorielle utilisé pour dériver un bon livre de codes
• Hachage sensible à la localité (LSH) : une méthode pour effectuer une réduction de dimension probabiliste de données de grande dimension
• Réseau neuronal
  • Rétropropagation : Une méthode d' apprentissage supervisé qui nécessite un enseignant qui connaît, ou peut calculer, la sortie souhaitée pour une entrée donnée
  • Hopfield net : un réseau de neurones récurrents dans lequel toutes les connexions sont symétriques
  • Perceptron : le type le plus simple de réseau de neurones feedforward : un classificateur linéaire .
  • Réseaux de neurones à couplage d'impulsions (PCNN) : modèles de neurones proposés en modélisant le cortex visuel d' un chat et développés pour le traitement d'images biomimétiques haute performance .
  • Réseau de fonctions de base radiale : un réseau de neurones artificiels qui utilise des fonctions de base radiales comme fonctions d'activation
  • Carte auto-organisatrice : un réseau non supervisé qui produit une représentation en basse dimension de l'espace d'entrée des échantillons d'apprentissage
• Forêt aléatoire : classer en utilisant de nombreux arbres de décision
• Apprentissage par renforcement :
  • Q-learning : apprend une fonction action-valeur qui donne l'utilité attendue de prendre une action donnée dans un état donné et de suivre une politique fixe par la suite
  • État–Action–Récompense–État–Action (SARSA) : apprendre une politique de processus décisionnel de Markov
  • Apprentissage de la différence temporelle
• Machine à vecteurs de pertinence (RVM) : similaire à SVM, mais fournit une classification probabiliste
• Apprentissage supervisé : apprentissage par des exemples (ensemble de données étiqueté divisé en ensemble d'apprentissage et ensemble de test)
• Support-Vector Machine (SVM) : un ensemble de méthodes qui divisent des données multidimensionnelles en trouvant un hyperplan de division avec la marge maximale entre les deux ensembles
  • SVM structuré : permet l'apprentissage d'un classificateur pour les étiquettes de sortie structurées générales.
• Algorithme Winnow : lié au perceptron, mais utilise un schéma multiplicatif de mise à jour du poids

Théorie du langage de programmation

• Linéarisation C3 : un algorithme utilisé principalement pour obtenir une linéarisation cohérente d'une hiérarchie d'héritage multiple en programmation orientée objet
• Algorithme de Chaitin : un algorithme d'allocation de registres de coloration de graphe ascendant qui utilise le coût/degré comme métrique de débordement
• Algorithme d'inférence de type Hindley-Milner
• Algorithme Rete : un algorithme de filtrage efficace pour la mise en œuvre de systèmes de règles de production
• Algorithme Sethi-Ullman : génère un code optimal pour les expressions arithmétiques

Analyse

• Algorithme CYK : Un algorithme O(n ³ ) pour l'analyse de grammaires sans contexte sous la forme normale de Chomsky
• Analyseur Earley : Un autre algorithme O(n ³ ) pour analyser n'importe quelle grammaire sans contexte
• Analyseur GLR : Un algorithme pour analyser n'importe quelle grammaire sans contexte par Masaru Tomita . Il est adapté aux grammaires déterministes, sur lesquelles il effectue un temps presque linéaire et O(n ³ ) dans le pire des cas.
• Algorithme inside-outside : Un algorithme O(n ³ ) pour ré-estimer les probabilités de production dans les grammaires probabilistes sans contexte
• LL parser : Un algorithme d'analyse temporelle linéaire relativement simple pour une classe limitée de grammaires sans contexte
• Analyseur LR : un algorithme d'analyse temporelle linéaire plus complexe pour une plus grande classe de grammaires sans contexte . Variantes :
  • Analyseur LR canonique
  • Analyseur LALR (look-ahead LR)
  • Analyseur de priorité des opérateurs
  • Analyseur SLR (Simple LR)
  • Analyseur de priorité simple
• Analyseur Packrat : Un algorithme d'analyse temporelle linéaire prenant en charge certaines grammaires sans contexte et des grammaires d'expression d'analyse
• Analyseur de descente récursive : Un analyseur descendant adapté aux grammaires LL( k )
• Algorithme shunting-yard : convertit une expression mathématique en notation infixe en suffixe
• Analyseur Pratt
• Analyse lexicale

Algorithmes quantiques

• Algorithme de Deutsch–Jozsa : critère d'équilibre pour la fonction booléenne
• Algorithme de Grover : fournit une accélération quadratique pour de nombreux problèmes de recherche
• Algorithme de Shor : fournit une accélération exponentielle (par rapport aux algorithmes non quantiques actuellement connus) pour factoriser un nombre
• Algorithme de Simon : fournit une accélération prouvablement exponentielle (par rapport à tout algorithme non quantique) pour un problème de boîte noire

Théorie du calcul et automates

• L'algorithme de Hopcroft , l'algorithme de Moore , et l' algorithme de Brzozowski : algorithmes pour minimiser le nombre d'états dans un automate fini déterministe
• Construction de Powerset : Algorithme pour convertir un automate non déterministe en automate déterministe .
• Algorithme de Tarski-Kuratowski : un algorithme non déterministe qui fournit une borne supérieure pour la complexité des formules dans la hiérarchie arithmétique et la hiérarchie analytique

Théorie de l'information et traitement du signal

Théorie du codage

Détection et correction des erreurs

• Codes BCH
  • Algorithme de Berlekamp-Massey
  • Algorithme de Peterson-Gorenstein-Zierler
  • Correction d'erreur Reed-Solomon
• Algorithme BCJR : décodage de codes correcteurs d'erreurs définis sur des treillis (principalement des codes convolutifs)
• Correction d'erreur directe
• Code gris
• Codes de Hamming
  • Hamming(7,4) : un code de Hamming qui encode 4 bits de données en 7 bits en ajoutant 3 bits de parité
  • Distance de Hamming : somme du nombre de positions différentes
  • Poids de Hamming (dénombrement de population) : trouver le nombre de bits 1 dans un mot binaire
• Contrôles de redondance
  • Adler-32
  • Contrôle de redondance cyclique
  • Algorithme de Damm
  • Somme de contrôle de Fletcher
  • Contrôle de redondance longitudinale (LRC)
  • Algorithme de Luhn : une méthode de validation des numéros d'identification
  • Algorithme Luhn mod N : extension de Luhn aux caractères non numériques
  • Parité : technique de détection d'erreur simple/rapide
  • Algorithme de Verhoeff

Algorithmes de compression sans perte

• Transformée de Burrows–Wheeler : prétraitement utile pour améliorer la compression sans perte
• Pondération de l'arbre de contexte
• Encodage delta : aide à la compression de données dans lesquelles des données séquentielles se produisent fréquemment
• Compression dynamique de Markov : Compression par codage arithmétique prédictif
• Codeurs de dictionnaire
  • Codage de paires d'octets (BPE)
  • Dégonfler
  • Lempel–Ziv
    • LZ77 et LZ78
    • Lempel–Ziv Jeff Bonwick (LZJB)
    • Algorithme de chaîne de Lempel-Ziv-Markov (LZMA)
    • Lempel–Ziv–Oberhumer (LZO) : axé sur la vitesse
    • Lempel–Ziv–Stac (LZS)
    • Lempel–Ziv–Storer–Szymanski (LZSS)
    • Lempel–Ziv–Welch (LZW)
    • LZWL : variante basée sur la syllabe
    • LZX
    • Lempel–Ziv Ross Williams (LZRW)
• Codage entropique : schéma de codage qui attribue des codes aux symboles de manière à faire correspondre les longueurs de code avec les probabilités des symboles
  • Codage arithmétique : codage entropique avancé
    • Codage de plage : identique au codage arithmétique , mais vu d'une manière légèrement différente
  • Codage de Huffman : compression sans perte simple tirant parti des fréquences relatives des caractères
    • Codage adaptatif de Huffman : technique de codage adaptatif basée sur le codage de Huffman
    • Algorithme de fusion de packages : optimise le codage de Huffman sous réserve d'une restriction de longueur sur les chaînes de code
  • Codage Shannon-Fano
  • Codage Shannon–Fano–Elias : précurseur du codage arithmétique
• Codage entropique avec des caractéristiques entropiques connues
  • Codage de Golomb : forme de codage entropique optimale pour les alphabets suivant des distributions géométriques
  • Codage Rice : forme de codage entropique optimale pour les alphabets suivant des distributions géométriques
  • Encodage binaire tronqué
  • Codage unaire : code qui représente un nombre n avec n suivis d'un zéro
  • Codes universels : encode les entiers positifs en mots de code binaires
    • Codage Elias delta , gamma et oméga
    • Codage exponentiel-Golomb
    • Codage de Fibonacci
    • Codage Levenshtein
• Système de compression d'image rapide et sans perte (FELICS) : un algorithme de compression d'image sans perte
• Encodage incrémental : encodage delta appliqué aux séquences de chaînes
• Prédiction par appariement partiel (PPM) : une technique de compression de données statistiques adaptative basée sur la modélisation et la prédiction du contexte
• Encodage run-length : compression de données sans perte tirant parti des chaînes de caractères répétés
• Algorithme SEQUITUR : compression sans perte par inférence grammaticale incrémentale sur une chaîne

Algorithmes de compression avec perte

• 3Dc : un algorithme de compression de données avec perte pour les cartes normales
• Compression audio et vocale
  • Algorithme A-law : algorithme de compression-extension standard
  • Prédiction linéaire excitée par le code (CELP) : compression de la parole à faible débit
  • Codage prédictif linéaire (LPC) : compression avec perte en représentant l' enveloppe spectrale d'un signal numérique de parole sous forme compressée
  • Algorithme Mu-law :
  algorithme standard de compression ou de compression-extension de signal analogique
• Codage prédictif linéaire déformé (WLPC)

Compression d'images

• Block Troncation Coding (BTC) : un type de technique de compression d'image avec perte pour les images en niveaux de gris
• Ondelette Zerotree intégrée (EZW)
• Algorithmes de transformation en cosinus rapide ( algorithmes FCT) : calcule efficacement la transformation en cosinus discrète (DCT)
• Compression fractale : méthode utilisée pour compresser des images à l'aide de fractales
• Définir le partitionnement dans les arbres hiérarchiques (SPIHT)
• Compression en ondelettes : forme de compression de données bien adaptée à la compression d'images (parfois aussi compression vidéo et compression audio)

Codage par transformation : type de compression de données pour des données "naturelles" comme des signaux audio ou des images photographiques

Compression de vidéo

Quantification vectorielle : technique souvent utilisée en compression de données avec perte

Traitement des signaux numériques

• Algorithme adaptatif-additif ( algorithme AA) : trouvez la phase de fréquence spatiale d'une source d'onde observée
• Transformée de Fourier discrète : détermine les fréquences contenues dans un (segment de a) signal
  • Algorithme FFT de Bluestein
  • Algorithme FFT de Bruun
  • Algorithme FFT de Cooley-Tukey
  • Transformée de Fourier Rapide
  • Algorithme FFT à facteur premier
  • Algorithme FFT de Rader
• Algorithme de repliement rapide : un algorithme efficace pour la détection d'événements approximativement périodiques dans les données de séries chronologiques
• Algorithme de Gerchberg-Saxton : Algorithme de récupération de phase pour les plans optiques
• Algorithme de Goertzel : identifie une composante fréquentielle particulière dans un signal. Peut être utilisé pour le décodage des chiffres DTMF .
• Synthèse de cordes Karplus-Strong : synthèse de modélisation physique pour simuler le son d'une corde martelée ou pincée ou de certains types de percussion

Traitement d'image

• Amélioration du contraste
  • Égalisation de l'histogramme : utilisez l'histogramme pour améliorer le contraste de l'image
  • Égalisation d'histogramme adaptative : égalisation d' histogramme qui s'adapte aux changements locaux de contraste
• Étiquetage des composants connectés : recherche et étiquetage des régions disjointes
• Tramage et demi-teinte
  • Diffusion d'erreurs
  • Trempage Floyd-Steinberg
  • Tramage ordonné
  • Riemersma tramage
• Elser difference-map algorithm : un algorithme de recherche pour les problèmes généraux de satisfaction de contraintes. Utilisé à l'origine pour la microscopie à diffraction des rayons X
• Détection de caractéristiques
  • Détecteur de bords Canny : détectez une large gamme de bords dans les images
  • Transformée de Hough généralisée
  • Hough transformer
  • Algorithme de Marr-Hildreth : un algorithme de détection précoce des contours
  • SIFT (Scale-invariant feature transform) : est un algorithme pour détecter et décrire des caractéristiques locales dans les images.
  • SURF ( Speeded Up Robust Features ) : est un détecteur de caractéristiques locales robuste, présenté pour la première fois par Herbert Bay et al. en 2006, qui peut être utilisé dans des tâches de vision par ordinateur comme la reconnaissance d'objets ou la reconstruction 3D. Il s'inspire en partie du descripteur SIFT. La version standard de SURF est plusieurs fois plus rapide que SIFT et revendiquée par ses auteurs comme étant plus robuste contre les différentes transformations d'images que SIFT.
• Déconvolution Richardson–Lucy : algorithme de dé-flou d'image
• Déconvolution aveugle : algorithme de suppression du flou d'image lorsque la fonction d'étalement des points est inconnue.
• Filtrage médian
• Seam carving : algorithme de redimensionnement d'image sensible au contenu
• Segmentation : partitionner une image numérique en deux ou plusieurs régions
  • Algorithme GrowCut : un algorithme de segmentation interactif
  • Algorithme de marcheur aléatoire
  • Région en croissance
  • Transformation de bassin versant : une classe d'algorithmes basée sur l'analogie de bassin versant

Génie logiciel

• Algorithmes de cache
• Conversion CHS : conversion entre les systèmes d'adressage de disque
• Double dabble : Convertir des nombres binaires en BCD
• Fonction de hachage : convertit une grande quantité de données, éventuellement de taille variable, en une petite donnée, généralement un seul entier pouvant servir d'index dans un tableau
  • Fonction de hachage Fowler–Noll–Vo : rapide avec un faible taux de collision
  • Hachage Pearson : calcule uniquement la valeur 8 bits, optimisé pour les ordinateurs 8 bits
  • Hachage Zobrist : utilisé dans la mise en place de tables de transposition
• Algorithme de classement Unicode
• Algorithme d'échange Xor : échange les valeurs de deux variables sans utiliser de tampon

Algorithmes de base de données

• Algorithms for Recovery and Isolation Exploiting Semantics (ARIES) : récupération de transaction
• Algorithmes de jointure
  • Boucle imbriquée de bloc
  • Joindre par hachage
  • Jointure en boucle imbriquée
  • Trier-Fusionner Join

Algorithmes des systèmes distribués

• Synchronisation de l'horloge
  • Algorithme de Berkeley
  • L'algorithme de Cristian
  • Algorithme d'intersection
  • Algorithme de Marzullo
• Consensus (informatique) : s'accorder sur une valeur ou une histoire unique parmi des processeurs peu fiables
  • Algorithme de consensus Chandra-Toueg
  • Algorithme de Paxos
  • Radeau (informatique)
• Détection de la fin du processus
  • Algorithme de Dijkstra-Scholten
  • L'algorithme de Huang
• Ordre Lamport : un ordre partiel des événements basé sur la relation arrivé-avant
• Élection du leader : une méthode de sélection dynamique d'un coordinateur
  • Algorithme d'intimidation
• Exclusion mutuelle
  • Algorithme d'exclusion mutuelle distribuée de Lamport
  • Algorithme log(n) de Naimi-Trehel
  • L'algorithme de Maekawa
  • L'algorithme de Raymond
  • Algorithme Ricart–Agrawala
• Algorithme de snapshot : enregistre un état global cohérent pour un système asynchrone
  • Algorithme de Chandy-Lamport
• Horloges vectorielles : génèrent un ordre partiel des événements dans un système distribué et détectent les violations de causalité

Algorithmes d'allocation et de désallocation de mémoire

• Buddy memory allocation : Algorithme pour allouer de la mémoire de telle sorte que la fragmentation soit moindre.
• Éboueurs
  • Algorithme de Cheney : Une amélioration sur le collecteur semi-espace
  • ramasse-miettes générationnel : ramasse-miettes rapides qui séparent la mémoire par âge
  • Algorithme Mark-compact : une combinaison de l' algorithme Mark-Sweep et de l' algorithme de copie de Cheney
  • Marquer et balayer
  • Collecteur semi-espace : Un des premiers collectionneurs de copies
• Comptage de références

La mise en réseau

• Algorithme de Karn : résout le problème d'obtenir des estimations précises du temps d'aller-retour des messages lors de l'utilisation de TCP
• Algorithme de Luleå : une technique pour stocker et rechercher efficacement des tables de routage Internet
• La congestion du réseau
  • Retard exponentiel
  • Algorithme de Nagle : améliorer l'efficacité des réseaux TCP/IP en fusionnant les paquets
  • Backoff exponentiel binaire tronqué

Algorithmes des systèmes d'exploitation

• Algorithme du banquier : Algorithme utilisé pour éviter les blocages.
• Algorithmes de remplacement de page : Sélection de la page victime dans des conditions de faible mémoire.
  • Cache de remplacement adaptatif : meilleures performances que LRU
  • Horloge avec remplacement adaptatif (CAR) : est un algorithme de remplacement de page dont les performances sont comparables au cache de remplacement adaptatif

Synchronisation des processus

• L'algorithme de Dekker
• Algorithme de la boulangerie de Lampport
• Algorithme de Peterson

Planification

• Date limite la plus rapprochée première programmation
• Programmation équitable
• Ordonnancement avec le moins de temps mort
• Ordonnancement de liste
• File d'attente de commentaires à plusieurs niveaux
• Ordonnancement à cadence monotone
• Ordonnancement à tour de rôle
• Travail le plus court suivant
• Temps restant le plus court
• Algorithme top-nodes : gestion du calendrier des ressources

Planification des E/S

Planification de disque

• Algorithme d'ascenseur : Algorithme de planification de disque qui fonctionne comme un ascenseur.
• Recherche la plus courte en premier : Algorithme d'ordonnancement du disque pour réduire le temps de recherche .

Voir également

• Liste des structures de données
• Liste des algorithmes d'apprentissage automatique
• Liste des algorithmes de recherche de chemin
• Liste des sujets généraux sur les algorithmes
• Liste des termes relatifs aux algorithmes et aux structures de données
• Heuristique

Les références