DEUG MIAS M2

Structures de données

Types abstraits et Types concrets
Un type est une classe de données ayant des propriétés communes. Les types sont utilisés pour aider à vérifier la correction des programmes, pour traduire les programmes en code exécutable (compilation), etc. C'est une notion fondamentale de l'informatique.
Dans la suite on va parler de types abstraits et de types concrets. On utilise les types abstraits pour la réalisation et les types concrets pour le codage. Les types concrets dépendent donc du langage de programmation que l'on utilise.
Types abstraits
Un type abstrait est définit par :
•	un nom ;
•	un ensemble de constructeurs (constantes ou fonctions) qui permettent de produire des données du type abstrait à partir d'autres données ;
•	des opérateurs qui permettent de manipuler les données du type abstrait ;
•	parfois, des invariants qui caractérisent les données du type abstrait.
Exemple :
Par exemple, on peut parler du type polynôme car tout polynôme peut être représenté par un degré et une suite de coefficients ci :
P(x) = cnxn + cn-1xn-1 + … + c1x + c0
On peut avoir définir deux constructeurs :
•	le polynôme constant (degré 0)
•	une fonction qui prend un polynôme P et un terme constant C et construit le polynôme P.x + C
Les opérations sur les polynômes peuvent être par exemple :
•	l'addition, la multiplication par une constante, le quotient, etc.
•	l'évaluation pour un x donné, etc.
La déclaration peut se faire de la façon suivante :
type polynôme
	{ constructeurs }
	polynôme_nul
	construire : polynôme * réel -> polynôme
	{ opérations }
	ajouter : polynôme * polynôme -> polynôme
	éval : polynôme * réel -> réel
Types concrets
Les types concrets sont les types utilisés dans les langages de programmation. Alors qu'un type abstrait ne fait aucune supposition sur la représentation (le codage) des données du type, un type concret définit précisément l'implantation en machine des donnés de ce type, et les opérations prédéfinies qui sont disponibles. 
Par exemple, un type abstrait "entier naturel" représente tout nombre ≥ 0, mais le type concret correspondant peut ne coder que les entiers entre 0 et 65535.
Les constructeurs et les opérations du type abstrait sont :
•	soit codées par des fonctions et des procédures du langage ;
•	soit codées directement par les opérations prédéfinies du type concret.
Dans le premier cas on parle de codage explicite et dans le second de codage implicite (vu en M1).
Dans un langage impératif, il faut déclarer le type de chaque variable, argument et valeur de retour de fonction du programme. Cela permet de vérifier que les constructions du programme sont correctes du point de vue des types. Nous reviendrons sur ce point en détail plus tard. Par exemple :
•	affectation v := expr. Il faut que v et expr soient de même type (entier par exemple). Dans certains cas on accepte des types compatibles (entier et réel par exemple).
•	conditionnelle, itérations tantque et répéter : l'expression doit avoir un type booléen (vrai ou faux).
Les types concrets d'un langage de programmation sont
•	les types de base (primitifs)
•	les types composés (structurés)
Dans la suite, on décrit un ensemble de types abstraits de base et composés qui correspondent (à peu près) aux types concrets usuels des langages impératifs. L'usage de ces types abstraits permettra de faciliter le codage implicite, qui est en général plus efficace à exécuter et plus concis à écrire.
Types de base
Les types de base sont les types les plus simples et correspondent généralement aux entités manipulées directement par la machine.
Types énumérés
Un type énuméré est défini par un domaine fini, décrit par l'énumération de ses éléments :
type carte
	{constantes: }
	pique, coeur, carreau, trèfle
On utilisera la notation plus concise suivante :
type carte = (pique, coeur, carreau, trèfle) 
Les constante d'un type énuméré sont ordonnées, selon l'ordre de leur déclaration. Cela permet de définir un constructeur et 3 opérations sur tout type énuméré :
image : entier -> carte	{ constructeur }
ord : carte -> entier		{ indice dans l'énumération }
suivant : carte -> carte	{ élément suivant }
précédent : carte -> carte	{ élément précédent }
Cela nous permet de définir plusieurs invariants :
image(ord(x)) = x
image(x) défini => ord(image(x)) = x
suivant(x) = image(ord(x) + 1)
précédent(x) = image(ord(x) - 1)
Le type booléen est prédéfini avec les valeurs faux et vrai. Les opérations de l'algèbre de Boole sont définies sur les booléens :
et : booléen * booléen -> booléen
ou : booléen * booléen -> booléen
non : booléen -> booléen
Le type caractère est prédéfini et représente l'ensemble des caractères imprimables. On note les constantes de ce type entre quotes : 
'a', 'b', ..., 'z', '0', ..., '9', ';', '$', ...
Types numériques
Les types entier et réel sont prédéfinis. Les opérations arithmétiques et logiques usuelles sont définies sur ces types. Un entier peut être converti en réel et un réel peut être converti en entier (par troncature de la partie décimale).
Il y a une différence importante entre les types numériques abstraits, qui correspondent aux ensembles Z et R, et les types concrets, qui ne représentent qu'un ensemble fini de valeurs.
Types intervalles
On définit un type intervalle à partir d'un type énuméré ou du type entier par la notation suivante :
type rouge = couleur dans [coeur .. carreau]
type lettres = caracrtère dans ['a' .. 'z']
type dizaine = entier dans [10 .. 19]
Un type intervalle représente l'ensemble des constantes comprises entre les deux bornes de l'intervalle. Cette définition a un sens puisque les constantes d'un type intervalle sont toujours ordonnées.
Des règles particulières s'appliquent pour que les valeurs d'un type intervalle soient converties en valeur de leur type de base. Elles seront décrites plus tard.
Types composés
Les types composés (appelés aussi types structurés) sont définis à partir d'un constructeur de type et d'un ou plusieurs types composants. Nous allons voir :
•	les types produit ;
•	les types tableau ;
•	les types somme.
Types produit
Un type produit est construit à partir d'un ensemble de composants. Chaque composant peut être extrait par une opération dite de projection :
type complexe
	{ constructeur }
	creer_complexe : réel * réel -> complexe
	{ operations }
	partie_réelle : complexe -> réel 
	partie_imaginaire : complexe -> réel 
On appelle ce type un type enregistrement ou structure, les composants s'appellent des champs  et on le note :
type complexe : produit
		re : réel
		im : réel
	fin
La notation pointée permet d'accéder aux champs 
c.re = partie_réelle (c)
c.im = partie_imaginaire (c)
On peut définir d'autres opérations sur les nombres complexes, comme le module et l'argument. (Noter que dans ce cas, on aurait pu représenter également un nombre complexe par son module et son argument, et avoir des opérations retournant les parties réelles et imaginaires.)
Les champs d'un enregistrement peuvent apparaitre en partie gauche d'une affectation :
c.re <- 1.0
Cela est équivalent à utiliser une nouvelle opération :
changer_partie_réelle : complexe * réel -> complexe
qui vérifie l'invariant :
partie_réelle (changer_partie_réelle (c, r)) = r.
L'affectation
c.re <- 1.0
est équivalente à
c <- changer_partie_réelle (c, 1.0)
Si l'on veut que le programme vu au premier cours puisse calculer des racines complexes, il suffit de modifier le cas d < 0 :
	lexique
		c1, c2 : complexe
	début
		...
		selon le cas d
			...
			d < 0 :
				c1.re <- -b / 2*a
				c1.im <- √d / 2*a
				c2.re <- -b / 2*a
				c2.im <- -√d / 2*a
Types tableau
Le type tableau permet de représenter des fonctions à domaine fini : à chaque valeur d'un indice, le tableau associe une valeur ou élément de tableau.
Par exemple, on peut représenter les valeurs des cartes dans un jeu par :
type carte = (roi, dame, valet, as)
type valeur_carte 
	{ opérations }
	valeur : tableau * carte -> entier
	change_valeur : tableau * carte * entier -> tableau
A chaque carte, le tableau fait correspondre une valeur entière, accessible par l'opération valeur. On peut changer la valeur qui correspond à une carte par l'opération change_valeur. On peut se représenter un tableau comme un bloc-tiroirs dont chaque tiroir a une étiquette correspondant à son indice dans le tableau et dont le contenu est la valeur. Chaque tiroir est appelé un élément du tableau.
Un invariant de tableau est le suivant :
valeur (change_valeur (t, c, x), c) = x
Pour faciliter l'usage des tableaux, on les note comme suit :
type carte = (roi, dame, valet, as)
type valeur_carte = tableau [carte] de entier
Le type de l'indice (ici carte) doit être un type énuméré ou intervalle. Le type des éléments (ici entier) peut être quelconque. Pour accéder aux éléments d'un tableau, on utilise la notation indicée :
t[i] = valeur (t, i)
Un élément de tableau peut apparaitre en partie gauche d'une affectation, ce qui permet de changer sa valeur :
t[i] <- v 
est équivalent à
t <- changer_valeur (t, i, v)
L'accès à un élément de tableau n'est légal que si l'indice est compris dans l'intervalle défini à la déclaration du tableau.
Avec l'exemple des cartes :
type carte = (roi, dame, valet, as)
lexique
	points : tableau [carte] de entier
	main : tableau [1..5] de carte
	total : entier
début
	points[roi] <- 10
	points[dame] <- 9
	points [valet] <- 8
	points [as] <- 1
	pour i parcourant [1..5] faire
		main [i] <- carte_hasard
	
	total <- 0
	pour i parcourant [1..5] faire
		total <- total + points[main[i]]
Lorsque l'on utilise comme indice un type intervalle d'entier, on retrouve pratiquement la notation indicée usuelle en mathématiques :
type vecteur = tableau [1..10] de réel
	somme_vecteur = vecteur * vecteur -> vecteur
	produit_scalaire = vecteur * vecteur -> réel

fonction somme_vecteur (v1, v2) 
lexique
	v : vecteur
	i : 1..10
début
	pour i parcourant [1..10]
		v[i] <- v1[i] + v2[i]
	retourner v

fonction produit_scalaire (p, q) 
lexique
	produit : réel
	i : 1..10
début
	produit <- 0
	pour i parcourant [1..10]
		produit <- produit + p[i] * q[i]
	retourner produit
Cet exemple montre que l'on peut considérer le type tableau comme un type produit particulier. Pour des vecteurs à 3 dimensions, au aurait pu écrire :
type vecteur3D = produit
		x, y, z : réel
	fin
	somme3D = vecteur3D * vecteur3D -> vecteur3D

fonction somme3D (v1, v2) 
lexique
	v : vecteur3D
début
	v.x <- v1.x + v2.x
	v.y <- v1.y + v2.y
	v.z <- v1.z + v2.y
	retourner v
On voit que l'écriture est plus lourde, surtout si l'on avait des vecteurs à 10 dimensions. On remarque cependant la similitude entre la notation pointée et la notation indicée.
Tableaux multi-dimensionnels
On peut définir des tableaux multi-dimensionnels (ou matrices) en utilisant le fait que les éléments d'un tableau peuvent eux-même être des tableaux :
type matrice= tableau [1..4] de tableau [1..4] de réel
L'accès se fait alors par :
lexique
	m : matrice
début
	m[1][1] <- 0
Pour simplifier la notation, on peut écrire :
type matrice = tableau [1..4, 1..4] de réel
lexique
	m : matrice
début
	m[1, 1] := 0
Exemple 1 - type Liste
On peut décrire un type "liste d'entiers" par le type abstrait suivant :
type Liste
	{ constructeurs }
	ListeVide
	Cons : entier * Liste -> Liste
	{ opérations }
	Longueur : Liste -> entier
	Tete : Liste -> entier
	Fin : Liste -> Liste
	Concat : Liste * Liste -> Liste
	...
Une façon de représenter ce type abstrait par un type concret est d'utiliser un tableau qui va contenir les éléments de la liste :
type Liste = produit
		longueur : entier
		contenu : tableau [1..max] de entier
	fin

fonction ListeVide : Liste
lexique
	l : Liste
début
	l.longueur := 0
	retourner l
fin

fonction Cons (x : entier, l : Liste) : Liste
lexique
	i : entier
	res : Liste
début
	{ il faudrait verifier que longueur ≤ max }
	res.longueur := l.longueur + 1
	pour i parcourant [1..l.longueur]
		res.contenu [i+1] <- l.contenu [i]
	retourner res
fin

...
Pour des raisons d'efficacité, on peut souhaiter que Cons ajoute l'élément dans la liste passée en argument plutôt que de retourner une nouvelle liste. Il serait alors judicieux de mettre les éléments dans la liste dans l'ordre inverse. Ainsi un ajout en tête de liste revient a ajouter l'élément a la fin du tableau :
procédure Cons (x : entier, donnée-résultat l : Liste)
début
	{ il faudrait verifier que longueur ≤ max }
	l.longueur := l.longueur + 1
	l.contenu [l.longueur] <- x
fin
Exemple 2 - type Graphe
On veut représenter les relations entre un ensemble de gares SNCF. On se donne un type énuméré représentant les gares :
type gares = (Lille, Paris, Lyon, Nancy, 
			Marseille, Bordeaux, Nice)
Considérons les liaisons suivantes :

On peut aussi les représenter dans un tableau à deux dimensions :
	Lille	Paris	Lyon	Nancy	Marseille	Bordeaux	Nice	
Lille		X	X					
Paris	X		X	X	X	X		
Lyon	X	X		X	X			
Nancy		X	X					
Marseille		X	X				X	
Bordeaux		X						
Nice					X			
Ce tableau peut être représenter par un type tableau :
type ligne_SNCF = tableau [gares, gares] de booléen
Un tel graphe de connexions peut être utilisé pour répondre a un certain nombre de questions :
•	Peut-on se rendre de n'importe quelle gare à n'importe quelle autre gare ? (Le graphe est-il connexe ?)
•	Etant données deux gares A et B combien y a-t-il au minimum de changements ? (Plus cours chemin).
•	etc.
On peut aussi remplacer les croix par des distances kilométriques, et calculer ainsi la distance entre deux gares. On peut également avoir des liaisons à sens unique (la matrice n'est alors plus symétrique).
Types somme
Le type somme permet de représenter des unions disjointes de domaines.
Par exemple, les solutions d'une équation du second degré peuvent être :
•	2 racines réelles ;
•	2 racines complexes ;
•	une racine double ;
On peut définir le type abstrait suivant pour représenter ces solutions :
type solutions
	{constructeurs}
	réelles : réel * réel -> solutions
	complexes : réel * réel -> solutions
	double : réel -> solution
	
	{opérations}
	type_solution -> réelles | complexes | double
	
	{invariants}
	tag (réelles (r1,r2)) = réelles
	tag (complexes (c1, c2)) = complexe
	tag (double (d)) = double
On note un type somme de la façon suivante :
type type_solution = (réelles, complexes, double) 
type solutions = somme selon t : type_solution
		réelles : r1, r2 : réel
		complexes : c1, c2 : réel
		double : d : réel
	fin
Le type somme se comporte comme un type enregistrement : t, r1, r2, c1, c2, r sont des champs accessibles par la notation pointée. Le champ t est appelé "tag" ou "discriminant" car il indique dans quel sous-domaine on se trouve.
lexique
	racines : solutions
début
	...
	selon le cas d
		d > 0 :
			racines.t <- réelles
			racines.r1 <- ...
			racines.r2 <- ...
		d = 0 :
			racines.t <- double
			racines.d <- ...
		d < 0 :
			racines.t <- complexes
			racines.c1.re <- ...
			racines.c1.im <- ...
			racines.c2.re <- ...
			racines.c2.im <- ...
Il faut noter que l'accès à un champ n'est légal que si la valeur du discriminant correspond au sous-domaine qui contient ce champ. Ainsi, dans l'exemple ci-dessus, racines.d est illégal si racines.t vaut réelles.