TryAlgo

Liste des algorithmes traités dans notre livre

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