TD 6 - Pale machine

Votre opinion sur le cours de ce matin : Votre opinion sur le TD de la semaine dernière :

Préambule

Les deux parties sont indépendantes. Les dépendances entre les questions sont indiquées en début de question.

La clarté du code, sa bonne indentation et des commentaires éventuels seront pris en compte dans la notation.

Nous tiendrons compte également de la complexité de vos algorithmes, notamment lorsqu'une complexité attendue a été spécifiée dans la question.

À la différence de INF311, il n'y a pas de correction automatique à la volée. Comme pour les autres TDs, des tests vous sont proposés à chaque question.

Les documents autorisés sont : le polycopié de cours, les reproductions des planches des amphis, vos notes de cours.

Que la force soit avec vous.

Partie 1 - Sous-tableau de somme minimale

On se propose de résoudre le problème suivant : étant donné un tableau d'entiers t (positifs ou négatifs), déterminer la plus petite valeur k telle que k est la somme des éléments d'un sous-tableau non vide s de t. Voici deux exemples :

Dans la suite de ce problème, nous noterons t le tableau sur lequel nous travaillons et n le nombre de ses éléments. Nous noterons sub[i,j] le sous-tableau de t compris entre les indices i et j inclus. Nous noterons s(i,j) la somme des éléments de sub[i,j]. Enfin, nous noterons s*(t) la solution de notre problème pour le tableau t.

Nous allons coder quatre algorithmes, de plus en plus efficaces, pour résoudre ce problème.

Nous supposerons que tous les tableaux passés en argument de nos méthodes contiennent au moins un élément.

Il faut tout d'abord télécharger les deux fichiers suivants :

Question 1.1 : Algorithme cubique

(Cette question peut être traitée de manière indépendante.)

Nous allons commencer par la méthode la plus naïve : pour chaque sous-tableau sub[i,j], calculer s(i,j), et retenir la plus petite des sommes rencontrées sur l'ensemble des sous-tableaux. Renvoyer cette valeur.

Complétez la méthode suivante en implantant cet algorithme :

      static int minSubSum1(int[] t){
          return 0; // À modifier
      }
    

Afin de tester votre méthode, exécuter la classe TestsMinSubSum, en appelant la méthode testQuestion1 dans le main. L'affichage vous indiquera si les tests ont été concluants ou non.

Déposez le fichier MinSubSumProblem.java :

Question 1.2 : Algorithme quadratique

(Cette question peut être traitée de manière indépendante.)

Afin d'être à peine moins naïf que dans la question précédente, on peut faire la remarque suivante : Si je connais s(i,j), je peux calculer s(i,j+1) en temps constant. Implanter cette amélioration afin de rendre votre algorithme quadratique.

Complétez la méthode suivante :

      static int minSubSum2(int[] t){
          return 0; // À modifier
      }
    

Afin de tester votre méthode, exécuter la classe TestsMinSubSum, en appelant la méthode testQuestion2 dans le main. L'affichage vous indiquera si les tests ont été concluants ou non.

Déposez le fichier MinSubSumProblem.java :

Question 1.3 : Algorithme en O(nlog(n))

(Cette question peut être traitée de manière indépendante.)

Nous allons maintenant changer d'approche en utilisant le paradigme diviser pour régner. L'idée est la suivante : soit m l'indice de l'élément central de notre tableau t. Le sous-tableau de somme minimale doit respecter l'une des trois conditions suivantes :

  1. contenir l'élément d'indice m ;
  2. être le sous-tableau de somme minimale du tableau sub[0,m-1] ;
  3. être le sous-tableau de somme minimale du tableau sub[m+1,n-1].

Dans le cas a., il faut procéder de la manière suivante : chercher l'indice i compris entre 0 et m qui minimise s(i,m) ; chercher l'indice j compris entre m et n-1 qui minimise s(m,j) ; la valeur optimale vaut alors s(i,j). Attention, les recherches de i et j doivent être indépendantes, autrement dit le cas a. doit être traité de manière linéaire, et non pas quadratique.

Cette remarque nous conduit naturellement à écrire une méthode récursive int minSubSum3Rec(int[] t, int left, int right) qui doit renvoyer la valeur s*(sub[left,right]). Écrire ensuite une méthode int minSubSum3(int[] t) qui appelle correctement minSubSum3Rec afin de renvoyer la valeur s*(t).

Complétez les deux méthodes suivantes :

      static int minSubSum3Rec(int[] t, int left, int right){
          return 0; // À modifier
      }

      static int minSubSum3(int [] t){
          return 0; // À modifier
      }
    

Afin de tester votre méthode, exécuter la classe TestsMinSubSum, en appelant la méthode testQuestion3 dans le main. L'affichage vous indiquera si les tests ont été concluants ou non.

Déposez le fichier MinSubSumProblem.java :

Question 1.4 : Algorithme linéaire

(Cette question peut être traitée de manière indépendante.)

Enfin, nous allons coder l'algorithme suivant qui est linéaire :

      int minSubSum4(un tableau t de n éléments)
      ---------------------------------------------------------------------------
        sum : un entier qui vaut t[0]
        s : un entier qui vaut sum
        Pour chaque valeur r comprise entre 1 et (n-1)
           Si s est positif ou nul
              s prend la valeur t[r]
           Sinon
              s prend la valeur (s+t[r])
           Si s est plus petit que sum
              sum prend la valeur s
        Renvoyer la valeur sum
    

Complétez la méthode suivante :

      static int minSubSum4(int[] t){
          return 0; // À modifier
      }
    

Afin de tester votre méthode, exécuter la classe TestsMinSubSum, en appelant la méthode testQuestion4 dans le main. L'affichage vous indiquera si les tests ont été concluants ou non.

Déposez le fichier MinSubSumProblem.java :

Partie 2 - Quelques calculs sur les arbres

Dans cet exercice, nous allons travailler sur des arbres dont le nombre de fils n'est pas borné. En voici un exemple :

Nous utiliserons la classe Tree suivante :

      public class Tree {
         int value;
         int height;
         LinkedList<Tree> children;
      }
    

Le champ value contient la valeur stockée en un sommet donné (par exemple 7 pour la racine de l'arbre représenté ci-dessus). Les fils d'un sommet sont stockés dans un champ children de type LinkedList<Tree>. Nous utilisons également un champ height de type int qui mémorise la hauteur de l'arbre, c'est-à-dire la distance maximale entre la racine de l'arbre et l'une de ses feuilles. Voici (en rouge) les hauteurs de chacun des sommets de l'arbre présenté ci-dessus :

Il faut télécharger les deux fichiers suivants :

Question 2.1 : Construire des arbres

(Cette question peut être traitée de manière indépendante.)

Complétez les deux constructeurs suivants :

      Tree(int v, LinkedList<Tree> s){
	    //À compléter
      }

      Tree(int v){
	    //À compléter
      }
    

Le premier constructeur doit construire un arbre dont la valeur de la racine vaut v, et dont les sous-arbres sont donnés par la liste chaînée s. Il ne sera pas nécessaire de dupliquer la liste reçue en argument du constructeur. Le second constructeur construit une feuille de valeur v. Dans les deux constructeurs, vous devrez veiller à bien initialiser le champ height ; dans le cas du premier constructeur, vous pourrez supposer que les champs height des sous-arbres sont corrects. Dans le cas du second constructeur, il faudra bien initialiser le champ children afin qu'il soit possible d'ajouter des fils à l'arbre par la suite.

Complétez désormais la méthode suivante :

      void addChild(Tree t){
           //À compléter
      }
    

Cette méthode ajoute l'arbre t à la fin de la liste des fils de l'arbre appelant this. Une fois encore, il faudra veiller à ce que la valeur du champ height de l'arbre appelant soit toujours correcte à la sortie de cette méthode.

Afin de tester votre méthode, exécuter la classe TestsTree, en appelant la méthode testQuestion1 dans le main. L'affichage vous indiquera si les tests ont été concluants ou non.

Déposez le fichier Tree.java :

Question 2.2 : Taille de l'arbre

(Cette question dépend de la question 2.1.)

On appelle taille d'un arbre le nombre de sommets qu'il contient. L'arbre qui nous sert d'exemple depuis le début a une taille égale à 10.

Complétez la méthode suivante :

	int size(){
	    return 0; // À modifier
	}
      
qui calcule la taille de l'arbre appelant this.

Afin de tester votre méthode, exécuter la classe TestsTree, en appelant la méthode testQuestion2 dans le main. L'affichage vous indiquera si les tests ont été concluants ou non.

Déposez le fichier Tree.java :

Question 2.3 : Largeur de l'arbre

(Cette question dépend de la question 2.1.)

On appelle largeur de l'arbre le plus grand nombre de sommets à même distance de la racine. Voici une illustration sur deux arbres :

Afin de calculer la largeur de l'arbre, on vous propose d'utiliser l'algorithme suivant :

      int Largeur(Arbre a)
      ---------------------------------------------------------------------------
        max : un entier qui vaut 0
        S1 et S2 : deux ensembles initialement vides
        Ajouter l'arbre a à l'ensemble S1
        Pour chaque valeur d comprise entre 0 et la hauteur de l'arbre a
           nb : un entier qui vaut 0
           Tant que S1 est non vide
                Enlever un élément t de S1
                Incrémenter nb
                Ajouter tous les fils de t à l'ensemble S2
           Si nb>max
                max prend la valeur de nb
           Échanger les contenus des ensembles S1 et S2
       Renvoyer la valeur max
    

Complétez la méthode suivante :

	int width(){
	    return 0; // À modifier
	}
      
qui calcule la largeur de l'arbre appelant this. On pourra représenter les deux ensembles S1 et S2 avec des LinkedList<Tree>.

Afin de tester votre méthode, exécuter la classe TestsTree, en appelant la méthode testQuestion3 dans le main. L'affichage vous indiquera si les tests ont été concluants ou non.

Déposez le fichier Tree.java :

Question 2.4 : Produire un tableau à partir d'un arbre

(Cette question dépend des questions 2.1 et 2.2.)

On souhaite désormais pouvoir produire un tableau qui contient tous les éléments de l'arbre. Pour cette question, on suppose que les fils d'un sommet sont ordonnés selon l'ordre dans lequel ils apparaissent dans la liste chaînée children du sommet en question. On veut que l'ordre des éléments dans le tableau corresponde à un parcours préfixe de l'arbre. Voici une illustration :

Complétez la méthode suivante :

	int[] toArray(){
	    return null; // À modifier
	}
      
qui renvoie un tableau contenant les éléments de l'arbre appelant dans l'ordre préfixe. Cette méthode utilisera une autre méthode récursive :
	int toArrayRec(int[] tab, int deb){
	    return 0; // À modifier
	}
      
La méthode toArrayRec écrit dans le tableau tab, en commençant à la case d'indice deb, les éléments de l'arbre this dans l'ordre préfixe. Elle renvoie l'indice de la case située immédiatement à droite de la dernière case dans laquelle elle a écrit un élément.

Afin de tester votre méthode, exécuter la classe TestsTree, en appelant la méthode testQuestion4 dans le main. L'affichage vous indiquera si les tests ont été concluants ou non.

Déposez le fichier Tree.java :

Question 2.5 : Diamètre de l'arbre

(Cette question dépend de la question 2.1.)

On appelle diamètre de l'arbre un plus long chemin sans cycle entre deux sommets de l'arbre. Par abus de langage, on appelera aussi diamètre la longueur d'un tel chemin. Il est facile de constater que tout diamètre vérifie l'une des trois propriétés suivantes : (a) relier deux feuilles en passant par la racine ; (b) relier deux feuilles sans passer par la racine ; (c) relier la racine et une feuille. La figure suivante illustre ces trois cas :

Complétez la méthode suivante :

	int diameter(){
	    return 0; // À modifier
	}
      
qui calcule le diamètre de l'arbre appelant this. On pourra procéder de la manière suivante : évaluer la longueur d'un plus long chemin dans chacun des trois cas (a), (b) et (c), renvoyer la plus grande de ces trois valeurs. Pour les cas (a) et (c), les champs height devraient vous être utiles ! Dans le cas où le diamètre d'un arbre correspond au cas (b), on peut remarquer que le diamètre de l'arbre est aussi le diamètre de l'un de ses fils.

Afin de tester votre méthode, exécuter la classe TestsTree, en appelant la méthode testQuestion5 dans le main. L'affichage vous indiquera si les tests ont été concluants ou non.

Déposez le fichier Tree.java :


Voici des solutions possibles : MinSubSumProblem.java et Tree.java.