# Liste des algorithmes au programme de MP2I/MPI

On ne liste que les algorithmes à pseudo code, qu'on pourrait implémenter.
On ne liste pas les algorithmes qu'il faut savoir surtout exécuter à la main, comme déterminiser un automate par exemple, ni les algorithmes qui relèvent de l'implémentation d'un type abstrait.

On étiquette les algorithmes selon leur position par rapport au programme
[p] au programme, explicitement
[c] dans le cadre du programme, mais pas cet algorithme précisément
[h] hors programme

## Algorithmes divers
- addition binaire [c]
- incrémentation binaire [c]
- puissance rapide [c]
- Euclide = calcul du pgcd [c], calcul des coefficients de Bézout [c]

## Algorithmes de tri et comparaisons
- recherche dichotomique [p]
- tri rapide : partition [c], tri rapide simple [c], tri rapide randomisé [c], calcul de la médiane randomisé [c]
- tri fusion [c]
- tri par tas [c]

## Algorithmes sur les graphes (hors parcours)
- Kruskal [p], Boruvka [h]
- calculer un tri topologique [c]
- calcul d'un couplage maximum [p]

## Algorithmes de parcours de graphes
- parcours quelconque : décomposition en composantes connexes [p], détection de biparti [c], accessibilité
- parcours en largeur : distance en nombre d'arcs [c]
- parcours en profondeur : détection de circuit [c], Kosaraju [p]
- Dijkstra [p], A* [p], Prim [h]

## Algorithme d'arborescents
- recherche exhaustive : Quine [p], les 8 reines [c]
- branch-and-bound [p]
- élagage alpha-beta [p]

## Algorithmes sur les automates
- Berry-Sethi calculer l'automate associé à une expression régulière, i.e. l'automate de Glushkov [p]
- calculer l'expression régulière associé à un automate [p]

## Algorithmes d'IA
- k-plus proches voisins [p]
- ID3 [p]
- k-moyennes [p]
- HAC [p]


## Algorithmes de programmation dynamique (exemples)
- calculer k parmi n [c]
- sac-à-dos [c]
- plus long sous-mot commun [c], plus long facteur commun [c], distance de Levenstein = distance d'édition [h]
- Floyd-Warshall [p] ou accessibilité en $k$ étapes dans un graphe [c]
- Montrer que l'étoile d'un langage dans P est aussi dans P [h]

## Algorithmes gloutons (exemples)
- Huffman [p]
- Kruskal [p]
- réservation de salles [c], sac-à-dos fractionnaire [c]

## Algorithmes diviser pour régner (exemples)
- tri fusion [c]
- calcul du sous-tableau de somme max [c]
- multiplication par blocs [c] (de nombre = Karatsuba, ou de matrice = Strassen)

## Algorithmes du texte
- plus long sous-mot commun [c], plus long facteur commun [c]
- recherche de motif : naïve [c], Boyer Moore [p], Rabin-Karp [p], avec un automate [c]
- compression : Huffman [p], LZW [p]

## Algorithmes de programmation concurrente
- algorithme de Peterson [p]
- algorithme de la boulangerie de Lamport [p], algorithme des niveaux [h], algorithme de Dijkstra[h]