Programmation efficace : les 128 algorithmes qu'il faut avoir compris et codés en Python au cours de sa vie : préparation aux concours de programmation
Enregistré dans:
| Auteur principal: | |
|---|---|
| Autres auteurs: | |
| Support: | Livre |
| Langue: | Français |
| Publié: |
Paris :
Ellipses,
copyright 2016.
|
| Collection: | Références sciences
|
| Sujets: | |
| Autres localisations: | Voir dans le Sudoc |
| Résumé: | Sélection de problèmes algorithmiques, accompagnés de leurs solutions en Python 3, en vue de se préparer aux entretiens et aux concours de programmation. ↑Electre 2018 |
Table des matières:
- 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