392 Programmer

LA PROGRAMMATION POUR...

2 les lves ingnieurs2 . . . ou les collgiens

2 dbutants2 . . . ou confirms

Cours de lcole des Ponts ParisTech - 2012/2013Renaud Keriven et Pascal MonasseIMAGINE - cole des Ponts ParisTech{keriven,monasse}@imagine.enpc.fr

Version lectronique et programmes :http://imagine.enpc.fr/~monasse/Info/

"Ne traitez pas vos ordinateurs comme des tres vivants...Ils naiment pas a !"

"Cet ordinateur ne fait pas du tout ce que je veux !" "Exact... Il fait ce que tu lui demandes de faire !"

TABLE DES MATIRES TABLE DES MATIRES

Table des matires

1 Prambule 91.1 Pourquoi savoir programmer ? . . . . . . . . . . . . . . . . . . . . . . . . 111.2 Comment apprendre ? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.1 Choix du langage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.2.2 Choix de lenvironnement . . . . . . . . . . . . . . . . . . . . . . . 131.2.3 Principes et conseils . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Bonjour, Monde ! 152.1 Lordinateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.1.1 Le micro-processeur . . . . . . . . . . . . . . . . . . . . . . . . . . 172.1.2 La mmoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.1.3 Autres Composants . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2 Systme dexploitation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.3 La Compilation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.4 Lenvironnement de programmation . . . . . . . . . . . . . . . . . . . . . 24

2.4.1 Noms de fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.4.2 Debuggeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.4.3 TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3 Premiers programmes 273.1 Tout dans le main() ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.1.2 Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.1.3 Boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.1.4 Rcrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.2.1 Retour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2.2 Paramtres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.2.3 Passage par rfrence . . . . . . . . . . . . . . . . . . . . . . . . . 413.2.4 Porte, Dclaration, Dfinition . . . . . . . . . . . . . . . . . . . . 443.2.5 Variables locales et globales . . . . . . . . . . . . . . . . . . . . . . 453.2.6 Surcharge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.3 TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473.4 Fiche de rfrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4 Les tableaux 514.1 Premiers tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.2 Initialisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.3 Spcificits des tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53


4.3.1 Tableaux et fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . 544.3.2 Affectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4.4 Rcrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.4.1 Multi-balles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.4.2 Avec des chocs ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.4.3 Mlanger les lettres . . . . . . . . . . . . . . . . . . . . . . . . . . . 61


5 Les structures 675.1 Rvisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.1.1 Erreurs classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.1.2 Erreurs originales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.1.3 Conseils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.2 Les structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695.2.1 Dfinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695.2.2 Utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

5.3 Rcration : TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715.4 Fiche de rfrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6 Plusieurs fichiers ! 756.1 Fichiers spars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 766.1.2 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776.1.3 Utilisation dans un autre projet . . . . . . . . . . . . . . . . . . . . 786.1.4 Fichiers den-ttes . . . . . . . . . . . . . . . . . . . . . . . . . . . 786.1.5 A ne pas faire... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 816.1.6 Implmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 816.1.7 Inclusions mutuelles . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.2 Oprateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826.3 Rcration : TP suite et fin . . . . . . . . . . . . . . . . . . . . . . . . . . . 836.4 Fiche de rfrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

7 La mmoire 877.1 Lappel dune fonction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

7.1.1 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 877.1.2 Pile des appels et dbuggeur . . . . . . . . . . . . . . . . . . . . . 89

7.2 Variables Locales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 917.2.1 Paramtres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 927.2.2 La pile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

7.3 Fonctions rcursives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 927.3.1 Pourquoi a marche ? . . . . . . . . . . . . . . . . . . . . . . . . . . 937.3.2 Efficacit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

7.4 Le tas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 957.4.1 Limites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 957.4.2 Tableaux de taille variable . . . . . . . . . . . . . . . . . . . . . . . 957.4.3 Essai dexplication . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

7.5 Loptimiseur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 977.6 Assertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

2


7.7 TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 987.8 Fiche de rfrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997.9 Examens sur machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

8 Allocation dynamique 1038.1 Tableaux bidimensionnels . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

8.1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1038.1.2 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1048.1.3 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

8.2 Allocation dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1068.2.1 Pourquoi a marche ? . . . . . . . . . . . . . . . . . . . . . . . . . . 1068.2.2 Erreurs classiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1078.2.3 Consquences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

8.3 Structures et allocation dynamique . . . . . . . . . . . . . . . . . . . . . . 1098.4 Boucles et continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1128.5 TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1128.6 Fiche de rfrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

9 Premiers objets 1179.1 Philosophie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1179.2 Exemple simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1189.3 Visibilit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1199.4 Exemple des matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1209.5 Cas des oprateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1229.6 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1249.7 Protection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

9.7.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1259.7.2 Structures vs Classes . . . . . . . . . . . . . . . . . . . . . . . . . . 1279.7.3 Accesseurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127


10 Constructeurs et Destructeurs 13310.1 Le problme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13310.2 La solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13410.3 Cas gnral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

10.3.1 Constructeur vide . . . . . . . . . . . . . . . . . . . . . . . . . . . 13410.3.2 Plusieurs constructeurs . . . . . . . . . . . . . . . . . . . . . . . . 13610.3.3 Tableaux dobjets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

10.4 Objets temporaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13810.5 TP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13910.6 Rfrences Constantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

10.6.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13910.6.2 Mthodes constantes . . . . . . . . . . . . . . . . . . . . . . . . . . 140

10.7 Destructeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14210.8 Destructeurs et tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14410.9 Constructeur de copie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14410.10Affectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14510.11Objets avec allocation dynamique . . . . . . . . . . . . . . . . . . . . . . . 146

3


10.11.1 Construction et destruction . . . . . . . . . . . . . . . . . . . . . . 14610.11.2 Problmes ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14710.11.3 Solution ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148

10.12Fiche de rfrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15110.13Devoir crit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

11 En vrac... 15511.1 Chanes de caratres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15511.2 Fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

11.2.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15711.2.2 Chanes et fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . 15811.2.3 Objets et fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

11.3 Valeurs par dfaut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15911.3.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15911.3.2 Utilit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16011.3.3 Erreurs frquentes . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

11.4 Accesseurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16011.4.1 Rfrence comme type de retour . . . . . . . . . . . . . . . . . . . 16111.4.2 Utilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16111.4.3 operator() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16211.4.4 Surcharge et mthode constante . . . . . . . . . . . . . . . . . . . 16211.4.5 "inline" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163

11.5 Assertions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16511.6 Types numrs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16511.7 Fiche de rfrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166

12 En vrac (suite) ... 17112.1 Oprateur binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17112.2 Valeur conditionnelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17212.3 Boucles et break . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17312.4 Variables statiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17412.5 const et tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17512.6 template . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

12.6.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17512.6.2 template et fichiers . . . . . . . . . . . . . . . . . . . . . . . . . . 17712.6.3 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17712.6.4 STL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

12.7 Fiche de rfrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18212.8 Devoir final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

13 Structure de donnes 18913.1 Rappels sur les tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18913.2 La complexit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

13.2.1 Mais quest-ce donc que la complexit ? . . . . . . . . . . . . . . . 19013.2.2 Comment la mesure-t-on ? . . . . . . . . . . . . . . . . . . . . . . . 19113.2.3 La notation O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19113.2.4 P et NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19113.2.5 Pourquoi est-ce important ? . . . . . . . . . . . . . . . . . . . . . . 192

13.3 Le vecteur : un tableau encapsul dans une classe . . . . . . . . . . . . . 192

4


13.3.1 Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19213.3.2 Complexit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19313.3.3 Gestion mmoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

13.4 La pile, Last In First Out (LIFO) . . . . . . . . . . . . . . . . . . . . . . . . 19313.5 La file, First In First Out (FIFO) . . . . . . . . . . . . . . . . . . . . . . . . 19413.6 La liste chane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19613.7 Rcapitulatif des complexits . . . . . . . . . . . . . . . . . . . . . . . . . 19713.8 Les itrateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19713.9 Autres structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198

14 Algorithmes de tri 19914.1 Complexit minimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19914.2 Algorithmes quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 19914.3 QuickSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20014.4 File de priorit et HeapSort . . . . . . . . . . . . . . . . . . . . . . . . . . 202

14.4.1 Insertion dans la file de priorit (push) . . . . . . . . . . . . . . . 20214.4.2 Retrait de la file de priorit (pop) . . . . . . . . . . . . . . . . . . . 20314.4.3 Stockage de la file de priorit . . . . . . . . . . . . . . . . . . . . . 20314.4.4 HeapSort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

14.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

A Travaux Pratiques 205A.1 Lenvironnement de programmation . . . . . . . . . . . . . . . . . . . . . 205

A.1.1 Bonjour, Monde ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205A.1.2 Premires erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207A.1.3 Debugger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209A.1.4 Sil reste du temps . . . . . . . . . . . . . . . . . . . . . . . . . . . 210A.1.5 Installer Imagine++ chez soi . . . . . . . . . . . . . . . . . . . . . . 210

A.2 Variables, boucles, conditions, fonctions . . . . . . . . . . . . . . . . . . . 211A.2.1 Premier programme avec fonctions . . . . . . . . . . . . . . . . . 211A.2.2 Premier programme graphique avec Imagine++ . . . . . . . . . . 211A.2.3 Jeu de Tennis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

A.3 Tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215A.3.1 Mastermind Texte . . . . . . . . . . . . . . . . . . . . . . . . . . . 215A.3.2 Mastermind Graphique . . . . . . . . . . . . . . . . . . . . . . . . 217

A.4 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219A.4.1 Etapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219A.4.2 Aide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221A.4.3 Thorie physique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

A.5 Fichiers spars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224A.5.1 Fonctions outils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224A.5.2 Vecteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224A.5.3 Balle part . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225A.5.4 Retour la physique . . . . . . . . . . . . . . . . . . . . . . . . . . 225

A.6 Les tris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227A.6.1 Mlanger un tableau . . . . . . . . . . . . . . . . . . . . . . . . . . 227A.6.2 Tris quadratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228A.6.3 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229A.6.4 Gros tableaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

5


A.7 Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231A.7.1 Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231A.7.2 Tableaux statiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 231A.7.3 Tableaux dynamiques . . . . . . . . . . . . . . . . . . . . . . . . . 232A.7.4 Charger un fichier . . . . . . . . . . . . . . . . . . . . . . . . . . . 232A.7.5 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232A.7.6 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233A.7.7 Suite et fin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233

A.8 Premiers objets et dessins de fractales . . . . . . . . . . . . . . . . . . . . 234A.8.1 Le triangle de Sierpinski . . . . . . . . . . . . . . . . . . . . . . . . 234A.8.2 Une classe plutt quune structure . . . . . . . . . . . . . . . . . . 235A.8.3 Changer dimplmentation . . . . . . . . . . . . . . . . . . . . . . 235A.8.4 Le flocon de neige . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

A.9 Tron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237A.9.1 Serpent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237A.9.2 Tron . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238A.9.3 Graphismes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238

B Examens 241B.1 Examen sur machine 2011 : nonc . . . . . . . . . . . . . . . . . . . . . . 241

B.1.1 Automate cellulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . 241B.1.2 Travail demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

B.2 Examen sur machine 2010 : nonc . . . . . . . . . . . . . . . . . . . . . . 244B.2.1 Visualisation 3D par z-buffer . . . . . . . . . . . . . . . . . . . . . 244B.2.2 Travail demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244B.2.3 Annexe : les formules . . . . . . . . . . . . . . . . . . . . . . . . . 247

B.3 Examen sur machine 2009 : nonc . . . . . . . . . . . . . . . . . . . . . . 249B.3.1 Spirale dUlam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249B.3.2 Travail demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

B.4 Examen sur machine 2008 : nonc . . . . . . . . . . . . . . . . . . . . . . 251B.4.1 Ensemble de Mandelbrot . . . . . . . . . . . . . . . . . . . . . . . 251B.4.2 Travail demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

B.5 Examen sur machine 2007 : nonc . . . . . . . . . . . . . . . . . . . . . . 253B.5.1 Chemins entre deux points . . . . . . . . . . . . . . . . . . . . . . 253B.5.2 Travail demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253

B.6 Examen sur machine 2006 : nonc . . . . . . . . . . . . . . . . . . . . . . 254B.6.1 Voyageur de commerce par recuit simul . . . . . . . . . . . . . . 254B.6.2 Travail demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

B.7 Examen sur machine 2005 : nonc . . . . . . . . . . . . . . . . . . . . . . 256B.7.1 Construction du Modle 3D . . . . . . . . . . . . . . . . . . . . . . 256B.7.2 Projection : du 3D au 2D . . . . . . . . . . . . . . . . . . . . . . . . 256B.7.3 Affichage lcran . . . . . . . . . . . . . . . . . . . . . . . . . . . 257B.7.4 Animation du ttradre . . . . . . . . . . . . . . . . . . . . . . . . 257B.7.5 Un modle plus labor . . . . . . . . . . . . . . . . . . . . . . . . 258

B.8 Examen sur machine 2004 : nonc . . . . . . . . . . . . . . . . . . . . . . 259B.8.1 Calcul de lexponentielle dun nombre complexe . . . . . . . . . . 259B.8.2 Compression RLE . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

B.9 Examen sur machine 2003 : nonc . . . . . . . . . . . . . . . . . . . . . . 263B.9.1 Crible dratosthne . . . . . . . . . . . . . . . . . . . . . . . . . . 263

6


B.9.2 Calcul de pi par la mthode de Monte Carlo . . . . . . . . . . . . . 263B.9.3 Serpent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

B.10 Devoir maison 2007 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . . 267B.11 Devoir maison 2006 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . . 269

B.11.1 Enonc Tours de Hanoi . . . . . . . . . . . . . . . . . . . . . . . 269B.12 Devoir maison 2004 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . . 272

B.12.1 Tableau dexcution . . . . . . . . . . . . . . . . . . . . . . . . . . 272B.12.2 Constructeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273B.12.3 Le compte est bon . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

B.13 Devoir maison 2003 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . . 278B.13.1 Tableau dexcution . . . . . . . . . . . . . . . . . . . . . . . . . . 278B.13.2 Grands entiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279B.13.3 Constructeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

B.14 Devoir surveill 2011 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . 282B.14.1 Liste avec sauts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282B.14.2 Travail demand . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283

B.15 Devoir surveill 2010 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . 286B.15.1 Programmation : machine registres . . . . . . . . . . . . . . . . . 286B.15.2 Algorithmique : ensemble sans doublon . . . . . . . . . . . . . . . 288

B.16 Devoir surveill 2009 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . 290B.16.1 Quaffiche ce programme ? . . . . . . . . . . . . . . . . . . . . . . 290B.16.2 Programmation : enrichir la classe polynme . . . . . . . . . . . . 293B.16.3 Algorithmie : problme de slection . . . . . . . . . . . . . . . . . 293

B.17 Devoir surveill 2008 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . 294B.17.1 Erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294B.17.2 Problme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296

B.18 Devoir surveill 2007 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . 298B.18.1 Groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298B.18.2 Anniversaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

B.19 Devoir surveill 2006 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . 301B.19.1 Erreurs corriger . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301B.19.2 Quaffiche ce programme ? . . . . . . . . . . . . . . . . . . . . . . 302B.19.3 Tableau dexcution . . . . . . . . . . . . . . . . . . . . . . . . . . 304B.19.4 Huit dames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

B.20 Devoir surveill 2005 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . 308B.20.1 Erreurs corriger . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308B.20.2 Quaffiche ce programme ? . . . . . . . . . . . . . . . . . . . . . . 308B.20.3 Tableau dexcution . . . . . . . . . . . . . . . . . . . . . . . . . . 310B.20.4 Rsolveur de Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . 311

B.21 Devoir surveill 2004 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . 314B.21.1 Erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314B.21.2 Quaffiche ce programme ? . . . . . . . . . . . . . . . . . . . . . . 315B.21.3 Chemins dans un graphe . . . . . . . . . . . . . . . . . . . . . . . 318B.21.4 Tours de Hano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319B.21.5 Table de hachage . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322

B.22 Devoir surveill 2003 : nonc . . . . . . . . . . . . . . . . . . . . . . . . . 324B.22.1 Tableau dexcution . . . . . . . . . . . . . . . . . . . . . . . . . . 324B.22.2 Erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325B.22.3 Quaffiche ce programme ? . . . . . . . . . . . . . . . . . . . . . . 326

7


B.22.4 Le jeu du Pendu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328B.22.5 Programme mystre . . . . . . . . . . . . . . . . . . . . . . . . . . 329

C Imagine++ 331C.1 Common . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331C.2 Graphics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331C.3 Image . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332C.4 LinAlg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333

D Fiche de rfrence finale 335

8

1. Prambule

Chapitre 1

Prambule

Note : Ce premier chapitre maladroit correspond ltat desprit dans lequel cecours a dbut en 2003, dans une priode o lInformatique avait mauvaise presse lcole des Ponts. Nous le maintenons ici en tant que tmoin de ce quil faillait fairealors pour amener les lves ne pas ngliger lInformatique. Si lon ignore la navetde cette premire rdaction (et le fait que Star Wars nest plus autant la mode !),lanalyse et les conseils qui suivent restent dactualit.

(Ce premier chapitre tente surtout de motiver les lves ingnieurs dans leur apprentissagede la programmation. Les enfants qui se trouveraient ici pour apprendre programmer sontsrement dj motivs et peuvent sauter au chapitre suivant ! Profitons-en pour tenir des proposqui ne les concernent pas...)

Le Matre Programmeur 1 : "Rassure-toi ! Les ordinateurs sont stupides ! Program-mer est donc facile."

LApprenti Programmeur 2 : "Matre, les ordinateurs ne sont certes que des ma-chines et les dominer devrait tre ma porte. Et pourtant... Leur manque din-telligence fait justement quil mest pnible den faire ce que je veux. Programmerexige de la prcision et la moindre erreur est sanctionne par un message incom-prhensible, un bug 3 ou mme un crash de la machine. Pourquoi doit-on treaussi... prcis ?" Programmer rend maniaque ! Dailleurs, les informaticiens sont tousmaniaques. Et je nai pas envie de devenir comme a...

1. Permettez ce terme ouvertement Lucasien. Il semble plus appropri que lhabituel Gourou souventutilis pour dcrire lexpert informaticien. Nous parlons bien ici dun savoir-faire transmettre de Matre Apprenti et non dune secte...

2. Le jeune Padawan, donc, pour ceux qui connaissent...3. Je naurai aucun remord dans ce polycopi utiliser les termes habituels des informaticiens... en

essayant videmment de ne pas oublier de les expliquer au passage. Anglicismes souvent incompr-hensibles, ils constituent en ralit un argot propre au mtier dinformaticien, argot que doit bien vi-demment accepter et faire sien lApprenti sous peine de ne rien comprendre au discours de ses collguesdune part, et demployer des adaptations franaises ridicules ou peu usites dautre part. Naviguer surla toile, envoyer un courriel ou avoir un bogue commencent peut-tre devenir des expressions com-prhensibles. Mais demandez-donc votre voisin sil reoit beaucoup de pourriels (terme propos pourtraduire "Spams") !

1. Prambule

M.P. : "La prcision est indispensable pour communiquer avec une machine. Cest lHomme de sadapter. Tu dois faire un effort. En contre-partie tu deviendrasson matre. Rjouis-toi. Bientt, tu pourras crer ces tres obissants que sont lesprogrammes."

A.P. : "Bien, Matre..." Quel vieux fou ! Pour un peu, il se prendrait pour Dieu. La vrit,cest quil parle aux machines parce quil ne sait pas parler aux hommes. Il comble avecses ordinateurs son manque de contact humain. Linformaticien type... Il ne lui manqueplus que des grosses lunettes et les cheveux gras 4. "Matre, je ne suis pas sr den avoirenvie. Je ny arriverai pas. Ne le prenez pas mal, mais je crois tre davantage doupour les Mathmatiques ! Et puis, quoi savoir programmer me servira-t-il ?"

M.P. : "Les vrais problmes qui se poseront toi, tu ne pourras toujours les r-soudre par les Mathmatiques. Savoir programmer, tu devras !"

A.P. : "Jessaierai..." Je me demande sil a vraiment raison ! Je suis sr quil doit tre nulen Maths. Voil la vrit !

...

Oublions l ce dialogue aussi caricatural que maladroit. Il montre pourtant claire-ment la situation. Rsumons :

Pour celui qui sait, programmer : est un jeu denfant. est indispensable. est une activit cratrice et panouissante.

Pour celui qui apprend, programmer : est difficile. ne sert rien. est une activit ingrate qui favorise le renfermement 5 sur soi-mme.

Dans le cas o llve est ingnieur, nous pouvons complter le tableau : Pour le professeur, apprendre programmer :

devrait tre simple et rapide pour un lve ingnieur. est plus utile quapprendre davantage de Mathmatiques.

Pour llve, programmer : est un travail de "technicien 6" quil naura jamais faire lui-mme. nest pas aussi noble que les Mathmatiques, bref, nest pas digne de lui.

En fait, les torts sont partags : Le professeur :

ne ralise pas que ses lves ont un niveau avanc en maths parce quils enfont depuis plus de dix ans, et quil leur faudra du temps pour apprendre neserait-ce que les bases de la programmation. Du temps... et de la pratique, car,si programmer est effectivement simple en regard de ce que ses lves saventfaire en maths, il ncessite une tournure desprit compltement diffrente etbeaucoup de travail personnel devant la machine.

4. Toute ressemblance avec des personnages rels ou imaginaires, etc.5. Utiliser un ordinateur pour programmer a tout aussi mauvaise presse que de jouer aux jeux vido.

Programmer est pourtant souvent un travail dquipe.6. avec tout le sens pjoratif que ce terme peut avoir pour lui.

10

1. Prambule 1.1. Pourquoi savoir programmer ?

oublie quil a le plus souvent appris seul quand il tait plus jeune, en program-mant des choses simples et ludiques 7. Il devrait donc faire venir ses lves la programmation par le ct ludique, et non avec les mmes sempiternelsexemples 8.

Llve : ne se rend pas compte que savoir programmer lui sera utile. Il sagit pourtant

dune base qui se retrouve dans tous les langages et mme dans la plupart deslogiciels modernes 9. Et puis, considr comme "le jeune" donc le moins "al-lergique" aux ordinateurs, il se verra vraisemblablement confier son premierposte la ralisation de quelques petits programmes en plus de ses attributionsnormales.

sarrange un peu trop facilement dun mpris de bon ton pour la programma-tion. Il lui est plus ais dapprendre une n-ime branche des mathmatiquesque de faire leffort dacqurir par la pratique une nouvelle tournure desprit.

On laura compris, il est la fois facile et difficile dapprendre programmer. Pourlingnieur, cela demandera de la motivation et un peu deffort : essentiellement demettre ses maths de ct et de retrouver le got des choses basiques. Pour un coll-gien, motivation et got de leffort seront au rendez-vous. Il lui restera malgr tout acqurir quelques bases darithmtique et de gomtrie. Comme annonc par le titrede ce cours, collgien et ingnieur en sont au mme point pour lapprentissage de laprogrammation. De plus, et cest un phnomne relativement nouveau, il en est demme pour le dbutant et le "geek 10". Expliquons-nous : le passionn dinformatiquea aujourdhui tellement de choses faire avec son ordinateur quil sera en gnral in-collable sur les jeux, internet, les logiciels graphiques ou musicaux, linstallation oula configuration de son systme, lachat du dernier gadget USB la mode, etc. maisquen contrepartie il sera mauvais programmeur. Il y a quelques annes, il y avait peu faire avec son ordinateur sinon programmer. Programmer pour combler le manquede possibilits de lordinateur. Aujourdhui, faire le tour de toutes les possibilits dunordinateur est une occupation plein temps ! Ainsi, le "fana info" passe-t-il sa jour-ne se tenir au courant des nouveaux logiciels 11 et en oublie quil pourrait lui aussien crer. En conclusion, collgiens ou ingnieurs, dbutants ou passionns, tous leslves sont galit. Cest donc sans complexe que lingnieur pourra apprendre programmer en mme temps que le fils de la voisine.

1.1 Pourquoi savoir programmer ?

Nous venons partiellement de le dire. Rsumons et compltons :

7. Cest une erreur frquente de croire quil intressera ses lves en leur faisant faire des pro-grammes centrs sur les mathmatiques ou le calcul scientifique. De tels programmes leur seront peut-tre utiles plus tard, mais ne sont pas forcment motivants. Lalgbre linaire ou lanalyse numriquesont des domaines passionnants tudier... mais certainement pas programmer. Il faut admettre sanscomplexe que programmer un flipper, un master-mind ou un labyrinthe 3D est tout aussi formateur etplus motivant quinverser une matrice creuse.

8. La liste est longue, mais tellement vraie : quel cours de programmation ne rabche pas les clbres"factorielle", "suites de Fibonacci", "Quick Sort", etc ?

9. Savoir programmer ne sert pas seulement faire du C++ ou du Java, ni mme du Scilab, du Matlabou du Maple : une utilisation avance dExcel ou du Word demande parfois de la programmation !

10. Une rcompense qui me trouve un substitut satisfaisant cette expression consacre.11. Sans mme dailleurs avoir le temps den creuser convenablement un seul !

11

1.2. Comment apprendre ? 1. Prambule

1. Cest la base. Apprendre un langage prcis nest pas du temps perdu car lesmmes concepts se retrouvent dans la plupart des langages. De plus, les logicielscourants eux-mmes peuvent se programmer.

2. Il est frquent quun stage ou quune embauche en premier poste comporte unpeu de programmation, mme, et peut-tre surtout, dans les milieux o peu degens programment.

3. Savoir programmer, cest mieux connatre le matriel et les logiciels, ce qui estpossible techniquement et ce qui ne lest pas. Mme un poste non technique,cest important pour prendre les bonnes dcisions.

1.2 Comment apprendre ?

1.2.1 Choix du langage

Il faut dabord choisir un langage de programmation. Un ingnieur pourrait vi-demment tre tent dapprendre programmer en Maple, Matlab, Scilab ou autre. Ilfaut quil comprenne quil sagit l doutils spcialiss pour mathmaticien ou ing-nieur qui lui seront utiles et qui, certes, se programment, mais pas proprement parlerde langages gnralistes complets. Sans argumenter sur les dfauts respectifs des lan-gages qui en font partie, il nous semble vident quil ne sagit pas du bon choix pourlapprentissage de la programmation.

En pratique, le choix actuel se fait souvent entre C++ et Java. Bien que Java aie tconu, entre autres, dans un soucis de simplification du C++ 12, nous prfrerons C++pour des raisons pdagogiques :

1. C++ est plus complexe dans son ensemble mais nen connatre que les bases estdj bien suffisant. Nous ne verrons donc dans ce cours quun sous ensemble duC++, suffisant en pratique.

2. Plus complet, C++ permet une programmation de haut niveau mais aussi uneprogrammation simple, adapte au dbutant 13. C++ permet galement une pro-grammation proche de la machine, ce qui est important pour le spcialiste maisaussi pour le dbutant, car seule une bonne comprhension de la machine aboutit une programmation convenable et efficace 14.

3. C++ est souvent incontournable dans certains milieux, par exemple en finance.

4. Enfin, certains aspects pratiques et pourtant simples de C++ ont disparu dansJava 15.

Encore une fois, rptons que le choix du langage nest pas le plus important et quelessentiel est dapprendre programmer.

12. Nous ne rduisons videmment pas Java un sous ensemble de C++. Il lui est suprieur surcertains aspects mais il est dexpressivit plus rduite.

13. Java force un cadre de programmation objet, droutant pour le dbutant.14. Ne pas comprendre ce que la machine doit faire pour excuter un programme, conduit des pro-

grammes inconsidrment gourmands en temps ou mmoire.15. Les oprateurs par exemple.

12

1. Prambule 1.2. Comment apprendre ?

1.2.2 Choix de lenvironnement

Windows et Linux ont leurs partisans, souvent farouchement opposs, tel pointque certains nadmettent pas quil est possible dtre partisan des deux systmes lafois. Conscients des avantages et des inconvnients de chacun des deux systmes, nousnen prnons aucun en particulier 16. Ceci dit, pour des raisons pdagogiques, nouspensons quun environnement de programmation intgr, cest dire un logiciel uniquepermettant de programmer, est prfrable lutilisation de multiples logiciels (diteur,compilateur, debuggeur, etc.). Cest vrai pour le programmeur confirm, qui trouveen gnral dans cet environnement des outils puissants, mais cest encore plus crucialpour le dbutant. Un environnement de programmation, cest :

Toutes les tapes de la programmation regroupes en un seul outil de faon co-hrente.

Editer ses fichiers, les transformer en programme, passer en revue ses erreurs,dtecter les bugs, parcourir la documentation, etc. tout cela avec un seul outilergonomique.

Sans arrire pense de principe, nous avons opt pour lenvironnement de Microsoft,Visual Studio, la fois simple et puissant. Il est le plus utilis des produits commer-ciaux. Il en existe quelques quivalents gratuits sous linux, mais pas encore suffisam-ment aboutis pour nous faire hsiter. Cest donc le choix de Visual Studio et ce choixseul qui est la raison de lutilisation de Windows au dtriment de linux... Mieux en-core, il existe maintenant une version de Visual gratuite : Visual Express. Comme pourle choix du langage, le choix de lenvironnement nest pas limitant et en connatre unpermet de sadapter facilement nimporte quel autre.

1.2.3 Principes et conseils

Au niveau auquel nous prtendons lenseigner, la programmation ne requiert nigrande thorie, ni connaissances encyclopdiques. Les concepts utiliss sont rudimen-taires mais cest leur mise en oeuvre qui est dlicate. Sil ny avait quun seul conseil donner, ce serait la rgle des trois "P" :

1. Programmer

2. Programmer

3. Programmer

La pratique est effectivement essentielle. Cest ce qui fait quun enfant a plus de facili-ts, puisquil a plus de temps. Ajoutons quand mme quelques conseils de base :

1. Samuser. Cest une vidence en matire de pdagogie. Mais cest tellement faciledans le cas de la programmation, quil serait dommage de passer ct ! Au pire,si programmer nest pas toujours une partie de plaisir pour tout le monde, il vautmieux que le programme obtenu dans la douleur soit intressant pour celui quila fait !

2. Bricoler. Ce que nous voulons dire par l, cest quil ne faut pas hsiter tton-ner, tester, fouiller, faire, dfaire, casser, etc. Lordinateur est un outil exprimen-tal. Mais sa programmation est elle aussi une activit exprimentale la base.Mme si le programmeur aguerri trouvera la bonne solution du premier jet, il

16. Lidal est en fait davoir les deux "sous la main".

13

1.2. Comment apprendre ? 1. Prambule

est important pour le dbutant dapprendre connatre le langage et loutil deprogrammation en jouant avec eux.

3. Faire volontairement des erreurs. Provoquer les erreurs pendant la phase dap-prentissage pour mieux les connatre est le meilleur moyen de comprendre beau-coup de choses et aussi de reprer ces erreurs quand elles ne seront plus volon-taires.

4. Rester (le) matre 17 (de la machine et de son programme). Que programmer soitexprimental ne signifie pas pour autant quil faille faire nimporte quoi jusquce que a marche plus ou moins. Il faut avancer progressivement, mthodique-ment, en testant au fur et mesure, sans laisser passer la moindre erreur ou im-prcision.

5. Debugger. Souvent, la connaissance du debuggeur (loutil pour rechercher lesbugs) est nglige et son apprentissage est repouss au stade avanc. Il sagitpourtant dun outil essentiel pour comprendre ce qui se passe dans un programme,mme dpourvu de bugs. Il faut donc le considrer comme essentiel et faisantpartie intgrante de la conception dun programme. L encore, un bon environ-nement de programmation facilite la tche.

Gardons bien prsents ces quelques principes car il est maintenant temps de...

passer notre premier programme !

17. Le vocabulaire nest pas choisi au hasard : un programme est une suite dordres, de commandes oudinstructions. On voit bien qui est le chef !

14

2. Bonjour, Monde !

Chapitre 2

Bonjour, Monde !

(Si certains collgiens sont arrivs ici, ils sont bien courageux ! Lorsque je disais tout lheure quils pouvaient facilement apprendre programmer, je le pensais vraiment. Par contre,cest avec un peu doptimisme que jai prtendu quils pouvaient le faire en lisant un polycopidestin des ingnieurs. Enfin, je suis pris mon propre pige ! Alors, tout hasard, je vaistenter dexpliquer au passage les mathmatiques qui pourraient leur poser problme.)

Si lon en croit de nombreux manuels de programmation, un premier programmedoit toujours ressembler a :

# inc lude using namespace std ;

i n t main ( ){

cout

2. Bonjour, Monde !

programme est lanc 5. Dlimite par les accolades ({ ligne 5 et } ligne 8), la fonctionmain() se termine ligne 7 par return 0; qui lui ordonne de retourner lentier 0. Notonsau passage que toutes les instructions se terminent par un point-virgule ;. Enfin, laligne 6, seule ligne "intressante", cout

2. Bonjour, Monde! 2.1. Lordinateur

Chapitre 2 (deuxime essai)

Comment a marche ?

Le problme avec le programme prcdent est quil est trs loin de ce quun ordi-nateur sait faire naturellement. En fait, un ordinateur ne sait pas faire de C++. Il nesait que calculer 10, transformer des nombres en autres nombres. Bien que peu compr-hensible pour le dbutant, un programme en C++ se veut le plus proche possible delHomme, tout en restant videmment accessible 11 la machine. Le C++ est un lan-gage trs complet, peut-tre mme trop. Il peut tre relativement proche de la machinesi ncessaire et au contraire de "haut niveau" quand il le faut. La largeur de son spectreest une des raisons de son succs. Cest aussi ce qui fait que son apprentissage completdemande un long travail et nous ne verrons ici quun partie restreinte du C++ !

2.1 Lordinateur

Pour savoir ce quun ordinateur sait vraiment faire, il faut commencer par son or-gane principal : le micro-processeur.

2.1.1 Le micro-processeur

Quel quil soit 12 et quelle que soit sa vitesse 13, un micro-processeur ne sait faire quedes choses relativement basiques. Sans tre exhaustif, retenons juste ceci :

Il sait excuter une suite ordonne dinstructions. Il possde un petit nombre de mmoires internes appeles registres. Il dialogue avec le monde extrieur via de la mmoire 14 en plus grande quantit

que ses registres. Cette mmoire contient, sous forme de nombres, les instructions excuter et les

donnes sur lesquelles travailler. Les instructions sont typiquement :

Lire ou crire un nombre dans un registre ou en mmoire. Effectuer des calculs simples : addition, multiplication, etc. Tester ou comparer des valeurs et dcider ventuellement de sauter une autre

partie de la suite dinstructions.Voici par exemple ce que doit faire le micro-processeur quand on lui demande

dexcuter "c=3a+2b;" en C++, o a,b,c sont trois variables entires :10. Un computer, quoi !11. Cette notion est videmment dpendante de notre savoir faire informatique linstant prsent.

Les premiers langages taient plus loigns de lHomme car plus proches de la machine qui tait alorsrudimentaire, et lon peut envisager que les futurs langages seront plus proches de lHomme.

12. Pentium ou autre13. Plus exactement la frquence laquelle il excute ses instructions. Aujourdhui lhorloge va envi-

ron 3GHz. (Mais attention : une instruction demande plus dun cycle dhorloge !)14. Aujourdhui, typiquement 1Go (giga-octets), soit 102410241024 mmoires de 8 bits (mmoires

pouvant stocker des nombres entre 0 et 255).

17

2.1. Lordinateur 2. Bonjour, Monde !

00415A61 mov eax,dword ptr [a] // mettre dans le registre eax// le contenu de ladresse o// est mmorise la variable a

00415A64 imul eax,eax,3 // effectuer eax=eax*300415A67 mov ecx,dword ptr [b] // idem mais b dans ecx00415A6A lea edx,[eax+ecx*2] // effectuer edx=eax+ecx*200415A6D mov dword ptr [c],edx // mettre le contenu du registre edx

// ladresse o est mmorise la// variable c

Sous lenvironnement Visual Studio que nous utiliserons, ce programme est dsi-gn comme du Code Machine. Le nombre au dbut de chaque ligne est une adresse.Nous allons en reparler. A part lui, le reste est relativement lisible pour lHomme (at-tention, cest moi qui ai ajout les remarques sur le cot droit !). Ceci parce quil sagitdun programme en langage assembleur, cest--dire un langage o chaque instruc-tion est vraiment une instruction du micro-processeur, mais o le nom de ces instruc-tions ainsi que leurs arguments sont explicites. En ralit, le micro-processeur ne com-prend pas lassembleur. Comprendre "mov eax,dword ptr [a]" lui demanderaitnon seulement de dcoder cette suite de symboles, mais aussi de savoir o est rangela variable a. Le vrai langage du micro-processeur est le langage machine, dans lequelles instructions sont des nombres. Voici ce que a donne pour notre "c=3a+2b;" :00415A61 8B 45 F800415A64 6B C0 0300415A67 8B 4D EC00415A6A 8D 14 4800415A6D 89 55 E0

A part encore une fois la colonne de gauche, chaque suite de nombres 15 correspondvidemment une instruction prcise. Cest tout de suite moins comprhensible 16 !Notons que chaque micro-processeur son jeu dinstructions ce qui veut dire que la tra-duction de c=3a+2b; en la suite de nombres 8B45F86BC0038B4DEC8D14488955E0est propre au Pentium que nous avons utilis pour notre exemple :

Une fois traduit en langage machine pour un micro-processeur donn, unprogramme C++ na de sens que pour ce micro-processeur.

Remarquons aussi que les concepteurs du Pentium ont dcid de crer une instructionspcifique pour calculer edx=eax+ecx2 en une seule fois car elle est trs frquente. Sion avait demand c=3a+3b;, notre programme serait devenu :00415A61 8B 45 F8 mov eax,dword ptr [a]00415A64 6B C0 03 imul eax,eax,300415A67 8B 4D EC mov ecx,dword ptr [b]00415A6A 6B C9 03 imul ecx,ecx,300415A6D 03 C1 add eax,ecx00415A6F 89 45 E0 mov dword ptr [c],eax

car "lea edx,[eax+ecx*3]" nexiste pas !Mais revenons nos nombres...

15. Nombres un peu bizarres, certes, puisquil contiennent des lettres. Patience, jeune Padawan ! Nousen reparlons aussi tout de suite !

16. Et pourtant, les informaticiens programmaient comme cela il ny a pas si longtemps. Ctait djtrs bien par rapport lpoque antrieure o il fallait programmer en base 2... et beaucoup moins bienque lorsquon a pu enfin programmer en assembleur !

18

2. Bonjour, Monde ! 2.1. Lordinateur

2.1.2 La mmoire

La mmoire interne du micro-processeur est gre comme des registres, un peucomme les variables du C++, mais en nombre prdfini. Pour stocker 17 la suite dins-tructions lui fournir, on utilise de la mmoire en quantit bien plus importante, d-signe en gnral par la mmoire de lordinateur. Il sagit des fameuses "barrettes" 18 demmoire que lon achte pour augmenter la capacit de sa machine et dont les prixfluctuent assez fortement par rapport au reste des composants dun ordinateur. Cettemmoire est dcoupe en octets. Un octet 19 correspond un nombre binaire de 8 bits 20,soit 28 = 256 valeurs possibles. Pour se reprer dans la mmoire, il nest pas ques-tion de donner des noms chaque octet. On numrote simplement les octets et onobtient ainsi des adresses mmoire. Les nombres 00415A61, etc. vus plus haut sont desadresses ! Au dbut, ces nombres taient crits en binaire, ce qui tait exactement ceque comprenait le micro-processeur. Cest devenu draisonnable quand la taille dela mmoire a dpass les quelques centaines doctets. Le contenu dun octet de m-moire tant lui aussi donn sous la forme dun nombre, on a opt pour un systmeadapt au fait que ces nombres sont sur 8 bits : plutt que dcrire les nombre en bi-naire, le choix de la base 16 permettait de reprsenter le contenu dun octet sur deuxchiffres (0,1,...,9,A,B,C,D,E,F). Le systme hexadcimal 21 tait adopt... Les conversionsde binaire hexadcimal sont trs simples, chaque chiffre hexadcimal valant pour unpaquet de 4 bits, alors quentre binaire et dcimal, cest moins immdiat. Il est aujour-dhui encore utilis quand on dsigne le contenu dun octet ou une adresse 22. Ainsi,notre fameux c=3a+2b; devient en mmoire :

adresse mmoire contenu reprsente00415A61 8B00415A62 45 mov eax,dword ptr [a]00415A63 F800415A64 6B00415A65 C0 imul eax,eax,3

... ...

17. Encore un anglicisme...18. Aujourdhui, typiquement une ou plusieurs barrettes pour un total de 1 ou 2Go, on la dj dit.

Souvenons nous avec une larme loeil des premiers PC qui avaient 640Ko (kilo-octet soit 1024 octets),voire pour les plus ags dentre nous des premiers ordinateurs personnels avec 4Ko, ou mme despremires cartes programmables avec 256 octets !

19. byte en anglais. Attention donc ne pas confondre byte et bit, surtout dans des abrviations comme512kb/s donnes pour le dbit dun accs internet... b=bit, B=byte=8 bits

20. Le coin des collgiens : en binaire, ou base 2, on compte avec deux chiffres au lieu de dix dha-bitude (cest dire en dcimal ou base 10). Cela donne : 0, 1, 10, 11, 100, 101, 110, 111, ... Ainsi, 111 enbinaire vaut 7 . Chaque chiffre sappelle un bit. On voit facilement quavec un chiffre on compte de 0 1 soit deux nombres possibles ; avec deux chiffres, de 0 3, soit 4 = 2 2 nombres ; avec 3 chiffres, de0 7, soit 8 = 2 2 2 nombres. Bref avec n bits, on peut coder 2n (2 multipli par lui-mme n fois)nombres. Je me souviens avoir appris la base 2 en grande section de maternelle avec des cubes en bois !trange programme scolaire. Et je ne dis pas a pour me trouver une excuse dtre devenu informaticien.Quoique...

21. Coin des collgiens (suite) : en base 16, ou hexadcimal, on compte avec 16 chiffres. Il faut inven-ter des chiffres au del de 9 et on prend A,B,C,D,E,F. Quand on compte, cela donne : 0, 1, 2, ..., 9, A, B,C, D, E, F, 10, 11, 12, 13, ..., 19, 1A, 1B, 1C, ... Ainsi 1F en hexadcimal vaut 31. Avec 1 chiffre, on comptede 0 15 soit 16 nombres possibles ; avec 2 chiffres, de 0 255 soit 256 = 16 16 nombres possibles, etc.Un octet peut scrire avec 8 bits en binaire, ou 2 nombres en hexadcimal et va de 0 255, ou 11111111en binaire, ou FF en hexadcimal.

22. Dans ce cas, sur plus de 2 chiffres : 8 pour les processeurs 32 bits, 16 pour les processeurs 64 bits.

19

2.1. Lordinateur 2. Bonjour, Monde !

La mmoire ne sert pas uniquement stocker la suite dinstructions excuter maisaussi toutes les variables et donnes du programme, les registres du micro-processeurtant insuffisants. Ainsi nos variables a,b,c sont stockes quelque part en mmoire surun nombre doctets suffisant 23 pour reprsenter des nombres entiers (ici 4 octets) etdans un endroit dcid par le C++, de tel sorte que linstruction 8B45F8 aille bienchercher la variable a ! Cest un travail pnible, que le C++ fait pour nous et que lesprogrammeurs faisaient autrefois la main 24. Bref, on a en plus 25 :

adresse mmoire contenu reprsente... ...

00500000 a100500001 a2 a00500002 a300500003 a400500004 b100500005 b2 b00500006 b300500007 b4

... ...

o les octets a1, ..., a4 combins donnent lentier a sur 32 bits. Certains processeurs (ditsbig-endian) 26 dcident a = a1a2a3a4, dautres (little-endian) 27 que a = a4a3a2a1. Celasignifie que :

Tout comme pour les instructions, un nombre stock par un micro-processeur dans un fichier peut ne pas tre comprhensible par un autremicro-processeur qui relit le fichier !

2.1.3 Autres Composants

Micro-processeur et mmoire : nous avons vu le principal. Compltons le tableauavec quelques autres lments importants de lordinateur.

23. Les variables ayant plus de 256 valeurs possibles sont forcment stockes sur plusieurs octets.Ainsi, avec 4 octets on peut compter en binaire sur 4 8 = 32 bits, soit 232 valeurs possibles (plus de 4milliards).

24. Ce qui tait le plus pnible ntait pas de dcider o il fallait ranger les variables en mmoire, maisdajuster les instructions en consquence. Si on se trompait, on risquait dcrire au mauvais endroit dela mmoire. Au mieux, cela effaait une autre variable ce comportement est encore possible de nosjours au pire, cela effaait des instructions et le programme pouvait faire de "grosses btises" ceciest aujourdhui impossible sous Windows ou Linux, et ne concerne plus que certains systmes.

25. Nous faisons ici un horrible mensonge des fins simplificatrices. Dans notre cas, les variablestaient des variables locales la fonction main() donc stockes dans la pile. Elles ne sont pas uneadresse mmoire dfinie lavance de manire absolue mais une adresse relative lemplacemento la fonction rangera ses variables locales en fonction de ce que le programme aura fait avant. Celaexplique la simplicit de linstruction mov eax,dword ptr [a] dans notre cas. Nous verrons toutcela plus tard.

26. Comme les PowerPC des vieux Macs27. Comme les processeurs Intel et AMD

20

2. Bonjour, Monde ! 2.1. Lordinateur

Types de mmoire

La mmoire dont nous parlions jusquici est de la mmoire vive ou RAM. Elle estrapide 28 mais a la mauvaise ide de seffacer quand on teint lordinateur. Il faut doncaussi de la mmoire morte ou ROM, cest--dire de la mmoire conservant ses donnesquand lordinateur est teint mais qui en contre-partie ne peut tre modifie 29. Cettemmoire contient en gnral le minimum pour que lordinateur dmarre et excuteune tche prdfinie. Initialement, on y stockait les instructions ncessaires pour que leprogrammeur puisse remplir ensuite la RAM avec les instructions de son programme.Il fallait retaper le programme chaque fois 30 ! On a donc rapidement eu recours desmoyens de stockage pour sauver programmes et donnes lextinction de lordinateur. Ilsuffisait alors de mettre en ROM le ncessaire pour grer ces moyens de stockages.

Moyens de stockage

Certains permettent de lire des donnes, dautres den crire, dautres les deux la fois. Certains ne dlivrent les donnes que dans lordre, de manire squentielle,dautres, dans lordre que lon veut, de manire alatoire. Ils sont en gnral bien pluslents que la mmoire et cest srement ce quil faut surtout retenir ! On recopie donc enRAM la partie des moyens de stockage sur laquelle on travaille.

Faire travailler le micro-processeur avec le disque dur est BEAUCOUP pluslent quavec la mmoire (1000 fois plus lent en temps daccs, 100 fois plusen dbit) a

a. Rajoutez un facteur 50 supplmentaire entre la mmoire et la mmoire cache du proces-seur !

Au dbut, les moyens de stockages taient mcaniques : cartes ou bandes perfo-res. Puis ils devinrent magntiques : mini-cassettes 31, disquettes 32, disques durs 33 oubandes magntiques. Aujourdhui, on peut rajouter les CD, DVD, les cartes mmoire,les "cls USB", etc, etc.

Priphriques

On appelle encore priphriques diffrents appareils relis lordinateur : clavier,souris, cran, imprimante, modem, scanner, etc. Ils taient initialement l pour servirdinterface avec lHomme, comme des entres et des sorties entre le micro-processeuret la ralit. Maintenant, il est difficile de voir encore les choses de cette faon. Ainsi

28. Moins que les registres, ou mme que le cache mmoire du processeur, dont nous ne parlerons pasici.

29. Il est pnible quune ROM ne puisse tre modifie. Alors, une poque, on utilisait des mmoiresmodifiables malgr tout, mais avec du matriel spcialis (EPROMS). Maintenant, on a souvent recours de la mmoire pouvant se modifier de faon logicielle (mmoire "flashable") ou, pour de trs petitesquantits de donnes, une mmoire consommant peu (CMOS) et complte par une petite pile. Dansun PC, la mmoire qui sert dmarrer sappelle le BIOS. Il est flashable et ses paramtres de rglagesont en CMOS. Attention lusure de la pile !

30. A chaque fois quon allumait lordinateur mais aussi chaque fois que le programme plantait etseffaait lui-mme, cest--dire la plupart du temps !

31. Trs lent et trs peu fiable, mais le quotidien des ordinateurs personnels.32. Le luxe. Un lecteur de 40Ko cotait 5000F !33. Les premiers taient de vritables moteurs de voiture, rservs aux importants centres de calcul.

21

2.2. Systme dexploitation 2. Bonjour, Monde !

les cartes graphiques, qui pouvaient tre considres comme un priphrique allantavec lcran, sont-elles devenues une partie essentielle de lordinateur, vritables puis-sances de calcul, tel point que certains programmeur les utilisent pour faire des cal-culs sans mme afficher quoi que ce soit. Plus encore, cest lordinateur qui est parfoisjuste considr comme maillon entre diffrents appareils. Qui appellerait priphriqueun camscope quon relie un ordinateur pour envoyer des vidos sur internet ou lestransfrer sur un DVD ? Ce serait presque lordinateur qui serait un priphrique ducamscope !

2.2 Systme dexploitation

Notre vision jusquici est donc la suivante :

1. Le processeur dmarre avec les instructions prsentes en ROM.

2. Ces instructions lui permettent de lire dautres instructions prsentes sur le disquedur et quil recopie en RAM.

3. Il excute les instructions en question pour il lire des donnes (entres) prsenteselles-aussi sur le disque dur et gnrer de nouvelles donnes (sorties). A moinsque les entres ou les sorties ne soient changes via les priphriques.

Assez vite, ce principe a volu :

1. Le contenu du disque dur a t organis en fichiers. Certains fichiers reprsen-taient des donnes 34, dautres des programmes 35, dautres encore contenaienteux-mmes des fichiers 36.

2. Les processeurs devenant plus rapides et les capacits du disque dur plus impor-tantes, on a eu envie de grer plusieurs programmes et den excuter plusieurs :lun aprs lautre, puis plusieurs en mme temps (multi-tches), puis pour plu-sieurs utilisateurs en mme temps (multi-utilisateurs) 37, enfin avec plusieurs pro-cesseurs par machine.

Pour grer tout cela, sest dgag le concept de systme dexploitation 38. Windows, Unix(dont linux) et MAC/OS sont les plus rpandus. Le systme dexploitation est aujour-dhui responsable de grer les fichiers, les interfaces avec les priphriques ou les uti-lisateurs 39, mais son rle le plus dlicat est de grer les programmes (ou tches ouprocess) en train de sexcuter. Il doit pour cela essentiellement faire face deux pro-blmes 40 :

34. Les plus courantes taient les textes, o chaque octet reprsentait un caractre. Ctait le clbrecode ASCII (65 pour A, 66 pour B, etc.). A lre du multimdia, les formats sont aujourdhui nombreux,concurrents, et plus ou moins normaliss.

35. On parle de fichier excutable...36. Les rpertoires.37. Aujourdhui, cest pire. Un programme est souvent lui mme en plusieurs parties sexcutant en

mme temps (les threads). Quant au processeur, il excute en permanence plusieurs instructions en mmetemps (on dit quil est super-scalaire) !

38. Operating System39. Esprons quun jour les utilisateurs ne seront pas eux-aussi des priphriques !40. Les processeurs ont videmment volu pour aider le systme dexploitation faire cela

efficacement.

22

2. Bonjour, Monde ! 2.3. La Compilation

1. Faire travailler le processeur successivement par petites tranches sur les diff-rents programmes. Il sagit de donner la main de manire intelligente et qui-table, mais aussi de replacer un process interrompu dans la situation quil avaitquitte lors de son interruption.

2. Grer la mmoire ddie chaque process. En pratique, une partie ajustable dela mmoire est rserve chaque process. La mmoire dun process devient m-moire virtuelle : si un process est dplac un autre endroit de la mmoire physique(la RAM), il ne sen rend pas compte. On en profite mme pour mettre tempo-rairement hors RAM (donc sur disque dur) un process en veille. On peut aussiutiliser le disque dur pour quun process utilise plus de mmoire que la mmoirephysique : mais attention, le disque tant trs lent, ce process risque de devenirlui aussi trs lent.

Lorsquun process besoin de trop de mmoire, il utilise, sans prve-nir, le disque dur la place de la mmoire et peut devenir trs lent.On dit quil swappe (ou pagine). Seule sa lenteur (et le bruit du disquedur !) permet en gnral de sen rendre compte (on peut alors sen as-surer avec le gestionnaire de tche du systme).

Autre progrs : on gre maintenant la mmoire virtuelle de faon sparer lesprocess entre eux et, au sein dun mme process, la mmoire contenant les ins-tructions de celle contenant les donnes. Il est rigoureusement impossible quunprocess bugg puisse modifier ses instructions ou la mmoire dun autre processen crivant un mauvais endroit de la mmoire 41.

Avec larrive des systmes dexploitation, les fichiers excutables ont du sadapterpour de nombreuse raisons de gestion et de partage de la mmoire. En pratique, unprogramme excutable linux ne tournera pas sous Windows et rciproquement, mmesils contiennent tous les deux des instructions pour le mme processeur.

Un fichier excutable est spcifique, non seulement un processeur donn,mais aussi un systme dexploitation donn.

Au mieux, tout comme les versions successives dune famille de processeur essaientde continuer comprendre les instructions de leurs prdcesseurs, tout comme lesversions successives dun logiciel essaient de pouvoir lire les donnes produites avecles versions prcdentes, les diffrentes versions dun systme dexploitation essaientde pouvoir excuter les programmes faits pour les versions prcdentes. Cest la com-patibilit ascendante, que lon paye souvent au prix dune complexit et dune lenteuraccrues.

2.3 La Compilation

Tout en essayant de comprendre ce qui se passe en dessous pour en tirer des infor-mations utiles comme la gestion de la mmoire, nous avons entrevu que transformerun programme C++ en un fichier excutable est un travail difficile mais utile. Cer-tains logiciels disposant dun langage de programmation comme Maple ou Scilab netransforment pas leurs programmes en langage machine. Le travail de traduction est

41. Il se contente de modifier anarchiquement ses donnes, ce qui est dj pas mal !

23

2.4. Lenvironnement de programmation 2. Bonjour, Monde !

fait lexcution du programme qui est alors analys au fur et mesure 42 : on parlealors de langage interprt. Lexcution alors est videmment trs lente. Dautres lan-gages, comme Java, dcident de rsoudre les problmes de portabilit, cest--dire dedpendance au processeur et au systme, en plaant une couche intermdiaire entrele processeur et le programme : la machine virtuelle. Cette machine, videmment critepour un processeur et un systme donns, peut excuter des programmes dans unlangage machine virtuel 43, le "byte code". Un programme Java est alors traduit en sonquivalent dans ce langage machine. Le rsultat peut tre excut sur nimporte quellemachine virtuelle Java. La contrepartie de cette portabilit est videmment une pertedefficacit.

La traduction en code natif ou en byte code dun programme sappelle la compila-tion 44. Un langage compil est alors opposer un langage interprt. Dans le cas du C++et de la plupart des langages compils (Fortran, C, etc), la compilation se fait vers ducode natif. On transforme un fichier source, le programme C++, en un fichier objet, suitedinstructions en langage machine.

Cependant, le fichier objet ne se suffit pas lui-mme. Des instructions supplmen-taires sont ncessaires pour former un fichier excutable complet :

de quoi lancer le main() ! Plus prcisment, tout ce que le process doit faire avantet aprs lexcution de main().

des fonctions ou variables faisant partie du langage et que le programmeur utilisesans les reprogrammer lui-mme, comme cout, cout|min()|, etc. Lensemble deces instructions constitue ce quon appelle une bibliothque 45.

des fonctions ou variables programmes par le programmeur lui-mme dansdautres fichiers source compils par ailleurs en dautres fichiers objet, mais quilveut utiliser dans son programme actuel.

La synthse de ces fichiers en un fichier excutable sappelle ldition des liens. Le pro-gramme qui ralise cette opration est plus souvent appel linker quditeur de liens...

En rsum, la production du fichier excutable se fait de la faon suivante :

1. Compilation : fichier source fichier objet.2. Link : fichier objet + autres fichiers objets + bibliothque standard ou

autres fichier excutable.

2.4 Lenvironnement de programmation

Lenvironnement de programmation est le logiciel permettant de programmer. Dansnotre cas il sagit de Visual Studio Express. Dans dautres cas, il peut simplement sagirdun ensemble de programmes. Un environnement contient au minimum un diteurpour crer les fichiers sources, un compilateur/linker pour crer les excutables, un de-

42. mme sil est parfois pr-trait pour acclrer lexcution.43. Par opposition, le "vrai" langage machine du processeur est alors appel code natif.44. Les principes de la compilation sont une des matires de base de linformatique, traditionnelle et

trs formatrice. Quand on sait programmer un compilateur, on sait tout programmer (videmment, uncompilateur est un programme ! On le programme avec le compilateur prcdent ! Mme chose pour lessystmes dexploitation...). Elle ncessite un cours part entire et nous nen parlerons pas ici !

45. Une bibliothque est en fait un ensemble de fichiers objets pr-existants regroups en un seul fi-chier. Il peut sagir de la bibliothque des fonctions faisant partie de C++, appele bibliothque standard,mais aussi dune bibliothque supplmentaire fournie par un tiers.

24

2. Bonjour, Monde ! 2.4. Lenvironnement de programmation

buggeur pour traquer les erreurs de programmation, et un gestionnaire de projet pourgrer les diffrents fichiers sources et excutables avec lesquels on travaille.

Nous reportons ici le lecteur au texte du premier TP. En plus de quelques notionsrudimentaires de C++ que nous verrons au chapitre suivant, quelques informationssupplmentaires sont utiles pour le suivre.

2.4.1 Noms de fichiers

Sous Windows, lextension (le suffixe) sert se reprer dans les types de fichier : Un fichier source C++ se terminera par .cpp 46. Un fichier objet sera en .obj Un fichier excutable en .exe

Nous verrons aussi plus loin dans le cours : Les "en-tte" C++ ou headers servant tre inclus dans un fichier source : fichiers.h

Les bibliothques (ensembles de fichiers objets archivs en un seul fichier) : fichier.lib ou .dll

2.4.2 Debuggeur

Lorsquun programme ne fait pas ce quil faut, on peut essayer de comprendre cequi ne va pas en truffant son source dinstructions pour imprimer la valeur de certainesdonnes ou simplement pour suivre son droulement. Ca nest videmment pas trspratique. Il est mieux de pouvoir suivre son droulement instruction par instruction etdafficher la demande la valeur des variables. Cest le rle du debuggeur 47.

Lorsquun langage est interprt, il est relativement simple de le faire sexcute pas pas car cest le langage lui-mme qui excute le programme. Dans le cas dun langagecompil, cest le micro-processeur qui excute le programme et on ne peut pas larrter chaque instruction ! Il faut alors mettre en place des points darrt en modifiant tem-porairement le code machine du programme pour que le processeur sarrte lorsquilatteint linstruction correspondant la ligne de source debugger. Si cest compliqu mettre au point, cest trs simple utiliser, surtout dans un environnement de pro-grammation graphique.

Nous verrons au fur et mesure des TP comment le debuggeur peut aussi inspecterles appels de fonctions, espionner la modification dune variable, etc.

2.4.3 TP

Vous devriez maintenant aller faire le TP en annexe A.1. Si la pratique est essen-tielle, en retenir quelque chose est indispensable ! Vous y trouverez aussi commentinstaller Visual sur votre ordinateur (lien http://imagine.enpc.fr/~monasse/Imagine++ mentionn la fin du TP). Voici donc ce quil faut retenir du TP :

46. Un fichier en .c sera considr comme du C. Diffrence avec linux : un fichier en .C sera aussitrait comme du C et non comme du C++ !

47. Dbogueur en franais !

25

2.4. Lenvironnement de programmation 2. Bonjour, Monde !

1. Toujours travailler en local et sauvegarder sur le disque partag, clUSB, etc.

2. Type de projet utilis : Imagine++ Project

3. Nettoyer ses solutions quand on quitte.

4. Lancer directement une excution sauve et gnre automatiquement.Attention toutefois de ne pas confirmer lexcution si la gnrationsest mal passe.

5. Double-cliquer sur un message derreur positionne lditeur sur ler-reur.

6. Toujours bien indenter.

7. Ne pas laisser passer des warnings !

8. Savoir utiliser le debuggeur.

9. Touches utiles :F7 = = Build

F5 = = Start debugging

F10 = = Step over

F11 = = Step inside

Ctrl+K,Ctrl+F = Indent selection

Nous en savons maintenant assez pour apprendre un peu de C++...

26

3. Premiers programmes

Chapitre 3

Premiers programmes

Pars exprimenter au fur et mesure avec notre environnement de programmation, il esttemps dapprendre les premiers rudiments du C++. Nous allons commencer par programmernimporte comment... puis nous ajouterons un minimum dorganisation en apprenant fairedes fonctions.

On organise souvent un manuel de programmation de faon logique par rapportau langage, en diffrents points successifs : les expressions, les fonctions, les variables,les instructions, etc. Le rsultat est indigeste car il faut alors tre exhaustif sur chaquepoint. Nous allons plutt ici essayer de voir les choses telles quelles se prsententquand on apprend : progressivement et sur un peu tous les sujets la fois 1 ! Ainsi, cenest que dans un autre chapitre que nous verrons la faon dont les fonctions mmo-risent leurs variables dans la "pile".

3.1 Tout dans le main() !

Rien dans les mains, rien dans les poches... mais tout dans le main(). Voici commentun dbutant programme 2.

Cest dj une tape importante que de programmer au kilomtre, en plaantlintgralit du programme dans la fonction main(). Lessentiel est avanttout de faire un programme qui marche !

3.1.1 Variables

Types

Les variables sont des mmoires dans lesquelles sont stockes des valeurs (ou don-nes). Une donne ne pouvant tre stocke nimporte comment, il faut chaque fois d-cider de la place prise en mmoire (nombre doctets) et du format, cest--dire de la faondont les octets utiliss vont reprsenter les valeurs prises par la variable. Nous avonsdj rencontr les int qui sont le plus souvent aujourdhui stocks sur quatre octets,

1. La contre-partie de cette prsentation est que ce polycopi, sil est fait pour tre lu dans lordre, estpeut-tre moins adapt servir de manuel de rfrence. .

2. Et bien des lves, ds que le professeur nest plus derrire !

3.1. Tout dans le main() ! 3. Premiers programmes

soit 32 bits, et pouvant prendre 232 = 4294967296 valeurs possibles 3. Par convention,les int stockent les nombres entiers relatifs 4, avec autant de nombres ngatifs que denombres positifs 5, soit, dans le cas de 32 bits 6, de 2147483648 2147483647 suivantune certaine correspondance avec le binaire 7.

Dire quune variable est un int, cest prciser son type. Certains langages nont pasla notion de type ou essaient de deviner les types des variables. En C++, cest initia-lement pour prciser la mmoire et le format des variables quelles sont types. Nousverrons que le compilateur se livre un certain nombre de vrifications de cohrencede type entre les diffrentes parties dun programme. Ces vrifications, pourtant bienpratiques, ntaient pas faites dans les premires versions du C, petit frre du C++, caravant tout, rptons-le :

Prciser un type, cest prciser la place mmoire et le format dune variable.Le compilateur, sil pourra mettre cette information profit pour dtecterdes erreurs de programmation, en a avant tout besoin pour traduire le sourceC++ en langage machine.

Dfinition, Affectation, Initialisation, Constantes

Avant de voir dautres types de variables, regardons sur un exemple la syntaxe utiliser :

1 i n t i ; / / D f i n i t i o n2 i =2; / / A f f e c t a t i o n3 cout

3. Premiers programmes 3.1. Tout dans le main() !

Les lignes 1 et 2 dfinissent une variable nomme i 8 de type int puis affecte2 cette variable. La reprsentation binaire de 2 est donc stocke en mmoirel o le compilateur dcide de placer i. Ce qui suit le "double slash" ( // ) est uneremarque : le compilateur ignore toute la fin de la ligne, ce qui permet de mettredes commentaires aidant la comprhension du programme.

La ligne 3 affiche la valeur de i puis un espace (sans aller la ligne) Les lignes 4, 5 et 6 dfinissent un int nomm j , recopie la valeur de i, soit 2,

dans j , puis mmorise 1 dans i. Notez bien que i et j sont bien deux variablesdiffrentes : i passe 1 mais j reste 2 !

La ligne 8 nous montre comment dfinir simultanment plusieurs variables dumme type.

La ligne 9 nous apprend que lon peut affecter des variables simultanment unemme valeur.

A la ligne 12, des variables sont dfinies et affectes en mme temps. En fait,on parle plutt de variables initialises : elles prennent une valeur initiale enmme temps quelles sont dfinies. Notez que, pour des raisons defficacit, lesvariables ne sont pas initialises par dfaut : tant quon ne leur a pas affect unevaleur et si elles nont pas t initialises, elles valent nimporte quoi 9 !

Attention toutefois, il est inutile de tenter une initialisation simultane. Cest in-terdit. La ligne 14 provoque une erreur.

Enfin, on peut rajouter const devant le type dune variable : celle-ci devient alorsconstante et on ne peut modifier son contenu. La ligne 15 dfinit une telle variableet la ligne 16 est une erreur.

En rsum, une fois les lignes 14 et 16 supprimes, ce (passionnant !) programme af-fiche 10 :

2 1 2 3 3 4 5 5 2147483647

Les noms de variable sont composs uniquement des caractres a z (et majus-cules), chiffres et underscore _ (vitez celui-ci, il nest pas trs esthtique), mais nepeuvent pas commencer par un chiffre. Nutilisez pas de caractres accentus, car celapose des problmes de portabilit.

Porte

Dans lexemple prcdent, les variables ont t dfinies au fur et mesure des be-soins. Ce nest pas une vidence. Par exemple, le C ne permettait de dfinir les variablesque toutes dun coup au dbut du main(). En C++, on peut dfinir les variables en coursde route, ce qui permet davantage de clart. Mais attention :

8. Le nom dune variable est aussi appel identificateur. Les messages derreur du compilateur utilise-ront plutt ce vocabulaire !

9. Ainsi, un entier ne vaut pas 0 lorsquil est cr et les octets o il est mmoris gardent la valeur quilavaient avant dtre rquisitionns pour stocker lentier en question. Cest une mauvaise ide dutiliserla valeur dune variable qui vaut nimporte quoi et un compilateur mettra gnralement un warning sion utilise une variable avant de lui fournir une valeur !

10. du moins sur une machine 32 bits, cf. remarque prcdente sur INT_MAX

29


les variables "nexistent" (et ne sont donc utilisables) qu partir de la ligneo elles sont dfinies. Elles ont une dure de vie limite et meurent ds quelon sort du bloc limit par des accolades auquel elles appartiennent a. Cestce quon appelle la porte dune variable.

a. Cest un peu plus compliqu pour les variables globales. Nous verrons a aussi...

Ainsi, en prenant un peu davance sur la syntaxe des tests, que nous allons voir toutde suite, le programme suivant provoque des erreurs de porte aux lignes 2 et 8 :

i n t i ;i = j ; / / Er r eur : j n e x i s t e pas e n c o r e !i n t j =2 ;i f ( j >1) {

i n t k =3;j =k ;

}i =k ; / / Er r eur : k n e x i s t e p l u s .

Autres types

Nous verrons les diffrents types au fur et mesure. Voici malgr tout les pluscourants :

i n t i =3 ; / / E n t i e r r e l a t i fdouble x = 1 2 . 3 ; / / Nombre r e l ( d o u b l e p r c i s i o n )char c= A ; / / C a r a c t r es t r i n g s=" hop " ; / / Chane de c a r a c t r e sbool t =true ; / / B o o l e n ( v r a i ou f aux )

Les nombres rels sont en gnral approchs par des variables de type double ("doubleprcision", ici sur 8 octets). Les caractres sont reprsents par un entier sur un oc-tet (sur certaines machines de -128 127, sur dautres de 0 255), la correspondancecaractre/entier tant celle du code ASCII (65 pour A, 66 pour B, etc.), quil nest heu-reusement pas besoin de connatre puisque la syntaxe A entre simples guillemets esttraduite en 65 par le compilateur, etc. Les doubles guillemets sont eux rservs aux"chanes" de caractres 11. Enfin, les boolens sont des variables qui valent vrai (true)ou faux (false).

Voici, pour information, quelques types supplmentaires :

f l o a t y =1.2 f ; / / Nombre r e l s i m p l e p r c i s i o nunsigned i n t j =4 ; / / E n t i e r n a t u r e lsigned char d=128; / / E n t i e r r e l a t i f un o c t e tunsigned char d=254; / / E n t i e r n a t u r e l un o c t e tcomplex z ( 2 , 3 ) ; / / Nombre compl exe

o lon trouve : les float , nombres rels moins prcis mais plus courts que les double, ici sur

4 octets (Les curieux pourront explorer la documentation de Visual et voir que

11. Attention, lutilisation des string ncessite un #include au dbut du programme.

30


les float valent au plus FLT\_MAX (ici, environ 3.4e+38 12) et que leur valeur laplus petite strictement positive est FLT\_MIN (ici, environ 1.2e38), de mmeque pour les double les constantes DBL\_MAX et DBL\_MIN valent ici environ1.8e+308 et 2.2e308),

les unsigned int, entiers positifs utiliss pour aller plus loin que les int dans lespositifs (de 0 UINT_MAX, soit 4294967295 dans notre cas),

les unsigned char, qui vont de 0 255, les signed char, qui vont de -128 127, et enfin les nombres complexes 13.

3.1.2 Tests

Tests simples

Les tests servent excuter telle ou telle instruction en fonction de la valeur duneou de plusieurs variables. Ils sont toujours entre parenthses. Le et scrit &&, leou ||, la ngation !, lgalit ==, la non-galit !=, et les ingalits >, >=, < et


Enfin, une dernire chose trs importante : penser utiliser == et non = sous peinedavoir des surprises 14. Cest peut-tre lerreur la plus frquente chez les dbutants.Elle est heureusement signale aujourdhui par un warning...

Attention : utiliser if ( i==3) ... et non if ( i=3) ... !

Le "switch"

On a parfois besoin de faire telle ou telle chose en fonction des valeurs possiblesdune variable. On utilise alors souvent linstruction switch pour des raisons de clartde prsentation. Chaque cas possible pour les valeurs de la variable est prcis aveccase et doit se terminer par break 15. Plusieurs case peuvent tre utiliss pour prciserun cas multiple. Enfin, le mot cl default, placer en dernier, correspond aux cas nonprciss. Le programme suivant 16 ragit aux touches tapes au clavier et utilise unswitch pour afficher des commentaires passionnants !

1 # inc lude 2 using namespace std ;3 # include / / Non s t a n d a r d !45 i n t main ( )6 {7 bool f i n i = f a l s e ;8 char c ;9 do {

10 c=_getch ( ) ; / / Non s t a n d a r d !11 switch ( c ) {12 case a :13 cout


26 d e f a u l t :27 cout


11 / / c e t e s t e s t v r a i12 cout


3.1.4 Rcrations

Nous pouvons dj faire de nombreux programmes. Par exemple, jouer au justeprix. Le programme choisit le prix, et lutilisateur devine :

1 # inc lude 2 # include < c s t d l i b >3 using namespace std ;45 i n t main ( )6 {7 i n t n=rand ( )%100 ; / / nombre d e v i n e r e n t r e 0 e t 998 i n t i ;9 do {

10 cout > i ;12 i f ( i >n )13 cout


16 while ( r != = && r != + && r != ) ;17 i f ( r== = )18 trouve=true ;19 e l s e i f ( r== )20 b=c1; / / C e s t moins , on e s s a i e e n t r e a e t c121 e l s e22 a=c +1; / / C e s t p lus , on e s s a i e e n t r e c +1 e t b23 } while ( ! trouve && ( a

3. Premiers programmes 3.2. Fonctions

FIGURE 3.1 Traits et cercles au hasard...

fonctions appeles dans ce petit programme (openWindow, fillRect et milliSleep) sontaussi fournies par Imagine.

3.2 Fonctions

Lorsquon met tout dans le main() on ralise trs vite que lon fait souvent descopier/coller de bouts de programmes. Si des lignes de programmes commencent seressembler, cest quon est vraisemblablement devant loccasion de faire des fonctions.On le fait pour des raisons de clart, mais aussi pour faire des conomies de frappe auclavier !

Il faut regrouper les passages identiques en fonctions : pour obtenir un programme clair... et pour moins se fatiguer !Attention bien comprendre quand faire une fonction et ne pas simple-ment dcouper un programme en petits morceaux sans aucune logique a.

a. ou juste pour faire plaisir au professeur. Mal dcouper un programme est la meilleurefaon de ne plus avoir envie de le faire la fois suivante. Encore une fois, le bon critre est icique la bonne solution est gnralement la moins fatiguante.

En fait, pouvoir rutiliser le travail dj fait est le fil conducteur dune bonne program-mation. Pour linstant, nous nous contentons, grce aux fonctions, de rutiliser ce quenous venons de taper quelques lignes plus haut. Plus tard, nous aurons envie de ruti-liser ce qui aura t fait dans dautres programmes, ou longtemps auparavant, ou dansles programmes dautres personnes, ... et nous verrons alors comment faire.

Prenons le programme suivant, qui dessine des traits et des cercles au hasard, etdont la figure 3.1 montre un rsultat :

1 # inc lude 2 using namespace Imagine ;3 # include < c s t d l i b >4 using namespace std ;

37

3.2. Fonctions 3. Premiers programmes

56 i n t main ( )7 {8 openWindow ( 3 0 0 , 2 0 0 ) ;9 f o r ( i n t i =0 ; i


openWindow (w, h ) ;f o r ( i n t i =0 ; i


2. Une fonction peut comporter plusieurs instructions return 24. Cela permet de sor-tir quand on en a envie, ce qui est bien plus clair et plus proche de notre faon depenser :

i n t s igne_avec_un_seul_return ( double x ) {i n t s ;i f ( x==0)

s =0;e l s e i f ( x


i f ( ! ca_decroche )re turn ;

p a r l e r ( ) ;raccro cher ( ) ;

}

3.2.2 Paramtres

Nous navons vu que des fonctions un seul paramtre. Voici comment faire pouren passer plusieurs ou nen passer aucun :

/ / Nombre e n t r e a e t bi n t hasard2 ( i n t a , i n t b ){

re turn a +( rand ()%( ba + 1 ) ) ;}

/ / Nombre e n t r e 0 e t 1double hasard3 ( ){

re turn rand ( ) / double (RAND_MAX) ;}. . .

i n t a=hasard2 ( 1 , 1 0 ) ;double x=hasard3 ( ) ;

. . .

Attention bien utiliser x=hasard3() et non simplement x=hasard3 pour appeler cettefonction sans paramtre. Ce simple programme est aussi loccasion de parler duneerreur trs frquente : la division de deux nombres entiers donne un nombre entier !Ainsi, crire double x=1/3; est une erreur car le C++ commence par calculer 1/3 avecdes entiers, ce qui donne 0, puis convertit 0 en double pour le ranger dans x. Il ne saitpas au moment de calculer 1/3 quon va mettre le rsultat dans un double ! Il faut alors faireen sorte que le 1 ou le 3 soit une double et crire double x=1.0/3; ou double x=1/3.0;.Si, comme dans notre cas, on a affaire deux variables de type int, il suffit de convertirune de ces variables en double avec la syntaxe double (...) que nous verrons plus tard.

1. Fonction sans paramtre : x=hop(); et non x=hop;.

2. Division entire : double x=1.0/3; et non double x=1/3; double x=double(i)/j; et non double x=i/j;, ni mme

double x=double(i/j); a

a. Cette conversion en double arrive trop tard !

3.2.3 Passage par rfrence

Lorsquune fonction modifie la valeur dun de ses paramtres, et si ce paramtretait une variable dans la fonction appelante, alors la variable en question nest pasmodifie. Plus clairement, le programme suivant choue :

41


void t r i p l e ( i n t x ) {x=x 3 ;

}. . .

i n t a =2;t r i p l e ( a ) ;cout


void un_point ( i n t& x , i n t& y ) {x = . . . ;y = . . . ;

}. . .

i n t a , b ;un_point ( a , b ) ;

. . .

Ainsi, notre programme de dessin alatoire deviendrait :

1 # include 2 using namespace Imagine ;3 # include < c s t d l i b >4 using namespace std ;56 / / Nombre e n t r e 0 e t n17 i n t hasard ( i n t n )8 {9 re turn rand ()%n ;

10 }1112 Color une_couleur ( ) {13 re turn Color ( hasard ( 2 5 6 ) , hasard ( 2 5 6 ) , hasard ( 2 5 6 ) ) ;14 }1516 void un_point ( i n t w, i n t h , i n t& x , i n t& y ) {17 x=hasard (w) ;18 y=hasard ( h ) ;19 }2021 i n t main ( )22 {23 const i n t w=300 ,h=200;24 openWindow (w, h ) ;25 f o r ( i n t i =0 ; i

3.2. Fonctions 3. Premi

Documents

392 Programmer