Sommaire

1
Tutoriel
d’initiation
à
Python
—
1re
partie 1
1.1 Installation et premier exemple . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Installation de Python . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Premier exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.4 Utilisation de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Types d’objets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Entiers et flottants . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.3 Nombres complexes . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.4 Booléens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.5 Chaînes de caractères . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.6 Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.7 Polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Graphes de fonctions et courbes paramétrées . . . . . . . . . . . . . . . 6
1.3.1 Le module matplotlib . . . . . . . . . . . . . . . . . . . . . . 6
1.3.2 Graphes de fonctions . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.3 Courbes paramétrées . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Algorithmique 1 9
2.1 Eléments d’architecture des ordinateurs . . . . . . . . . . . . . . . . . . 9
2.1.1 Composants d’une machine numérique . . . . . . . . . . . . . . 9
2.1.2 Le modèle de John von Neumann . . . . . . . . . . . . . . . . . 10
2.1.3 Les périphériques . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.1.4 Le fonctionnement de l’unité centrale . . . . . . . . . . . . . . . 11
2.1.5 La mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Représentation des nombres dans un ordinateur . . . . . . . . . . . . . 12
2.2.1 Représentation des nombres entiers dans un ordinateur . . . . 12
2.2.1.1 Représentation des nombres entiers naturels . . . . . . 12
2.2.1.2 Représentation des nombres entiers relatifs . . . . . . 13
2.2.2 Représentation des nombres réels dans un ordinateur . . . . . . 13
2.2.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . 13
vi SOMMAIRE

2.2.2.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.2.3 Approximation d’un réel . . . . . . . . . . . . . . . . . 15
2.2.2.4 Flottants en simple précision . . . . . . . . . . . . . . . 16
2.2.2.5 Flottants en double précision . . . . . . . . . . . . . . . 16
2.3 Algorithmique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.1 Définition et structure d’un algorithme . . . . . . . . . . . . . . 17
2.3.2 Procédures en Python . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.3 Variables locales et variables globales . . . . . . . . . . . . . . . 18
2.3.4 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.5 Boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4.1 Introduction à la récursivité . . . . . . . . . . . . . . . . . . . . . 20
2.4.2 Exemple prototypique de fonction récursive : la factorielle . . . 20
2.4.3 La méthode « diviser pour régner » . . . . . . . . . . . . . . . . 21
2.5 Etude d’un algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.1 Terminaison d’un algorithme . . . . . . . . . . . . . . . . . . . . 22
2.5.1.1 Cas d’un algorithme itératif . . . . . . . . . . . . . . . 22
2.5.1.2 Cas d’un algorithme récursif . . . . . . . . . . . . . . . 22
2.5.2 Correction d’un algorithme . . . . . . . . . . . . . . . . . . . . . 23
2.5.2.1 Cas d’un algorithme itératif . . . . . . . . . . . . . . . 23
2.5.2.2 Cas d’un algorithme récursif . . . . . . . . . . . . . . . 23
2.5.3 Complexité d’un algorithme . . . . . . . . . . . . . . . . . . . . 23
2.5.3.1 Différentes classes de complexité . . . . . . . . . . . . 23
2.5.3.2 Exemple de calcul de complexité : cas d’école . . . . . 24
2.5.4 Suites récurrentes utiles en algorithmique . . . . . . . . . . . . . 25
2.6 Nombres et polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6.1 Calcul de puissances . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.6.1.1 Algorithme d’exponentiation naïve . . . . . . . . . . . 28
2.6.1.2 Algorithme d’exponentiation rapide . . . . . . . . . . 28
2.6.2 Algorithme d’Euclide . . . . . . . . . . . . . . . . . . . . . . . . 30
2.6.2.1 Principe et implémentation . . . . . . . . . . . . . . . . 30
2.6.2.2 Majorant de la complexité de l’algorithme d’Euclide . 31
2.6.2.3 Algorithme d’Euclide étendu . . . . . . . . . . . . . . 33
2.6.3 Cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.6.3.1 Petit théorème de Fermat . . . . . . . . . . . . . . . . . 34
2.6.3.2 Le système RSA . . . . . . . . . . . . . . . . . . . . . . 35
2.6.4 Evaluation d’un polynôme en un point . . . . . . . . . . . . . . 36
2.6.4.1 Algorithme naïf . . . . . . . . . . . . . . . . . . . . . . 36
2.6.4.2 Algorithme de Horner . . . . . . . . . . . . . . . . . . 36
2.7 Recherche dans un tableau trié . . . . . . . . . . . . . . . . . . . . . . . 37
2.7.1 Tableaux et listes en informatique . . . . . . . . . . . . . . . . . 37
2.7.2 Recherche séquentielle . . . . . . . . . . . . . . . . . . . . . . . . 38
2.7.3 Recherche dichotomique . . . . . . . . . . . . . . . . . . . . . . . 38
2.8 Algorithmes de tri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.8.1 Tri par sélection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.8.2 Tri par insertion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
SOMMAIRE vii

2.9 Utilisation de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.9.1 Utilisation d’un fichier texte . . . . . . . . . . . . . . . . . . . . . 42
2.9.1.1 Ecriture, lecture et ajout de données . . . . . . . . . . . 42
2.9.1.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.9.2 Utilisation d’un fichier csv . . . . . . . . . . . . . . . . . . . . . . 43
2.9.2.1 Définition et opérations de base . . . . . . . . . . . . . 43
2.9.2.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.10 Compléments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.10.1 Récursivité à plusieurs variables . . . . . . . . . . . . . . . . . . 45
2.10.1.1 Définitions et exemples . . . . . . . . . . . . . . . . . . 45
2.10.1.2 Théorème d’induction . . . . . . . . . . . . . . . . . . . 46
2.10.2 Transformation d’un programme Python en un exécutable . . . 46
2.10.2.1 Ajout de Python aux variables d’environnement . . . 47
2.10.2.2 Fichier setup.py associé à un fichier Python . . . . . . 47
2.10.2.3 Compilation du fichier setup.py . . . . . . . . . . . . . 47
2.11 EXERCICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2.11.1 Nombres et polynômes . . . . . . . . . . . . . . . . . . . . . . . 48
2.11.2 Algorithmes itératifs . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.11.3 Récursivité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.11.4 Tris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.12 PROBLEMES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

3 Tutoriel d’initiation à Python — 2e partie 77

3.1 Algèbre linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.1.1 Le module numpy . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.1.2 Tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.1.3 Tableaux contenant des coefficients aléatoires . . . . . . . . . . . 78
3.1.4 Opérations sur les tableaux . . . . . . . . . . . . . . . . . . . . . 78
3.2 Graphiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.2.1 Superposition de graphes . . . . . . . . . . . . . . . . . . . . . . 81
3.2.2 Courbes implicites . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.2.3 Fenêtres contenant plusieurs graphiques . . . . . . . . . . . . . 82
3.2.4 Représentations graphiques dans l’espace . . . . . . . . . . . . . 82
3.2.5 Animations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
3.3 Résolution numérique d’équations . . . . . . . . . . . . . . . . . . . . . 84
3.3.1 Systèmes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.3.2 Le module scipy . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.3.3 Dérivation d’une fonction . . . . . . . . . . . . . . . . . . . . . . 85
3.3.4 Equations non linéaires . . . . . . . . . . . . . . . . . . . . . . . 85
3.3.5 Equations différentielles . . . . . . . . . . . . . . . . . . . . . . . 85
3.4 Intégration numérique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.4.1 Méthode standard . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.4.2 Méthode des trapèzes . . . . . . . . . . . . . . . . . . . . . . . . 86
3.5 Calcul formel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.5.1 Le module sympy . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.5.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
viii SOMMAIRE

4 Ingénierie numérique et simulation 89

4.1 Calcul approché d’intégrales . . . . . . . . . . . . . . . . . . . . . . . . . 89
4.1.1 Méthodes des rectangles . . . . . . . . . . . . . . . . . . . . . . . 90
4.1.2 Méthode des trapèzes . . . . . . . . . . . . . . . . . . . . . . . . 91
4.2 Résolution d’équations différentielles . . . . . . . . . . . . . . . . . . . 93
4.2.1 Cadre d’étude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
4.2.2 Méthode d’Euler classique . . . . . . . . . . . . . . . . . . . . . 93
4.2.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.2.4 Généralisation : θ−schéma . . . . . . . . . . . . . . . . . . . . . 95
4.3 Approximation de racines d’équations . . . . . . . . . . . . . . . . . . . 95
4.3.1 Méthode de dichotomie . . . . . . . . . . . . . . . . . . . . . . . 95
4.3.2 Méthode de la tangente de Newton . . . . . . . . . . . . . . . . 96
4.4 Résolution de systèmes linéaires . . . . . . . . . . . . . . . . . . . . . . 97
4.4.1 Résolution de systèmes linéaires . . . . . . . . . . . . . . . . . . 97
4.4.2 Opérations élémentaires sur les rangées . . . . . . . . . . . . . . 97
4.4.2.1 Multiplication d’une rangée par un coefficient non nul 98
4.4.2.2 Echange de deux rangées parallèles . . . . . . . . . . . 98
4.4.2.3 Matrices de transvection . . . . . . . . . . . . . . . . . 98
4.4.3 Algorithme du pivot partiel de Gauss . . . . . . . . . . . . . . . 98
4.4.3.1 Etude de l’algorithme du pivot partiel de Gauss . . . . 99
4.4.3.2 Cas des matrices symétriques définies positives . . . . 101
4.4.3.3 Implémentation de l’algorithme de triangularisation
de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.4.3.4 Complexité de l’algorithme de triangularisation de
Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.4.3.5 Implémentation de l’algorithme du pivot partiel de
Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.4.3.6 Complexité de l’algorithme du pivot partiel de Gauss 103
4.4.4 Factorisation LU . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
4.4.4.1 Existence de la factorisation LU . . . . . . . . . . . . . 104
4.4.4.2 Implémentation de l’algorithme de factorisation LU . 105
4.4.4.3 Résolution d’un système linéaire par remontée . . . . 106
4.4.4.4 Deux autres applications . . . . . . . . . . . . . . . . . 106
4.5 Probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.5.1 Simulation des lois de probabilité . . . . . . . . . . . . . . . . . 107
4.5.2 Calcul d’intégrales par la méthode de Monte Carlo . . . . . . . 108
4.6 EXERCICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.6.1 Tracés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.6.2 Tracés avec la tortue . . . . . . . . . . . . . . . . . . . . . . . . . 121
4.6.3 Intégration numérique et équations différentielles . . . . . . . . 124
4.6.4 Calcul approché de racines . . . . . . . . . . . . . . . . . . . . . 131
4.6.5 Matrices et systèmes linéaires . . . . . . . . . . . . . . . . . . . . 135
4.6.6 Résolution approchée d’équations aux dérivées partielles . . . . 143
4.6.7 Polynômes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.6.8 Probabilités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4.7 PROBLEMES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
SOMMAIRE ix

5 Bases de données 181

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
5.1.1 Présentation des systèmes de gestion de bases de données . . . 181
5.1.2 Architecture trois tiers . . . . . . . . . . . . . . . . . . . . . . . . 181
5.1.3 Quatre étapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5.1.4 Conception d’une base de données . . . . . . . . . . . . . . . . . 182
5.2 Modèle conceptuel de données . . . . . . . . . . . . . . . . . . . . . . . 182
5.2.1 Présentation du modèle . . . . . . . . . . . . . . . . . . . . . . . 182
5.2.2 Exemple de référence . . . . . . . . . . . . . . . . . . . . . . . . . 183
5.2.3 Entités et attributs . . . . . . . . . . . . . . . . . . . . . . . . . . 184
5.2.4 Types, occurrences et identifiants . . . . . . . . . . . . . . . . . . 184
5.2.5 Associations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186
5.2.5.1 Associations 1 − 1 . . . . . . . . . . . . . . . . . . . . . 187
5.2.5.2 Associations 1 − N . . . . . . . . . . . . . . . . . . . . 187
5.2.5.3 Associations N − M . . . . . . . . . . . . . . . . . . . . 188
5.2.6 Entités faibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
5.2.7 Contraintes d’intégrité . . . . . . . . . . . . . . . . . . . . . . . . 188
5.2.8 Méthode de création d’un modèle conceptuel de données . . . 189
5.3 Modèle logique de données . . . . . . . . . . . . . . . . . . . . . . . . . 189
5.3.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
5.3.2 Contraintes référentielles et graphe des clés étrangères . . . . . 191
5.3.3 Passage d’un modèle conceptuel à un modèle logique . . . . . . 192
5.3.4 Opérateurs de l’algèbre relationnelle . . . . . . . . . . . . . . . . 194
5.3.4.1 Réunion . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
5.3.4.2 Intersection . . . . . . . . . . . . . . . . . . . . . . . . . 195
5.3.4.3 Différence . . . . . . . . . . . . . . . . . . . . . . . . . . 195
5.3.4.4 Produit cartésien . . . . . . . . . . . . . . . . . . . . . . 195
5.3.4.5 Projection . . . . . . . . . . . . . . . . . . . . . . . . . . 195
5.3.4.6 Sélection (ou restriction) . . . . . . . . . . . . . . . . . 196
5.3.4.7 Renommage . . . . . . . . . . . . . . . . . . . . . . . . 196
5.3.4.8 Jointure . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
5.3.4.9 Schémas standards pour la projection, la sélection et
la jointure . . . . . . . . . . . . . . . . . . . . . . . . . . 197
5.3.4.10 Division cartésienne . . . . . . . . . . . . . . . . . . . . 197
5.3.4.11 Fonctions d’agrégation . . . . . . . . . . . . . . . . . . 197
5.4 Utilisation d’une base de données . . . . . . . . . . . . . . . . . . . . . . 198
5.4.1 Création de la base de données . . . . . . . . . . . . . . . . . . . 199
5.4.2 Peuplement de la base de données . . . . . . . . . . . . . . . . . 200
5.4.3 Interrogation de la base de données . . . . . . . . . . . . . . . . 201
5.4.3.1 Projection . . . . . . . . . . . . . . . . . . . . . . . . . . 201
5.4.3.2 Sélection . . . . . . . . . . . . . . . . . . . . . . . . . . 201
5.4.3.3 Produit cartésien . . . . . . . . . . . . . . . . . . . . . . 202
5.4.3.4 Réunion . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
5.4.3.5 Intersection . . . . . . . . . . . . . . . . . . . . . . . . . 202
5.4.3.6 Jointure . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
5.4.3.7 Fonctions d’agrégation . . . . . . . . . . . . . . . . . . 203
x SOMMAIRE

5.4.4 MySQL et Python . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

5.5 EXERCICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
5.6 PROBLEMES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
6 Algorithmique 2 217
6.1 Piles et files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
6.1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
6.1.2 Exemples d’utilisation de piles . . . . . . . . . . . . . . . . . . . 218
6.1.3 Opérations sur les piles . . . . . . . . . . . . . . . . . . . . . . . 219
6.1.4 Opérations sur les files . . . . . . . . . . . . . . . . . . . . . . . . 219
6.2 Retour sur les algorithmes de tri . . . . . . . . . . . . . . . . . . . . . . 219
6.2.1 Tri par fusion ou tri dichotomique (merge sort) . . . . . . . . . . 219
6.2.2 Tri rapide (quick sort) . . . . . . . . . . . . . . . . . . . . . . . . 220
6.3 Transformée de Fourier discrète . . . . . . . . . . . . . . . . . . . . . . . 222
6.3.1 Principe : polynômes d’interpolation de Lagrange . . . . . . . . 222
6.3.2 Définition de la transformée de Fourier discrète . . . . . . . . . 223
6.3.3 Transformée de Fourier rapide (FFT) . . . . . . . . . . . . . . . . 224
6.3.3.1 Principe de calcul . . . . . . . . . . . . . . . . . . . . . 224
6.3.3.2 Algorithme de Cooley et Tukey . . . . . . . . . . . . . 224
6.3.3.3 Complexité de l’algorithme de Cooley et Tukey . . . . 225
6.3.4 Transformée de Fourier discrète inverse . . . . . . . . . . . . . . 226
6.3.5 Transformée de Fourier discrète en dimension 2 . . . . . . . . . 226
6.3.6 Deux applications de la transformée de Fourier discrète . . . . 227
6.3.6.1 Valeurs approchées des coefficients de Fourier . . . . 227
6.3.6.2 Produit rapide de deux polynômes . . . . . . . . . . . 227
6.4 Traitement d’images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
6.4.1 Affichage d’une image en Python . . . . . . . . . . . . . . . . . 228
6.4.2 Synthèse des couleurs . . . . . . . . . . . . . . . . . . . . . . . . 230
6.4.3 Filtres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
6.4.4 Filtres non linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . 231
6.4.5 Filtres linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
6.4.6 Utilisation de la FFT en traitement d’images . . . . . . . . . . . 235
6.4.6.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
6.4.6.2 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
6.5 EXERCICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
6.5.1 Piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
6.5.2 Tri rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
6.5.3 Transformée de Fourier . . . . . . . . . . . . . . . . . . . . . . . 241
6.5.4 Traitement d’images . . . . . . . . . . . . . . . . . . . . . . . . . 247
6.6 PROBLEMES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

A BIOGRAPHIE DES SCIENTIFIQUES CITES 257

B
COMPLEXITE
D’ALGORITHMES 265

#JCMJPHSBQIJF 26

*OEFY 26