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 p1, ..., pn. 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 pi sous la contrainte åi Î E pi £ L. Pour cela, l'algorithme procède par examen systématique de toutes les sélections possibles et conserve la meilleure.

Toutes les valeurs p1, ..., pn, 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=(U1, ..., Un), le jeu de fragments à assembler.
  1. On crée une matrice M de dimension n× n, où M(i,j) est égal au chevauchement maximal de Ui avec Uj 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.

  2. 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.
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.