Liste d'algorithmes
# Liste d'algorithmes

Cette liste recense des algorithmes par catégorie.

## Liste par catégories

### Compression de données

* Run-length encoding (RLE)
* Codage de Huffman
* Lempel-Ziv-Welch (LZW)
* Transformée de Burrows-Wheeler (BWT)

### Tris

**Algorithmes en temps quadratique**

* Tri à bulles (bubble sort)
* Tri par sélection (selection sort)
* Tri par insertion (insertion sort)
* Tri de Shell

**Algorithmes en $T(n)=n.\log(n)$**

* Tri rapide (quick sort) ou Quicksort
* Tri fusion (merge sort)
* Tri par tas (heap sort)
* Introspective Sort
* Smoothsort
* Tri Arborescent

**Algorithmes en temps linéaire**

* Tri par dénombrement (counting sort)
* Tri par base (radix sort)
* Tri par paquets (bucket sort)
* Tri de crêpes (pancake sorting)

### Cryptographie

**Chiffrement par substitution**

* ROT13 (rotation de 13 caractères, sans clé)
* Chiffre de Vigenère (chiffrement polyalphabétiques)

**Cryptographie symétrique**

* DES
* 3DES
* AES
* RC4
* RC5
* MISTY1
* Liste complète d'algorithmes de cryptographie symétrique.

**Cryptographie asymétrique**

* RSA
* Elliptic Curve Cryptography
* ElGamal
* Liste complète d'algorithmes de cryptographie asymétrique.

**Algorithmes de hachage**

* CRC
* MD5
* RIPEMD
* SHA-0
* SHA-1
* Liste complète d'algorithmes de hachage.

**Test de primalité**

* Test de primalité de Lucas-Lehmer
* Algorithme d'Agrawal-Saxena-Kayal

### Graphes

Liste des algorithmes de la théorie des graphes

* Algorithme de Prim, arbre couvrant minimal
* Algorithme de Kruskal, arbre couvrant minimal

**Pathfinding**

* Algorithme de Dijkstra
* Algorithme de Floyd-Warshall
* Algorithme de Warshall
* Algorithme de Ford-Bellman
* A*, un algorithme très répandu, de calcul de Pathfinding
* Algorithme de parcours en largeur
* Algorithme de parcours en profondeur
* Algorithme de Viterbi

**Arbre de décision**

* ID3
* CHAID
* CART
* C4.5
* C5
* Exhaustive CHAID
* QUEST

### Graphisme

* Algorithme de Bresenham, dessin d'un segment de droite
* Algorithme de Canny, détection des contours d'une image
* Algorithme de de Casteljau, dessin de courbes de Bézier
* Algorithme d'Oslo, dessin de B-splines
* Algorithme du peintre, masquage d'objets en 3D
* Algorithme de remplissage par diffusion
* Algorithme de Sobel, détection de contours
* Algorithme de Bentley-Ottmann, détection d'intersections dans un ensemble de segments
* GrowCut

### Génie logiciel

* Algorithme du banquier, allocation de ressource sans blocage
* Algorithme de la boulangerie, exclusion mutuelle
* Algorithme de Dekker, exclusion mutuelle
* Algorithme de Peterson, exclusion mutuelle
* Algorithme des nœuds chapeaux, gestion d'un calendrier de ressources
* Algorithme Round-Robin, ordonnancement

### Mathématiques

**Algèbre linéaire**

* Algorithme de Coppersmith-Winograd, produit de matrices
* Algorithme de Strassen, produit de matrices
* Algorithme de Freivalds, produit de matrices probabiliste
* Algorithme de Faddeev-Leverrier, calcul du polynôme caractéristique d'une matrice carrée

**Optimisation**

* Algorithme de Balas-Hammer
* Algorithme de Levenberg-Marquardt
* Algorithme de Newton
* Algorithme du simplexe
* Algorithme glouton
* Algorithme MinMax
* Negamax (en)
* Élagage alpha-bêta
* Expectiminimax tree (en)
* Méthode du nombre d'or
* Algorithme à estimation de distribution
* Méthode de Monte-Carlo
* Algorithme de Monte-Carlo
* Recherche arborescente Monte-Carlo
* Algorithme de Las Vegas
* Algorithme évolutionniste
* Algorithme génétique
* Algorithme mémétique
* Apprentissage profond

**Autres domaines**

* Algorithme de Berlekamp, factorisation de polynômes
* Algorithme de Cantor-Zassenhaus, factorisation de polynômes
* Algorithme rho de Pollard, décomposition en produit de facteurs premiers
* Algorithme de Risch, calcul de primitive
* Méthode multipolaire rapide, en analyse numérique

### Texte

* Algorithme d'Aho-Corasick, recherche de mots-clé
* Algorithme de Boyer-Moore, recherche de sous-chaînes
* Algorithme de Knuth-Morris-Pratt, recherche de sous-chaîne
* Algorithme de Rabin-Karp, recherche de sous-chaînes
* Algorithme de Wagner-Fischer, calcul de distance de Levenshtein

### Divers

* Tours de Hanoï
* Algorithme du British Museum
* Algorithme de Gauss Jordan
* Algorithme d'Euclide
* Algorithme du lièvre et de la tortue
* Algorithme de Nagle
