Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Conservatoire National des Arts & Métiers Centre associé de Nice Le Raisonnemen

Conservatoire National des Arts & Métiers Centre associé de Nice Le Raisonnement Informatique & La Programmation Informatique - Cycle A Algorithmique & Programmation Jean Demartini 1994 - 1995 - 1996 - 1997 - 1998 - 1999 - 2000 Table des Matières - i - 1. Introduction..................................................................................................................................... 1 2. Les Fonctions................................................................................................................................... 8 2.1 Rappel sur les fonctions ........................................................................................................................ 9 2.2 Les Différentes formes de la définition d’une fonction ........................................................................ 9 2.2.1 Construction d’un domaine ou d’un codomaine....................................................................... 10 2.2.2 Définition en intention .............................................................................................................. 11 2.2.3 Définition en extension............................................................................................................. 12 2.2.4 Techniques de définition........................................................................................................... 12 2.2.5 Egalité de deux fonctions.......................................................................................................... 16 2.3 Composition des fonctions.................................................................................................................. 18 2.4 Techniques de conception................................................................................................................... 19 2.4.1 Abstraction par composition & nommage ................................................................................ 19 2.4.2 Abstraction par généralisation .................................................................................................. 20 2.4.3 Abstraction fonctionnelle & Curryfication ............................................................................... 22 2.4.4 Application d'une fonction à ses arguments & évaluation........................................................ 23 2.4.5 Définition d’un environnement................................................................................................. 24 2.4.6 Evaluation en ordre normal & évaluation en ordre applicatif................................................... 24 2.5 Fonctions d’ordre supérieur ................................................................................................................ 26 2.6 Fonctions «à effets» ............................................................................................................................ 28 2.7 Fonctions & équations......................................................................................................................... 29 2.7.1 Points fixes d'une fonction........................................................................................................ 31 2.7.2 Opérateur de point fixe ............................................................................................................. 32 2.7.3 Résolution d'une équation quelconque...................................................................................... 33 2.7.4 Inversion d'une fonction monotone quelconque ....................................................................... 33 2.7.5 Généralisons un peu (encore ?)................................................................................................. 34 2.8 Fonctions & processus ........................................................................................................................ 34 2.8.1 Récursivité linéaire & itération................................................................................................. 35 2.8.2 Récursivité en arbre .................................................................................................................. 37 2.8.3 Ordre de croissance................................................................................................................... 38 2.9 Mathématique et informatique - Digression........................................................................................ 39 2.9.1 Les nombres de tous les jours ................................................................................................... 40 2.9.2 Fonctions opérant sur les nombres de tous les jours................................................................. 40 2.10 Conclusions......................................................................................................................................... 41 2.11 Exercices ............................................................................................................................................. 41 3. Les Données................................................................................................................................... 49 3.1 Les Nombres booléens ........................................................................................................................ 50 3.1.1 Définition des Constantes booléennes ...................................................................................... 50 3.1.2 Opérations sur les Nombres booléens....................................................................................... 50 3.1.3 La Fonction «si» (notée →) ...................................................................................................... 52 3.2 Les Nombres rationnels....................................................................................................................... 52 3.2.1 Définition du Nombre rationnel................................................................................................ 53 3.2.2 Opérations sur les Nombres rationnels ..................................................................................... 54 3.2.3 Symbole & Citation .................................................................................................................. 55 - ii - 3.2.4 Représentations interne du Nombre rationnel........................................................................... 56 3.2.5 Comparaison de deux nombres rationnels ................................................................................ 57 3.3 Barrières d'abstraction......................................................................................................................... 60 3.4 Qu'est-ce qu'une donnée ?................................................................................................................... 61 3.5 Exercices ............................................................................................................................................. 62 4. Les Structures. .............................................................................................................................. 66 4.1 Structures de données.......................................................................................................................... 66 4.2 La Paire (2-uplet). ............................................................................................................................... 67 4.3 L’Enregistrement (n-uplet).................................................................................................................. 68 4.4 Le Tableau (n-uplet)............................................................................................................................ 70 4.5 Le «Filtrage» et les Fonctions non curryfiées..................................................................................... 71 4.6 La Liste & le Chaînage des Paires ...................................................................................................... 72 4.7 Les Nœuds & les Arbres binaires........................................................................................................ 78 4.7.1 Les Nœuds................................................................................................................................. 78 4.7.2 Les Arbres binaires. .................................................................................................................. 79 4.7.3 Recherche dans un Arbre binaire.............................................................................................. 80 4.7.4 Construction d’un Arbre binaire ............................................................................................... 80 4.7.5 Les Parcours d’un Arbre binaire. .............................................................................................. 81 4.8 Codage de Huffman & utilisation des arbres binaires......................................................................... 82 4.9 Equivalence opérationnelle. ................................................................................................................ 84 4.9.1 Egalité de deux Atomes. ........................................................................................................... 85 4.9.2 Egalité de deux Structures......................................................................................................... 86 4.10 Conclusion........................................................................................................................................... 86 4.11 Exercices. ............................................................................................................................................ 87 5. Eléments de Programmation. ...................................................................................................... 96 5.1 Définir & Programmer. ....................................................................................................................... 97 5.1.1 Application fonctionnelle.......................................................................................................... 97 5.1.2 Abstraction fonctionnelle.......................................................................................................... 97 5.1.3 Données primitives. .................................................................................................................. 97 5.1.4 Structures courantes.................................................................................................................. 98 5.1.5 Formes particulières.................................................................................................................. 98 5.1.6 Un Langage pour s’exprimer, un Langage pour programmer. ................................................. 99 5.2 Le Langage Scheme............................................................................................................................. 99 5.3 Expressions Scheme. ......................................................................................................................... 100 5.4 Nommage & Environnement. ........................................................................................................... 102 5.5 Principaux Objets prédéfinis Scheme................................................................................................ 103 5.5.1 Données Scheme. .................................................................................................................... 103 5.5.2 Paire Scheme. .......................................................................................................................... 103 5.5.3 Liste Scheme. .......................................................................................................................... 104 5.5.4 Vecteur Scheme....................................................................................................................... 106 5.6 lambda : le constructeur de fonctions................................................................................................ 107 5.7 Expressions conditionnelles & prédicats........................................................................................... 108 5.7.1 if et les expressions conditionnelles........................................................................................ 108 5.7.2 Prédicats.................................................................................................................................. 109 5.7.3 Exemples d’utilisation d’expressions conditionnelles............................................................ 109 5.8 quote et citations................................................................................................................................ 109 - iii - 5.9 Equivalence opérationnelle. .............................................................................................................. 110 5.10 Formes dérivées................................................................................................................................. 110 5.10.1 cond et les expressions gardées............................................................................................... 110 5.10.2 let et les extensions de l'environnement.................................................................................. 112 5.10.3 let* et les extensions emboitées. ............................................................................................. 113 5.10.4 letrec et les extensions récursives. .......................................................................................... 114 5.11 Scheme et l’application fonctionnelle. .............................................................................................. 115 5.12 Evaluation des expressions composées............................................................................................. 115 5.13 Formes spéciales. .............................................................................................................................. 117 5.14 Où l’on reparle de define................................................................................................................... 119 5.15 Effets de bord. ................................................................................................................................... 120 5.16 Exercices. .......................................................................................................................................... 121 6. Les Structures mutables............................................................................................................. 126 6.1 Etat & Affectation............................................................................................................................. 127 6.2 Variables d'Etat & Affectation.......................................................................................................... 128 6.3 Egalité & Identité. ............................................................................................................................. 130 6.4 «Prix à payer» pour l'Affectation. ..................................................................................................... 131 6.5 Variables & Environnements - Modèle graphique............................................................................ 133 6.6 Les Structures mutables prédéfinies de Scheme................................................................................ 133 6.7 Quelques structures mutables très utiles. .......................................................................................... 134 6.7.1 La Référence. .......................................................................................................................... 134 6.7.2 La Pile. .................................................................................................................................... 136 6.7.3 La File d'attente....................................................................................................................... 136 6.7.4 Le Dictionnaire. ...................................................................................................................... 137 6.8 Variables, Environnements & autres Considérations........................................................................ 139 6.8.1 Définitions des Fonctions et .................................................................................................. 140 6.8.2 Sémantique d’un Symbole. ..................................................................................................... 140 6.8.3 Sémantique de set!. ................................................................................................................. 141 6.8.4 Sémantique d’une Forme lambda. .......................................................................................... 141 6.8.5 La Fonction . ........................................................................................................................... 141 6.8.6 Sémantique d’une Forme letrec. ............................................................................................. 141 6.9 Exercices. .......................................................................................................................................... 141 7. Représentation des Données abstraites..................................................................................... 145 7.1 Le «Mégateuf Gym Center».............................................................................................................. 146 7.1.1 Cahier des charges .................................................................................................................. 146 7.2 Spécifications générales.................................................................................................................... 146 7.2.1 Fichier-Clients......................................................................................................................... 146 7.2.2 Client....................................................................................................................................... 147 7.2.3 Date ......................................................................................................................................... 147 7.2.4 Adresse.................................................................................................................................... 148 7.2.5 Simulons les Spécifications .................................................................................................... 148 7.3 Spécifications détaillées.................................................................................................................... 150 7.3.1 Fichier-Clients......................................................................................................................... 150 7.3.2 Client....................................................................................................................................... 151 7.3.3 Date ......................................................................................................................................... 152 7.3.4 Adresse.................................................................................................................................... 153 7.4 Le «Mégateuf Gym Center» s'aggrandit ........................................................................................... 153 - iv - 7.4.1 Specifications générales.......................................................................................................... 154 7.5 Spécifications détaillées de la Supervision. ...................................................................................... 155 7.6 Aiguillage par le type........................................................................................................................ 156 7.7 Programmation par Transmission de Messages................................................................................ 157 7.8 Programmation dirigée par les Données. .......................................................................................... 158 7.8.1 Spécifications générales de l’Aiguillage................................................................................. 158 7.8.2 Utilisation de Table dans le Cadre de l’Application............................................................... 158 7.8.3 Spécifications détaillées de Table........................................................................................... 159 7.9 Le «Cycle de Vie d’un Logiciel»...................................................................................................... 160 7.10 Exercices. .......................................................................................................................................... 161 7.11 Annexe : structure «Ensemble»......................................................................................................... 163 8. Objets & Programmation Orientée Objets .............................................................................. 166 8.1 Qu'est-ce qu'un Objet ?...................................................................................................................... 168 8.1.1 Attributs d'un Objet................................................................................................................. 168 8.1.2 Méthodes & Messages d'un Objet........................................................................................... 170 8.1.3 Espèce d'un Objet & Héritage................................................................................................. 174 8.2 Objets-Classe & Objets-Instance ...................................................................................................... 178 8.3 Une Serrure à Code ........................................................................................................................... 180 8.3.1 Spécifications générale du Système de Serrure ...................................................................... 180 8.3.2 Spécifications détaillées.......................................................................................................... 184 8.4 Un petit Coup d'Oeil en Arrière ........................................................................................................ 186 8.5 Exercices ........................................................................................................................................... 188 8.6 Annexes............................................................................................................................................. 191 8.6.1 Constructeur d'Objets.............................................................................................................. 191 8.6.2 Dictionnaire des Attributs & des Méthodes............................................................................ 191 9. Spécifier puis Implémenter........................................................................................................ 194 9.1 Les Eléments de construction d'une Application C........................................................................... 195 9.1.1 .............................................................................................................................Expressions.195 9.1.2 Instructions.............................................................................................................................. 196 9.1.3 Déclarations. ........................................................................................................................... 197 9.1.4 ...........................................................................................................................Blocs de code197 9.1.5 ...........................................................................................................Fonctions & Procédures198 9.1.6 Structures de Données............................................................................................................. 199 9.2 Architecture d'une Application C...................................................................................................... 200 9.3 Processus de Développement d'une Application............................................................................... 201 9.4 Constitution des Paquetages.............................................................................................................. 202 9.5 Typage explicite des Données........................................................................................................... 203 9.5.1 Types de Base. ........................................................................................................................ 204 9.5.2 Les Données simples............................................................................................................... 204 9.5.3 Les Pointeurs........................................................................................................................... 205 9.5.4 Types construits. ..................................................................................................................... 206 9.5.5 Nommage des Types............................................................................................................... 209 9.5.6 Type d'une Fonction................................................................................................................ 209 9.5.7 Forçage du Type...................................................................................................................... 211 9.6 Les Environnements d'une Application C......................................................................................... 211 9.6.1 Règles de Visibilité................................................................................................................. 212 9.6.2 Environnement permanent global d'une Application.............................................................. 213 - v - 9.6.3 Environnement statique local d'un Paquetage......................................................................... 214 9.6.4 Environnements privés d'un Bloc de Code. ............................................................................ 214 9.6.5 Environnement manuel dit «le tas»......................................................................................... 216 9.7 Paquetage de la Paire......................................................................................................................... 218 9.7.1 Spécifications détaillées de la Paire........................................................................................ 218 9.7.2 Interface de la Paire................................................................................................................. 218 9.7.3 Implémentation de la Paire. .................................................................................................... 219 9.8 Paquetage de la Liste......................................................................................................................... 220 9.8.1 Spécifications détaillées de la Liste. ....................................................................................... 221 9.8.2 Interface de la Liste................................................................................................................. 221 9.8.3 Implémentation de la Liste...................................................................................................... 221 9.9 Le Paquetage de la Pile. .................................................................................................................... 222 9.9.1 Spécifications détaillées de la Pile.......................................................................................... 222 9.9.2 Interface de la Pile................................................................................................................... 223 9.9.3 Implémentation de la Pile ....................................................................................................... 223 9.10 Les Procédures C............................................................................................................................... 224 9.11 Transmission de Messages en langage C.......................................................................................... 227 9.12 Récursion terminale & Processus itératif.......................................................................................... 229 9.12.1 Traduction de l'Invariant......................................................................................................... 229 9.12.2 Structures de Boucle. .............................................................................................................. 231 9.13 Le Pré-Processeur C.......................................................................................................................... 232 9.13.1 Intégration de Fichiers. ........................................................................................................... 233 9.13.2 Définition de Constantes......................................................................................................... 233 9.13.3 Définition de Formes spéciales............................................................................................... 233 9.13.4 Traitement conditionnel.......................................................................................................... 234 9.14 Conclusion......................................................................................................................................... 236 9.15 Exercices. .......................................................................................................................................... 236 - 1 - Copyright © Jean DEMARTINI - 1994 - 1995 - 1996 - 1997 1. Introduction Aux temps héroïques, dans les années 50 et 60, l’informaticien était celui qui savait utiliser un ordinateur, essentiellement pour faire des calculs. Son but était presque toujours de trou- ver une méthode de calcul — algorithme mettant en œuvre les organes d’un ordinateur : cir- cuits de calcul, mémoire et organes d’entrée/sortie — décrite sous la forme d’un programme. L’informaticien était un programmeur, ce qui l’amusait beaucoup et l’informa- tique était une forme d’artisanat. Aussi longtemps qu’il n’a pas été possible de récupérer commodément les programmes écrits par d’autres, l’informaticien a été programmeur — il passait son temps à réécrire des programmes — et il a fallut qu’il apprenne à écrire, seul ou avec d’autres des programmes de plus en plus complexes et de plus en plus gros. Pendant longtemps, on a pu croire (ou voulu faire croire) que l’informatique était une scien- ce en soi, celle qui consiste à programmer de façon plus ou moins rationnelle des ordina- teurs ordinateurs1 . Bien entendu, cette vision est aussi naïve que celle qui consiste à croire que uploads/s3/ le-raisonnement-que-amp-la-program-mat-ion-jean-demartini-ebook-french-computers-programming-langage-verified-by-gho.pdf