Au coeur des algorithmes
Les bases de la programmation avec Python
Bradford Tuckfield
Benoît Clenet
Deboeck Supérieur
Remerciements15
Introduction17
À qui s'adresse ce livre ?19
À propos de ce livre20
Préparer l'environnement21
Installer Python sur Windows21
Installer Python sur macOS22
Installer Python sur Linux23
Installation de modules tiers23
Résumé23
Chapitre 1
Résolution de problèmes25
L'approche analytique26
Le modèle galiléen26
Stratégie de résolution en fonction de x28
Le physicien intrinsèque29
L'approche algorithmique30
Penser avec son cou31
Application de l'algorithme de Chapman34
Résoudre des problèmes à l'aide d'algorithmes35
Résumé36
Chapitre 2
Histoires d'algorithmes39
La multiplication des paysans russes40
Poser la MPR à la main40
Implémenter la MPR en Python44
L'algorithme d'Euclide46
Réaliser l'algorithme d'Euclide à la main47
Implémenter l'algorithme d'Euclide en Python48
Les carrés magiques japonais49
Créer le carré de Luo Shu en Python49
Implémenter l'algorithme de Kurushima en Python50
Résumé61
Chapitre 3
Minimisation et maximisation63
Fixer le taux d'imposition63
Premiers pas dans la bonne direction64
Transformer les pas en algorithme67
Critique de la montée de gradient69
Le problème de l'extrémum local71
Education et revenus de toute une vie71
Gravir la colline de l'éduction de la bonne façon73
De la maximisation à la minimisation74
La maximisation en général76
Quand ne faut-il pas utiliser d'algorithme ?77
Résumé79
Chapitre 4
Tri et recherche81
Tri par insertion81
Coder l'insertion82
Trier par insertion84
Mesurer l'efficacité algorithmique85
Pourquoi se soucier d'efficacité ?86
Mesurer le temps avec précision87
Compter les étapes88
Comparaison à des fonctions connues90
Accroître la précision théorique93
Utilisation de la notation grand O95
Tri par fusion96
Fusionner96
De la fusion au tri98
Tri par sommeil101
Du tri à la recherche103
La recherche par dichotomie103
Applications de la recherche par dichotomie106
Résumé107
Chapitre 5
Maths pures109
Fractions continues109
Transmettre phi de manière concise110
Complément sur les fractions continues112
Un algorithme pour engendrer des fractions continues113
Des nombres décimaux aux fractions continues117
Des fractions aux racines120
Racines carrées120
L'algorithme de Babylone120
Racines carrées en Python122
Générateurs de nombres aléatoires123
L'éventualité du hasard123
Le générateur congruentiel linéaire124
Evaluer un GNPA125
Les tests de Diehard127
Registres à décalage à rétroaction linéaire129
Résumé132
Chapitre 6
Optimisation avancée133
La vie d'un commercial134
Posons le problème135
Cerveau contre muscles138
L'algorithme du plus proche voisin140
Implémenter la recherche du plus proche voisin140
À la recherche d'autres améliorations142
Des algorithmes pour le cupide144
Introduction à la fonction de température145
Le recuit simulé147
Optimiser notre algorithme150
Eviter les régressions importantes152
Permettre le retour arrière153
Évaluer notre performance154
Résumé156
Chapitre 7
Géométrie157
Le problème du facteur157
Triangles160
Étude avancée des triangles162
Trouver le centre du cercle circonscrit163
Améliorer notre fonction de dessin165
Triangulation de Delaunay166
Produire une triangulation de Delaunay de manière incrémentale168
Implémenter la triangulation de Delaunay171
De Delaunay à Voronoï175
Résumé179
Chapitre 8
Langage181
Pourquoi les algorithmes du langage sont-ils si compliqués ?181
Insertion d'espaces182
Définir une liste de mots et en trouver une occurrence183
Prendre en compte les mots composés185
À la recherche des mots potentiels situés entre les espaces existants185
Utiliser un corpus importé pour vérifier les mots valides187
Trouver les premières et secondes moitiés des mots potentiels188
Complétion de phrases191
Tokenisation et obtention de n-grammes191
Notre stratégie193
Trouver les n + 1 -grammes candidats193
Sélectionner une phrase selon sa fréquence194
Résumé196
Chapitre 9
Machine learning197
Arbres de décision197
Construire un arbre de décision199
Télécharger notre échantillon de données199
Examiner les données200
Séparer nos données201
Décomposer efficacement203
Sélectionner les variables de séparation205
Ajouter de la profondeur207
Évaluation de notre arbre de décision210
Le problème du surapprentissage212
Perfectionnements et améliorations214
Forêts aléatoires215
Résumé216
Chapitre 10
Intelligence artificielle217
La Pipopipette218
Dessiner le plateau du jeu219
Représenter les parties220
Marquer les points d'une partie221
Arbres du jeu et comment gagner une partie222
Construire notre arbre224
Gagner une partie227
Perfectionner notre IA231
Résumé232
Chapitre 11
Aller encore plus loin233
Aller plus loin avec les algorithmes233
Construire un chatbot235
Représentation vectorielle d'un texte236
Similarité de vecteurs239
Être meilleur et plus rapide241
Des algorithmes pour les audacieux242
Résoudre les mystères les plus profonds244
Index247