Université des Sciences et Technologies de Lille

Licence Miage - Programmation 1
Examen de janvier 2000

Durée : 3 heures.
Documents autorisés. Calculatrices non autorisées

Dans chacun des deux exercices, vous pouvez utiliser les fonctions ou procédures définies aux questions précédentes, même si vous n'avez pas su les écrire.

Exercice 1 (7 points)

Vous partez en voyage, et vous avez fait n valises, de poids respectifs p₁, ..., p_n. Malheureusement, le poids des bagages est réglementé par le transporteur aérien avec lequel vous partez et la limite fixée L est inférieure au poids total de vos bagages. Le problème est de trouver la sélection de valises qui satisfasse au mieux la contrainte de poids, c'est-à-dire trouver quel est le sous-ensemble E de {1, ..., n} qui maximise å_{i Î E} p_i sous la contrainte å_{i Î E} p_i £ L. Pour cela, l'algorithme procède par examen systématique de toutes les sélections possibles et conserve la meilleure.

Toutes les valeurs p₁, ..., p_n, L sont supposées entières. On dispose d'un type Bagages représentant l'ensemble des valises, caractérisées par leurs poids.

     type Bagages is array(Natural range <>) of Positive;

Pour n valises, remarquez qu'une sélection peut être représentée par un tableau de booléens indexé de 1 à n. On définit donc le type

     type Selection is array(Natural range <>) of Boolean;

Question 1. Le premier travail demandé par l'algorithme est de savoir énumérer toutes les sélections d'un ensemble de bagages. Proposez un ordre d'énumération, puis écrivez une fonction

     Suivante(S:Selection) return Selection

qui retourne la sélection qui succède à S dans l'ordre d'énumération.

Question 2. Écrire une fonction Selectionner(B:Bagages; L:Natural) return Selection qui pour un ensemble de bagages B et un poids limite L détermine la sélection optimale.

Question 3. Quelle est la complexité de la fonction Selectionner ?

Exercice 2 (13 points)

Le chevauchement maximal entre deux mots U et V est la taille du plus long mot qui soit en même temps suffixe de U et préfixe de V. Notez bien que cette notion n'est pas symétrique en U et V. Par exemple, le chevauchement maximal de AGGTCA avec TCAGTGTA est 3 et le chevauchement maximal de TCAGTGTA avec AGGTCA est 1.

On s'intéresse plus précisément aux chevauchements entre mots représentant des fragments d'ADN, qui sont des mots formés à partir des quatre lettres A, C, G et T (représentant quatre nucléotides). Pour simplifier, on suppose pour l'instant qu'un fragment d'ADN est de longueur constante, 200.

Question 1. Écrire un type ADN représentant un fragment d'ADN.

Question 2. Écrire une fonction Chevauchement(U,V:ADN) return Natural qui calcule le chevauchement maximal de U avec V.

On souhaite en fait étudier l'assemblage d'une famille de fragments d'ADN en une unique séquence, à partir des chevauchements entre fragments. (Ce problème trouve sa motivation dans un contexte biologique, quand on veut séquencer de longues molécules d'ADN.) Une famille de fragments est représentée par le type Jeu

        type Jeu is array(Positive range <>) of ADN;

Par exemple, si le jeu de fragments est (AATCCA, ACCG, CGAAT, CAG) un assemblage possible est [2,3,1,4], qui correspond à

Un algorithme pour traiter cette question est le suivant. Soit T=(U₁, ..., U_n), le jeu de fragments à assembler.

On crée une matrice M de dimension n× n, où M(i,j) est égal au chevauchement maximal de U_i avec U_j si i¹ j. Par convention, les valeurs de la diagonale sont -1, pour indiquer qu'un fragment ne peut pas être assemblé avec lui-même.
On construit ensuite de manière incrémentale une liste L représentant l'ordre d'assemblage des fragments suivant la stratégie ci-dessous.
- Initialement, L est vide.
- On sélectionne dans la matrice M le couple de mots U_i et U_j de chevauchement maximal, et on les assemble: L= [i, j]. Cet assemblage entraine qu'aucun fragment ne plus être associé à droite de U_i, ni à gauche de U_j. On met à jour la matrice M, en marquant à -1 les coefficients concernés.
- On cherche ensuite U_k tel que le chevauchement de U_k avec la tête de L ou de la fin de L avec U_k soit maximal. On ajoute k à L, en tête ou en queue suivant le cas. De nouveau, la matrice doit être mise à jour.
- On recommence l'étape précédente, jusqu'à avoir assemblé tous les fragments. La liste L contient alors n éléments.

Question 3. Le type Matrice est défini par

      type Matrice is array(Positive range <>, Positive range<>) of Integer;

Écrire la fonction Initialisation(T:Jeu) return Matrice qui retourne la matrice suivant la règle 1.

On vous fournit le paquetage Paq_Liste, implémentant le type Liste avec des primitives pour l'ajout en tête et en fin d'éléments.

     generic
        type Element is private;
     Package Paq_Liste is
        type Liste  is private;
        procedure Initialiser(F:in out Liste);
        function Est_Vide(F:Liste) Return Boolean;
        procedure Ajout_tete(F:in out Liste; P: out Element);
        procedure Ajout_fin(F:in out Liste; P:in Element) ;
     private
         ...
    end Paq_Liste;

Pour l'instant, ne vous occupez pas de la partie privée du paquetage.

Question 4. Écrire la fonction Assemblage(T:Jeu) return Liste qui construit une liste d'assemblages suivant la règle 2.

Question 5. Comment peut-on améliorer le type ADN de la question 1 pour pouvoir traiter l'assemblage de fragments d'ADN de taille variable ?

Question 6. Écrire la spécification qu'un paquetage générique qui permettrait l'assemblage de fragments de n'importe quelle taille, sur un alphabet quelconque.

Question 7. Revenons au paquetage Paq_Liste. Complétez la spécification et écrivez le corps des fonctions Ajout_tete et Ajout_fin.