Programmations

Janvier 2004

DEVOIR DE SYNTHESE 2° ANNEE - INSA de LYON

Module "PROGRAMMATIONS"

Tous documents autorisés - Durée : 3 heures

Barème indicatif : 7 points sur les exercices, 13 points sur le problème.

NB. La recopie d’extraits des supports de cours sans adaptation au sujet ne donnera pas de points. Présenter correctement avec indentation et commenter les points délicats.

EXERCICES (ne pas recopier les énoncés sur votre copie)

Soit les déclarations suivantes :

Const MaxLignes = 30 ; MaxColonnes = 50 ; {nous prendrons 6 et 8 dans les exemples}

Type t_lignes = 1..MaxLignes ; t_colonnes = 1..MaxColonnes ;

t_val = array[t_lignes,t_colonnes] of integer ;

t_matrice = record nblignes : t_lignes ; nbcolonnes : t_colonnes ;

info : t_val end ;

Si X est de type t_matrice, les valeurs entières utiles pour X.info vont de 1 à X.nblignes pour les indices des lignes et de 1 à X.nbcolonnes pour les indices des colonnes.

Q1 : Donner la déclaration et la réalisation d’une fonction booléenne EXO1 qui à partir d’une matrice fournie A de type t_matrice renvoie dans un booléen vrai si la matrice a au moins N lignes et M colonnes et faux sinon. On considère que N et M sont deux entiers fournis et la fonction EXO1 a donc 3 paramètres.

Q2 : Donner la déclaration et la réalisation d’une fonction booléenne EXO2 qui à partir de deux matrices A et B fournies de type t_matrice renvoie vrai si les contenus de A et B sont identiques et faux sinon. Rappelons que la comparaison directe d’enregistrements n’est pas utilisable.

Q3 : Donner la déclaration et une réalisation de la procédure EXO3 qui à partir d’une matrice fournie A de type t_matrice renvoie dans B de type t_matrice la sous-matrice carrée de taille N ayant pour coin supérieur gauche A.info[X,Y] où X et Y désignent une position valide dans A (à valeur dans t_lignes et t_colonnes). Un dernier paramètre booléen OK indique si cette extraction a été possible et donc si B a des valeurs significatives (vrai dans ce cas, faux sinon). Ainsi, sur la matrice A représentée ci-dessous à gauche, si l’on demande l’extraction de la sous-matrice carrée de taille N = 3 et de coin supérieur gauche X = 1 et Y = 1, on obtient la matrice B représentée à droite. L’extraction avec X = 4 et Y = 3 n’est pas faisable.

5	6	1	4	9	2	9	5	.	.
		7	2	1	4	9	6	.	.
A		8	3	7	2	1	2	.	.
		4	5	8	3	7	1	.	.
		7	8	3	2	9	4	.	.
		.	.	.	.	.	.	.	.

3	3	1	4	9	.	.	.	.	.
		7	2	1	.	.	.	.	.
B		8	3	7	.	.	.	.	.
		.	.	.	.	.	.	.	.
		.	.	.	.	.	.	.	.
		.	.	.	.	.	.	.	.

Q4 : Même question pour une procédure EXO4 qui doit renvoyer la sous-matrice, lorsquelle existe, pour laquelle A.info[X,Y] désigne son coin inférieur droit. Ainsi, si l’on demande l’extraction sur A de la sous-matrice carrée de taille N = 3 et de coin inférieur droit X = 4 et Y = 5, on obtient la même matrice B représentée ci-dessus. L’extraction avec X = 2 et Y = 3 n’est pas faisable.

PROBLEME : Réseaux de transport

Les pouvoirs publics sont très intéressés par l’amélioration de la circulation et la sécurité des usagers des réseaux de transport en commun avec, par exemple, de nouvelles utilisations du robot YARSOZK. Sur un arrêt de bus ou des quais de stations de métro, il peut prendre chaque usager en photo. Le robot YARSOZK coûte très cher et il n’est installé que dans un nombre limité de stations. Une association souhaite proposer aux usagers qui n’aiment pas être pris en photo un programme de calcul d’itinéraires. Il faut essayer, si possible, de relier une station X à une station Y sans jamais monter dans ou descendre d’un moyen de transport dans une station équipée du robot YARSOZK.

Nous allons repérer les stations par des codes entiers. Le petit réseau de transport représenté ci-dessous comporte 4 lignes et 8 stations. Ainsi, on peut aller de la station 3 aux stations 2, 4 et 6. On doit pouvoir travailler avec des nombres très variables de stations par ligne ce qui va justifier le choix d’une structure dynamique. On utilise les concepts de chemin (succession de stations) et de ligne (succession de stations desservies en séquence par un même train ou bus). Une ligne peut être décrite par deux chemins mais les chemins ne servent pas seulement à décrire des lignes : ils sont utilisés aussi dans la construction d’itinéraires. Par exemple, on peut parler du chemin C10 qui emprunte les stations 1, 2, 3 et 6 (par utilisation des lignes L1 et L3).

Ligne L1 : chemins C1/C2 (1-2-3-4/4-3-2-1)

Ligne L2 : chemins C3/C4 (5-6-7/7-6-5)

Ligne L3 : chemins C5/C6 (8-6-3/3-6-8)

Ligne L4 : chemins C7/C8 (1-5-8/8-5-1)

1 2 3 4

5 6 7

8

Nous allons tout d’abord nous intéresser à la gestion des chemins représentés grâce aux types suivants :

Type t_pposte = ^t_poste ;

t_poste = record station : integer ; photo : boolean ;

suite : t_pposte end ;

t_chemin = record nom : string ;

debut : t_pposte ;

fin : t_pposte  end ;

On peut représenter le chemin C10 (1-2-3-6) qui conduit des stations 1 à 6 par :
C10

1 F 2 T 3 F 6 F

Le champ photo dit si la station est équipée du robot YARSOZK (T pour « true ») ou pas (F pour « false »). Ainsi, on note que la station 2 est équipée du robot.

Sur une variable C de type t_chemin, C.debut désigne le premier poste de la liste de stations et C.fin désigne le dernier poste. La succession des valeurs prises par le champ station dans les postes de la liste donne des stations pour aller de C.debut^.station à C.fin^.station.

Q5. Donner une réalisation de la fonction Init_Chemin qui renvoie une valeur de type t_chemin en donnant au nouveau chemin le nom Nom_Chemin.

Function Init_Chemin (Nom_Chemin : string) : t_chemin ;
Q6. Donner une réalisation de la procédure Ajout_Station_Chemin qui transforme la valeur de C de type t_chemin en ajoutant toujours en queue de la liste linéaire de tête C.debut un poste pour la station désignée par Num.

Procedure Ajout_Station_Chemin (Var C : t_chemin ; Num : integer) ;
Q7. Donner une réalisation de la procédure Cherche qui, étant donné C de type t_chemin et une station Num, renvoie, lorsqu’un poste correspondant à Num existe dans C, deux pointeurs P et PP de type t_pposte de sorte que P pointe le poste pour lequel station vaut Num alors que PP désigne le poste précédent celui pointé par P dans la structure chaînée. Lorsque la station n’appartient pas au chemin C, ces deux pointeurs doivent valoir NIL et le paramètre OK a la valeur fausse (vraie sinon).

Procedure Cherche (C:t_chemin ; Num :integer ; Var P,PP : t_pposte; Var OK:boolean) ;

Q8. Proposer une réalisation de la procédure Concat qui concatène (met bout à bout) deux chemins C1 et C2 de type t_chemin pour produire un chemin C3 de type t_chemin lorsque la dernière station de C1 est égale à la première station de C2. C3 ne contiendra qu’une occurrence de cette station de liaison. Ainsi, si C1 comporte 1 puis 2 puis 3 et C2 comporte 3 puis 6, alors C3 contiendra 1 puis 2 puis 3 puis 6. Cette condition sur les deux chemins C1 et C2 est supposée vérifiée à l’appel de Concat.

Procedure Concat (C1, C2 : t_chemin ; Var C3 : t_chemin) ;

Q9. Proposer une réalisation de la procédure Detruire qui supprime dans C de type t_chemin la station désignée par Num. On suppose ici que cette station appartient bien à C.

Procedure Detruire (Var C : t_chemin ; Num : integer) ;

On construit maintenant une représentation de l’ensemble des lignes (et donc du réseau de transport) en utilisant la structure de données définie ci-dessous. Si R est de type t_reseau, R.val est un tableau d’au plus 100 éléments et R.nb dit combien de chemins sont effectivement stockés. On peut ainsi mémoriser les chemins correspondant à au plus 50 lignes de métro ou de bus. En effet, par convention, si le i-ème élément du tableau R.val donne la succession des postes pour aller du terminus X au terminus Y, on décide que le i+1-ième élément de ce même tableau donne celle qui permet d’aller de Y à X.

Const Max_Lignes = 100 ;

Type t_reseau = record nb : integer ;

val : array [1..Max_Lignes] de t_chemin  end ;
La construction d’un réseau se fait à l’aide de la procédure Construire_Réseau qui ne vous est pas demandée et dont l’entête est :

Procedure Construire_Réseau (Var Reseau : t_reseau ; Var nb_lignes : integer) ;
On suppose que la valeur de nb est toujours inférieure ou égale à Max_Lignes et vaut 0 lorsque la structure est vide.
Q10. En supposant qu’un réseau R de type t_reseau a été créé, proposer une procédure Direct qui renvoie dans son paramètre OK vrai s’il existe un chemin conduisant sans changement de la station X à la station Y (faux sinon). Quand OK vaut vrai, IT de type t_chemin est le chemin direct de longueur minimale (en nombre de stations) pour aller de X à Y. On suppose que X et Y sont des stations différentes. Quand OK vaut faux, la valeur de IT ne sera pas exploitée.

Procedure Direct (R : t_reseau ; X, Y : integer ; Var OK : boolean ; Var IT : t_chemin) ;
NB. On pourra utiliser une fonction Long fournie, qui, étant donné un chemin C de type de t_chemin renvoie le nombre de stations dans ce chemin.

Function Long (C : t_chemin) : integer ;
Q11. En supposant qu’un réseau R de type t_reseau a été créé, proposer une procédure Route qui renvoie dans son paramètre OK vrai si il est possible de relier la station X à la station Y avec au plus un changement de ligne (faux sinon). Quand OK vaut vrai, IT de type t_chemin est le chemin de longueur minimale avec au plus un changement de ligne pour aller de X à Y. Quand OK vaut faux, la valeur de IT ne sera pas exploitée. Ainsi, dans le réseau donné en exemple, le plus court chemin avec au plus un changement pour aller de 1 à 7 est celui qui passe par les stations 1, 5, 6 puis 7.

Procedure Route (R : t_reseau ; X, Y : integer ; Var OK : boolean ; Var IT : t_chemin) ;

On peut maintenant s’intéresser aux usagers photophobes.

Q12. On veut traiter le même problème que dans la question précédente avec une procédure Photophobes ayant les mêmes paramètres que Route et calculant, lorsque cela est possible, un chemin de la station X à la station Y sans monter ou descendre à une station équipée du robot. Si X et Y sont équipées du robot, il est clair qu’il n’existe pas de solution et l’on suppose que le cas ne se produit pas.

Procedure Photophobes (R : t_reseau ; X, Y : integer ;

Var OK : boolean ; Var IT : t_chemin) ;

Q12a. Expliquer la réalisation de Photophobes par modification du code de la procédure Route (Question Q11) sans forcément recopier ce qui est inchangé.

Q12b. Expliquer comment on pourrait réutiliser sans modification la procédure Route (Question Q11) pour faire le travail demandé à Photophobes mais à condition d’avoir modifié la représentation R du réseau.