HC bis
Jean-Jacques Lévy
30 Mai 2002
Avertissement La rédaction doit être claire, concise et
précise.
Soit n³ 0 un entier. On représente un sous-ensemble X de
l'ensemble E={0,... ,n-1} par la liste chaînée de ses
éléments en ordre croissant. On dira aussi que X est une partie de
E. Une classe déclarée Partie correspond à ces listes.
Question 1 Définir la classe Partie.
Question 2 Ecrire la fonction
Partie union (Partie x, Partie y)
qui calcule l'union des parties X et Y. Donner la complexité de
cette fonction.
On considère une relation binaire R sur E et son graphe
associé, c'est-à-dire le sous-ensemble de E × E des
paires d'entiers vérifiant la relation
graphe(R) = {(i,j) | i R j, i Î E, j Î E}
Supposons donné un ensemble de relations c1, c2, ...ck de
graphes X1, X2, ...Xk donnés. Alors on considère une
algèbre de termes r, s, t, ..., représentant des relations
binaires. Un terme r ou s est défini récursivement par:
| r,s |
::= |
r + s |
union |
| |
| |
r s |
composition |
| |
| |
r-1 |
inverse |
| |
| |
ci |
graphe donné |
Plus précisément, si r et s sont deux termes qui représentent les
relations de graphes X et Y, alors r + s représente la relation
de graphe X È Y. De même la composition rs représente la
relation de graphe {(i,j) | $ kÎ E, (i,k)Î X, (k,j)Î
Y}. Enfin r-1 a pour graphe {(i,j)|(j,i)Î X}.
Question 3 Définir la classe abstraite Relation et ses
sous-classes Union, Composition, Inverse, et Graphe. (La classe Graphe utilisera la représentation creuse
des graphes par un tableau des listes de successeurs de chaque sommet
i, vue dans le cours.)
Question 4 Définir dans ces classes une méthode
Graphe graphe()
telle que r.graphe()
calcule le graphe de la relation r. En donner sa complexité.
(On utilisera la programmation par objets).
Question 5 Si r est la relation de graphe R, on considère une
nouvelle construction r* de graphe
Si=0¥Ri, et sa classe correspondante
Etoile. L'algèbre des relations devient:
| r,s |
::= |
... |
comme avant |
| |
| |
r* |
Que devient alors la méthode graphe()? Ecrire la fonction
correspondante. Quelle est sa complexité?
This document was translated from LATEX by
HEVEA.