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 ji Î Ej Î 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.