Programmation efficace

1 Introduction                                                         7
    1.1 Les concours de programmation                                  7
        1.1.1 Sites d’entraînement                                     9
        1.1.2 Réponses des juges                                      10
    1.2 Notre choix : Python                                          11
    1.3 Entrées-sorties                                               12
        1.3.1 Lire l’entrée standard                                  12
        1.3.2 Format de l’affichage                                   15
    1.4 Complexité                                                    15
    1.5 Types abstraits et structures de données essentielles         17
        1.5.1 Pile                                                    17
        1.5.2 Dictionnaire                                            18
        1.5.3 File                                                    18
        1.5.4 File de priorité et tas                                 19
        1.5.5 Union-find                                              23
    1.6 Techniques                                                    24
        1.6.1 Comparer                                                24
        1.6.2 Trier                                                   25
        1.6.3 Balayage                                                25
        1.6.4 Algorithmes gloutons                                    26
        1.6.5 Programmation dynamique                                 27
        1.6.6 Coder des ensembles dans des entiers                    28
        1.6.7 Recherche dichotomique                                  29
    1.7 Conseils                                                      31
    1.8 Pour aller plus loin                                          33
2 Chaînes de caractères                                               35
    2.1 Anagrammes                                                    35
    2.2 T9 — texte sur 9 touches                                      36
    2.3 Correcteur orthographique                                     38
    2.4 Recherche de motifs — Knuth-Morris-Pratt                      40
    2.5 Bords maximaux — Knuth-Morris-Pratt                           41
    2.6 Chaîne en puissance                                           44
    2.7 Recherche de motifs — Rabin-Karp                              45
    2.8 Plus long palindrome d’une chaîne — Manacher                  48
3 Séquences                                                           51
    3.1 Plus court chemin dans une grille                             51
    3.2 Distance d’édition de Levenshtein                             52
    3.3 Plus longue sous-séquence commune                             54
    3.4 Plus longue sous-séquence croissante                          55
    3.5 Stratégie gagnante dans un jeu à deux joueurs                 58
4 Tableaux                                                            59
    4.1 Fusion de listes triées                                       59
    4.2 Somme d’une plage                                             60
    4.3 Doublon d’une plage                                           60
    4.4 Plus grande somme d’une plage                                 61
    4.5 Requêtes de minimum d’une plage — arbre de segments           61
    4.6 Requêtes de somme d’une plage — arbre de Fenwick              64
    4.7 Fenêtres avec k éléments distincts                            66
5 Intervalles                                                         67
    5.1 Arbre d’intervalles                                           67
    5.2 Union d’intervalles                                           69
    5.3 Couverture d’intervalles                                      70
6 Graphes                                                             73
    6.1 Codage en Python                                              73
    6.2 Codage en C++ ou Java                                         74
    6.3 Graphes implicites                                            75
    6.4 Parcours en profondeur — DFS                                  76
    6.5 Parcours en largeur — BFS                                     77
    6.6 Composantes connexes                                          78
    6.7 Composantes bi-connexes                                       81
    6.8 Tri topologique                                               85
    6.9 Composantes fortement connexes                                87
    6.10 2-satisfiabilité                                             92
7 Cycles dans les graphes                                             95
    7.1 Chemin eulérien                                               95
    7.2 Problème du postier chinois                                   98
    7.3 Cycles de ratio poids sur longueur minimal — Karp             98
    7.4 Cycles de ratio coût sur temps minimal                       101
    7.5 Voyageur de commerce                                         102
8 Plus courts chemins                                                103
    8.1 Propriété de composition                                     103
    8.2 Graphes avec poids 0 ou 1                                    105
    8.3 Graphes avec poids positifs ou nuls — Dijkstra               106
    8.4 Graphes avec poids arbitraires — Bellman-Ford                109
    8.5 Toutes paires source-destination — Floyd-Warshall            110
    8.6 Grille                                                       112
    8.7 Variantes                                                    113
        8.7.1 Graphe non pondéré                                     113
        8.7.2 Graphe orienté acyclique                               113
        8.7.3 Plus long chemin                                       113
        8.7.4 Plus long chemin dans un arbre                         114
        8.7.5 Chemin qui minimise le poids maximal sur les arcs      114
        8.7.6 Graphe pondéré sur les sommets                         114
        8.7.7 Chemin qui minimise le poids maximal sur les sommets   114
        8.7.8 Toutes les arêtes appartenant à un plus court chemin   114
9 Couplages et flots                                                 117
    9.1 Couplage maximum biparti                                     118
    9.2 Couplage parfait de poids maximal — Kuhn-Munkres             121
    9.3 Couplage planaire sans croisement                            127
    9.4 Mariages stables — Gale-Shapley                              129
    9.5 Flot maximum par Ford-Fulkerson                              130
    9.6 Flot maximum par Edmonds-Karp                                133
    9.7 Flot maximum par Dimic                                       134
    9.8 s — t coupe minimum                                          137
    9.9 s — t coupe minimum pour graphe planaire                     138
    9.10 Problème de transport                                       139
    9.11 Réduction entre couplages et flots                          140
    9.12 Largeur d’un ordre partiel — Dilworth                       142
10 Arbres                                                            145
    10.1 Code de Huffman                                             146
    10.2 Ancêtre commun le plus proche                               149
    10.3 Plus long chemin dans un arbre                              152
    10.4 Arbre couvrant de poids minimal — Kruskal                   153
11 Ensembles                                                         155
    11.1 Sac à dos                                                   155
    11.2 Rendu de monnaie                                            156
    11.3 Sous-ensemble de valeur totale donnée                       157
    11.4 k-somme                                                     159
12 Points et polygones                                               161
    12.1 Enveloppe convexe                                           162
    12.2 Mesures d’un polygone                                       163
    12.3 Paire de points les plus proches                            164
    12.4 Polygone rectilinéaire simple                               167
13 Rectangles                                                        169
    13.1 Former des rectangles                                       169
    13.2 Plus grand carré dans une grille                            170
    13.3 Plus grand rectangle dans un histogramme                    171
    13.4 Plus grand rectangle dans une grille                        172
    13.5 Union de rectangles                                         173
    13.6 Union de rectangles disjoints                               177
14 Calculs                                                           179
    14.1 PGCD                                                        179
    14.2 Coefficients de Bézout                                      179
    14.3 Coefficients binomiaux 11144 44e e                          180
    14.4 Exponentiation rapide                                       180
    14.5 Nombres premiers                                            181
    14.6 Évaluer une expression arithmétique                         181
    14.7 Systèmes d’équations linéaires                              184
    14.8 Multiplication d’une séquence de matrices                   188
15 Exploration exhaustive                                            191
    15.1 Tous les chemins pour un laser                              191
    15.2 Couverture exacte                                           194
    15.3 Sudoku                                                      200
    15.4 Énumération de permutations                                 201
    15.5 Le compte est bon                                           204
Bibliographie                                                        209
Index                                                                211