Td corrigé introduction a la programmation orientee objet et au langage ... - Free pdf

introduction a la programmation orientee objet et au langage ... - Free

Les formateurs seront invités à déposer/proposer un sujet d'examen. .... Un programme en langage C est constitué des six groupes de composants ...... empile() : permet d'empiler un entier dans une pile existante ;; depile() : dépile le dernier ...




part of the document



'abstraction des données  PAGEREF _Toc6120950 \h 16
1.4.3 La programmation orientée objet  PAGEREF _Toc6120951 \h 17
1.4.4 Le principe de partage  PAGEREF _Toc6120952 \h 17
1.4.5 Les invariants  PAGEREF _Toc6120953 \h 17
1.5 La chaîne de développement et ses outils  PAGEREF _Toc6120954 \h 17
1.5.1 Généralités sur les outils de développement  PAGEREF _Toc6120955 \h 17
1.5.2 Editeurs de textes  PAGEREF _Toc6120956 \h 18
1.5.3 Mise en forme  PAGEREF _Toc6120957 \h 18
1.5.4 Analyseur syntaxique  PAGEREF _Toc6120958 \h 18
1.5.5 Compilation et édition de lien  PAGEREF _Toc6120959 \h 18
1.5.6 Langage machine  PAGEREF _Toc6120960 \h 19
1.5.7 Outils de recherche d'erreurs  PAGEREF _Toc6120961 \h 19
1.5.8 Outils de génie logiciel  PAGEREF _Toc6120962 \h 19
1.5.9 Profileur  PAGEREF _Toc6120963 \h 19
1.5.10 Outils de test  PAGEREF _Toc6120964 \h 19
1.5.11 Graphe de la chaîne de développement  PAGEREF _Toc6120965 \h 20
1.5.12 Choix du langage de programmation  PAGEREF _Toc6120966 \h 20
1.5.13 Raisons du succès du langage C  PAGEREF _Toc6120967 \h 20
2. Algorithmique élémentaire  PAGEREF _Toc6120968 \h 22
2.1 Introduction  PAGEREF _Toc6120969 \h 22
2.2 Mise au point préalable et preuve d'un algorithme  PAGEREF _Toc6120970 \h 22
2.3 Transcription du problème sous une forme calculable  PAGEREF _Toc6120971 \h 22
2.4 Complexité  PAGEREF _Toc6120972 \h 23
2.4.1 Problèmes NPcomplets  PAGEREF _Toc6120973 \h 23
2.4.2 Comportement asymptotique  PAGEREF _Toc6120974 \h 23
2.5 Enoncés de problèmes classiques  PAGEREF _Toc6120975 \h 24
2.5.1 Recherche d'une valeur dans un tableau  PAGEREF _Toc6120976 \h 24
2.5.2 Problème du tri  PAGEREF _Toc6120977 \h 25
2.5.3 Enoncé du problème du représentant de commerce  PAGEREF _Toc6120978 \h 25
2.5.4 Problème de l'arrêt  PAGEREF _Toc6120979 \h 25
2.6 Méthodes de conception d'algorithmes  PAGEREF _Toc6120980 \h 26
2.6.1 Méthodes par décomposition  PAGEREF _Toc6120981 \h 26
2.6.2 Diviser pour régner  PAGEREF _Toc6120982 \h 26
2.6.3 La modularité  PAGEREF _Toc6120983 \h 27
2.6.4 Critères de modularité  PAGEREF _Toc6120984 \h 27
2.6.5 Principes de modularité  PAGEREF _Toc6120985 \h 27
3. Méthodologie de programmation  PAGEREF _Toc6120986 \h 29
3.1 Principes généraux de la programmation  PAGEREF _Toc6120987 \h 29
3.1.1 Choix du langage de programmation  PAGEREF _Toc6120988 \h 29
3.1.2 Méta langage  PAGEREF _Toc6120989 \h 29
3.1.3 Commentaires  PAGEREF _Toc6120990 \h 29
3.1.4 Règles d'or de la programmation  PAGEREF _Toc6120991 \h 29
3.2 Grammaire  PAGEREF _Toc6120992 \h 30
3.2.1 Langage et grammaire  PAGEREF _Toc6120993 \h 30
3.2.2 Syntaxe et sémantique  PAGEREF _Toc6120994 \h 31
3.2.3 Mots clés  PAGEREF _Toc6120995 \h 31
3.2.4 Représentation interne des objets  PAGEREF _Toc6120996 \h 31
3.2.5 Objets de base du langage  PAGEREF _Toc6120997 \h 32
3.2.6 Construction d'objets complexes  PAGEREF _Toc6120998 \h 32
3.2.7 Opérations sur les objets de base  PAGEREF _Toc6120999 \h 32
3.3 Opérations d'entrées/sorties  PAGEREF _Toc6121000 \h 33
3.4 Structure d'un programme  PAGEREF _Toc6121001 \h 33
3.4.1 Instruction élémentaire  PAGEREF _Toc6121002 \h 33
3.4.2 Alphabet  PAGEREF _Toc6121003 \h 33
3.4.3 Définition  PAGEREF _Toc6121004 \h 34
3.4.4 Déclaration  PAGEREF _Toc6121005 \h 34
3.4.5 Affectation  PAGEREF _Toc6121006 \h 34
3.4.6 Niveaux de complexité d'une instruction  PAGEREF _Toc6121007 \h 35
3.4.7 Structure de bloc  PAGEREF _Toc6121008 \h 35
3.4.8 Fonction  PAGEREF _Toc6121009 \h 36
3.4.9 Modes de transmission des arguments d'une fonction  PAGEREF _Toc6121010 \h 36
3.4.10 Exemple de fonction complexe : la fonction qsort  PAGEREF _Toc6121011 \h 37
3.4.11 Procédure  PAGEREF _Toc6121012 \h 38
3.4.12 Programme principal  PAGEREF _Toc6121013 \h 38
3.4.13 Exemple de la structure d'un programme en C  PAGEREF _Toc6121014 \h 38
3.5 Structures de contrôle des programmes  PAGEREF _Toc6121015 \h 39
3.5.1 Test  PAGEREF _Toc6121016 \h 39
3.5.2 Branchement inconditionnel (ne pas utiliser)  PAGEREF _Toc6121017 \h 39
3.5.3 Branchement conditionnel (ne pas utiliser)  PAGEREF _Toc6121018 \h 39
3.6 Algorithme itératif  boucle  PAGEREF _Toc6121019 \h 42
3.6.1 Généralités  PAGEREF _Toc6121020 \h 42
3.6.2 Boucle à nombre d'itérations bornées  PAGEREF _Toc6121021 \h 43
3.6.3 Boucle à nombre d'itérations non borné  PAGEREF _Toc6121022 \h 44
3.6.4 Boucle Répéter… jusqu'à  PAGEREF _Toc6121023 \h 47
3.7 Programmes itératifs  PAGEREF _Toc6121024 \h 48
3.7.1 Construction récurrente  PAGEREF _Toc6121025 \h 48
3.7.2 Exemples  PAGEREF _Toc6121026 \h 48
3.7.3 Exercice commenté : le problème du drapeau hollandais  PAGEREF _Toc6121027 \h 49
3.7.4 Cas des boucles imbriquées  PAGEREF _Toc6121028 \h 51
3.7.5 Bibliographie du présent chapitre  PAGEREF _Toc6121029 \h 51
4. Concepts de base des Langages Orientés Objet et langage C  PAGEREF _Toc6121030 \h 52
4.1 Généralités  PAGEREF _Toc6121031 \h 52
4.2 Classes  PAGEREF _Toc6121032 \h 53
4.2.1 Définitions  PAGEREF _Toc6121033 \h 53
4.2.2 Héritage  PAGEREF _Toc6121034 \h 53
4.3 Approche orientée objet, données abstraites et encapsulation  PAGEREF _Toc6121035 \h 54
4.3.1 Types abstraits de données  PAGEREF _Toc6121036 \h 54
4.3.2 Encapsulation des données  PAGEREF _Toc6121037 \h 54
4.4 Initialisation des données  PAGEREF _Toc6121038 \h 55
4.5 Polymorphisme, surcharge et généricité  PAGEREF _Toc6121039 \h 55
4.6 Principes généraux de protection des données  PAGEREF _Toc6121040 \h 56
4.7 Abstraction et encapsulation en langage C  PAGEREF _Toc6121041 \h 56
4.7.1 Premier essai d’implémentation d'un type abstrait en C  PAGEREF _Toc6121042 \h 57
4.7.2 Deuxième essai d’implémentation d'un type abstrait en C  PAGEREF _Toc6121043 \h 58
4.7.3 Troisième essai d’implémentation d'un type abstrait en C  PAGEREF _Toc6121044 \h 59
4.7.4 Conclusion sur les types abstraits en C  PAGEREF _Toc6121045 \h 60
5. Le C++, langage procédural  PAGEREF _Toc6121046 \h 61
5.1 Introduction  PAGEREF _Toc6121047 \h 61
5.2 Commentaire  PAGEREF _Toc6121048 \h 61
5.3 Types  PAGEREF _Toc6121049 \h 62
5.4 Saisie et affichage élémentaire en C++  PAGEREF _Toc6121050 \h 63
5.4.1 Opérateurs de base  PAGEREF _Toc6121051 \h 63
5.4.2 Interprétation objet des entrées/sorties  PAGEREF _Toc6121052 \h 65
5.5 Définition et instruction exécutable  PAGEREF _Toc6121053 \h 65
5.6 Déclaration et définition  PAGEREF _Toc6121054 \h 66
5.7 Opérateurs spécifiques au langage C++  PAGEREF _Toc6121055 \h 66
5.8 Caractéristiques d'un fichier en tête  PAGEREF _Toc6121056 \h 66
5.9 Le spécificateur const et les variables  PAGEREF _Toc6121057 \h 67
5.10 Complément sur le type struct  PAGEREF _Toc6121058 \h 67
5.11 L'opérateur de résolution de portée  PAGEREF _Toc6121059 \h 67
6. Le C++, langage fonctionnel  PAGEREF _Toc6121060 \h 69
6.1 Prototypage  PAGEREF _Toc6121061 \h 69
6.2 Le type void  PAGEREF _Toc6121062 \h 69
6.3 Surcharge d'une fonction  PAGEREF _Toc6121063 \h 70
6.4 Valeur par défaut des arguments d'appel  PAGEREF _Toc6121064 \h 72
6.5 Référence  PAGEREF _Toc6121065 \h 74
6.5.1 Le type référence  PAGEREF _Toc6121066 \h 74
6.5.2 Transmission d'argument par référence  PAGEREF _Toc6121067 \h 75
6.5.3 Le spécificateur const et la transmission d'argument par référence  PAGEREF _Toc6121068 \h 77
6.5.4 Transmission du résultat d'un appel de fonction par référence  PAGEREF _Toc6121069 \h 78
6.6 Variables et fonctions statiques  PAGEREF _Toc6121070 \h 79
6.6.1 Variables statiques  PAGEREF _Toc6121071 \h 79
6.6.2 Fonctions statiques  PAGEREF _Toc6121072 \h 80
7. Classes en langage C++  PAGEREF _Toc6121073 \h 80
7.1 Principes  PAGEREF _Toc6121074 \h 80
7.2 Définitions  PAGEREF _Toc6121075 \h 81
7.2.1 Classes et instances  PAGEREF _Toc6121076 \h 81
7.2.2 Propriétés des fonctions spécifiées inline  PAGEREF _Toc6121077 \h 83
7.3 Qualification d'accès aux membres d'une classe  PAGEREF _Toc6121078 \h 83
7.4 Méthode  PAGEREF _Toc6121079 \h 85
7.5 Le pointeur this  PAGEREF _Toc6121080 \h 85
7.6 Méthode spécifiée constante  PAGEREF _Toc6121081 \h 86
7.7 Membre statique  PAGEREF _Toc6121082 \h 88
7.7.1 Donnée membre statique de la classe  PAGEREF _Toc6121083 \h 88
7.7.2 Variable statique définie dans une méthode  PAGEREF _Toc6121084 \h 89
7.7.3 Méthode statique  PAGEREF _Toc6121085 \h 90
7.8 Pointeur sur les membres d'une classe  PAGEREF _Toc6121086 \h 91
8. Constructeur et destructeur  PAGEREF _Toc6121087 \h 93
8.1 Définitions  PAGEREF _Toc6121088 \h 93
8.2 Constructeur  PAGEREF _Toc6121089 \h 93
8.2.1 Constructeur implicite  PAGEREF _Toc6121090 \h 93
8.2.2 Constructeur explicite  PAGEREF _Toc6121091 \h 94
8.2.3 Constructeurs multiples  PAGEREF _Toc6121092 \h 96
8.2.4 Transtypage par appel d'un constructeur  PAGEREF _Toc6121093 \h 98
8.3 Destructeur  PAGEREF _Toc6121094 \h 103
9. Allocation dynamique  PAGEREF _Toc6121095 \h 104
9.1 Principes de gestion de l’allocation dynamique en C++  PAGEREF _Toc6121096 \h 104
9.2 L'opérateur new  PAGEREF _Toc6121097 \h 104
9.3 L'opérateur delete  PAGEREF _Toc6121098 \h 104
9.4 Règles d'utilisation  PAGEREF _Toc6121099 \h 104
9.5 Exemples  PAGEREF _Toc6121100 \h 105
10. Surcharge des opérateurs  PAGEREF _Toc6121101 \h 109
10.1 Généralités et syntaxe  PAGEREF _Toc6121102 \h 109
10.2 Opérateur surchargé membre d'une classe  PAGEREF _Toc6121103 \h 109
10.3 Opérateur surchargé non membre d'une classe  PAGEREF _Toc6121104 \h 111
10.4 Amitie et levée partielle de l'encapsulation  PAGEREF _Toc6121105 \h 112
10.5 Surcharge de l'opérateur <  PAGEREF _Toc6121106 \h 113
10.6 Transtypage d'un objet typé vers le type classe  PAGEREF _Toc6121107 \h 114
10.7 Surcharge d'opérateur et fonction amie  PAGEREF _Toc6121108 \h 116
10.8 Surcharge de l'opérateur []  PAGEREF _Toc6121109 \h 117
10.9 L'opérateur d'affectation  PAGEREF _Toc6121110 \h Erreur ! Signet non défini.
10.9.1 Constructeur copie  PAGEREF _Toc6121111 \h 119
10.9.2 Surcharge de l'opérateur d'affectation  PAGEREF _Toc6121112 \h 123
10.10 Surcharge des opérateurs d'incrémentation et de décrémentation  PAGEREF _Toc6121113 \h 125
10.11 Surcharge de l'opérateur fonctionnel  PAGEREF _Toc6121114 \h 126
10.12 Opérateurs de transtypage  PAGEREF _Toc6121115 \h 129
10.13 Opérateurs de comparaison  PAGEREF _Toc6121116 \h 129
10.14 Opérateurs de déréférenciation, de référence, de sélection de membre  PAGEREF _Toc6121117 \h 129
10.15 Opérateurs d'allocation dynamique de mémoire  PAGEREF _Toc6121118 \h 130
11. Classes imbriquées  PAGEREF _Toc6121119 \h 132
11.1 Définition  PAGEREF _Toc6121120 \h 132
11.2 Données membres instances d'une autre classe  PAGEREF _Toc6121121 \h 132
11.3 Exercice récapitulatif sur les classes imbriquées  PAGEREF _Toc6121122 \h 134
12. L'héritage en langage C++  PAGEREF _Toc6121123 \h 139
12.1 Définitions  PAGEREF _Toc6121124 \h 139
12.2 Résolution de visibilité  PAGEREF _Toc6121125 \h 141
12.3 Qualifications d'accès des objets d'une classe  PAGEREF _Toc6121126 \h 142
12.4 Qualification de l'héritage  PAGEREF _Toc6121127 \h 142
12.4.1 Qualifications de l'héritage des objets de la classe de base  PAGEREF _Toc6121128 \h 142
12.4.2 Règles d'accès aux objets dans la classe dérivée  PAGEREF _Toc6121129 \h 143
12.4.3 Inclusion des classes dérivées dans la classe de base  PAGEREF _Toc6121130 \h 144
12.4.4 Transtypage selon la qualification de l'héritage  PAGEREF _Toc6121131 \h 145
12.4.5 Requalification des qualifications d'accès dans les classes dérivées  PAGEREF _Toc6121132 \h 145
12.5 Classes dérivées et constructeur  PAGEREF _Toc6121133 \h 151
12.6 Classe virtuelle  PAGEREF _Toc6121134 \h 153
12.6.1 Définition  PAGEREF _Toc6121135 \h 153
12.6.2 Règles d'utilisation des classes virtuelles  PAGEREF _Toc6121136 \h 157
12.7 Méthodes virtuelles, lien dynamique, polymorphisme  PAGEREF _Toc6121137 \h 157
12.8 Règles de dérivation  PAGEREF _Toc6121138 \h 160
12.9 Méthodes virtuelles pures - classes abstraites  PAGEREF _Toc6121139 \h 162
12.9.1 Définitions  PAGEREF _Toc6121140 \h 162
12.9.2 Conteneur et objets polymorphiques  PAGEREF _Toc6121141 \h 163
13. Les modèles génériques (template)  PAGEREF _Toc6121142 \h 169
13.1 Généralités  PAGEREF _Toc6121143 \h 169
13.2 Déclaration de type générique  PAGEREF _Toc6121144 \h 169
13.3 Fonction et classe générique  PAGEREF _Toc6121145 \h 170
13.3.1 Fonctions avec des types d'arguments génériques  PAGEREF _Toc6121146 \h 170
13.3.2 Classe générique  PAGEREF _Toc6121147 \h 172
13.3.3 Méthodes génériques  PAGEREF _Toc6121148 \h 175
13.4 Instanciation des paramètres génériques  PAGEREF _Toc6121149 \h 177
13.4.1 Instanciation implicite de fonction avec des arguments de type générique  PAGEREF _Toc6121150 \h 177
13.4.2 Instanciation explicite d'objet générique  PAGEREF _Toc6121151 \h 179
13.4.3 Problèmes soulevés par l'instanciation des objets génériques  PAGEREF _Toc6121152 \h 182
13.5 Spécialisation des objets génériques  PAGEREF _Toc6121153 \h 182
13.5.1 Spécialisation partielle d'une classe  PAGEREF _Toc6121154 \h 183
13.5.2 Spécialisation totale d'une classe  PAGEREF _Toc6121155 \h 185
13.5.3 Spécialisation d'une méthode d'une classe générique  PAGEREF _Toc6121156 \h 185
13.6 Paramètres génériques template template  PAGEREF _Toc6121157 \h 187
13.7 Déclaration des constantes génériques  PAGEREF _Toc6121158 \h 188
13.8 Généricité et méthode virtuelle  PAGEREF _Toc6121159 \h 189
13.9 Mot clé typename  PAGEREF _Toc6121160 \h 192
13.10 Fonctions exportées  PAGEREF _Toc6121161 \h 192
14. Espace de noms  PAGEREF _Toc6121162 \h 194
14.1 Espace nommé et anonyme  PAGEREF _Toc6121163 \h 194
14.1.1 Espace nommé  PAGEREF _Toc6121164 \h 194
14.1.2 Espace anonyme  PAGEREF _Toc6121165 \h 196
14.1.3 Alias d'espace de noms  PAGEREF _Toc6121166 \h 197
14.2 Déclaration using  PAGEREF _Toc6121167 \h 197
14.2.1 Règles d'utilisation  PAGEREF _Toc6121168 \h 197
14.2.2 Héritage et déclaration using  PAGEREF _Toc6121169 \h 199
14.3 Directive using  PAGEREF _Toc6121170 \h 200
15. Les exceptions en langage C++  PAGEREF _Toc6121171 \h 202
15.1 Principes sémantiques  PAGEREF _Toc6121172 \h 202
15.2 Principes de gestion des exceptions en langage C++  PAGEREF _Toc6121173 \h 202
15.3 Génération et traitement d'une exception  PAGEREF _Toc6121174 \h 203
15.3.1 Zone de prise en compte d'une exception  PAGEREF _Toc6121175 \h 203
15.3.2 Définition d'un gestionnaire d'exception  PAGEREF _Toc6121176 \h 204
15.4 Remontée des exceptions  PAGEREF _Toc6121177 \h 205
15.5 Liste des exceptions autorisées pour une fonction  PAGEREF _Toc6121178 \h 206
15.6 Exceptions et constructeurs  PAGEREF _Toc6121179 \h 207
15.7 Exceptions et allocation mémoire  PAGEREF _Toc6121180 \h 209
15.8 Hiérarchie des exceptions  PAGEREF _Toc6121181 \h 209
16. Identification des types dynamiques  PAGEREF _Toc6121182 \h 212
16.1 Identification dynamique d’un type  PAGEREF _Toc6121183 \h 212
16.1.1 La classe type_info  PAGEREF _Toc6121184 \h 212
16.1.2 L'opérateur typeid  PAGEREF _Toc6121185 \h 213
16.2 Transtypages en langage C++  PAGEREF _Toc6121186 \h 214
16.2.1 Généralités sur les opérateurs de transtypage  PAGEREF _Toc6121187 \h 214
16.2.2 Transtypage dynamique  PAGEREF _Toc6121188 \h 214
16.2.3 Transtypage statique  PAGEREF _Toc6121189 \h 216
16.2.4 Transtypage de constance et de volatilité  PAGEREF _Toc6121190 \h 217
16.2.5 Opérateur de réinterprétation des données  PAGEREF _Toc6121191 \h 217
17. Exercices  PAGEREF _Toc6121192 \h 219
17.1 Exercice récapitulatif  PAGEREF _Toc6121193 \h 219
17.2 Exercices sur les constructeurs et les destructeurs  PAGEREF _Toc6121194 \h 222
17.2.1 Exercice 1  PAGEREF _Toc6121195 \h 222
17.2.2 Exercice 2  PAGEREF _Toc6121196 \h 223
17.2.3 Exercice 3  PAGEREF _Toc6121197 \h 224
17.2.4 Exercice 4  PAGEREF _Toc6121198 \h 226
17.3 Exercice : implémentation de type utilisateur en C++  PAGEREF _Toc6121199 \h 227
17.4 Exercice : exemple de type abstrait en C++  PAGEREF _Toc6121200 \h 229
18. Règles de priorité des opérateurs  PAGEREF _Toc6121201 \h 234
19. BIBLIOGRAPHIE  PAGEREF _Toc6121202 \h 236
Index  PAGEREF _Toc6121203 \h 237
 Le génie logiciel
De l'art de la programmation aux méthodes du génie logiciel
Evolutions de la programmation
Cinquante ans après les débuts de l'informatique, les méthodes et les outils de développement d'applications ont beaucoup évolués : on est passé du langage machine au langage de cinquième générationXE "langage de quatrième génération" ainsi qu'au générateur d'applicationsXE "générateur d'applications". On peut faire la classification sommaire suivante
Génération :  1ère 2ème 3ème 4ème 5ème
langage machine Assembleur langage évolué S.G.B.D. L4G, générateurs
Programmation et rendement
En 1972, le rendement moyen d'un programmeur professionnel est de 8 lignes par heure (source Pentagone : colloque de Monterey : The high cost of software). L'écriture de "bons" programmes est très longue et difficile.
Coûts de développement
Les mêmes statistiques indiquent à cette époque un coût d'écriture par instruction de 75 $ US et de mise au point de 4 000 $ US.
Evolution du profil du programmeur
Le profil du programmeur a évolué depuis 1950 :
1950 Il est un initié qui utilise exclusivement le langage machine.
1968 Il est considérée comme un artiste (Knuth).
1975 Il doit respecter une discipline (Dijkstra) et suivre quelques règles de programmation non empirique.
1981 La programmation est devenue une science (D.Gries).
Les causes
Les concepts de test et de branchement conditionnelXE "branchement conditionnel" (ou rupture de séquenceXE "rupture de séquence") dûs à Von Neumann, ont permis le démarrage de l'écriture de programmes informatiques. Malheureusement, l'utilisation du branchement conditionnel est aussi une des sources importante d'erreurs car bien souvent les programmeurs, au moment de la rédaction du programme, effectuent des branchements multiples et quelquefois (?) ne savent plus, oublient le pourquoi du branchement. Petit à petit, la nécessité de structurer sa pensée et les programmes est apparue et a donné naissance aux concepts de la programmation structurée. "Ce qui se conçoit bien s'énonce clairement et les mots pour le dire arrivent aisément..."
Ces concepts sont utilisés dans les langages structurés tels le le C (Kernighan & Ritchie), ADA (Ichbiah), Java.
Leur utilisation a conduit à la suppression de la rupture de séquence, "ennemie du bon programmeur".
Erreurs et preuves de programmes
Il faut toujours se souvenir de cette constatation d'E. Dijkstra : "Essayer un programme peut seulement montrer qu'il contient des erreurs. Jamais qu'il est juste".
Le génie logiciel
Le génie logiciel XE "génie logiciel"est l'art de développer des logiciels. Il devrait être une discipline d'ingénierie aussi solidement établie dans ses méthodes et ses principes que le génie civil. Nous en sommes encore loin aujourd'hui.
Difficultés de conception des logiciels
Plusieurs facteurs contribuent à rendre difficile la conception et le développement des logiciels :
Ils peuvent être d'une très grande complexité, à la limite de l'ingéniosité humaine.
Aucune loi physique ne permet de limiter l'espace des solutions possibles.
Les causes des pannes sont aléatoires. Une simple erreur d'inattention dans un programme de plusieurs millions de lignes peut interrompre le service qu'il fournit.
Chaque détail compte
Des erreurs d'apparence anodine peuvent se glisser dans des programmes. Soit le programme C suivant :
if (i =  0) printf ("la valeur de i est zéro\n");
else printf('la valeur de i n'est pas zéro\n");
Contrairement à ce qu'une lecture rapide laisserait penser, et contrairement à l'intention du programmeur, ce programme imprime "la valeur de i est zéro" quelle que soit la valeur de la variable i car en C, le symbole =  représente l'opérateur d'affectation et non l'opérateur de comparaison logique (qui en C s'écrit = = ). La valeur de l'expression i = 0 est toujours nulle, quel que soit le contenu initial de la variable i, et la condition du test n'est jamais satisfaite.
Une simple question d'argent ?
Le logiciel embarqué dans la navette spatiale américaine a été développé avec le soin le plus extrême, et on estime son prix de revient à 25.000 FF par ligne (sans les commentaires). Aucun organisme dans le monde, à part la NASA ne peut se permettre d'investir autant d'argent par ligne de code. Pourtant, ce logiciel contient encore des erreurs. A chaque vol, les astronautes partent avec la liste des erreurs référencées dont l'une est la suivante : lors de l'utilisation simultanée de deux claviers , le ou logique des caractères saisis est transmis à l'ordinateur. La solution retenue a été de n'utiliser qu'un clavier à la fois.
Le développeur de logiciels
On observe des différences de productivité considérables entre programmeurs médiocres et programmeurs de talent.
On pense trop souvent que le développement de logiciel est une tâche dégradante, à confier à des ingénieurs débutants. Pourtant, la conception d'ouvrages d'art importants est toujours confiée à des ingénieurs confirmés. Et on comprend mal pourquoi il faudrait opérer différemment pour la conception des logiciels car c'est une tâche qui requiert autant d'expertise pour être menée à bien.
Valeur d'un logiciel
Le folklore informatique ignore un point important : la valeur marchande d'un logiciel tient autant à son introduction rapide sur le marché qu'à ses qualités propres. Le client n'est pas toujours prêt à attendre qu'un programmeur exceptionnellement doué ait trouvé une solution élégante à son problème. Il a tort à long terme, mais il paie.
Etapes du développement d'un logiciel
Les différentes étapes de développement d'un logiciel, présentées ici en séquence, interagissent en réalité de façon complexe.
Analyse
L'analyse consiste à déterminer les grandes lignes du logiciel ainsi que ses contraintes d'utilisation et d'exploitation. Il faut en outre cerner les besoins de l'utilisateur.
Voici quelques questions typiquement abordées lors de cette phase de développement.
De quel type de programme s'agitil (traitement de transactions, contrôleur temps réel, applicatif bureautique, etc.) ?
Quelles en sont les entrées et les sorties ?
Sur quel matériel et quel système d'exploitation doitil s'exécuter?
De combien de temps et de personnel disposet'on pour développer l'application ?
Quelles en seront les extensions futures les plus probables ?
Qui en est le destinataire (grand public ou professionnels pour lesquels une période de formation peut être prévue) ?
Spécification
La spécification XE "spécification"est une réponse formelle aux besoins identifiés durant l'étape d'analyse. Elle comprend :
une description précise des entrées et des sorties,
des données chiffrées sur le temps de développement et sur les configurations matérielles et logicielles requises,
des données chiffrées résultants des spécifications (nombre d'utilisateurs, temps de réponse, etc.),
une version préliminaire de la documentation de l'application.
Documentation
La documentation fait partie intégrante de l'effort de programmation. Le programme luimême en constitue une partie importante.
A cela doit s'ajouter un document technique de référenceXE "document technique de référence" qui comprend des aspects normatifs, et formalise l'effort de conception du logiciel. Notamment :
une description précise de l'architecture générale du projet et de son découpage en modules,
une description précise des fonctions de chaque module, de leurs interfaces et protocoles de communication,
une description précise des composants logiciels utilisés (bibliothèques graphiques, générateurs d'interface, générateurs de requêtes de base de données, composants réutilisables pour d'autres projets, etc.).
Programmation
Une fois les outils de développement choisis, l'étape de la programmation consiste à écrire le code des différents modules. On réalise généralement incrémentalement les fonctionnalités du logiciel, et on effectue des tests sur chaque module avant d'assembler le tout.
La méthode des approximations successives
L'effort de programmation fait généralement apparaître des erreurs de conception, qui nécessitent une modification du découpage du logiciel en modules et en conséquence une modification des documents rédigés à l'étape précédente.
Programmation et chirurgie
Programmer prend du temps et n'est pas toujours une tâche d'exécutant. Les éditeurs de logiciel les plus performants utilisent plutôt le modèle de l'équipe chirurgicale. Le chirurgien est responsable des parties les plus délicates et les plus difficiles du logiciel, et le reste de l'équipe sert de support, programmant les parties les plus aisées et rédigeant la documentation.
Mise au point et tests
Preuves de programmes
La preuve mathématique complète qu'un programme correspond à ses spécifications est la seule garantie qu'un programme ne comporte pas d'erreurs. Toutefois, on ignore comment rédiger les spécifications d'un logiciel de façon non ambiguë et parfaite. La complexité d'une telle preuve la rendrait impossible sans une certaine forme d'automatisation. Or les logiciels d'analyse de programmes sont limités pour des raisons théoriques. On sait par exemple qu'il n'existe aucun algorithme capable de déterminer si un programme risque de boucler indéfiniment. Les logiciels d'analyse formelleXE "analyse formelle" (de logiciels) ne peuvent être que des aides partielles à la preuve. Il en existe, mais leur application est pour le moment limitée car ils imposent une méthodologie de développement très rigide.
Jeux d'essais
On se rabat donc sur des simulations ou tests pour valider un logiciel. Idéalement il faudrait en essayer tous les modules de façon exhaustive. Dans la réalité, on utilise deux types d'approches :
des tests ciblés, pour mettre des erreurs en évidence. Un bon exemple est de tester les conditions limites. On pourra tester le fonctionnement d'une procédure de tri sur un tableau de taille nulle ou sur un tableau contenant des entrées identiques. Ces tests ciblés peuvent demander de l'ingéniosité.
Des tests en utilisation réelle, généralement faits par un client enthousiaste ou impatient. Ces tests sont réalisés sur des versions préliminaires du logiciel, appelées alpha ou beta releases. C'est ce qu'à fait, à 500 000 exemplaires, l'éditeur de logiciels Microsoft, avant la sortie du système Windows 95. Cela n'a d'ailleurs pas suffit, loin de là, à éliminer tous les bogues.
Maintenance et support
La maintenanceXE "maintenance" d'un logiciel consiste à en corriger les boguesXE "bug", à en étendre les fonctionnalités, et à en assurer le portage sur différentes plateformes matérielles et systèmes d'exploitation. Elle est coûteuse et son importance souvent sousestimée. Il s'agit en fait de la continuation de l'effort de développement. Ainsi, le logiciel de traitement de texte Word, initialement développé par une équipe de quatre personnes, est maintenu par une équipe de vingtcinq. On commet trop souvent l'erreur de ne pas anticiper les besoins de maintenance pendant le développement initial d'un logiciel.
Le support XE "support"d'un logiciel consiste à assurer un service de formation et d'assistance auprès de la clientèle. Son coût n'est pas non plus négligeable.
On estime à 70% du coût total de développement celui de la maintenance dont on rappelle la nécessité :
évolutivité du logiciel.
correction de ses bugs.
Productivité du logiciel
Les aspects économiques du développement de logiciel sont encore mal maîtrisés. Ainsi, connaissant le coût de la réalisation du logiciel de l'A310 et le cahier des charges de celui de l'A320, son coût fut estimé, à méthode de développement équivalente, entre 3 et 12 fois celui de l'A310, selon les méthodes d'évaluation. Une des difficultés de ce type d'exercice prévisionnel est la manque de précision de la mesure de productivité du logiciel que plusieurs techniques permettent, imparfaitement, de mesurer.
Le nombre de lignes de code par programmeur par jour
La mesure la plus couramment utilisée de la productivité d'une équipe de développement est le nombre de lignes de programme produites par jour. Elle est mauvaise pour au moins trois raisons :
Un programmeur compétent consacre un temps parfaitement productif à réduire le taille de ses programmes. Ce travail en réduit la complexité et en augmente la valeur.
Cette mesure ne fait pas la différence entre la productivité d'une équipe qui réalise un logiciel de 10.000 lignes de code en un an, et celle qui réalise en deux ans un logiciel de capacité équivalente de 20.000 lignes de code.
Le nombre de lignes de code produites par un programmeur par jour varie selon la complexité du logiciel. Une mesure empirique de cet effet est donnée par la formule suivante :
effort =  constante * (taille du programme)1.5
Une meilleure mesure de productivité
Pour obtenir une meilleure mesure de la productivité d'une équipe de développement, il est préférable d'estimer directement la valeur et le coût de développement d'un logiciel.
La valeur d'un logiciel tient compte de sa valeur marchande, de son évolution probable dans le temps ainsi que de la complexité intrinsèque du problème résolu, qui représente une indication de la difficulté qu'aura la concurrence à reproduire un effort de développement similaire ainsi que la possibilité de réutiliser tout ou partie de ce logiciel.
Le coût de développement d'un logiciel doit inclure le coût de développement proprement dit, le surcoût du au retard possible de sa commercialisation, ainsi que celui de son support et de sa maintenance pendant sa durée de vie.
Critères de qualité du logiciel
Un logiciel doit être doté des qualités suivantes :
Validité : aptitude d'un logiciel à réaliser exactement les tâches définies par sa spécification.
Robustesse : aptitude d'un logiciel à fonctionner même dans des conditions anormales.
Extensibilité : facilité d'adaptation d'un logiciel à une modification des spécifications.
Réutilisabilité : aptitude d'un logiciel à être réutilisé en partie ou en totalité pour de nouvelles applications.
Compatibilité : aptitude d'un logiciel à pouvoir être combiné avec d'autres.
Efficacité : bonne utilisation des ressources matérielles et logicielles
Portabilité : facilité d'adaptation d'un logiciel à différents environnements matériels et logiciels.
Vérifiabilité : facilité de préparation des procédures de recette et de certification, notamment des tests et des procédures de déboguage.
Intégrité : aptitudes d'un logiciel à protéger ses différentes composantes (programmes, données) contre des accès ou des modifications non autorisées.
Facilité d'utilisation du logiciel par les utilisateurs (fonctionnement, préparation d'utilisation, interprétation des résultats, réparation en cas d'erreurs d'utilisation).
L'ergonomie
Un programme peut être parfait du point de vue de ses concepteurs et contenir cependant des défauts qui peuvent s'avérer fatals. La catastrophe de l'Airbus A320 du Mont Sainte Odile en est une illustration. Cet avion avait un écran d'affichage sur lequel s'affichait, selon un mode choisi par le pilote (la position d'un bouton), la vitesse verticale de l'avion en pieds par seconde ou l'inclinaison de sa trajectoire en degrés. Il semble que le pilote ait interprété le contenu de l'écran d'affichage d'une façon, sans s'apercevoir que le copilote avait changé le mode d'affichage. L'avion a ainsi perdu trop rapidement de l'altitude sans que le pilote s'en aperçoive à temps. Dans cet exemple, le logiciel a fonctionné parfaitement, selon ses spécifications. De nos jours, nous plaçons des barrières de sécurité le long des routes aux endroits dangereux. Nous avons encore à apprendre à le faire dans la conception du logiciel. La leçon à retenir de la catastrophe du Mont Sainte Odile est qu'une mauvaise interface hommemachine peut être aussi dangereuse qu'une erreur de programmation.
Le long terme
Le manque de vision à long terme dans le développement de logiciels est aussi la source de nombreux déboires. Le problème de loin le plus fréquent est causé par l'introduction de limites arbitraires d'adressage ou de précision, dont il est difficile de se débarrasser après coup. En voici deux exemples.
Cobol
Cobol, un langage de programmation introduit dans les années cinquante pour les programmes de gestion, a connu un succès qui a dépassé de loin les anticipations de ses concepteurs. De nombreux programmes Cobol seront toujours utilisés en l'an 2000; malheureusement Cobol ne réservant que deux chiffres décimaux pour indiquer l'année, il a fallu dépenser des milliards pour corriger le bogue de l'an 2000.
Les missiles Patriot
Le système de défense antiaérienne Patriot de l'armée américaine n'a pas intercepté un missile SCUD qui a fait 28 victimes au nord de l'Arabie Saoudite durant la guerre du Golfe. La raison était un décalage de l'horloge du système de défense dans le temps, le système ayant été initialement conçu pour intercepter des avions, et non des missiles ballistiques qui se déplacent plus rapidement.
Les mécanismes d'abstraction
Deux grandes classes de méthodes permettent de simplifier la conception et la réalisation de logiciels : les mécanismes d'abstraction et les invariants de programme.
Les mécanismes d'abstractionXE "mécanisme d'abstraction" cherchent à distinguer l'information nécessaire à l'utilisation d'un logiciel et celle qui est nécessaire à sa réalisation. L'objectif est de permettre le développement de logiciels complexes en minimisant les dépendances entre les modules et la communication nécessaire entre les équipes de développement. Rappelons pour mémoire la définition du mot abstraction :
Définition
Fait de considérer à part un élément (qualité ou relation) d'une représentation ou d'une notion, en portant spécialement l'attention sur lui et en négligeant les autres.
Les deux principaux mécanismes d'abstraction sont l'abstraction procédurale et l'abstraction par les données. Une bonne abstraction dissimule une fonction à la fois complexe et utile derrière une interface simple à utiliser. Toute la difficulté de la conception d'un programme réside dans leurs choix.
L'abstraction procédurale
L'abstraction procéduraleXE "abstraction procédurale" regroupe dans une procédure une action (calcul, action de contrôle, manipulation de données, etc.), pour la rendre utilisable comme une primitive de l'environnement de programmation. Elle permet au programmeur de faire appel à une fonction tout en faisant abstraction des détails de sa réalisation. Le programmeur n'a besoin de comprendre que les paramètres qu'elle accepte et la fonction qu'elle réalise. Il n'a pas besoin de savoir comment cette fonction est réalisée. Par exemple, l'utilisation d'une procédure de tri ne nécessite pas de connaître l'algorithme utilisé par le programme.
L'abstraction des données
La plupart des logiciels s'organisent naturellement autour de la manipulation de certains types de données : listes, tables, graphes, fichiers, processus, fenêtres, transactions, relations, etc.
L'abstraction des donnéesXE "abstraction des données" masque leur représentation interneXE "représentation interne" selon leur type. Elle n'autorise leur manipulation qu'à travers un ensemble défini de procédures, appelées méthodesXE "méthode", dérivant de leur définition mathématique.
Définition
Un type abstrait XE "type abstrait"est la donnée d'un ensemble de valeurs et des procédures nécessaires pour y accéder et les modifier.
L'illustration la plus simple d'une telle abstraction est la notion de fichier utilisée par les appels systèmes du système d'exploitation UNIX, qui leur donne accès à travers un ensemble d'appels système (open, close, read, write).
La programmation orientée objet
L'abstraction des données est l'idée la plus importante en génie logiciel de ces vingt dernières années. Son utilisation simplifie considérablement l'architecture de logiciels complexes. Depuis les années quatrevingt, elle a connu une explosion de popularité avec l'introduction de langages de programmation dits orientés objet, dont le langage C++ est un des représentants connus. Comme l'exemple des fichiers UNIX l'illustre, on peut simuler l'abstraction des données par le mécanisme d'abstraction procédurale d'un langage comme le C.
Le principe de partage
L'abstraction procédurale comme l'abstraction des données permettent de respecter un des principes les plus importants du développement logiciel : le principe du partage.
Définition
Aucune partie ou fonction d'un logiciel ne doit être dupliquée.
Toute violation du principe du partage est source d'erreurs et de surcoûts durant la maintenance du logiciel. Lorsqu'un logiciel complexe ne respecte pas ce principe, il est facile d'oublier de modifier une des multiples copies d'une fonction, créant ainsi des inconsistances dans le logiciel. Le principe du partage est un excellent guide pour qui cherche à déterminer les bonnes abstractions sur lesquelles baser l'architecture d'un logiciel.
Les invariants
Un invariant est une propriété d'un programme qui est vraie à un point donné d'exécution du programme, pour chaque exécution possible du programme. C'est un outil conceptuel simple mais essentiel.
La chaîne de développement et ses outils
Généralités sur les outils de développementXE "outils de développement"
Pour s'exécuter, tout programme doit suivre le cycle suivant :
écriture du programme dans un langage évolué : c'est le code source,
transformation du code source en langage machine : c'est la compilation,
recherche par l'éditeur de liens dans les diverses bibliothèques des variables dont les référenceXE "référence"s sont non satisfaites à la compilation pour la génération définitive du code exécutableXE "code exécutable"
La chaîne de développement est constituée par l'ensemble des outils constituant le support de programmation et permettant de créer des programmes exécutables. Ils sont de quatre types :
édition et génération d'un programme exécutable,
analyseur syntaxique et sémantique des programmes,
outils de génie logiciel,
utilitaires divers.
Editeurs de textes
Un éditeur de texteXE "éditeur de texte" est un programme puissant permettant l'écriture du texte. Il doit permettre de modifier facilement un (ou plusieurs) mots dans une ligne, ou dans tout un programme, d'insérer, de modifier, de déplacer, de dupliquer des lignes dans un texte. Certains éditeurs très évolués sont de véritables traitements de texte.
Mise en forme
La mise en forme d'un fichier source d'un programme peut être complétée par l'utilisation d'un enjoliveur de programmes
Analyseur syntaxique
La vérification de la grammaire d'un programme source est réalisé par un analyseur syntaxiqueXE "analyseur syntaxique", dont les règles grammaticales sont plus strictes que celles du compilateur lui même. Il renvoit les messages d'erreurs du compilateur ainsi que des messages d'avertissement spécifiques lorsqu'il détecte des incohérences de définition ou des problèmes éventuels de portabilité.
L'utilisation systématique d'un tel outil est recommandée avec comme objectifs l'élimination progressive de tous les messages d'avertissement (warning) ou d'erreur.
Compilation et édition de lien
L'adressage symboliqueXE "adressage symbolique" désigne des adresses mémoire ou des valeurs par des symboles alphanumériquesXE "alphanumérique" appelés respectivement étiquetteXE "étiquette"s (labelXE "label"s) ou symboleXE "symbole"s. Le programmeur peut ainsi associer une adresse en mémoire avec son contenu. On fait référenceXE "référence" à un symbole quand il est utilisé dans une instruction du programme. Cette référence est une référence interneXE "référence interne" si le symbole est défini dans le programme, référence externeXE "référence externe" sinon. Si on fait référence à un symbole avant de l'avoir défini explicitement, on dit que la référence est une référence en avantXE "référence en avant". La correspondance entre un symbole et son adresse est assurée par la table des symbolesXE "table des symboles". Les références sont satisfaites quand il est possible d'associer un symbole à son adresse à partir de la table des symboles.
Pour que les références puissent être satisfaites, il est nécessaire à la plupart des compilateurs de procéder en deux passeXE "passe"s :
passe 1 : construction de la table des symboles,
passe 2 : achèvement de la table des références en avant, incomplète à la première passe.
Langage machine
Le langage machine est spécifique au calculateur. Toutes les instructions en langage machine sont représentées par une suite de 0 et 1 sous la forme :
CO CA AD
code condition zone
opération d'adressage adresse
Exemple : soit l'instruction (codée ici en hexadécimal et en binaire) sur 32 bits
Hexadécimal 10 25 0208
Binaire 0001 0000 0010 1001 0000 0010 0000 1000
Outils de recherche d'erreurs
Un debugger (débogueur) permet de contrôler l'exécution et d'examiner les données internes d'un programme pour isoler l'origine d'erreurs. D'autres outils de mise au point permettent d'identifier des anomalies de références en mémoire (pointeurs pendants, fuites de mémoire).
Un débogueur symboliqueXE "debogeur symbolique" exécute sous son contrôle des programmes pas à pas avec édition possible des variables intermédiaires permettant la recherche des erreurs de programmation.
Outils de génie logiciel
Les techniques actuelles de développement d'applications imposent une programmation de plus en plus modulaire. Il faut donc disposer d'outils de génération de fichiers exécutables construits à partir de fichiers sources, éventuellement écrits dans différents langages de programmation, de fichiers compilés, de fichiers édités de telle sorte que l'on puisse faire des modifications dans un fichier (source, bibliothèque,...) sans avoir à recompiler tout l'ensemble, surtout s'il est important (plusieurs milliers de lignes de codes d'origines diverses par exemple).
Profileur
Les profileursXE "profileur" permettent d'obtenir des statistiques d'exécution et de déterminer les éventuelles inutilisations des certaines séquences en isolant les parties d'un programme qui utilisent le plus de temps d'exécution.
Outils de test
Les outils de tests sont importants pendant le développement et la maintenance d'un logiciel.
Un test de régressionXE "test de régression" est une suite de tests que l'on utilise pour vérifier systématiquement qu'une modification n'a pas introduit d'erreur, donc qu'elle n'a pas fait régresser le logiciel.
Les tests de couvertureXE "tests de couverture" vérifient que toutes les parties d'un logiciel sont effectivement vérifiées.
D'autres outils enfin génèrent automatiquement des jeux de test ayant certaines propriétés.
Graphe de la chaîne de développement
EMBED MSDraw \* MERGEFORMAT
Choix du langage de programmation
La plupart des logiciels sont développés dans des langages d'usage général, tels le C ou le C++. Le langage Fortran est surtout utilisé en calcul scientifique, et Cobol en informatique de gestion, mais C et C++ peuvent aussi être utilisés dans ce type d'applications.
Raisons du succès du langage C
Le langage C n'est pas un langage de programmation sans défaut. Il n'est pas fortement typé, et il lui manque certains mécanismes importants d'abstraction (objets) et de contrôle (exceptions). Enfin il force le programmeur à gérer luimême son espace mémoire. Ces problèmes sont partiellement corrigés en C++, dont le succès est essentiellement du à sa compatibilité avec C.
La popularité du langage C s'explique de différentes façons :
UNIX et C
Le langage C a été inventé dans les laboratoires de recherche d'AT&T pour réaliser les premières versions d'UNIX. Il a donc bénéficié de sa diffusion.
Langage de bas niveau
Le langage C est un langage dit de bas niveau qui permet un contrôle fin des performances d'un logiciel et peut être utilisé dans la plupart des applications.
Normalisation et portabilité
Le langage C est normalisé. Il s'exécute de façon presque identique sur toutes les machines. C'est la meilleure approximation d'un langage portable qui existe. Un logiciel développé en langage C sur une machine peut être compilé et exécuté avec un minimum d'effort sur la plupart des ordinateurs existants. La portabilité du langage C est un avantage économique considérable pour un développeur de logiciel.
Interface hommemachine
La plupart des logiciels existants offrent une interface avec le langage C : système d'exploitation, système de gestion de bases de données, systèmes de fenêtrage, tableurs, pour ne citer que les plus importants. En outre, de nombreux outils de développement existent.
Pour un développeur de logiciel, la portabilité est le critère le plus important, suivi de l'existence d'outils de développement.
Algorithmique élémentaire
Introduction
Le mot algorithme est dérivé du nom du mathématicien Persan Mohammed ibn Mûsâ alKhoârizmî à qui l'on doit un traité d'arithmétique : règles de restauration et de réduction.
Un calcul effectifXE "calcul effectif" est une suite d'opérations élémentaires que l'on peut, au moins théoriquement, en disposant de suffisant de temps et de papier, effectuer à la main.
Un problème calculatoireXE "problème calculatoire" est une relation binaire entre un ensemble d'entrées (input) et un ensemble de sorties (output). Il faut donc clairement identifier les données et les résultats que l'on souhaite obtenir.
Un algorithmeXE "algorithme" est une méthode effective de calcul qui permet de résoudre un problème calculatoire donné. Il est important d'en définir précisément la notion pour utiliser à bon escient la puissance des outils mathématiques et les classifier.
Mise au point préalable et preuve d'un algorithme
Les points essentiels pour mettre au point un algorithme sont les suivants :
Nécessité d'analyser le problème préalablement à sa programmation.
Formalisation de l'énoncé.
On peut à ce moment là seulement définir l'algorithme pour obtenir les résultats recherchés.
Robustesse
Il doit être robuste en ce sens qu'il doit fonctionner quelles que soient ses données. Tous les cas doivent avoir été prévus de telle sorte qu'il existe toujours un traitement correspondant à la situation du problème (toujours particulier) à résoudre.
Preuve de l'algorithme
Il faut au moins vérifier, à défaut de prouver théoriquement, que l'algorithme choisi donne la solution théorique et définir, préalablement au passage sur ordinateur, un jeu complet d'essaisXE "jeu d'essais" devant représenter l'ensemble des cas possibles. Cette dernière étape est, en principe, la plus rapide car l'écriture du programme doit être ramenée à une simple traduction de l'algorithme dans le langage de programmation retenu.
Transcription du problème sous une forme calculable
L'algorithme posé en langage naturel doit être transcrit dans un langage de programmation, de préférence évolué.
Le compilateur ou l'interprète de commandes permet de traduire le problème en langage machine, selon le type du langage choisi, interprété ou compilé.
Complexité
La complexité d'un problème représente le nombre d'opérations nécessaires à sa résolution. Elle devra avoir été évaluée de telle sorte que l'on puisse déterminer à priori le temps de calcul.
Certains problèmes ont des solutions théoriques inexploitables. Par exemple au jeu d'échecs, un ordinateur peut parfaitement battre le champion du monde dans la mesure où il peut faire, de façon itérative, l'inventaire de toutes les solutions, en ...3 siècles de calcul pour les ordinateurs les plus performants actuellement.
L'algorithme choisi sera donc un compromis entre sa complexité et sa difficulté de mise en œuvre. Souvent, les algorithmes les plus simples sont les plus efficaces.
Exemple
La résolution d'un système d'équation par la méthode de Cramer nécessite un temps de calcul très important puisque le calcul d'un déterminant d'une matrice carrée d'ordre n par cette méthode nécessite n! opérations. L'inversion d'un système linéaire par cette méthode nécessite donc 0((n+1)!) opérations. Dès que n est "suffisamment" grand, le nombre d'opérations de cette méthode devient rédhibitoire. En comparaison, la méthode de Gauss de résolution de système par triangulation ne nécessite que 0(n2) opérations.
Il faudra donc vérifier que l'algorithme retenu n'est pas stupide.
Problèmes NPcomplets
Il est parfois impossible de calculer le nombre d'opérations nécessaires à la résolution d'un problème. Dans certaines situations, la complexité d'un algorithme n'est pas polynomiale ce qui conduit à de nouvelles classes de problèmes : les problèmes NPcompletsXE "problème NP-complet".
Comportement asymptotique
L'analyse de la performance des algorithmes détermine les ressources matérielles nécessaires à leur exécution : temps de calcul, mémoire, nombre d'accès disque pour des algorithmes de gestion de bases de données opérant sur de grandes quantités d'informations.
Comportement asymptotique
L'analyse des algorithmes étudie leur comportement asymptotique en fonction d'un petit nombre de paramètres caractéristiques de la taille de leurs entrées. Pour un algorithme de tri, un seul paramètre suffit : le nombre d'éléments à trier. Dans le cas d'un graphe, on en utilise souvent deux : son nombre de sommets et son nombre d'arêtes.
Voici trois types d'analyse asymptotique : l'analyse du cas pire, l'analyse en moyenne, et l'analyse amortie. Dans tous les cas, on recherche une borne supérieure de la forme O(f(n)), où f est le plus souvent un polynôme en n ou une fonction logarithmique en log n.
L'analyse du cas pireXE "analyse du cas pire" consiste à déterminer une borne supérieure au temps d'exécution d'un algorithme.
L'analyse en moyenneXE "analyse en moyenne" consiste à déterminer une borne supérieure au temps d'exécution moyen d'un algorithme. Elle suppose la définition d'un espace de probabilités sur l'ensemble des entrées de l'algorithme pour une taille d'entrées donnée. Ses résultats dépendent du choix de l'espace de probabilités.
L'analyse amortieXE "analyse amortie" permet d'obtenir des résultats en moyenne sans hypothèse probabiliste. Elle consiste à déterminer une borne supérieure au temps d'exécution d'une séquence d'opérations algorithmiques dont le temps d'exécution moyen est obtenu en divisant le temps total par le nombre d'opérations.
Algorithmes presque toujours corrects
Un algorithme probabiliste joue aux dés : il prend des décisions en tirant des nombres au hasard, et produit un résultat correct avec une probabilité arbitrairement proche de 1, mais non égale à un. Ce concept permet d'obtenir efficacement de très grands nombres premiers.
Enoncés de problèmes classiques
Recherche d'une valeur dans un tableau
Enoncé du problème
Entrées
A, un tableau d'entiers, contenant n éléments, notés (A[0],...,A[n-1]); X, un entier;
Sortie
Recherche, s'il existe, du plus petit entier positif i tel que A[i] =  X; sinon n.
Exemple d'algorithme
Tous les éléments du tableau sont examinés jusqu'à ce qu'un élément A[i] égal à X soit trouvé. Le résultat est la première valeur de i pour laquelle A[i] =  X, ou n si aucun élément de A n'est égal à X.
Cet algorithme est optimal si aucune information sur le contenu de A n'est connue. Par contre, si les éléments de A sont rangés en ordre de croissant, la recherche peut s'effectuer beaucoup plus efficacement, avec un temps proportionnel à log n. En voici une réalisation en C :
int recherche_element_tableau(const int a[], int n, int x)
// tableau a[], dimension n, élément recherché x
{int i;
for (i =  0; i  0 alors aller_à impression
sinon x =  x
is
impression : imprimer x
Exemple2 : Résolution d'une équation du second degré
On se donne a,b,c réels. On cherche x solution de l'équation ax2 + bx + c = 0. La solution est bien connue. Soit delta =  b2  4ac.
(Notation racine : rac).
si delta SYMBOL 179 \f "Symbol" 0 alors
EMBED Equation  is
si delta 
FinFaire
Exemple 1
Calcul de exp(x)
EMBED Equation  =  EMBED Equation 
Le calcul à l'infini étant impossible, il faut définir ici un test d'arrêt. Soit
EMBED Equation 
Le calcul est arrêté dès que EMBED Equation , SYMBOL 101 \f "Symbol" fixé.
Algorithme
Initialisation
Tant que d > SYMBOL 101 \f "Symbol" faire
calcul de Sn+1
calcul de d =  EMBED Equation 
FinFaire
Problème
Que se passe til si l'algorithme ne converge pas et que le test d'arrêt n'est pas vérifié (d n'est jamais  epselon; // précision du calcul

int factorielle(int); // prototype (ou maquette), retour entier, 1 argument entier

double somme=0;
double valeur;

// initialisation de la boucle
int n=0;
valeur=1./factorielle(n); // appel


// boucle Tant que (condition) Faire
// .....
// FinFaire

while ((valeur > epselon) && (n  n alors Fini
sinon
P(x,i+1) =  x*P(x,i)
i =  i+1
aller_à Boucle
is
Initialisation : P(x,1) =  x
Exercice commenté : le problème du drapeau hollandais
Soit (a1,...,an) une suite d'entiers naturels, dans un ordre quelconque.
Il faut la réordonner de la façon suivante :
on classe à gauche tous les entiers de la liste congrus à 0 modulo 3,
on classe à droite tous les entiers de la liste congrus à 2 modulo 3,
on classe "au milieu" tous les entiers de la liste congrus à 1 modulo 3.
Hypothèse de récurrence et notations
Soient :
i l'indice du 1er élément congru à 1 mod 3,
j l'indice de l'élément courant, que l'on va trier,
k l'indice du 1er élément congru à 2 mod 3.
Avant le tri, à l'étape j, on est dans la situation suivante :
i1 nombres congrus à 0 modulo 3 sont triés, en place,
ji nombres congrus à 1 modulo 3 sont triés, en place,
nk+1 nombres congrus à 2 modulo 3 sont triés, en place.
tableau (SYMBOL 186 \f "Symbol" 0, SYMBOL 186 \f "Symbol" 1, x, ,SYMBOL 186 \f "Symbol" 2 ...)
indice 1 i j k n
états triés triés non triés triés
Soit r =  reste de la division de aj mod(3) =  mod(aj, 3).
1ère analyse
si r =  1 alors aj est à sa place is
si r =  2 alors permuter (aj, ak1) is
si r =  0 alors permuter (ai, aj)is
Méthode à utiliser
1) Proposer
une hypothèse de récurrence,
une situation générale,
un invariant de boucle.
Cette hypothèse est de la forme : on a fait une partie du travail. C'est la phase constructive.
2) Voir si c'est fini
si j =  k alors FINI is
3) Se rapprocher de la solution en préservant l'hypothèse de récurrence;
On considère aj, nouvel élément de la liste. Il y a 3 situations à évaluer :
(i) r =  1 : l'élément est à sa place.
si r =  1 alors j =  j+1; SUIVANT is recommencer en tête de boucle
// l'hypothèse de récurrence reste vérifiée puisque l'on a rien fait
(ii) déplacer l'élément
a) r =  0 : dans ce cas, on permute (ai, aj) . Ainsi, on classe aj sans perturber le tri.
SYMBOL 186 \f "Symbol" 0 SYMBOL 186 \f "Symbol" 1 1 SYMBOL 186 \f "Symbol" 2
1 i j k n
Il faut rétablir l'hypothèse de récurrence en incrèmentant i et j. Donc
si r =  0 alors ech(ai, aj); // modifie l'hypothèse de récurrence
i =  i+1; j =  j+1; SUIVANT // rétablit l'hypothèse de récurrence
is
b) Dernier cas : r =  2
On procède comme dans le cas précédent : on échange ak1 inconnu avec aj connu.
ech(ai, ak1); k =  k1
Il reste à initialiser le processus
Les valeurs initiales à choisir doivent respecter l'hypothèse de récurrence. Il faut vérifier les conditions intiales. Le nombre d'éléments en place au départ est tel que :
i-1 = 0 SYMBOL 222 \f "Symbol" i = 1
j-i = 0 SYMBOL 222 \f "Symbol" j = i = 1
n-k+1 = 0 SYMBOL 222 \f "Symbol" k =  n+1
Remarques
a) A chaque pas de boucle : d(j,k) diminue de 1.
b) Le nombre d'échanges est inférieur à n par cette méthode.
c) Il faut rechercher une bonne hypothèse de récurrence.
d) Il ne pas forcément rechercher la meilleure.
e) Autre méthode : boucle TANT QUE
Le programme final obtenu est le suivant :
Initialisation
k =  n+1; i =  1; j =  1
Tri
Tant que j SYMBOL 185 \f "Symbol" k
Faire
r =  mod(aj,3)
si r =  1 alors j =  j+1; is // aj est à sa place donc au suivant
si r =  2 alors permuter (aj, ak1); k =  k1; is // permuter ak1, aj
si r =  0 alors permuter (aj, ai); i =  i+1; j =  j+1 is
FinFaire
Cas des boucles imbriquées
Supposons que l'on ait deux boucles imbriquées de la forme suivante :
Pour i =  1 à n faire
pour j =  1 à p faire
si  alors sortir de la boucle 2 is
FinFaire 2
FinFaire 1
On écrira :
sortir de la boucle 2 par exit 2.
Bibliographie du présent chapitre
Premières leçons de programmation : J. ARSAC - 1980 CedicNathan
The science of programming : DIJKSTRA - 1981 Digue
PASCAL  Manuel de l'utilisateur : Kathleen JENSEN  Niklaus WIRTH
The art of programming  Donald Knuth (1968)
Some notes on structure programming  Edger Dijkstra
A discipline of programming  Edger Dijkstra
The science of programming  D. Gries (1981)
Le langage C : Kernighan & Ritchie (1988)
Concepts de base des Langages Orientés Objet et langage C
Généralités
La couche objet XE "couche objet"  constitue une abstraction XE "abstraction"  entre l'implémentation des applications et leur utilisation, apportant ainsi un meilleur confort de programmation.
Elle intègre le concept traditionnel de modularité XE "modularité" .
L'encapsulation des données XE "encapsulation des données"  leurs garantit une meilleure protection donc une plus grande fiabilité des programmes.
Philosophie objet
L'analyse des problèmes se présente d'une manière plus naturelle si l'on considère séparément les données et leurs propriétés :
les données constituent les variables XE "variables" ,
les propriétés les opérations XE "opérations"  qu'on peut leur appliquer.
De ce point de vue, les données et le code sont logiquement inséparables, même s'ils sont gérés dans différentes régions de la mémoire.
Ces considérations conduisent à la définition d'un objet XE "objet"  : ensemble de données sur lesquelles des procédures, appelées méthodes XE "méthodes" , peuvent opérer XE "opérer" . La programmation d'un objet étant réalisée à partir de ses données et méthodes, elle semble plus logique que la programmation procédurale les méthodes étant partagées et les données séparées.
Classes
Définitions
Objet
Un objet XE "objet"  est un "paquet" logiciel constitué d’un ensemble de procédures appelées méthodes XE "méthode"  et de données associées.
Ces objets peuvent être définis et gérés indépendamment les uns des autres.
Messages
Les objets peuvent échanger des informations sous forme de message que le langage Simula XE "Simula"  définit comme le résultat de l'application d'une méthode opérant sur un objet. L'objet à l'origine du message XE "message"  en est l'émetteur XE "émetteur"  et l'objet destinataire le récepteur XE "récepteur" .
Classe
Une classeXE "classe" est constituée d'un ensemble d'objets appelés instances, dotés de propriétés communesXE "instance " représentées selon à un modèle abstrait XE "modèle abstrait" .
L'instanciationXE "instanciation" est une relation d'appartenance d'un objet à une classe donnée. Chaque instanciation provoque une allocation de mémoire XE "allocation de mémoire"  dont l'initialisation est réalisée par une méthode appelée constructeur XE "constructeur" . Lorsqu'elle est détruite, une méthode conjuguée est exécutée : le destructeur XE "destructeur" . Le programmeur peut redéfinir ses propres constructeurs et destructeurs.
La classe définit la structure des données, appelées champs XE "champs" , variables d'instance, XE "variables d'instance"  ou données membresXE "données membres" de la classe (aspect statique) dont seront constitués les objets correspondants.
Les opérations sur les instances sont réalisées par les méthodesXE "méthode" ou fonctions membresXE "fonction membre" de la classe (aspect dynamique).
Héritage
Définition
L'héritageXE "héritage" permet de transmettre les propriétés d'une classe (la classe mèreXE "classe mère" ou classe de baseXE "classe de base") à une autre classe (classe filleXE "classe fille" ou classe dérivéeXE "classe dérivée") ce qui permet la réutilisation par la classe fille des fonctions et/ou des données membres de la classe mère accessibles.
Hiérarchie de classes
Les classes peuvent être organisées selon un modèle arborescent pour intégrer des cas de plus en plus particuliers au modèle générique de base.
Classes virtuelles (ou abstraites)
Une classe virtuelle XE "classe virtuelle"  est une classe sans possibilité d'instanciation d'objet, créée pour définir les données membres et les méthodes associées qui s'appliqueront à des classes de plus bas niveau dans la hiérarchie de classe XE "hiérarchie de classe" .
Approche orientée objet, données abstraites et encapsulation
Types abstraits de données
Approche orientée objet
Les logiciels orientés objet modélisent un système qui se veut une meilleure représentation du monde réel.
Types abstraits
La plupart des langages de programmation permettent au programmeur de définir ses propres types de données abstraites, en complément des types prédéfinis. Les langages orientés objets permettent en outre d'utiliser les opérateurs classiques sur ces données abstraites par surcharge XE "surcharge" .
De nouveaux types abstraits sont définis par création de nouvelles classes.
Extension de la notion de type du langage C en langage C++
La couche objet XE "couche objet"  constitue l'apport essentiel du langage C++ au langage C.
En langage C++, les notions de type et de classe sont identiques, les notions intégrées au langage C++ ayant transformé en classe le typage XE "typage"  traditionnel des données du langage C.
Le programmeur peut définir de nouvelles classes XE "classes"  donc de nouveaux types.
Exemple
Les types prédéfinis char, int, double, etc. représentent l'ensemble des propriétés des variables de ce type et en constituent la classe avec les opérateurs arithmétiques comme méthodes. L'addition devient un opérateur pouvant opérer sur des instances de la classe entier retournant un objet de la classe entier.
Utilisateur et programmeur
Les règles d'accès aux objets doivent être différentes pour l'utilisateur et le programmeur car il y a une distinction entre l'utilisation d'un objet et son implémentation XE "implémentation"  :
l'utilisateur d'un objet n'a pas à connaître sa représentation interne XE "représentation interne" ; pour lui, seul compte son comportement XE "comportement"  (principe de la boîte noire).
Le programmeur ne peut ignorer la façon dont une instance d'un type donné est représentée en binaire car la plage des valeurs possibles est essentielle. Ainsi, un mauvais choix de type de données abstraites à conduit au crash du premier vol de qualification du lanceur Ariane 5.
Encapsulation des données
Les méthodes autorisées constituent l'interface d'accès XE "interface d'accès"  entre l'utilisateur et les instances ce qui masque leur implémentation, donc les protège et améliore la fiabilité.
Les avantages sont immédiats :
l'utilisateur ne risque pas de provoquer des erreurs d'exécution par modification des données,
d'interface d'accès standard, l'objet est réutilisable dans un autre programme,
le programmeur peut modifier l'implémentation interne de l'objet sans réécrire tout le programme, les méthodes utilisées devant conserver les mêmes identificateurs et arguments. En cas d'erreur, seules ces dernières doivent être vérifiées.
Encapsulation
Les logiciels orientés objet sont conçus par assemblage de différents modules indépendants dans lesquels les données et les comportements sont encapsulés (encapsulation). XE "encapsulation" 
L'encapsulation encourage la dissimulation d'informations car le programmeur ne peut accéder à une instance qu'au travers des méthodes autorisées ce qui protège les données des objets extérieurs.
L'encapsulation permet de limiter les modifications au seul objet concerné.
Les types prédéfinis des langages C ou Pascal garantissent l'abstraction et l'encapsulation des données prédéfinies (par exemple le type float en C). Par contre, la complexité de la grammaire de ces langages ne permet pas ou n'incite pas le programmeur à définir des types utilisateur garantissant ces mêmes propriétés.
Initialisation des données
En langage C, les règles d’initialisation des variables sont complexes voir confuses. Ainsi, les variables statiques sont par défaut toujours initialisés, les variables automatiques non.
Ces règles sont appliquées sur des tableaux de façon fantaisistes par les éditeurs de logiciel ce qui nuit à la portabilité et à la robustesse des programmes.
Constructeur et destructeur
Une méthode d’initialisation, appelée constructeur XE "fonction constructeur" , est définie par défaut ou peut être redéfinie par le programmeur. Elle est toujours appelée implicitement ou explicitement lors de l'instanciation d'une variable de la classe.
La mémoire allouée par un constructeur est toujours récupérée par une méthode de destruction appelée destructeur.XE "fonction destructeur"
Polymorphisme, surcharge et généricité
Polymorphisme
On appelle polymorphisme XE "polymorphisme"  la faculté de dissimulation des détails de l'implémentation à travers une interface d’utilisation commune qui simplifie la communication entre objets.
Surcharge
La surcharge d'une fonctionXE "surcharge d'une fonction" permet de donner le même identificateur à plusieurs fonctions réalisant une action similaire sur des objets d'un type différent.
La surcharge d'un opérateurXE "surcharge d'un opérateur" permet d'étendre ses caractéristiques d'origine à des opérandes d'un type différent. C'estXE "surcharge" donc une forme de polymorphisme.
La surchargeXE "polymorphisme" peut s'exécuter en mode :
statique (early binding) : la détermination de la fonction ou de l'opérateur à exécuter est effectué à la compilation.
dynamique (dynamic binding ou late binding) : le choix de la fonction ou de l'opérateur à exécuter est effectué à l'exécution comme avec les méthodes virtuelles.
Exemple de fonction surchargée
Soit la classe des figures géométriques (cercles, carrés, rectangles, trapèzes). La méthode surchargée dessiner opère sur les instances de la classe… et dessiner un cercle est différent de dessiner un carré.
Exemple d'opérateur surchargé
Les opérateurs arithmétiques traditionnels du langage C sont surchargés :
l'opérateur arithmétique + est utilisé sur des opérandes de type int, float, double, etc..
En langage C++, cet opérateur surchargé peut opérer sur des nombres complexes, des matrices, etc.
Généricité
Un (unique) code générique XE "code générique"  peut opérer sur des données de différent type.
Exemple de code générique
Les macros définitions de type fonction du préprocesseur C.
Surcharge et généricité
Il ne faut pas confondre surcharge et généricitéXE "généricité" :
Une fonction surchargéeXE "surcharge" utilise une syntaxe d’appel unique pour traiter différentes implémentations d'une structure de données mais utilise différentes implémentations.
Une fonction générique utilise un code unique pouvant opérer sur des objets de type différent.
Le langage C++ implémente des objets génériques comme les fonctions génériques, les classes génériques, les méthodes génériques et les constantes génériques.
Principes généraux de protection des données
La protection des données dépend de l'application.
Le langage C++ n'offre pas de moyens de contrôle permettant de réaliser n'importe quelle protection. Les principes de base sont les suivants :
la protection contre les accidents de programmation est assurée par le compilateur. Elle n'est pas assurée contre la fraude ou des violations explicites des règles.
L'unité de protection et d'accès est la classe.
Le contrôle d'accès est réalisé à partir des identificateurs des objets et non à partir de leur type.
La visibilité n'est pas contrôlée.
Abstraction et encapsulation en langage C
Nous allons utiliser les concepts de programmation objet en C sur l'exemple suivant : définition d'une structure abstraite de pile et des méthodes associées.
Représentation interne et méthodes
La pile est représentée par un tableau.
La base et le sommet de la pile sont représentés par les deux pointeurs top et pile.
Les méthodes définies sont les suivantes :
la fonction pile_vide réalise l’initialisation de la pile,
la fonction push empile un objet,
la fonction pop dépile un objet.
L’ensemble est codé dans le fichier pile.c qui peut être compilé et édité dans une bibliothèque.
Interface utilisateur
L’interface utilisateur est décrite dans le fichier pile.h.
Premier essai d’implémentation d'un type abstrait en C
Fichier pile.c : définition d'une structure de pile d'entiers et des méthodes associées
/* Représentation de l'objet pile */
#define TAILLE 1024
static int pile[TAILLE];
static int* top=pile;

/* opérations autorisée */
int pile_vide (void){return top==pile;}

int push(int e)
{if (top-pile == TAILLE) return 0;
*top++=e;
return 1;
}

int pop(void)
{if (top!=pile) return *--top;}

void reinit_pile(void) {top=pile;}
Interface avec le programme de l’utilisateur
/* prototypes contenus dans le fichier utilisateur pile.h */
int pile vide(void);
int push(int);
int pop(void);
void reinit_pile(void);
Avantages et inconvénients
+ abstraction et encapsulation des données : on peut modifier l'implémentation (structure de données, corps des méthodes) sans modifier l'interface (prototypes des méthodes),
+ simplicité de l'écriture,
+ efficacité à l'exécution.
- la mémoire est gérée statiquement.
- l'utilisation est très limitée : un seul objet pile étant défini et l'objet abstrait correspondant ne l'étant pas, l'utilisateur ne peut pas instancier d'autres objets du même type. Cette remarque conduit à la modification de l’implémentation suivante.
Deuxième essai d’implémentation d'un type abstrait en C
Deuxième version de l'interface pile.h
typedef struct {int taille; int* base; int* top;} PILE;

/* Opérations autorisées */
void init_pile(PILE *, int);
int pile_vide(PILE *);
int push(PILE*, int);
int pop(PILE*);
void effacer_pile(PILE*);

Fichier pile.c (deuxième version)
#include
#include "pile.h"

void init_pile(PILE * pile, int taille)
{pile->top = pile->base = (int*) malloc((pile->taille=taille) *sizeof(int));}
int pile_vide(PILE *pile)
{return (pile->top == pile->base);}

int push(PILE* pile, int entier)
{if ((pile->top - pile->base) == pile->taille) return 0;
*pile->top++ = entier;
return 1;
}

int pop(PILE* pile)
{if (pile->top != pile->base) return *--pile->top;}

void effacer_pile(PILE* pile)
{free(pile->base);
pile->top=pile->base=0;
pile->taille = 0;
}
Programme d'utilisation
#include "pile.c"
#include

int main(void)
{int i=0;
PILE pile;
/* initialisation non automatique */
init_pile(&pile, 10);

/* utilisation de la pile */
while (push(&pile, i++))
while (!pile_vide(&pile)) printf("%d\n", pop(&pile));

/* destruction non automatique de la pile après utilisation */
effacer_pile(&pile);
}
Avantages et inconvénients
+ efficacité à l'exécution,
+ gestion mémoire dynamique,
+ le type abstrait pile est défini ce qui permet à l'utilisateur d'instancier autant d'objets pile qu'il le souhaite.
- abstraction et encapsulation des données : rien n'empêche l'utilisateur de manipuler la représentation d'un objet pile sans utiliser l'interface.
- simplicité de l'écriture : pointeurs
- initialisation et effacement à la charge de l'utilisateur
Troisième essai d’implémentation d'un type abstrait en C
La prise en compte des dernières remarques conduit à l'implémentation suivante :
Troisième version du fichier pile.h
/* Représentation des données */
typedef void* PILE ;

/* Opérations autorisées */
void init_pile(PILE, int);
int pile_vide(PILE);
int push(PILE, int);
int pop(PILE);
void effacer_pile(PILE*);

Troisième version du fichier pile.c
#include
#include "pile.h"
typedef struct{int taille; int *base; int *top;}pile;

void init_pile(void*a, int t)
{a = malloc(sizeof(pile));
((pile*)a)->top = ((pile*)a)->base = (int*)malloc((((pile*)a)->taille=t)*sizeof(int));
}

int pile_vide(void* a)
{if (((pile*)a)->top == ((pile*)a)->base) return 1; else return 0;}

int push(void* a, int e)
{if ((((pile*)a)->top - ((pile*)a)->base) == ((pile*)a)->taille) return 0;
*((pile*)a)->top++=e; return 1;
}

int pop(void* a)
{if (((pile*)a)->top !=((pile*)a)->base) return *--((pile*)a)->top;}
void effacer_pile(void** a)
{free(((pile*)*a)->base);
free(*a); *a=0;
}
Avantages et inconvénients
++ abstraction et encapsulation des données
+ gestion dynamique de la mémoire
+ le type pile est défini ce qui permet à l'utilisateur d'instancier autant d'objets pile qu'il le souhaite.
-- simplicité de l'écriture
- efficacité à l'exécution : indirection
- initialisation et vidage de la pile à la charge de l'utilisateur.
Conclusion sur les types abstraits en C
Le langage C permet d'encapsuler des données et de définir des types abstraits.
Il ne facilite pas la tâche du programmeur car l'encapsulation nécessite d'utiliser l'indirection d'où une complexité d'écriture.
Tout effort d'abstraction et d'encapsulation en C se traduit par une écriture plus complexe et un ralentissement possible à l'exécution.
Le C++, langage procédural
Introduction
C++ langage de programmation orienté objet
Le langage C++ a été crée par Bjarne StroustrupXE "Bjarne Stroustrup" pour intégrer les concepts de programmation objet dans le langage C à savoir :
puissance des langages orientés objets,
typage basé sur la définition de classes, d'instances et de méthodes,
définition de méthodes constructeur et destructeur,
prise en compte de l'héritage, simple ou multiple,
définition d'objets génériques.
contrôle des erreurs d'exécution possible pour le programmeur à partir de la gestion des exceptions.
Le C++ est un des langages de programmation les plus utilisés actuellement. Très efficace et performant, il est complexe donc quelquefois difficile à interpréter même si la lisibilité des programmes dépend aussi du programmeur. Enfin, ce langage est, avec le C, idéal pour ceux qui doivent assurer la portabilité de leurs programmes sources.
Le langage procédural et fonctionnel C++
Les caractéristiques du langage C++, langage procédural et fonctionnel sont les suivantes :
performances similaires à celles du langage C,
extension des fonctionnalités du langage C comme la transmission par référence, la définition d'arguments par défaut,
portabilité des fichiers sources,
contrôle d'erreur à la compilation basé sur un typage très fort.
Compatibilité C et C++
La syntaxe du langage C++ est compatible sur celle du C tout en évitant d'utiliser certaines de ses fonctionnalités grammaticalement douteuses.
Le langage C++ peut donc être considéré comme un surensemble du langage C, certains programmes C devant être adaptés avec des modifications minimes.
Commentaire
Le délimiteur // XE "//"  permet d'insérer des commentaires dans le programme, en particulier à la droite d’une instruction.
Exemple
int valeur; // Ceci est un entier
Types
Types de base
On retrouve les types de base traditionnels du langage C, avec quelques évolutions :
void;
unsigned char, signed char;
short int, int; long int (unsigned),
unsigned short int, unsigned int; unsigned long int,
float, double, long double (non implémenté);
enum;
Nommage des agrégats
Le nommage des agrégats évite de réutiliser les mots clés struct, class, union lors de l'instanciation des variables de classe.
Exemple
struct complexe {float reel; float imaginaire; };
complexe z; // et non struct complexe z;
Type booléen et énumération
Type booléen prédéfini.
Définition de constante symbolique par énumération avec contrôle de valeur.
Exemple
enum Booleen {FAUX, VRAI }; // différent de l'instruction {VRAI, FAUX};
enum COULEUR {VERT=5, ROUGE, JAUNE=9 };
// ROUGE équivaut à 6 par défaut.
COULEUR couleur = ROUGE; // couleur initialisé à 6.
couleur = -7; // incorrect
Type intégral
char, wchar_t; // caractère, caractère long
short, int, long, enum;
Type flottant
float, double;
Types arithmétiques
Les deux types précédents.
Types dérivés
& XE "&"  opérateur de référence XE "opérateur de référence" ,
* XE "*"  opérateur de déréférenciation XE "opérateur de déréférenciation" ,
[] XE "[]"  tableau XE "tableau" ,
() XE "()"  fonction XE "fonction" ,
const XE "const"  qualification d'un type, d'une variable ou du comportement d'une méthode,
class XE "class" , struct XE "struct" , union XE "union"  types agrégat définis par le programmeur,
.* XE ".*"  sélecteur sur objet membre (donnée ou méthode) XE "sélecteur d'objet membre" ,
-> XE "->"  sélecteur sur pointeur XE "sélecteur sur pointeur" .
Le type void*
Le pointeur générique void* XE "void*"  doit toujours explicitement être converti en un pointeur d'un type non générique.
Saisie et affichage élémentaire en C++
Opérateurs de base
Le langage C++ utilise les flots (streams), très souples, de préférence aux fonctions traditionnelles de la bibliothèque d'entrées/sorties du langage C :
scanf, printf, fscanf, fprintf, sscanf, sprints, gets, puts, fgets, fputs, getchar, putchar, etc…
Quatre flots sont initialisés au démarrage de l'exécution :
cin XE "cin"et l'opérateur associé >>
coutXE "cout" et l'opérateur associé est par définition le délimiteur syntaxique des données à saisir.
Le séparateur des données saisies est représenté par un ou (ou non exclusif) plusieurs caractères d'espacement, de tabulation ou les deux. Le caractère CR (retour chariot) est également autorisé.
Affichage
Le flot coutXE "cout" affiche des données d'un type prédéfini en format libre.
L’éventuel texte d'accompagnement est délimité par deux ".
L'opérateur a >> b; // saisie des variables a et b
cout
 :