Cours programmation en informatique pour débutant
Note : Ce premier chapitre maladroit correspond à l’état d’esprit dans lequel ce cours a débuté en 2003, dans une période où l’Informatique avait mauvaise presse à l’École des ponts. Nous le maintenons ici en tant que témoin de ce qu’il faillait faire alors pour amener les élèves à ne pas négliger l’Informatique. Si l’on ignore la naïveté de cette première rédaction (et le fait que Star Wars n’est plus autant à la mode !), l’analyse et les conseils qui suivent restent d’actualité.
—
(Ce premier chapitre tente surtout de motiver les élèves ingénieurs dans leur apprentissage de la programmation. Les enfants qui se trouveraient ici pour apprendre à programmer sont sûrement déjà motivés et peuvent sauter au chapitre suivant ! Pro?tons-en pour tenir des propos qui ne les concernent pas)
Cours programmation en informatique pour débutant
Table des matières :
1 Préambule 7
1.1 Pourquoi savoir programmer ? . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Comment apprendre ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.1 Choix du langage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.2 Choix de l’environnement . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.3 Principes et conseils . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Bonjour, Monde ! 13
2.1 L’ordinateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.1 Le micro-processeur . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.1.2 La mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.3 Autres Composants . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Système d’exploitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 La Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 L’environnement de programmation . . . . . . . . . . . . . . . . . . . . . . 22
2.4.1 Noms de ?chiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.4.2 Debuggeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.3 TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3 Premiers programmes 25
3.1 Tout dans le main() ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.2 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.3 Boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1.4 Récréations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 Retour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2.2 Paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2.3 Passage par référence . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.4 Portée, Déclaration, Dé?nition . . . . . . . . . . . . . . . . . . . . . 42
3.2.5 Variables locales et globales . . . . . . . . . . . . . . . . . . . . . . 43
3.2.6 Surcharge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3 TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4 Fiche de référence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4 Les tableaux 47
4.1 Premiers tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2 Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Spéci?cités des tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.1 Tableaux et fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.3.2 A?ectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.4 Récréations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4.1 Multi-balles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4.2 Avec des chocs ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.4.3 Mélanger les lettres . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.5 TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.6 Fiche de référence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5 Les structures 63
5.1 Révisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.1 Erreurs classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.2 Erreurs originales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.3 Conseils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2 Les structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.1 Dé?nition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.2 Utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.3 Récréation : TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.4 Fiche de référence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
6 Plusieurs ?chiers ! 71
6.1 Fichiers séparés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.1.2 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6.1.3 Utilisation dans un autre projet . . . . . . . . . . . . . . . . . . . . 74
6.1.4 Fichiers d’en-têtes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
6.1.5 A ne pas faire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.1.6 Implémentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2 Opérateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.3 Récréation : TP suite et ?n . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.4 Fiche de référence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
7 La mémoire 83
7.1 L’appel d’une fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.1.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
7.1.2 Pile des appels et débuggeur . . . . . . . . . . . . . . . . . . . . . . 85
7.2 Variables Locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.2.1 Paramètres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.2.2 La pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7.3 Fonctions récursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.3.1 Pourquoi ça marche ? . . . . . . . . . . . . . . . . . . . . . . . . . . 88
7.3.2 E?cacité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.4 Le tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.4.1 Limites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.4.2 Tableaux de taille variable . . . . . . . . . . . . . . . . . . . . . . . 91
7.4.3 Essai d’explication . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.5 L’optimiseur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.6 TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
…
A.2.2 Premier programme graphique avec la CLGraphics . . . . . . . . . 187
A.2.3 Jeu de Tennis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
A.3 Tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
A.3.1 Mastermind Texte . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
A.4 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
A.4.1 Etapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
A.4.2 Aide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
A.4.3 Théorie physique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
A.5 Fichiers séparés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
A.5.1 Fonctions outils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
A.5.2 Vecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
A.5.3 Balle à part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
A.5.4 Retour à la physique . . . . . . . . . . . . . . . . . . . . . . . . . . 201
A.6 Les tris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
A.6.1 Mélanger un tableau . . . . . . . . . . . . . . . . . . . . . . . . . . 203
A.6.2 Tris quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
A.6.3 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
A.6.4 Gros tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
A.7 Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
A.7.1 Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
A.7.2 Tableaux statiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
A.7.3 Tableaux dynamiques . . . . . . . . . . . . . . . . . . . . . . . . . . 208
A.7.4 Charger un ?chier . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
A.7.5 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208
A.7.6 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
A.7.7 Suite et ?n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
A.8 Premiers objets et dessins de fractales . . . . . . . . . . . . . . . . . . . . . 210
A.8.2 Une classe plutôt qu’une structure . . . . . . . . . . . . . . . . . . . 211
A.8.3 Changer d’implémentation . . . . . . . . . . . . . . . . . . . . . . . 211
A.8.4 Le ?ocon de neige . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
A.9 Tron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
A.9.1 Serpent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
A.9.2 Tron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
A.9.3 Graphismes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
B Examens 215
B.1 Examen sur machine 2003 : énoncé . . . . . . . . . . . . . . . . . . . . . . 215
B.1.1 Crible d’Ératosthène . . . . . . . . . . . . . . . . . . . . . . . . . . 215
B.1.2 Calcul de ¼ par la méthode de Monte Carlo . . . . . . . . . . . . . 215
B.1.3 Serpent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
B.2 Examen sur machine 2004 : énoncé . . . . . . . . . . . . . . . . . . . . . . 220
B.2.1 Calcul de l’exponentielle d’un nombre complexe . . . . . . . . . . . 220
B.2.2 Compression RLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
B.3 Examen sur machine 2005 : énoncé . . . . . . . . . . . . . . . . . . . . . . 223
B.3.1 Construction du Modèle 3D . . . . . . . . . . . . . . . . . . . . . . 223
B.3.2 Projection : du 3D au 2D . . . . . . . . . . . . . . . . . . . . . . . 223
B.3.3 A?chage à l’écran . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
B.3.4 Animation du tétraèdre . . . . . . . . . . . . . . . . . . . . . . . . 224
B.3.5 Un modèle plus élaboré . . . . . . . . . . . . . . . . . . . . . . . . . 225
B.4 Examen sur machine 2006 : énoncé . . . . . . . . . . . . . . . . . . . . . . 226
B.4.1 Voyageur de commerce par recuit simulé . . . . . . . . . . . . . . . 226
B.4.2 Travail demandé . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
B.5.1 Tableau d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . 227
B.5.2 Grands entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
B.5.3 Constructeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
B.6 Devoir écrit 2004 : énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
B.6.1 Tableau d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . 231
B.6.2 Constructeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
B.6.3 Le compte est bon . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
B.7 Devoir écrit 2006 : énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
B.7.1 Enoncé – Tours de Hanoi . . . . . . . . . . . . . . . . . . . . . . . . 237
B.8 Devoir ?nal 2003 : énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
B.8.1 Tableau d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . 240
B.8.2 Erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
B.8.3 Qu’a?che ce programme ? . . . . . . . . . . . . . . . . . . . . . . . 242
B.8.4 Le jeu du Pendu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
B.8.5 Programme mystère . . . . . . . . . . . . . . . . . . . . . . . . . . 245
B.9 Devoir ?nal 2004 : énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
B.9.1 Erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
B.9.2 Qu’a?che ce programme ? . . . . . . . . . . . . . . . . . . . . . . . 248
B.9.3 Chemins dans un graphe . . . . . . . . . . . . . . . . . . . . . . . . 251
B.9.4 Tours de Hanoï . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
B.9.5 Table de hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
B.10 Devoir ?nal 2005 : énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
B.10.1 Erreurs à corriger . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
B.10.3 Tableau d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . 259
B.10.4 Résolveur de Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . 260
B.11 Devoir ?nal 2006 : énoncé . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
B.11.1 Erreurs à corriger . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
B.11.2 Qu’a?che ce programme ? . . . . . . . . . . . . . . . . . . . . . . . 264
B.11.3 Tableau d’exécution . . . . . . . . . . . . . . . . . . . . . . . . . . 266
B.11.4 Huit dames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
C La CLGraphics 271
D Fiche de référence ?nale 273
Cours programmation en informatique pour débutant