Bibliographie p. [209]-210. Index

"Les nombreux problèmes algorithmiques de ce livre constituent à la fois une formation à la programmation et une préparation efficace aux compétitions (ACM/ICPC, Google Code Jam, Prologin, France-ioi, etc.) et entretiens d'embauche d'entreprises spécialisées en informatique (telles que Google ou Facebook). La variété des problèmes étudiés convient aux étudiants des écoles d'ingénieurs comme à ceux des parcours universitaires à partir de la L3. On y trouve les algorithmes classiques de géométrie ou de recherche de plus court chemin mais également des sujets plus atypiques tels que les arbres de Fenwick ou les liens dansants de Knuth. La rédaction dégage les idées essentielles pour la compréhension et indique les détails techniques à surmonter pour une implémentation efficace. Les codes complets et succincts en Python 3 présentés dans ce livre sont disponibles sur le site d'accompagnement http://tryalgo.org." [Source : 4e de couv.]

P. 7 1 Introduction P. 7 1.1 Les concours de programmation P. 9 1.1.1 Sites d'entraînement P. 10 1.1.2 Réponses des juges P. 11 1.2 Notre choix : Python P. 12 1.3 Entrées-sorties P. 12 1.3.1 Lire l'entrée standard P. 15 1.3.2 Format de l'affichage P. 15 1.4 Complexité P. 17 1.5 Types abstraits et structures de données essentielles P. 17 1.5.1 Pile P. 18 1.5.2 Dictionnaire P. 18 1.5.3 File P. 19 1.5.4 File de priorité et tas P. 23 1.5.5 Union-find P. 24 1.6 Techniques P. 24 1.6.1 Comparer P. 25 1.6.2 Trier P. 25 1.6.3 Balayage P. 26 1.6.4 Algorithmes gloutons P. 27 1.6.5 Programmation dynamique P. 28 1.6.6 Coder des ensembles dans des entiers P. 29 1.6.7 Recherche dichotomique P. 31 1.7 Conseils P. 33 1.8 Pour aller plus loin P. 35 2 Chaînes de caractères P. 35 2.1 Anagrammes P. 36 2.2 T9 - texte sur 9 touches P. 38 2.3 Correcteur orthographique P. 40 2.4 Recherche de motifs - Knuth-Morris-Pratt P. 41 2.5 Bords maximaux - Knuth-Morris-Pratt P. 44 2.6 Chaîne en puissance P. 45 2.7 Recherche de motifs - Rabin-Karp P. 48 2.8 Plus long palindrome d'une chaîne - Manacher P. 51 3 Séquences P. 51 3.1 Plus court chemin dans une grille P. 52 3.2 Distance d'édition de Levenshtein P. 54 3.3 Plus longue sous-séquence commune P. 55 3.4 Plus longue sous-séquence croissante P. 58 3.5 Stratégie gagnante dans un jeu à deux joueurs P. 59 4 Tableaux P. 59 4.1 Fusion de listes triées P. 60 4.2 Somme d'une plage P. 60 4.3 Doublon d'une plage P. 61 4.4 Plus grande somme d'une plage P. 61 4.5 Requêtes de minimum d'une plage - arbre de segments P. 64 4.6 Requêtes de somme d'une plage - arbre de Fenwick P. 66 4.7 Fenêtres avec k éléments distincts P. 67 5 Intervalles P. 67 5.1 Arbre d'intervalles P. 69 5.2 Union d'intervalles P. 70 5.3 Couverture d'intervalles P. 73 6 Graphes P. 73 6.1 Codage en Python P. 74 6.2 Codage en C++ ou Java P. 75 6.3 Graphes implicites P. 76 6.4 Parcours en profondeur - DFS P. 77 6.5 Parcours en largeur - BFS P. 78 6.6 Composantes connexes P. 81 6.7 Composantes bi-connexes P. 85 6.8 Tri topologique P. 87 6.9 Composantes fortement connexes P. 92 6.10 2-satisfiabilité

P. 95 7 Cycles dans les graphes P. 95 7.1 Chemin eulérien P. 98 7.2 Problème du postier chinois P. 98 7.3 Cycles de ratio poids sur longueur minimal - Karp P. 101 7.4 Cycles de ratio coût sur temps minimal P. 102 7.5 Voyageur de commerce P. 103 8 Plus courts chemins P. 103 8.1 Propriété de composition P. 105 8.2 Graphes avec poids 0 ou 1 P. 106 8.3 Graphes avec poids positifs ou nuls - Dijkstra P. 109 8.4 Graphes avec poids arbitraires - Bellman-Ford P. 110 8.5 Toutes paires source-destination - Floyd-Warshall P. 112 8.6 Grille P. 113 8.7 Variantes P. 113 8.7.1 Graphe non pondéré P. 113 8.7.2 Graphe orienté acyclique P. 113 8.7.3 Plus long chemin P. 114 8.7.4 Plus long chemin dans un arbre P. 114 8.7.5 Chemin qui minimise le poids maximal sur les arcs P. 114 8.7.6 Graphe pondéré sur les sommets P. 114 8.7.7 Chemin qui minimise le poids maximal sur les sommets P. 114 8.7.8 Toutes les arêtes appartenant à un plus court chemin P. 117 9 Couplages et flots P. 118 9.1 Couplage maximum biparti P. 121 9.2 Couplage parfait de poids maximal - Kuhn-Munkres P. 127 9.3 Couplage planaire sans croisement P. 129 9.4 Mariages stables - Gale-Shapley P. 130 9.5 Flot maximum par Ford-Fulkerson P. 133 9.6 Flot maximum par Edmonds-Karp P. 134 9.7 Flot maximum par Dinic P. 137 9.8 s - t coupe minimum P. 138 9.9 s - t coupe minimum pour graphe planaire P. 139 9.10 Problème de transport P. 140 9.11 Réduction entre couplages et flots P. 142 9.12 Largeur d'un ordre partiel - Dilworth P. 145 10 Arbres P. 146 10.1 Code de Huffman P. 149 10.2 Ancêtre commun le plus proche P. 152 10.3 Plus long chemin dans un arbre P. 153 10.4 Arbre couvrant de poids minimal - Kruskal P. 155 11 Ensembles P. 155 11.1 Sac à dos P. 156 11.2 Rendu de monnaie P. 157 11.3 Sous-ensemble de valeur totale donnée P. 159 11.4 k-somme P. 161 12 Points et polygones P. 162 12.1 Enveloppe convexe P. 163 12.2 Mesures d'un polygone P. 164 12.3 Paire de points les plus proches P. 167 12.4 Polygone rectilinéaire simple P. 169 13 Rectangles P. 169 13.1 Former des rectangles P. 170 13.2 Plus grand carré dans une grille P. 171 13.3 Plus grand rectangle dans un histogramme P. 172 13.4 Plus grand rectangle dans une grille P. 173 13.5 Union de rectangles P. 177 13.6 Union de rectangles disjoints P. 179 14 Calculs P. 179 14.1 PGCD P. 179 14.2 Coefficients de Bézout P. 180 14.3 Coefficients binomiaux P. 180 14.4 Exponentiation rapide P. 181 14.5 Nombres premiers P. 181 14.6 Évaluer une expression arithmétique P. 184 14.7 Systèmes d'équations linéaires P. 188 14.8 Multiplication d'une séquence de matrices P. 191 15 Exploration exhaustive P. 191 15.1 Tous les chemins pour un laser P. 194 15.2 Couverture exacte P. 200 15.3 Sudoku P. 201 15.4 Énumération de permutations P. 204 15.5 Le compte est bon P. 209 Bibliographie P. 211 Index