128 algorithmes

1. $s-t$ Coupe minimum planaire
2. $s-t$ Coupe minimum
3. 2-satisfiabilité
4. Ancêtre commun le plus proche par minimum dans une plage
5. Ancêtre commun le plus proche par racourcis
6. Andrew : enveloppe convexe
7. Arêtes critiques pour plus court chemin
8. Bellman-Ford var. : cycle poids négatif
9. Bellman-Ford : plus court chemin poids arbitraires
10. Chemin minimisant arête poids maximal
11. Chemin minimisant sommet poids maximal
12. Code de Huffman
13. Coefficient binomial direct
14. Coefficient binomial par coefficients de Bézout
15. Coefficients de Bézout
16. Combiner $n$ entiers en une expression arithmétique de valeur proche d’une valeur donnée
17. Composantes bi-connexes d’un graphe
18. Composantes connexes d’un graphe avec union-find
19. Composantes connexes d’un graphe par parcours en profondeur
20. Composants dans union de rectangles disjoints
21. Correcteur orthographique
22. Coupe minimum dans arbre pour minimiser plus long chemin
23. Couplage biparti maximal en $O(|U|\cdot|E|)$
24. Couplage biparti parfait minimisant arête poids maximal
25. Couplage planaire en $O(n\log n)$
26. Couplage planaire par en $O(n^3)$
27. Cycle de coût sur temps minimal
28. Cycle de poids moyen minimal
29. Cycle eulérien
30. Dijkstra : plus court chemin poids positifs ou nuls
31. Dinic : flot maximum par flot bloquant
32. Distance d’édition de Levenshtein entre deux chaînes
33. Décomposition minimale en chaînes d’un ordre partiel
34. Déterminer toutes les sous-séquences maximales composées d’éléments distincts
35. Edmonds-Karp : flot maximum par chemin augmentant plus court
36. Ensemble minimum de points intersectant chacun des intervalles donnés
37. Exponentiation rapide
38. Fenwick : tableau avec écriture par indice et lecture somme sur intervalle d’indices
39. Floyd-Warshall : plus courts chemins toutes paires source-destination
40. Ford-Fulkerson : flot maximum par chemins augmentants
41. Fusionner $k$ listes triées
42. Fusionner deux listes triées
43. Gale-Shapley : couplage biparti stable
44. Gauss-Jordan : système d’équations linéaires
45. Goldberg-Rao : flot maximum par flots bloquants binaires
46. Intervalle dans tableau de somme maximale
47. Inverser une fonction monotone
48. Knuth-Morris-Pratt : bord maximal d’une chaîne
49. Knuth-Morris-Pratt : cherche une chaîne dans une autre
50. Kosaraju : composantes fortement connexes
51. Kruskal : arbre couvrant de poids minimal
52. Kuhn-Munkres : couplage biparti maximum profit maximal
53. Kőnig : couverture minimale graphe biparti
54. Liens dansants : couverture exacte
55. Maintenir ensemble d’intervalles, déterminer liste d’intervalles contenant une valeur donnée
56. Manacher : plus long facteur palindrome
57. Nombres de Fibonacci
58. Orienter miroirs pour connectivité laser
59. Paire de points plus proches
60. Paire de valeurs plus proches
61. Parcours d’un graphe en largeur
62. Parcours d’un graphe en profondeur
63. Partition d’un ensemble d’entiers en deux parties
64. Partition d’un ensemble d’entiers en trois parties
65. Permuter vecteur $x$ pour minimiser le produit scalaire avec $y$
66. Placer des parenthèses pour optimiser une multiplication d’une séquence de matrices
67. Plus court chemin avec poids 0,1
68. Plus court chemin dans grille
69. Plus court chemin dans une grille
70. Plus court chemin graphe orienté acyclique
71. Plus court chemin sur graphe de configurations combinatoires
72. Plus grand carré monochromatique dans une grille
73. Plus grand commun diviseur
74. Plus grand rectangle dans histogramme
75. Plus grand rectangle monochromatique dans un grille
76. Plus long chemin dans un arbre par parcours en profondeur
77. Plus long chemin dans un arbre par programmation dynamique
78. Plus longue sous-séquence commune et croissante à deux séquences
79. Plus longue sous-séquence commune à $k$ séquences données
80. Plus longue sous-séquence commune à deux séquences triées
81. Plus longue sous-séquence commune à deux séquences
82. Plus longue sous-séquence non décroissante
83. Plus longue sous-séquence strictement croissante
84. Points entiers dans un polygone
85. Points entiers sur le contour d’un polygone
86. Postier chinois : cycle minimal couvrant chaque arête
87. Pour une chaîne $x$ trouver un entier $k$ tel que $x$ s’écrit comme $y^k$ pour une chaîne $y$
88. Prim : arbre couvrant de poids minimal
89. Problème de transport
90. Prochaine permutation
91. Proposer le mot le plus fréquent correspondant à un préfixe donné en mode T9
92. Rabin-Karp : chercher plus long facteur commun à deux chaînes en temps $O(n\log n)$
93. Rabin-Karp : chercher une chaîne dans une autre
94. Recherche dichotomique dans un domaine continu
95. Recherche dichotomique dans un tableau de taille $2^k$
96. Recherche dichotomique dans un tableau trié
97. Recherche trichotomique pour trouver le minimum d’une séquence convexe
98. Rendu de monnaie
99. Sac-à-dos
100. Simplicité polygone rectilinéaire
101. Somme d’un tableau sur un intervalle d’indices
102. Sous-ensemble de valeur totale donnée par intersection d’ensembles
103. Sous-ensemble de valeur totale donnée par programmation dynamique
104. Sous-matrice rectangulaire de somme maximale
105. Stratégie gagnante dans un jeu
106. Sudoku
107. Surface d’un polygone
108. Tableau avec écriture par indice et lecture minimum sur intervalle d’indices
109. Tarjan : composantes fortement connexes
110. Tas
111. Temps de déconnexion d’un graphe avec heure disparition par arête
112. Test probabiliste de Freivalds $AB=C$
113. Tous les rectangles formés par des points donnés
114. Tri casier
115. Trouver toutes les anagrammes à une liste de mots
116. Union d’intervalles
117. Union de rectangles en $O(n\log n)$
118. Union de rectangles en $O(n^2)$
119. Union de rectangles en $O(n^4)$
120. Union-find
121. Valeur intersectant un nombre maximal d’intervalles
122. Voyageur de commerce
123. k-somme en $O(n^{\lceil k/2 \rceil})$
124. k-somme en $O(n^{k-1})$
125. Élément en double d’un tableau sur un intervalle d’indices
126. Élément majoritaire d’un tableau
127. Ératosthène : nombres premiers
128. Évaluer une expression arithmétique