IFT-10541A : Hiver 2003 Semaine 1 : Type de données abstrait

IFT-10541A : Hiver 2003

Semaine 1 :Type de données abstrait

2

Programme = Algo. + données

Programmes et informations

information intermédiaire

outputinput

3

Conventions Représentation de l’information

conventions de représentation: integer idem pour tout programme sur

un même ordinateur, utilisant le même langage: int x;

conventions d’utilisation: integer pas de décimales: x = 5/2;

4

Conventions Structure d’information (de données):

conventions de représentation et d’utilisation d ’un certain type d’information

certaines sont fournies avec les langages: int, float, double, long, etc.

5

Conventions de représentation

Structuration de base = types simples

convention de représentation:

int x, y;

choix de représentation {manipulations}

0 0 00

0 0 ±00

± •bit de signe•complément à 1: C1

•complément à 2: C2

6

0 0 11

0 0 111

0

1 1 11

1 1 111

0

0 0 00

0 0 001

0

+3

-3

+15

-15

+0

-0

exemple: bit de signe

Conventions de représentation

7

Conventions d’utilisation manipulations:

accès: …x…, y = x; mise à jour: x = …; addition: y = x+1;

0 0 11

0 0 100

0 +3 (x)

+1

0 1 000 +4

+

8

Conventions d’utilisation0 0 11

0 0 100

0 +3 (x)

+(+1)

0 0 010 +2

-

0 0 11

0 0 101

0 +3 (x)

+(-1)

0 0 010 +2

+

9

Conventions d’utilisation0 0 11

0 1 000

0 +3 (x)

-(+4)

0 0 101 -1

-

0 1 00

0 0 110

0 +4

-(+3) (x)

0 0 101 -1

-

10

Opérateurs de haut niveau Opérateurs de plus haut niveau:

(plus abstraits)

post/pré-incrémentation: x++; ++x;

post/pré-décrémentation: x--; --x;

donnent une facilité de manipulation

11

Conventions transparentes Transparence des types de base:

00011101010101000101010101010010101010000111111100000101….

0 0 0 1 1

int x;

y = x++;

12

Types de base Types de base:

en C: int, float, char, double, long, short tableaux, struct, etc.

en Pascal: set

en SmallTalk: dictionnaires: {<clé,élément>}

13

Types structurés types de base modélisation de base

traitement numérique (appl. scientifiques) traitement de texte (caractères)

types structurés modélisation d’objets enregistrements (étudiants, cours, BD, …) modélisation orientée objet (OO)

types structurés = agrégation d’éléments de base

14

Construction d’un modèle Modélisation:

Réalité Modèle

typedef struct { plan pl[6]; } boite;

typedef struct { float x; float y; float z; } pt;

typedef struct { pt p[4]; } plan;

boite b1; float x;

x

15

Modélisation = transfert Modélisation:

Réalité Modèle

boite b1;…rotation(b1,45);…

16

Les types abstraits

typedef struct { plan pl[6]; } boite;

typedef struct { float x; float y; float z; } pt;

typedef struct { pt p[4]; } plan;

float x;boite b1;…rotation(b1,45);…

boîte noire

Modélisation: modèle près de la réalité modèle distant des détails d’implantation

17

Les types abstraits programme indépendant de

l’implantation du type boite :

boite b1, b2, b3;créer(b1, …);b2 = b1;b3 = b2;rotation(b1,45);pose_sur(b2,b3);

boite est alors un type abstrait!

18

Les types abstraits un type abstrait:

est défini uniquement par ses conventions d’utilisation par le comportement des objets de ce type (i.e., par

les fonctions applicables sur les objets de ce type) ne décrit pas le modèle d’implantation choisi

sert à isoler les programmes des données crée une indépendance des applications face aux

modèles d’implantation (continuité de la programmation structurée)

permet l’encapsulation de la définition d’un type

19

Les types abstraits Indépendance

programmes/données: modularité de développement facilité d’assemblage de modules validation modulaire et continue réutilisation coût d’entretien

20

L’interface avec les types de données de base :

donnéesprogramme

interface

int x, y;

y = x + 1;

int x, y;=, +, -, ++, --, *, /, ...

21

L’interface avec des types structurés :

donnéesprogramme

interface

boite b1;

rotation(b1,45);

boite b1;rotation, pose_sur, ...

22

Modèles d’implantation Choix d’un modèle d’implantation :

Besoins de l’application: temps de réponse volume de données volatilité des données

Ressources disponibles : temps CPU espace-mémoire systèmes d’exploitation et architecture du système complexité: temps de développement, d’implantation

et de mise à jour

23

Définition d’un type abstrait Programmation d’un type abstrait :

donnéesprogramme

interfacespécification formelled’un type abstrait

choix d’un modèled’implantation 

indépendants!!!

24

Cours de structures de données

Gestionnairede données

Programmeurd’application

interface

donnéesprogramme

spécification formelled’un type abstrait

choix d’un modèled’implantation 

Cours de structures de données

25

Tâches à maîtriser

Analyse:-besoins-contraintes

Conception:-choisir un modèle d ’implantation-réaliser l’implantation

Gestionnairede données

Programmeurd’application

interface

donnéesprogramme

spécification formelled’un type abstrait

choix d’un modèled’implantation 

3

4

1 2

26

Liste ordonnée d’éléments (int) L = <8,1,5,4,6> L1 = 8, L2 = 1, L3 = 5, L4 = 4, L5 = 6 <8,1,5,4,6> <8,1,4,6,5>

Utilité?

Un exemple : une liste ordonnée

27

Liste ordonnée d’éléments (int) L = <8,1,5,4,6> L1 = 8, L2 = 1, L3 = 5, L4 = 4, L5 = 6 <8,1,5,4,6> <8,1,4,6,5>

Utilité? liste de réquisitions

Réq.#1:2000 chemises1000 pantalons1500 cravates...

Réq.#2Réq.#3

Réq.#1

Un exemple : une liste ordonnée

28

Liste ordonnée d’éléments (int) L = <8,1,5,4,6> L1 = 8, L2 = 1, L3 = 5, L4 = 4, L5 = 6 <8,1,5,4,6> <8,1,4,6,5>

Utilité? liste de réquisitions file d’attente

32

1

Un exemple : une liste ordonnée

29

Liste ordonnée d’éléments (int) L = <8,1,5,4,6> L1 = 8, L2 = 1, L3 = 5, L4 = 4, L5 = 6 <8,1,5,4,6> <8,1,4,6,5>

Utilité? liste de réquisitions file d’attente parcours de graphe

4

85

6

1

Un exemple : une liste ordonnée

30

Liste ordonnée d’éléments (int) L = <8,1,5,4,6> L1 = 8, L2 = 1, L3 = 5, L4 = 4, L5 = 6 <8,1,5,4,6> <8,1,4,6,5>

Utilité? liste de réquisitions file d’attente parcours de graphe

4

85

6

1

Un exemple : une liste ordonnée

31

Manipulations (opérateurs): L L = ? (i.e., L = 0?) x L? Li

x = L?

L L +i x L -i L L L - x L = L’? L L’? L L’? lister L

L = <8,1,5,4,6>

Opérateurs d'une liste

32

Autres opérateurs?

sous-liste de L, à partir de i, pour une longueur de n: L[i,n]

concaténation de listes: L + L’

L = <8,1,5,4,6>

L[2,3] = <1,5,4>

L = <8,1,5,4,6>L’ = <1,9>

L + L’ = <8,1,5,4,6,1,9>

Opérateur : concaténation

33

Spécification formelle exemple d’utilisation: L L +posx

prototype de la fonction implantant l’opérateur: liste ajoutL(liste L, typeEl x, int pos, int *err);

préconditions conditions devant être vraies au départ pour assurer le bon fonctionnement de l ’opérateur

L ne doit pas être pleine et pos [1,|L|+1]

postconditions conditions étant vraies (observables) après l’application (correcte) de l’opérateur

L contient x si les préconditions sont respectées L est inchangée sinon *err contient 0 si l'ajout s'est bien déroulé, 1 si L est pleine, 2 si pos [1,|L|+1]

valeur(s) retournée(s) en output de l’application de l ’opérateur: L mise à jour ou L inchangée en cas d'erreurs

34

Spécification du type liste : -pos

L -posL

prototype: liste enleverPosEl(liste L, int pos, int *err);

préconditions: pos [1,|L|]

postconditions: L est inchangée si pos [1,|L|] avec *err = 2 L contient un élément de moins, l’élément Lpos avec *err=0,

sinon

valeur(s) retournée(s): L mise à jour ou inchangée en cas d'erreurs

35

Spécification du type liste : -

L L - x

prototype: liste enleverXL(liste L, typeEl x, int *err);

préconditions: x doit appartenir à L

postconditions: L contient un élément x de moins (le premier rencontré)

avec *err = 0 *err = 3 si x L

valeur(s) retournée(s): L inchangée si x n’appartenait pas à L L mise à jour sinon

36

Spécification du type liste : Lpos

Lpos

prototype: typeEl elL(liste L, int pos, int *err);

préconditions: pos [1,|L|]

postconditions: L est inchangée avec *err = 0 L est inchangée et *err = 2 si pos [1,|L|]

valeur(s) retournée(s): Une copie de Lpos si préconditions respectées