Solution proposée pour le ds du 8 Juin 1998

Solution proposée pour le DS du 8 Juin 1998 (partie Pascal)

========================================================================

PARTIE A Sur 2.75 points

========================================================================
1) Déclaration 0.25 point
Type

tPoint = Record

x,y,z : Real;

luminance : Byte

End;
Remarque : d'autres solutions sont acceptables. Par exemple :

Type

tPoint = Record

coordonnées : Array[1..3] Of Real;

luminance : Byte

End;

2) Déclarations 0.5 point
Type

listePoints = ^postePoint;

postePoint = Record

point : tPoint;

pointSuivant : listePoints

End;
Autre solution (mais moins bonne) :

Type

listePoints = ^postePoint;

postePoint = Record

x,y,z : Real;

luminance : Byte;

pointSuivant : listePoints

End;

3) Procédure d'initialisation de la liste 0.5 point
Procedure initListePoints (Var lp : listePoints);

Begin

lp := Nil

End;

4) Procédure de lecture du fichier 1.5 point
Procedure lireImage ( nomfic : String; Var lp : listePoints);
Var

fic : File Of tPoint;

pposte : ^postePoint;
Begin

Assign (fic,nomfic);

Reset (fic);

initListePoints(lp); {ne pas oublier l'initialisation}

While Not(Eof(fic)) Do

Begin

New(pposte);

Read(fic,pposte^.point);

pposte^.pointSuivant := lp; {chaînage en tête de liste}

lp := pposte

End;

Close(fic) {ne pas oublier la fermeture du fichier}

End;

========================================================================

PARTIE B sur 3.75 points

========================================================================
1) Déclaration 0.25 point
Type

tCoordonnées = Record

x1,y1,z1,x2,y2,z2,x3,y3,z3 : Real

End;
tTriangle = Record

numSurface : Integer;

coordonnées : tCoordonnées

End;
Remarque : d'autres solutions sont acceptables. Par exemple :

Type

tTriangle = Record

numSurface : Integer;

coordonnées : Array[1..9] Of Real

End;
ou encore :

Type

tTriangle = Record

numSurface : Integer;

x1,y1,z1,x2,y2,z2,x3,y3,z3 : Real

End;

2) Déclarations 0.5 point
Type

listeSurfaces = ^posteSurface;

listeTriangles = ^posteTriangle;
posteTriangle = Record

coordonnées : tCoordonnées;

triangleSuivant : listeTriangles

End;
posteSurface = Record

numSurface : Integer;

trianglesAssociés : listeTriangles;

surfaceSuivante : listeSurfaces

End;

3) Procédure d'initialisation 0.5 point
Procedure initListeSurfaces (Var ls : listeSurfaces);
Begin

ls := Nil

End;

4) Procédure de transfert 2.5 points
ON NE DEMANDE PAS DE RESPECTER L'ORDRE CROISSANT POUR LES NUMEROS DES SURFACES
Procedure lireSurfaces (nomfic : String; Var ls : listeSurfaces);
Var

fic : fichierCAO;

triangleLu : tTriangle;

ptSurface : listeSurfaces;

ptTriangle : listeTriangles;

trouvé : Boolean;

Begin

Assign (fic,nomfic);

Reset (fic);

initListeSurfaces(ls); {ne pas oublier l'initialisation}

While Not(Eof(fic)) Do

Begin

{on lit un triangle}

read (fic,triangleLu);

New(ptTriangle);

ptTriangle^ coordonnées := triangleLu.coordonnées;

{on cherche la surface correspondante dans ls}

ptSurface := ls;

trouvé := False;
While (ptSurface <> Nil) And Not(trouvé) Do

Begin

If ptSurface^.numSurface = triangleLu.numSurface Then

trouvé := True

Else

ptSurface := ptSurface^.surfaceSuivante

End; {Begin..End inutile}

If Not(trouvé) Then

Begin {la surface n'existe pas, on la crée, et on l'insère

en tête de la liste des surfaces

sans se soucier de l'ordre des numéros des surfaces}

New(ptSurface);

ptSurface^.numSurface := triangleLu.numSurface;

ptSurface^.trianglesAssociés := Nil;

ptSurface^.surfaceSuivante := ls;

ls := ptSurface

End;
{la surface existe déjà ou vient d'être créée, alors on insère

le triangle en tête de sous-liste}

ptTriangle^.triangleSuivant := ptSurface^.trianglesAssociés;

ptSurface^.trianglesAssociés := ptTriangle

End;

Close(fic) {ne pas oublier la fermeture du fichier}

End;

========================================================================

PARTIE C sur 3.5 points

========================================================================
Déclarations (0.5 point)
Type

couplePointSurface = Record

x,y,z : Real;

numSurface : Integer

End;
fichierSegment = File Of couplePointSurface;

Procédure (3 points)

Procedure ecrireSegmentation( nomfic : String; lp: listePoints;

ls : listeSurfaces);
Var

dMini, dCourante : real;

numSurfaceProche : Integer;

ptSurface : listeSurfaces;

ptTriangle : listeTriangles;

couple : couplePointSurface;

Begin

If ls = Nil Then

Writeln('Pas de surface, segmentation impossible'}

Else

Begin

Assign (fic, nomfic);

Rewrite (fic);
While lp <> Nil Do {pour chaque point}

Begin

{on cherche la surface la plus proche}
{on considère au départ que la surface la plus proche

est la première surface du premier triangle}

With lp^.point Do

With ls^.trianglesAssociés^.coordonnées Do

dMini := distance(x,y,z,x1,y1,z1,x2,y2,z2,x3,y3,z3);

numSurfaceProche := ls^.numSurface;

{une solution dans laquelle on fixe dMini de départ à une valeur très grande

(ex : dMini := 1. E+50) est moins bonne}

{parcours de la liste des surfaces}

ptSurface := ls;

While ptSurface <> Nil Do

Begin
{parcours de la sous-liste des triangles}

ptTriangle := ptSurface.trianglesAssociés;
While ptTriangle <> Nil Do

Begin

With lp^.point Do

With ptTriangle^.coordonnées Do

dCourante:=distance(x,y,z,x1,y1,z1,x2,y2,z2,x3,y3,z3);
If dMini > dCourante Then

{on a trouvé une surface plus proche}

{quand deux surfaces sont à égale distance

du point, on conserve la première surface trouvée}

Begin

dMini := dCourante;

numSurfaceProche := ptSurface^.numSurface

End;

ptTriangle := ptTriangle^.triangleSuivant

End;
ptSurface := ptSurface^.surfaceSuivante

End;
With lp^.point Do

Begin

couple.x := x;

couple.y := y;

couple.z := z;

couple.numSurface := numSurfaceProche

End;

Write(fic,couple);

lp := lp^.pointSuivant

End;

Close(fic) {ne pas oublier la fermeture du fichier}

End;

End;

Solution proposée pour le DS du 8 Juin 1998 (partie BD)

A) Algèbre relationnelle 3 pts

1)(0,5 pt) A = p_{C1, C2} ((Chauffeur _{Numéro=NoChauffeur} Livraison)

_{NoDestinataire=Numéro} (s_{NomVille = ‘Toulouse’} (Client)))

2) (0,5 pt) p_{Numéro, Nom} ( Chauffeur) - A

3) (1 pt) p_Nom (Ville) - p_NomVille (Livraison _{NoDestinataire=Numéro} Client)

4. 
   (1 pt) Couples chauffeur-client qui se connaissent :
   

B = p_{NoChauffeur, NoDestinataire} (Livraison) p_{NoChauffeur, NoExpéditeur} (Livraison)
Ensemble des couples chauffeur-client possibles :

C = p_Numéro (Chauffeur) Ä p_Numéro (Client)
Chauffeurs ne connaissant pas au moins un des clients :
D = p_C1 (C-B)
D’où la requète finale :

p_Numéro (Chauffeur) - D

B) SQL 4 pts Les distinct ne sont pas demandés explicitement.

1) (0,5 pt)

select NoLivraison, sum(Poids)

from Colis

Group by NoLivraison
Exemple de requête contenant une jointure inutile :
select Livraison.Numéro, sum(Poids)

from Livraison, Colis

where Livraison.Numéro=Colis.NoLivraison

Group by Livraison.Numéro

2) (1 pt)

select NomVille, count(*)

from Livraison, Client

where Livraison.NoDestinataire=Client.Numéro

Group by NomVille

3) (1 pt)

select Livraison.NoExpéditeur

from Livraison, Colis

where Colis.NoLivraison=Livraison.Numéro

group by Livraison.Numéro, Livraison.NoExpéditeur

having sum(Colis.Poids)>1000kg

4. 
   (1,5 pt)
   

select NoChauffeur, SUM(Distance)

from Livraison, Client as C1, Client as C2, ReliéeA

where Livraison.NoDestinataire=C1.Numéro

and Livraison.NoExpéditeur=C2.Numéro

and C1.NomVille=ReliéeA.NomVilleArrivée

and C2. NomVille=ReliéeA.NomVilleDépart

group by NoChauffeur

C) Conception 3 pts (ajouts dans les schémas donnés)

Entité-Association (1,5 pt)

Schéma relationnel (1,5 pt)

ParticipeA : (NoEquipier, NoLivraison)

Equipier : (Numéro, Nom, NomVille)

Le modèle logique de données est aussi accepté à la place du schéma relationnel :