Tda

Table des matières

Table des matières Introduction aux Types de Données Abstraits Généralités sur la modularité But: Qualité du logiciel Coût de la non qualité Les qualités fondamentales de composants logiciels (modules) Modularité : Principes Modularité : Autour des données ou autour des traitements Mise en œuvre de la modularité

Introduction aux Type de Données Abstrait : TDA Définition Avantages des TDA Inconvénients des TDA Programmation à l'aide des TDA Concevoir correctement les TDA Conception d'un TDA Exemple : Pile Spécification Représentation et implantation Types de base Les types scalaires Les types discrets Les entiers Les types énumérés Fonctions prédéfinies sur les types discrets Représentation du type booléen comme un TDA Représentation du type entier comme un TDA Les réels Représentation en virgule flottante Représentation en virgule fixe Représentation du type réel sous forme de TDA Conversion de type Les types composés Les structures statiques Structures cartésiennes simples http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...lic_html/pages_html/TDA/TDA_TableDesMatieres.html (1 of 4) [25-10-2001 20:46:08]

Table des matières

Représentation statique du type Ensemble en C Résumé Les structures dynamiques Les pointeurs Ramasse miettes Chaînage des trous Définition d'un nouveau TDA Vue interne et vue externe Spécification de la vue externe Opérations primitives Exemple : Spécification du type Fraction Définition structurelle du type Fraction Définition logique (abstraite) du type Fraction Quelle sorte de définition utiliser ? Implantations alternatives du type Fraction Opérations du type Fraction Programmation par contrat Application de la programmation par contrat à l'exemple des Fractions Types de Données Abstraits Classiques TDA Pile (Stack) Spécification du TDA Pile LIFO Implantation statique du TDA Pile Pile bornée (bounded Stack) Pile : Représentation par tableau en ADA Spécification 1 : sans abstraction de données Spécification 2 : avec abstraction de données Spécification 3 : Possibilité de définir la taille de la Pile Code du TDA PileEntiers en C avec abstraction des données TDA Pile défini comme une machine abstraite en ADA TDA PileEntiers défini comme une machine abstraite en C Code de Pile statique en JAVA Implantation dynamique du TDA Pile Implantation dynamique en ADA Implantation dynamique en C Implantation dynamique en JAVA Utilisation du TDA Pile Exemple - vérificateur de parenthèses Evaluation des expressions arithmétiques postfixées Exemple d'algorithme utilisant des piles : le Quick Sort ( non récursif ) TDA Files (Queues) Spécification du TDA Files http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...lic_html/pages_html/TDA/TDA_TableDesMatieres.html (2 of 4) [25-10-2001 20:46:08]

Table des matières

FIFO Implantation statique du TDA File Représentation statique du TDA File en ADA Représentation linéaire Représentation circulaire Représentation statique du TDA File en C Représentation statique du TDA File en JAVA Représentation statique du TDA File en C++ Implantation dynamique du TDA File Représentation dynamique du TDA File en ADA et en C Représentation dynamique du TDA File en Java Utilisation du TDA File TDA Listes (List) Listes linéaires Listes Triées Implantation semi-dynamique (Curseurs) Implantation semi-dynamique en ADA Implantation dynamique Implantation dynamique en C Sentinelle et double chaînage Implantation récursive du TDA Liste Graphes (Graphs) Graphes non orientés Graphes orientés simples Définitions Spécification du TDA GrapheOrienté simple Utilisation des Graphes Représentation d'un graphe simple orienté Matrice booléenne associée (ou matrice d'adjacence) Matrice d'incidence aux arcs Première solution : Liste de successeurs Deuxième solution : Liste de sommets et de successeurs Troisième solution : Structures homogènes Parcours de Graphes Parcours en profondeur Parcours en largeur Détection d'un circuit Tri topologique Arbres Terminologie Spécification du TDA ArbreBin (Type Arbre Binaire (2-aire)) Utilisation des Arbres http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...lic_html/pages_html/TDA/TDA_TableDesMatieres.html (3 of 4) [25-10-2001 20:46:08]

Table des matières

Parcours d'Arbre Parcours en profondeur d'abord Représentation des Arbres Arbre Binaire : Représentation chaînée Implantation dynamique d'ArbreBin en ADA Implémentation dynamique d'ArbreBin en C Arbre n-aire : Représentation chaînée Arbre Binaire : Représentation semi-dynamique ArbreBinaire en largeur : représentation dans un tableau Arbre Binaire de recherche Implantation dynamique d'un arbre de recherche en ADA Utilisation d'un Arbre Binaire de Recherche pour trier un tableau Arbre équilibré Isomorphisme liste-arbre

Accueil / Equipe Synthèse d'Images / IRIT / UPS / FRANCE / [email protected]

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...lic_html/pages_html/TDA/TDA_TableDesMatieres.html (4 of 4) [25-10-2001 20:46:08]

TDA Introduction

Introduction aux Types de DOnnées Abstraits Généralités sur la modularité But: Qualité du logiciel Qualités fondamentales : Réutilisabilité, fiabilité… Difficultés : Mettre en œuvre une vraie réutilisabilité. Gestion correcte des erreurs. ● 30 % du coût d'un logiciel passé en développement · 60% en réflexion initiale, · 15% codage et · 25% en tests et mise au point, ● 70 % en maintenance · 41% modifications demandées par les utilisateurs · 21% correction de bugs (urgents et routine) · 17,5% prise en compte de changements de formats dans les données · 9% correction de routine · 6% prise en compte de changements matériels · 5,5% documentation · 4% amélioration de l'efficacité · 3,5% divers

Coût de la non qualité : ●

●

●

●

●

Logiciel de commande et de contrôle de l'US air force : · Prévision initiale : 1,5 millions de $ · Coût total : 3,7 millions de $ Système de réservation United Airlines · Abandon après 56 millions de $ dépensés Problèmes rencontrés dans des logiciels de gestion : · Envoi de 20 000 journaux à la même adresse (sélecteur d'adresse bloqué), · Cartes de crédits systématiquement avalées (désaccord entre 2 calculateurs sur les années bissextiles) · Crack à la bourse de Londres (surcharge du système) Problèmes rencontrés dans des logiciels temps réels embarqués : · Avion F16 Déclaré sur le dos après le passage de l'équateur, · Mission Vénus : passage à 500 000 km au lieu de 5000 km (remplacement d'une virgule par un point), · Sonde sur Mars : perdu après le passage derrière Mars (altitude calculée en miles par une partie des développeurs et en km par une autre), · Exocet répertorié comme missile ennemi dans la guerre des Malouines · Fusée Russe pointant Hambourg au lieu du pôle nord (erreur de signe et donc de 180° du système de navigation), Problèmes rencontrés dans des logiciels temps réels sols : · Déclenchement d'un système de détection de missiles Américains (lune à l'horizon considérée comme OVNI), · Inondation de la ville de Colorado River ( erreur de temps d'ouverture du barrage).

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel/...t/public_html/pages_html/TDA/TDA_Introduction.html (1 of 8) [25-10-2001 20:46:43]

TDA Introduction

Les qualités fondamentales de composants logiciels (modules) Aptitude d'un produit logiciel à remplir exactement ses fonctions, définies par le cahier des charges et la spécification. Aptitude à fonctionner dans des conditions éventuellement anormales. Reprise d'erreurs et Fiabilité fonctionnement dégradé. Aptitude d'un composant logiciel à protéger ses données contre des accès extérieurs non Encapsulation (intégrité) autorisés. Facilité avec laquelle un composant logiciel se prête à une modification ou à une extension des Extensibilité fonctions qui lui sont demandées. Aptitude à être réutilisé, en tout ou partie, dans de nouvelles applications.Eviter dans le développement d'une application la re-conception et la ré-écriture d'algorithmes classiques de Réutilisabilité tri, recherche, lecture-écriture, comparaisons, parcours … qui reviennent sans cesse sous des formes légèrement différentes : en factorisant, une bonne fois pour toute, tout ce qui peut l'être. Facilité avec laquelle un composant logiciel peut être associé à d'autres pour construire une Compatibilité application. Facilité avec laquelle un produit peut être transféré sur différents environnements matériels et Portabilité logiciels. Facilité d'apprentissage, d'utilisation, de préparation des données, de correction des erreurs, Facilité d'emploi d'interprétation et d'utilisation des résultats Vérifiabilité Facilité de préparation de la recette et de la validation (jeux d'essais). Utilisation optimale des ressources matérielles (processeurs, mémoire interne et externe, Efficacité dispositifs d'entrée/sortie, etc.). Validité

Modularité : Principes Principes à respecter : Le problème doit être décomposé en modules indépendants : division du travail et simplification du problème au niveau de chaque module. Les modules produits doivent pouvoir être facilement combinés les uns avec les autres pour construire de nouvelles applications éventuellement dans des environnements très variés. Les modules développés dans la cadre d'une application doivent être compréhensibles séparément (indépendamment les uns des autres) (commentaires explicites, spécification bien pensée, lisibilité du code, sous-programmes bien ciblés et courts, etc.). L'application doit être conçue de telle façon qu'un changement mineur de spécification aura pour résultat des changements très limités et bien contrôlés au niveau des modules. · Principe N°1 : ne pas utiliser de constantes "en dur" dans le code. Chaque module qui effectue un traitement susceptible de produire une erreur doit le plus possible en assurer le traitement. · L'opération qui effectue une saisie clavier doit assurer que l'entrée tapée par l'utilisateur est correcte avant de la transmettre à l'appelant.

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel/...t/public_html/pages_html/TDA/TDA_Introduction.html (2 of 8) [25-10-2001 20:46:43]

TDA Introduction

Chaque module doit correspondre avec aussi peu de modules que possible :

Deux modules qui communiquent s'échangent aussi peu d'informations que possible, juste le nécessaire. Si deux modules communiquent, ceci doit être évident au coup d'œil (paramètres explicites, commentaires, documentation…). Encapsulation : masquage de l'information. Tout accès à une donnée d'un module doit être protégé. Une modification d'une donnée doit être effectuée uniquement par le module dans lequel est défini cette donnée (pas de modification d'une variable d'un module dans du code extérieur au module. Exemple de définition d'un module utilisé par un autre module :

Modularité : Autour des données ou autour des traitements ? Un programme effectue des actions sur des données. La structure du programme peut donc être fondée sur les actions ou sur les données. - Décomposition classique par les actions (traitements) (décomposition fonctionnelle en sous-programmes). OU - Décomposition par les données (modules, classes). NON à la décomposition fonctionnelle descendante : La décomposition descendante exige qu'on commence par définir précisément et rigoureusement le but à atteindre (c.à.d. le sommet de la décomposition arborescente). Exemple : Pour trier les personnes dans la commune, le maire définit un critère : Tri d'un les personnes selon leur âge puis selon le nom : http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel/...t/public_html/pages_html/TDA/TDA_Introduction.html (3 of 8) [25-10-2001 20:46:43]

TDA Introduction

fonction trierPersonnesSelonAge (t : TableauDePersonnes) i, j, deb, fin : integer; début pour i := t'first; i < t'last; i++ faire pour j := t'succ(i); j <= t'last; j++ faire si t(i).age > t(j).age alors permuter (t(i), t(j)); fsi fpour fpour deb := t'first; tq deb <= t'last faire // rechercher l'indice de la première personne d'une tranche d'age fin := deb; tq t(fin).age = t(deb).age faire j++; ftq fin--; pour i := deb; i < fin; i++ faire pour j := i; j<= fin; j++ faire si t(i).nom > t(j).nom alors permuter (t(i), t(j)); fsi fpour fpour deb := fin+1; ftq fin

● ● ●

●

●

Ce sous-programme sera difficilement utilisable ailleurs. il faudrait avoir le même type de tableau de personnes et le même besoin de trier selon l'age puis le nom dans une tranche d'age. Les choix initiaux conditionnent a priori les suivants. Le système obtenu est fait sur mesure à l'usage exclusif de LA fonction qu'il fallait réaliser. Chaque fonction est faite sur mesure pour répondre aux besoins spécifiques de celle du dessus (généralité ? réutilisabilité ??). Si les spécifications de la fonction requise (sommet de l'arbre) viennent à changer, toute l'arborescence s'écroule, sciée à la racine ! La notion de décomposition procédurale descendante est par principe contraire à la notion de réutilisabilité.

Les vrais systèmes logiciels n'ont pas de sommets. OUI à la composition ascendante de composants logiciels : ● Au lieu de partir de LA fonction à réaliser, partir des objets du système (avions, employés, piles, capteurs, comptes bancaires, tableaux, moteurs, souris, arbres, …) en créant un module par type d'objets qui gère la structure de chaque type d'objets et les services qu'il est capable d'offrir. ● Un type d'objet ainsi modélisé est stable dans le temps et peut être utilisé pour développer une application donnée. ● Compatibilité : L'utilisation d'opérations développées dans un module gérant un type d'objets assure que ces opérations sont compatibles entre elles. Exemple : les opérations stocker (x : X, index : integer, table T) et

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel/...t/public_html/pages_html/TDA/TDA_Introduction.html (4 of 8) [25-10-2001 20:46:43]

TDA Introduction

●

rechercher (index : integer, table : T) return X agiront bien sur la même donnée stockée dans un type de table donné. Réutilisabilité : Il faut pouvoir réutiliser des structures de données entières et non pas seulement les opérations.

Les systèmes logiciels sont caractérisés au premier abord par les données qu'ils manipulent et non par LA fonction (généralement instable) qu'ils assurent pour un temps. Ne pas demander ce que fait le système : Demander SUR

QUOI il agit !

Pour décrire les données, ne pas considérer une seule donnée mais une classe de données équivalentes : un Type de Données. Un Type de Données doit être décrit par le comportement des données (leurs propriétés externes) c'est à dire les services que le Type offre à l'extérieur, ce qui nous amène à la notion de :

Types de Données Abstraits Mise en œuvre de la modularité - Chaque module est connu de l'extérieur au travers d'une interface publique. Cette interface propose à un client extérieur tous les services offerts par le module (opérations publiques). Le reste des données et opérations du module constitue l'ensemble de ses "secrets" et doit être inaccessible de l'extérieur.

Un module correspond à une unité de compilation :

En C

un module est construit à partir : ● d'un fichier nomModule.h qui contient la spécification des données et la signature des opérations (sous-programmes) visibles depuis l'extérieur => INTERFACE, ● d'un fichier nomModule.c qui contient le code des opérations (sous-programmes) déclarées dans nomModule.h et le code des opérations (sous-programmes) non visibles depuis l'extérieur => CORPS.

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel/...t/public_html/pages_html/TDA/TDA_Introduction.html (5 of 8) [25-10-2001 20:46:43]

TDA Introduction

un module est construit à partir d'un paquetage (package) comprenant les deux parties suivantes : ● la spécification du package qui contient les données et signatures des opérations (sous-programmes) visibles depuis l'extérieur => INTERFACE, En ADA ● · le corps du package (body) qui contient le code des opérations (sous-programmes) déclarées dans la partie spécification du package et le code des opérations (sous-programmes) non visibles depuis l'extérieur => CORPS. un module est implanté par une classe qui décrit les attributs (données) et les méthodes En JAVA (sous-programmes) accessibles ou non accessibles depuis l'extérieur.

Exemple : Module Point2D En ADA : package Point2D_P is -- Attention type non protégé type Point2D is array (1..2) of float; -- Le Point est créé en (0,0) PROCEDURE creerPoint (p : out Point2D); -- Le point est déplacé de (x,y) PROCEDURE changerValeur ( p : in out Point2D; x, y : float); FUNCTION abscisse(p : Point2D) return float; FUNCTION ordonnee(p : Point2D) return float; END Point2D_P; package body Point2D_P is -- Le Point est créé en (0,0) procedure creerPoint (p : out Point2D) is begin p(p'first) := 0.0; p(p'last) := 0.0; end creerPoint; -- Le point est déplacé de (x,y) procedure changerValeur ( p : in out Point2D; x, y : float) is begin p(p'first) := p(p'first) + x; p(p'last) := p(p'last) + y; end changerValeur; function abscisse(p : Point2D) return float is begin return p(p'first); end abscisse; function ordonnee(p : Point2D) return float is begin return p(p'last); end ordonnee; end Point2D_P; Client en ADA: with Point2D_P, float_io; procedure essai1 is p : Point2D_P.Point2D; begin

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel/...t/public_html/pages_html/TDA/TDA_Introduction.html (6 of 8) [25-10-2001 20:46:43]

TDA Introduction

Point2D_P.creerPoint(p); Point2D_P.changerValeur(p, 10.0, 20.0); Point2D_P.changerValeur(p, 11.0, 22.0); float_io.put(Point2D_P.abscisse(p)); -- affiche 11.0 end essai1; En C Point2D.h /* Définition des données */ /* le module exporte le type Point2D */ /* ATTENTION, déclaré ainsi le type n'est pas protégé */ typedef struct { float coord[2]; } Point2D; /* Spécification des opérations (sous-programmes) */ /* Le Point est créé en (0,0) */ extern void creerPoint(Point2D *); /* Point en IN OUT */ /* Le Point est déplacé de (x,y) */ extern void changerValeur ( Point2D *,/* Point2D en IN OUT */ float, /* coord en x */ float); /* coord en y */ Point2D.c #include "Point2D.h" /* Corps des sous-programmes */ /* Le Point est créé en (0,0) */ void creerPoint(Point2D *p) { /* Point2D en IN OUT */ (*p).coord[0] = 0.0f; (*p).coord[1] = 0.0f; } /* Le Point est déplacé de (x,y) */ void changerValeur ( Point2D * p, /* Point2D en IN OUT */ float x, /* coord en x */ float y) { /* coord en y */ (*p).coord[0] = (*p).coord[0] + x; (*p).coord[1] = (*p).coord[0] + y; } En JAVA : // la classe met en oeuvre le type Point2D class Point2D { // attributs = données qui définissent un Point2D protected double coord[]; // l'accès de la donnée est protégé // opérations, méthodes // Le Point est créé en (0,0) public Point2D() { // méthode de création d'un nouveau Point2D coord = new double[2]; coord[0] = 0.0; coord[1] = 0.0; } // Le Point est déplacé de (x,y) public void changerValeur ( float x, // coord en x float y) {// coord en y http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel/...t/public_html/pages_html/TDA/TDA_Introduction.html (7 of 8) [25-10-2001 20:46:43]

TDA Introduction

coord[0] = coord[0] + x; coord[1] = coord[0] + y; } }

Accueil / Equipe Synthèse d'Images / IRIT / UPS / FRANCE / [email protected]

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel/...t/public_html/pages_html/TDA/TDA_Introduction.html (8 of 8) [25-10-2001 20:46:43]

TDA Introduction aux Types Abstraits de Données : TDA

Introduction aux Types Abstraits de Données : TDA Un type abstrait est une structure qui n'est pas définie en terme d'implantation en mémoire ou par la simple définition de ses composantes, mais plutôt en termes d'opérations et des propriétés d'application de ces opérations sur les données.

Définitions Un TDA est un ensemble de données et d'opérations sur ces données. Un TDA est une vue logique (abstraite) d'un ensemble de données, associée à la spécification des opérations nécessaires à la création, à l'accès et à la modification de ces données. Un TDA est un ensemble de données, organisé pour que les spécifications des données et des opérations sur ces données soient séparées de la représentation interne des données et de la mise en œuvre des opérations. Un TDA est caractérisé par : Son identité (nom, adresse en mémoire). Le type des données qu'il manipule (ce qui définit son état ou caractéristiques). Les opérations sur les données (sous-programmes définis dans le TDA). Les propriétés de ces opérations (axiomes permettant de définir le TDA). ●

Encapsuler : c'est associer données et opérations qui manipulent ces données en un seul endroit. Seuls le type et les opérations exportées sont visibles de l'extérieur. Les données du TDA ne doivent être manipulables que par des opérations du TDA.

●

L'abstraction de données (Information Hiding) : isole l'utilisateur des détails d'implantation de la structure employée. La spécification du type abstrait est indépendante de toute représentation de la (ou des) structure(s) en machine et de l'implantation des opérations associées. Les détails sont connus seulement par les fonctions qui mettent en œuvre les opérations sur la structure de données. Ces détails sont cachés au code utilisateur. Ceci a pour intérêt d'empêcher l'utilisateur d'une telle structure de modifier directement la structure avec le risque de la rendre éventuellement incohérente. Une autre conséquence intéressante est l'amélioration de la portabilité qui découle de l'indépendance entre la spécification des opérations sur de la structure et la méthode d'implantation choisie.

Les TDA sont nés de préoccupations de génie logiciel telles que l'abstraction, l'encapsulation et la vérification de type. Les TDA généralisent ainsi les types prédéfinis (ou types simples) : integer, float, boolean, array… Des concepteurs peuvent ainsi définir un nouveau type et les opérations agissant sur ce type. Le but est de gérer un ensemble fini d'éléments dont le nombre n'est pas fixé a priori. Les éléments de cet ensemble peuvent être de différentes sortes: nombres entiers ou réels, chaîne de caractères, ou des données plus complexes.

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...t/public_html/pages_html/TDA/TDA_IntroAuxTDA.html (1 of 3) [25-10-2001 20:47:28]

TDA Introduction aux Types Abstraits de Données : TDA

L'Application : partie qui utilise un TDA. L'Implantation : partie qui met en œuvre le TDA. L'application et l'implantation sont deux entités totalement distinctes. Une implantation donnée peut être utilisée par des applications très différentes sans lui apporter aucun changement.

Avantages des TDA Les TDA permettent une conception ascendante d'un problème à résoudre. On réutilise des briques de base (TDA offrant des types élémentaires tels que ListeChaînée, Pile, File, …). D'autres TDA sont ensuite généralement définis au dessus des TDA de base pour construire des briques plus complexes. Au plus haut niveau, un programme principal permet de faire démarrer l'application qui déclenchera l'utilisation de services offerts par tous les TDA utilisés par l'application. Exemple de conception :

● ●

Des TDA correctement conçus doivent être faciles à comprendre et à utiliser. Les TDA permettent de séparer complètement la spécification des données et services offerts de la mise en œuvre des services.

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...t/public_html/pages_html/TDA/TDA_IntroAuxTDA.html (2 of 3) [25-10-2001 20:47:28]

TDA Introduction aux Types Abstraits de Données : TDA

●

●

● ●

Exemple : Spécification et Body d'un package ADA qui peuvent être dans des fichiers séparés. Les TDA permettent de cacher à l'utilisateur la façon dont les données sont mises en œuvre et donc d'empêcher l'utilisateur des TDA de modifier lui-même les données. Il faut l'obliger à utiliser des opérations du TDA pour modifier les données. Exemple : En ADA, le type déclaré dans la partie Spécification doit être déclaré PRIVATE (voire LIMITED PRIVATE) pour empêcher toute modification depuis l'extérieur du package. La spécification des types abstraits est indépendante du langage, de l'implémentation. Par contre la mise en œuvre doit être réalisée avec un langage permettant l'abstraction et l'encapsulation des données. Les TDA permettent la prise en compte de types complexes (bâtis à partir des types de base). En finale, les TDA sont les briques d'une conception modulaire rigoureuse.

Inconvénients des TDA ●

●

●

L'utilisateur d'un TDA connaît les services mais ne connaît pas leur coût d'utilisation (car il ne sait pas comment le TDA a été implanté : structure statique ou dynamique; efficacité de l'implantation selon la plate forme sur laquelle l'application doit tourner). Le concepteur du TDA connaît le coût des services mais ne connaît pas leurs conditions d'utilisation. Il doit donc offrir des services très étudiés de façon à convenir à de nombreuses applications. Le choix des primitives est quelquefois difficile à faire. Un TDA doit également être très stable pour que l'application qui l'utilise ne soit pas amenée à changer son code parce que le TDA a modifié la spécification ou le service offert par une opération du TDA.

Accueil / Equipe Synthèse d'Images / IRIT / UPS / FRANCE / [email protected]

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...t/public_html/pages_html/TDA/TDA_IntroAuxTDA.html (3 of 3) [25-10-2001 20:47:28]

TDA Programation à l'aide des TDA

Programmation à l'aide des TDA Concevoir correctement les TDA Les programmeurs ont deux casquettes : Concepteur Le concepteur du TDA qui met en œuvre les primitives et doit connaître la représentation interne adoptée.

Utilisateur L'utilisateur du TDA qui ne connaît que les services (les opérations exportées) et n'accède jamais à la représentation interne.

●

Idée générale : voir les TDA comme une 'black box' (où l'information d'implantation est cachée) · entrées-sorties sont connues · la manière dont cela a été implanté ne l'est pas Règle générale : garder les calculs internes privés · avantage : meilleure modularité · meilleure répartition du travail · localisation non unique (la spécification et le code peuvent être dans des fichiers séparés)

●

L'application qui utilise un TDA est client du TDA.

●

Conception d'un TDA ●

●

●

Fournir une "interface" pour l'accès aux données et services - les données doivent être protégées (private ou protected selon le langage et le niveau de protection souhaité) . souvent nécessité de fonctions protected ou private également (fonctions utilitaires) - définition de fonctions publiques (public) pour permettre l'accès aux services la spécification (l'interface) doit être stable est bien conçue - spécification (interface) : ensemble d'opérations vues en dehors du TDA · c'est la partie publique de la définition · les méthodes publiques peuvent être appelées par des fonctions extérieures - l'interface doit être extrêmement stable et ne changer qu'en cas d'absolu nécessité (il fallait réfléchir avant !!) Les TDA sont égocentriques : · ils agissent sur leurs propres données · ils N'AGISSENT PAS sur des données d'autres TDA

Exemple : Pile Intéressons nous à la façon de spécifier un TDA en prenant l'exemple de la Pile qui est basé sur l'observation de piles de la vie réelle : Pile de livres, d'assiettes … Les Piles sont très utilisées en informatique, non seulement dans des application utilisateurs mais également lors de l'exécution de programmes où elles sont utilisées pour stocker les contextes d'exécution des sous-programmes. · On accède au 1° élément : le sommet. · On enlève le 1° élément : on dépile. · On ajoute un élément sur la pile : on empile. On décrira des opérations manipulant une pile avec les termes : sommet , empiler , dépiler… ●

Avantages : c'est une formulation universelle qui est indépendante du langage cible (C, ADA, JAVA, etc.).

●

Contrainte : il faudra construire avec le langage cible une structure de données représentant ce type abstrait de données, à l'aide de tableaux, structures, pointeurs, etc. et les fonctions ou procédures implantant les opérations sur le type.

Type de Données Abstrait : http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne...ublic_html/pages_html/TDA/TDA_Programmation.html (1 of 4) [25-10-2001 20:48:20]

TDA Programation à l'aide des TDA

L'application qui utilise un TDA est client du TDA :

●

●

Le type est connu à l'extérieur de la Pile. Dans la signature des opérations se trouve la Pile passée en paramètre. · empiler (p : in out Pile, e : Element); · sommet (p : Pile) return Element; · … Le client de la Pile applique les opérations à une Pile particulière qu'il a déclarée. · en ADA with Pile_P, integer_io; procedure … is p1, p2 : Pile_P.Pile -- on considère que ce sont des Piles d'entier begin Pile_P.empiler(p1, 10); Pile_P.empiler(p2, 20); integer_io.put(Pile_P.sommet(p1)); -- affiche 10 integer_io.put(Pile_P.sommet(p2)); -- affiche 20 …

Machine abstraite : Le TDA peut être conçu comme une MachineAbstraite (machine à états abstraits)

●

●

Dans ce cas, le type n'est pas connu de l'extérieur de la Pile (pas exporté). Le client de la Pile ne voit que les opérations : · empiler (e : Element); · sommet return Element; · … Si le client veut utiliser une Pile il faut créer une ou plusieurs références à la machine abstraite Pile : · en ADA:

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne...ublic_html/pages_html/TDA/TDA_Programmation.html (2 of 4) [25-10-2001 20:48:20]

TDA Programation à l'aide des TDA

with Pile_MA; package Saisie_p is procedure entreeDonnees; … end Saisie_p; package body Saisie_p is procedure entreeDonnees is begin Pile_MA.empiler(20); -- empile dans LA Pile_MA Pile_MA.empiler(10); end entreeDonnees; end Saisie_p; with Pile_MA, integer_io, Saisie_p; procedure essai is begin Saisie.entreeDonnees; integer_io.put(Pile_MA.sommet); -- affiche 10 Pile_MA.depiler; -- depile dans LA Pile_MA integer_io.put (Pile_MA.sommet); -- affiche 20 Pile_MA.depiler; end essai;

Implantation avec un langage objet : Avec un langage objet, une classe est un nouveau type

●

La classe EST un type. Elle protège ses données en ne permettant leur accès qu'au travers des opérations exportées. · en JAVA : class Pile { // Attributs … // méthodes (opérations) public void empiler (int i) { …} public Element sommet ( ) {…} … } // classe cliente de la Pile import Pile; class Bidon { // attributs protected Pile p1, p2; // ici p1 et p2 ne sont que des références nulles // opérations // constructeur de la classe Bidon : // alloue de la place pour les attributs de la classe Bidon public Bidon ( ) {

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne...ublic_html/pages_html/TDA/TDA_Programmation.html (3 of 4) [25-10-2001 20:48:20]

TDA Programation à l'aide des TDA

p1 = new Pile ( ); // on alloue de la place pour une Pile et on stocke // sa référence (son adresse mémoire) dans p1 p2 = new Pile ( ); // on alloue de la place pour une Pile et on stocke } // sa référence (son adresse mémoire) dans p2 public void operation1 (…) { p1.empiler (10); p2.empiler (20); System.out.print(p1.sommet()); // affiche 10 System.out.print(p2.sommet()); // affiche 20 } }

Spécification La propriété fondamentale d'une Pile est qu'on ne peut accéder qu'à l'élément en sommet de Pile. Tous les autres éléments, placés en dessous du sommet, ne peuvent être accédés qu'après avoir tout d'abord enlevé les éléments placés au dessus d'eux un par un. ● Comment définir ou spécifier le concept abstrait de Pile ? Il est nécessaire de spécifier tout ce qu'il faut connaître pour utiliser correctement et aisément une Pile, sans pour autant avoir à connaître l'implantation sous-jacente.

Représentation et implantation Il y a plusieurs manières de représenter les piles. Statique :

Tableaux => nombre max d'éléments fixés a priori.Gestion simple mais taille statique. Chaînages mis en œuvre à l'aide de pointeurs => nombre d'éléments uniquement limité par la place mémoire Dynamique : disponible.Gestion plus complexe mais taille dynamique.

Accueil / Equipe Synthèse d'Images / IRIT / UPS / FRANCE / [email protected]

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne...ublic_html/pages_html/TDA/TDA_Programmation.html (4 of 4) [25-10-2001 20:48:20]

TDA Types de base

Types de base Définition : Le typage est le fait d'associer à une variable (un objet), un ensemble de valeurs possibles ainsi que d'un ensemble d'opérations admissibles sur ces valeurs. Type = {ensemble de valeurs, opérations possibles} Le langage de programmation doit vérifier (autant que possible) que les valeurs que l'on place dans une variable, ainsi que le résultat d'une opération sont compatibles avec le(s) type(s) correspondant à l'affectation et à l'opération utilisée.

Les types scalaires Les types scalaires sont les types de données (généralement prédéfinis dans le langage de programmation) pour lesquels une variable ne contient qu'une seule information élémentaire. Ils se partagent en deux groupes : les types discrets et les réels. ● Les types scalaires · discrets : · réels:

Les types discrets Ils représentent des objets dont les valeurs possibles sont énumérables, en y ajoutant la contrainte d'un nombre fini de valeurs. ● Les types discrets : ° entiers ° énumérés ° intervalles

Les entiers Ils représentent des valeurs numériques signées ne comportant pas de partie fractionnaire. Le nombre de valeurs représentables sur un ordinateur étant fini, les entiers sont généralement limités à un intervalle de valeurs possibles. En ADA integer'last qui est donc le plus grand nombre entier représentable. Les valeurs de integer'first et integer'last dépendent de l'implantation : sur un micro-ordinateur, leur valeur sera plus petite que sur de plus gros systèmes. En C, les valeurs représentables dépendent de la taille du mot machine.

Les types énumérés http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne.../public_html/pages_html/TDA/TDA_TypesDeBase.html (1 of 8) [25-10-2001 20:48:58]

TDA Types de base

Les booléens Les objets de type booléen ne peuvent prendre que deux valeurs possibles : true et false. Les expressions comportant des valeurs booléens sont appelées des expressions logiques. Les opérations possibles sont : and, or, not et la comparaison ( =, /= ). Il est à noter que les opérateurs de comparaison donnent un résultat booléen, même si les opérandes sont d'un autre type.

Les caractères Le jeu de caractères d'une machine est l'énumération, dans un certain ordre, des lettres et signes affichables sur un écran ou imprimables sur papier. Les opérations possibles sont principalement les comparaisons : =, <>, >, <, <=, >=..

Les énumérations définies par l'utilisateur Il est possible de déclarer une suite ordonnée de labels qui ont un sens particulier pour l'utilisateur. Par exemple, on peut déclarer un type Semaine = (dimanche, lundi, mardi, mercredi, jeudi, vendredi, samedi); Toute variable du type Semaine pourra prendre une de ces sept valeurs (et aucune autre valeur ne sera légale). Les opérations possibles sont les comparaisons ( =, <>, <, >, <=, >= ).

Les intervalles Les intervalles ne forment pas, à proprement parler, un type de base. Il s'agit plutôt de types, générés à partir de types de base ou définis par l'utilisateur, restreignant l'ensemble des valeurs possibles du type parent. Exemple : subtype JourOuvrable is Semaine range lundi .. vendredi; subtype natural is integer range 0..integer'last; subtype positive is integer range 1..integer'last; Toutes les opérations applicables au type de base sont applicables au type qui en est dérivé. L'intérêt de l'utilisation des intervalles réside dans l'amélioration de la lisibilité des programmes (on voit plus clairement quelles sont les valeurs possibles) et l'augmentation de la sécurité de programmation (des valeurs illégales peuvent être automatiquement détectées à la compilation et à l'exécution).

Fonctions prédéfinies sur les types discrets En ADA, un certain nombre d'attributs peuvent s'appliquer aux types discrets : ° first : donne la première valeur de l'ensemble de valeurs, ° last : donne la dernière, http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne.../public_html/pages_html/TDA/TDA_TypesDeBase.html (2 of 8) [25-10-2001 20:48:58]

TDA Types de base

° succ : donne la valeur suivante ° pred : donne la précédente ° image : donne un équivalent de la valeur sous forme de chaîne de caractères, ° value : donne la valeur correspondante à une chaîne de caractères, ° pos : donne la position de la valeur en considérant que la valeur first est en position 0 ° val : donne la valeur qui est à une position donnée °… Exemple Semaine'pred(lundi) = dimanche Semaine'pred(dimanche) !!! n'existe pas character'pred('b') = 'a' integer'pred(i) = i-1 Semaine'succ(dimanche) = lundi Semaine'succ(samedi) !!! n'existe pas character'succ('a') = 'b' integer'succ(i) = i+1

Représentation du type booléen comme un TDA Spécification du type Boolean : Autre type utilisé : aucun Ensemble de valeurs Vrai, faux Opérations : not : booléen à booléen // fournit non b en entrée : b : booléen en sortie : b' : booléen pré conditions : aucun post conditions : b' == vrai si b == faux, b' == faux sinon ou : booléen x booléen à booléen // ou de deux booléens en entrée : a, b : booléen en sortie : b': booléen , a et b non modifiés pré conditions : aucun post conditions : b' == vrai si a == vrai ou si b == vrai, b' == faux sinon et : booléen x booléen à booléen // et de deux booléens en entrée : a, b : booléen en sortie : b': booléen , a et b non modifiés pré conditions : aucun

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne.../public_html/pages_html/TDA/TDA_TypesDeBase.html (3 of 8) [25-10-2001 20:48:58]

TDA Types de base

post conditions : b' == vrai si a == vrai et si b == vrai, b' == faux sinon Axiomes : a, b, c : booléen (1) not vrai == faux // relation entre constantes (2) not (not a) == a // négation involutive (3) a et vrai == a // vrai est l'élément neutre de et (4) a et faux == faux // faux est l'élément absorbant de et (5) (a et b) et c == a et (b et c) // associativité de et (6) a et b == b et a // commutativité de et (7) a ou b = not (not a et not b) // définition de ou (not (a ou b) == (not a et not b)) …

Représentation du type entier comme un TDA Spécification du type integer : Autre type utilisé : booléen Ensemble de valeurs integer'first .. integerl'last à intervalle dans Z Opérations : + != :=

== pred

*

/ <

>

mod <=

% >=

power

-unaire

succ

(on ne détaillera que les suivantes) succ : integer à integer // fournit l'entier suivant en entrée : i : integer en sortie : i' : integer (i non modifié) pré conditions : i < integer'last post conditions : i' = i+1 + : integer x integer à integer // addition de deux entiers en entrée : i, j : integer en sortie : i' : integer (i et j non modifiés) pré conditions : i + j <= integer'last et i + j >= integer'first post conditions : i' = i+j - : integer à integer en entrée : i: integer en sortie : i' : integer pré conditions : aucun post conditions : i' = -i == : integer x integer à booléen

// moins unaire

// égalité d'entiers

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne.../public_html/pages_html/TDA/TDA_TypesDeBase.html (4 of 8) [25-10-2001 20:48:58]

TDA Types de base

en entrée : i, j : integer en sortie : b : booléen (i et j non modifiés) pré conditions : aucune post conditions : b = vrai si i ==j, faux sinon < : Natural x Natural à booléen // comparaison d'entiers Natural en entrée : i, j : Natural en sortie : b : booléen (i et j non modifiés) pré conditions : aucune post conditions : b = vrai si i < j, faux sinon Axiomes : m, n, p : integer (1) 0 + n = n // élément neutre à gauche (1') n + 0 = n // élément neutre à droite (2) succ(m) + n = succ(m+n) // définition de + (3) (m + n) + p = m + (n + p) // associativité de + (4) m + n = n + m // commutativité de + (5) 0 == 0 est vrai // définition de == (6) succ(m) == 0 est faux // "" (7) 0 == succ(n) est faux (8) succ(m) == succ(n) <=> n == m (9) 0 < 0 est faux // définition de < (10) succ(m) < 0 est faux (11) 0 < succ(n) est vrai (12) succ(m) < succ(n) <=> m < n (13) m < n et n < p <=> m < p (14) -0 == 0 // définition du moins unaire (15) -(-n) == n // moins unaire involutive (16) succ(n) + (-succ(m)) == n + (-m) // n+1 + (-(m+1)) (17) -n + (-m) = -(n + m) Axiome concernant les opérations arithmétiques : m = ((m / n) * n) + (m mod n) // 3 = ((3 / 2) * 2) + (3 mod 2) = (2) + (1) = 3 // 2 = ((2 / 3) * 3) + (2 mod 3) = (0) + (2) = 2

Les réels ●

réels: ° virgule flottante ° virgule fixe

De tous les types de base, ce sont les nombres réels qui posent le plus de problèmes de représentation. L'ensemble des nombres réels étant, par définition, infini et indénombrable, il est impossible de le représenter avec une totale exactitude dans un ordinateur. La représentation qui en est faite ne peut donc constituer qu'une approximation. Il existe d'ailleurs plusieurs techniques de représentation, chacune ayant ses avantages et ses inconvénients. http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne.../public_html/pages_html/TDA/TDA_TypesDeBase.html (5 of 8) [25-10-2001 20:48:58]

TDA Types de base

Représentation en virgule flottante La représentation en virgule flottante consiste à représenter un nombre réel à l'aide de 3 composantes : le signe (S), l'exposant (E) et la mantisse (M).

Représentation en virgule fixe La représentation en virgule fixe consiste à utiliser une représentation similaire aux nombres entiers en attribuant un nombre de "bits" fixes à la partie fractionnaire et un autre nombre de "bits" à la partie entière. L'avantage principal de cette représentation étant de pouvoir utiliser les opérations arithmétiques des nombres entiers auxquelles s'ajoute l'opération de décalage. Ces opérations sont très efficaces et accélèrent d'autant le calcul. Les principaux inconvénients sont que la répartition de la "gamme" de nombres représentables est beaucoup plus étroite que pour la virgule flottante et que les erreurs d'arrondis sont aussi inévitables et s'accumulent beaucoup plus vite.

Représentation du type réel sous forme de TDA Autre type utilisé : booléen Ensemble de valeurs sous ensemble (fini) de IR Opérations : + : IR x IR à IR entrée : e, f : réel sortie : e' : réel (e et f inchangés) pré conditions : e+f représentable en machine post conditions : e' == e + f cos : IR à IR entrée : e : réel sortie : e' : réel (e inchangé) pré conditions : e exprime un angle en radians post conditions : e' == cos(e) < : IR x IR à booléen entrée : e, f : réel sortie : b : booléen (e et f inchangés) pré conditions : aucun post conditions : b == vrai si e < f, faux sinon power : IR x IR à IR entrée : e, f : réel sortie : e' : réel (e et f inchangés)

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne.../public_html/pages_html/TDA/TDA_TypesDeBase.html (6 of 8) [25-10-2001 20:48:58]

TDA Types de base

pré conditions : e^f représentable en machine post conditions : e' == e^f + * / sin log sqrt … Axiomes x* (y + z) = x * y + x * z ...

= …

>

…

Conversion de type Le langage ADA impose, des contraintes lors de la conversion de types. Il fait la distinction entre types dérivés et sous-types. Un sous-type, de même qu'un type dérivé, consiste en une restriction apportée à un type de base. Un sous-type reste compatible avec son type de base alors qu'un type dérivé est incompatible avec son type de base. Exemples : subtype OneDigit is integer range 0..9; subtype JourOuvrable is Semaine range Lundi..Vendredi; type Entier is new integer; type MilieuDeSemaine is new Semaine range Mardi..Jeudi; Dans les exemples qui précèdent : OneDigit est compatible avec integer, JourOuvrable est compatible avec Semaine, mais Entier n'est pas compatible avec integer : c'est un nouveau type ! et MilieuDeSemaine n'est pas compatible avec Semaine : c'est également un nouveau type... Il est toutefois possible de faire une conversion explicite d'un type dérivé vers son type de base (ou vice-versa) en préfixant l'objet du type à convertir par le type du résultat. Par exemple, si Jour est une variable de type Semaine, MilieuDeSemaine(Jour) est de type MilieuDeSemaine (il y aura erreur si la valeur associée à la variable Jour n'est pas comprise dans l'ensemble des valeurs possibles pour le type MilieuDeSemaine ). L'intérêt de cette distinction entre types dérivés et sous-types est une fois encore au niveau de la sécurité de programmation. Par exemple, si une variable est sensée représenter une superficie et une autre variable sensée représenter une longueur, cela n'aurait pas beaucoup de sens de vouloir les additionner, même si elles sont toutes les deux des valeurs numériques entières.

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne.../public_html/pages_html/TDA/TDA_TypesDeBase.html (7 of 8) [25-10-2001 20:48:58]

TDA Types de base

Accueil / Equipe Synthèse d'Images / IRIT / UPS / FRANCE / [email protected]

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personne.../public_html/pages_html/TDA/TDA_TypesDeBase.html (8 of 8) [25-10-2001 20:48:58]

TDA Types composés

Types composés Les types structurés (composés) sont implantés grâce à des : · structures statiques ou · structures dynamiques

Les structures statiques Structures cartésiennes simples Les structures cartésiennes simples sont des structures regroupant plusieurs composantes de type de base. Nous verrons ici 4 types de structures cartésiennes simples : · structures statiques tableaux enregistrements chaînes de caractères ensembles

Les tableaux Les tableaux sont constitués d'un regroupement de données de même type. Les données individuelles sont repérées par un sélecteur que l'on nomme indice du tableau. L'indice d'un tableau doit être de type énuméré. Cela pourra donc être un type énuméré défini par l'utilisateur, un intervalle d'entiers ou de booléens. Des variables de type tableau ne changent que de valeurs, jamais de structure ou d'ensemble de valeurs de base. Conséquence : l'espace qu'elles occupent en mémoire reste constant. Exemple procedure essai is subtype Index is integer range 0..9; type Semaine is (Dimanche, Lundi, Mardi, Mercredi, Jeudi, Vendredi, Samedi); type T1 is array (Index) of integer; type T2 is array (0..9) of integer; type T3 is array (boolean) of character; type T4 is array (false..true) of character; type T5 is array (Semaine) of integer;

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personn...blic_html/pages_html/TDA/TDA_TypesComposes.html (1 of 6) [25-10-2001 20:49:30]

TDA Types composés

●

●

●

●

heuresDeTravail : T5; begin ... heuresDeTravail[Lundi] := 8; ... end essai; La spécification de la structure de tableau peut se faire de la manière suivante : leur déclaration spécifie un intervalle d'indices et un type de base. Ceci détermine indirectement la taille du tableau. le rôle du tableau est de conserver pour chaque valeur d'indice une valeur de type de base associée. une seule valeur du type de base peut être associée à chaque valeur d'indice. Les primitives de manipulations sont : associer une valeur du type de base à une certaine valeur d'indice, fournir la valeur de type de base associée à une certaine valeur d'indice. en fonction de la déclaration, diagnostiquer la validité de l'indice fourni. On peut envisager de pouvoir associer, lors de la déclaration d'un tableau, une valeur initiale à quelques (ou toutes les) valeurs d'indices. C'est le cas en Ada, par exemple. Deux valeurs se suivent dans le tableau si les valeurs des indices auxquels elles sont associées se suivent dans la séquence des indices. Cela ne signifie pas pour autant que ces valeurs seront effectivement stockées dans des zones contiguës de la mémoire (même si c'est presque toujours le cas en réalité, pour des raisons d'efficacité).

Les enregistrements (structures) Les enregistrements sont constitués d'un regroupement de données de types différents. Les données individuelles sont repérées par un sélecteur que l'on nomme champ de l'enregistrement. L'identificateur de champ doit être un identificateur conforme aux règles lexicales du langage. Exemple

●

procedure essai is type Individu is record nom, prénom: string(1..20); age: integer; end record; -- Individu lui: Individu; begin ... lui.age := 15; ... end essai ; La spécification d'un enregistrement peut être la suivante : · La déclaration d'un enregistrement spécifie le nombre et le type d'éléments qu'il doit

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personn...blic_html/pages_html/TDA/TDA_TypesComposes.html (2 of 6) [25-10-2001 20:49:30]

TDA Types composés

●

contenir. · La taille nécessaire pour un enregistrement est ainsi fixée. · Chaque champ doit contenir une valeur correspondante à son type. Les opérations possibles sur les enregistrements dans leur globalité sont : · l'affectation · la comparaison ( =, <> ). · Les opérations possibles sur les différents champs d'un enregistrement sont celles associées au type du champ.

Les chaînes de caractères Le type chaîne de caractère : String, existe dans des langages comme ADA ou JAVA. Il existe donc des opérateurs permettant de manipuler les chaînes de caractères : concaténation par exemple. Toutefois, les chaînes de caractères sont représentées par des tableaux de caractères et peuvent être vues comme tel. En C, les chaînes de caractères sont stockées dans des tableaux de caractères et doivent obligatoirement être terminées par un caractère spécial qui indique la fin de la chaîne dans le tableau : '\0'. Ainsi, une chaîne de n caractères doit être contenue dans un tableau d'au moins n+1 caractères. La spécification des chaînes de caractères s'apparente à celle des tableaux, avec des opérations supplémentaires, différentes selon les langages.

Question : ne pourrait-on pas définir un type ChaîneDeCaractères, offrant un ensemble de services couvrant tous les besoins des utilisateurs, indépendant du langage et pouvant donc être mis en œuvre dans différents langages et sur différentes plate-formes ??? ● Les primitives de manipulations sont : · constituer une chaîne de caractères à partir d'une séquence de zéro, un ou plusieurs caractères, · l'affectation d'une chaîne à une variable de type compatible, · fournir la longueur d'une chaîne, · fournir le caractère se trouvant à une certaine position, · redéfinir le caractère se trouvant à une certaine position, · insérer une chaîne dans une autre à partir d'une certaine position, · détruire une portion d'une chaîne, à une certaine position et sur une certaine longueur, · concaténer deux chaînes, · extraire une sous-chaîne d'une chaîne, · trouver la position de la première occurrence d'une sous-chaîne, ·…

Les ensembles Les ensembles sont des structures que l'on ne retrouve quasiment qu'en Pascal. Ada ne les

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personn...blic_html/pages_html/TDA/TDA_TypesComposes.html (3 of 6) [25-10-2001 20:49:30]

TDA Types composés

offre pas de manière prédéfinie. Les ensembles se rapprochent beaucoup de la notion mathématique d'ensembles. Ils sont construits à partir de types de bases énumérés et permettent d'indiquer, pour chacune des valeurs du type de base, si cette valeur est présente ou absente de l'ensemble en question. Il n'y a pas de sélecteur possible. Exemple : var S, Voyelles, Consonnes: set of char; ... S := []; { ensemble vide } Voyelles := ['a','e','i','o','u','y']; Consonnes := ['b'..'d','f'..'h','j'..'n', 'p'..'t','v'..'x' ,'z']; S := [ 'b'..c ]; {noter le fait que c est une variable character }

La spécification d'un ensemble peut être la suivante : Se définit à partir de la définition mathématique des ensembles : Autres types utilisés (sortes) : Elément, Booléen, Natural Opérations : créer : -> Ensemble vide // possibilité d'opérateur créerSingleton entrée : aucun sortie : e : Ensemble pré conditions : post conditions : e == {} ensemble vide, card(e) == 0 ajout : Elément x Ensemble -> Ensemble entrée : i : Elément, e : Ensemble sortie : e' : Ensemble pré conditions : !present(i, e) post conditions : e' == e union {i} suppression : Elément x Ensemble -> Ensemble entrée : i : Elément, e : Ensemble sortie : e' : Ensemble pré conditions : present(i, e) post conditions : e' == e - {i} présent : Elément x Ensemble -> Booléen cardinal : Ensemble : Natural union : Ensemble x Ensemble à Ensemble entrée : e, f : Ensemble sortie : e' : Ensemble (e et f inchangés)

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personn...blic_html/pages_html/TDA/TDA_TypesComposes.html (4 of 6) [25-10-2001 20:49:30]

TDA Types composés

pré conditions : aucun post conditions : e' == e union éléments de f non présents dans e intersection: Ensemble x Ensemble à Ensemble entrée : e, f : Ensemble sortie : e' : Ensemble (e et f inchangés) pré conditions : aucun post conditions : e' == éléments de e présents aussi dans f Axiomes (équations) : e : Ensemble, x : Elément présent (x, créer ()) = faux présent (x, ajout (x, e)) = vrai présent (x, ajout (y, e)) = présent (x, e) ajout( y, ajout(x, e)) == ajout( x, ajout(y, e)) card (créer()) == 0 card (ajout (x, e)) == card(e) + 1 suppression(y, ajout(x, e)) == si x == y alors e sinon ajout(x, suppression(y, e)) … D'autres opérations sur les ensembles peuvent être les suivants :. création d'un ensemble singleton (initialisé avec un élément à la création), al différence de deux ensembles (permet de supprimer un ou plusieurs éléments), a comparaison de deux ensembles, le test d'inclusion d'un ensemble dans un autre. N.B. L'expression a ∉ S sera notée : not (a in S). Cardinalité Définition : La cardinalité est le nombre de valeurs distinctes appartenant à un type T. Un objet de ce type T ne pourra bien entendu avoir qu'une seule de ces valeurs à un instant donné Exemple type Forme = (Carré, Rectangle, Cercle, Ellipse); type Monnaie = (Franc, Livre, Dollar, Lire, Yen, Mark); type Genre = (Féminin, Masculin); card(Forme) = 4 card(Monnaie) = 6 card(Genre) = 2 type SmallInteger = 1..100; type Vecteur=array[1..3] of SmallInteger; card (SmallInteger) = 100 card (Vecteur) = 1003 http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personn...blic_html/pages_html/TDA/TDA_TypesComposes.html (5 of 6) [25-10-2001 20:49:30]

TDA Types composés

card (boolean) = 2 card (integer) = 2*(MaxInt+1) { pour le langage Pascal }

Représentation statique du type Ensemble en C

Résumé On peut résumer les principales caractéristiques des structures cartésiennes simples dans le tableau suivant : Structure :

Tableau

Déclaration a : array(I) of To

Sélecteur : Accès aux composantes: Type des composantes: Cardinalité :

a(i) (i∈I)

Enregistrement r : record S1 : T1; S2 : T2; Sn : Tn; end;

r.s (S∈S1,...Sn ) par le sélecteur avec par le sélecteur le nom déclaré d'un et le calcul de l'indice élément Toutes de même type Peuvent être de type To différent n ∏ card (Ti) Card(To)Card(I) i=1 prod. cartésien

Ensemble

set of To

aucun Test d'appartenance avec l'opérateur de relation présent Toutes de même type scalaire To 2Card(TO)

Ces structures simples peuvent être combinées pour former des structures plus complexes .

Accueil / Equipe Synthèse d'Images / IRIT / UPS / FRANCE / [email protected]

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personn...blic_html/pages_html/TDA/TDA_TypesComposes.html (6 of 6) [25-10-2001 20:49:30]

TDA Ensemble

Une représentation statique du TDA Ensemble possible : #include "Ensemble.h" void main() { Ensemble e1, e2, e3, e4; int i, j; e1 = creerEnsemble (); e2 = creerSingleton(1); printf("e2 = "); print(e2); i = 1; while (ajout(i, &e1) == TRUE) i++; printf("e1 = "); print(e1); if (suppression(3, &e1)== TRUE) { printf("e1 = "); print(e1); } printf("e2 = "); print(e2); ajout(2, &e2); printf("e2 + 2 = "); print(e2); e3 = clone(e1); printf("e3 = clone(e1) = "); print(e3); if (equals(e1, e3)) printf("e3 egale e1\n"); else printf("pb equals\n"); e3 = creerSingleton(3); ajout(4, &e3); if (unionEns(e2, e3, &e4)== TRUE) { printf("e4 = union(e2, e3) = "); print(e4); } if (inclus(e4, e3)) printf("e3 inclus dans e4\n"); if (!inclus(e4, e1)) printf("e1 pas inclus dans e4\n"); http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...drat/public_html/pages_html/TDA/TDA_Ensemble.html (1 of 6) [25-10-2001 20:49:57]

TDA Ensemble

e3 = interEns(e1, e4); printf("e3 = inter(e1, e4) = "); print(e3); printf("elementAt(e3, 1) = %d\n", elementAt(e3, 1)); e2 = diffEns(e4, e3); printf("e2 = diff(e4, e3) = "); print(e2); } //Représentation statique du type Ensemble en C, fichier Ensemble.h #define MAX_E 10 static const int TRUE = 1; static const int FALSE = 0; // type des Elements fixe a int typedef int Element; // Attention le type Ensemble n'est pas protégé typedef struct {Element v[MAX_E]; int n;} Ensemble; // creation d'un ensemble vide extern Ensemble creerEnsemble(); // creation d'un ensemble singleton extern Ensemble creerSingleton(Element); // ajout d'un element dans un ensemble // precondition : Ensemble non plein et Element non present extern int ajout(Element, Ensemble *); // suppression d'un element dans un ensemble // precondition : Element present extern int suppression(Element, Ensemble *); // test de presence d'un Element extern int present(Element, Ensemble); // cardinal de l'Ensemble extern int cardinal(Ensemble); // union de deux Ensembles (union, mot reserve en C => unionEns !) // precondition : l'union ne doit pas comporter plus de MAX_E Elements extern int unionEns(Ensemble, Ensemble, Ensemble *); // intersection de deux ensembles extern Ensemble interEns(Ensemble, Ensemble); // difference de deux ensembles ; le premier - le second extern Ensemble diffEns(Ensemble, Ensemble); // test d'inclusion du second Ensemble dans le premier extern int inclus(Ensemble, Ensemble); // obtention du ieme element extern Element elementAt(Ensemble, int); // test de l'egalite des contenus extern int equals(Ensemble, Ensemble);

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...drat/public_html/pages_html/TDA/TDA_Ensemble.html (2 of 6) [25-10-2001 20:49:57]

TDA Ensemble

// copie d'un Ensemble extern Ensemble clone(Ensemble); extern void print(Ensemble); fichier Ensemble.c #include "Ensemble.h" // Methodes dependantes de l'implantation //-------------------------int cardinal(Ensemble ens) { return (ens.n); } // obtention du ieme element Element elementAt(Ensemble ens , int i) { return ens.v[i]; } Ensemble creerEnsemble () { Ensemble ens; ens.n = 0; return ens; } Ensemble creerSingleton(Element e) { Ensemble ens; ens.v[0]= e; ens.n = 1; return ens; } int ajout (Element e, Ensemble * ens) { // Ensemble plein if (cardinal(*ens) == MAX_E) return FALSE; d'erreur pour traiter

// code // les erreurs

en C (*ens).v[(*ens).n] = e; (*ens).n = (*ens).n+1; return TRUE;

// code correct

} int suppression(Element e, Ensemble * ens) { int i, j; for (i=0; i < cardinal(*ens); i++) { // des qu'on trouve on supprime l'Element et on arrete if (elementAt(*ens, i) == e) { // decalage des Elements suivants d'un cran vers la droite for (j=i+1; j < cardinal(*ens); j++) (*ens).v[j-1] = elementAt(*ens, j); http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...drat/public_html/pages_html/TDA/TDA_Ensemble.html (3 of 6) [25-10-2001 20:49:57]

TDA Ensemble

// il y a un Element de moins (*ens).n = (*ens).n - 1; return TRUE; } } // Element non trouve return FALSE; } // methodes independantes de l'implantation //-------------------------int present(Element e, Ensemble ens) { int i; // on teste tous les Elements de l'Ensemble for (i=0; i < cardinal(ens); i++) // des qu'on trouve on arrete la recherche if (elementAt(ens, i) == e) return TRUE; // tout a ete examine sans trouver return FALSE; } int unionEns(Ensemble ens1, Ensemble ens2, Ensemble * e) { int i; int result; // on commence a mettre tous les Elements de ens1 dans e (*e) = clone(ens1); // puis on ajoute tous ceux non encore presents for (i=0; i < cardinal(ens2); i++) if (!present(elementAt(ens2, i), ens1)) { result = ajout(elementAt(ens2, i), e); if (result == FALSE) return FALSE; } return TRUE; } Ensemble interEns(Ensemble ens1, Ensemble ens2) { Ensemble e; int i; e = creerEnsemble(); for (i=0; i < cardinal(ens1); i++) if (present(elementAt(ens1, i), ens2)) ajout(elementAt(ens1, i), &e); return e; http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...drat/public_html/pages_html/TDA/TDA_Ensemble.html (4 of 6) [25-10-2001 20:49:57]

TDA Ensemble

} Ensemble diffEns(Ensemble ens1, Ensemble ens2) { Ensemble e; int i; e = clone(ens1); for (i=0; i < cardinal(ens2); i++) if (present(elementAt(ens2, i), e)) suppression(elementAt(ens2, i), &e); return e; } int inclus(Ensemble ens1, Ensemble ens2) { int i; for (i=0; i < cardinal(ens2); i++) if (!present(elementAt(ens2, i), ens1)) return FALSE; return TRUE; } int equals(Ensemble ens1, Ensemble ens2) { if (inclus(ens1, ens2) && inclus(ens2, ens1)) return TRUE; else return FALSE; } Ensemble clone(Ensemble ens) { Ensemble e; int i; e = creerEnsemble(); for (i=0; i < cardinal(ens); i++) ajout(elementAt(ens, i), &e); return e; } void print (Ensemble ens) { int i; printf("Ensemble : "); for (i = 0; i < cardinal(ens); i++) printf("%d, ", elementAt(ens, i)); printf(" \nFIN Ensemble\n"); }

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...drat/public_html/pages_html/TDA/TDA_Ensemble.html (5 of 6) [25-10-2001 20:49:57]

TDA Ensemble

Accueil / Equipe Synthèse d'Images / IRIT / UPS / FRANCE / [email protected]

http://www.irit.fr/ACTIVITES/EQ_SYNTHIM/personnel...drat/public_html/pages_html/TDA/TDA_Ensemble.html (6 of 6) [25-10-2001 20:49:58]