INF4110-10 Examen Intra (Automne 1998)

Examen intra -- INF4110-10

Automne 1998

Examen intra -- INF4110-10

Automne 1998

1. Induction (10 pts)

Définissons un type arbre binaire comme suit:

  type arbre ::= Feuille nat | Noeud nat arbre arbre

Dans de tels arbres, tant les feuilles que les noeuds internes conservent de l'information (nombre naturel).

Définissons aussi quelques opérations sur ds tels arbres:

  infos :: arbre -> sequence{nat}
  infos(Feuille n) = [n]
  infos(Noeud n a1 a2) = infos(a1) || [n] || infos(a2)

  nbNoeuds :: arbre -> nat
  nbNoeuds(Feuille n) = 1
  nbNoeuds(Noeud n a1 a2) = nbNoeuds(a1) + nbNoeuds(a2) + 1

Montrez (par induction) que pour tout arbre a, la propriété suivante est satisfaite:

  nbNoeuds(a) = length( infos(a) )

Note: Vous pouvez utiliser la propriété suivante (sans la démontrer):

• length(s1 || ... || sk) = length(s1) + ... + length(sk)

2. Notation ${\cal O}$ (18 pts)

[10] a) En utilisant uniquement la définition de ${\cal O}$, prouvez les affirmations présentées plus bas. Pour simplifier, vous pouvez supposer qu'il s'agit de fonctions définies sur les nombres non-négatifs (n >= 0) et que les fonctions génériques (f, g, ...) ne sont jamais négatives.

1.

n² + (n + 1)³ est $\Theta(n^3)$.

2.

Si f(n) est ${\cal O}(g(n))$ et g est ${\cal O}(h(n))$, alors f est ${\cal O}(h(n))$.

[8] b) Donnez un estimé ${\cal O}$ aussi précis que possible pour les fonctions suivantes (en utilisant, entre autres, la proposition 2.16, p. 49):

1.

$(n^4+n^2\;log\;n)(log\;n+1)+(12log\;n+2389)(n^2+435^{43})$

2.

log(n⁴ * 3ⁿ⁺⁴)

3. Analyse d'algorithmes (15 pts)

[6] a) L'algorithme suivant permet de multiplier deux nombres entiers naturels a et b:

  Algorithme produit( a, b: nat ) prod: nat
    prod <-- 0
    TANTQUE b > 0 FAIRE
      SI b MOD 2 = 1 ALORS
        prod <- prod + a
      FIN
      b <- b / 2
      a <- 2 * a
    FIN
    RETOURNER prod
  FIN

Quelle est la complexité asymptotique de cet algorithme? Justifiez.

[9] b) L'algorithme suivant permet de trouver le minimum et le maximum d'une séquence s de nombres naturels (le résultat est une paire de nombres, paire indiquée par ``(min, max)''):

  Algorithme min_max( s: sequence{nat} ) (min, max): (nat, nat)
    SI length(s) = 1 ALORS
      min <- s[0]
      max <- s[0]
    SINON
      (min1, max1) <- min_max( s[0..length(s)/2-1] )
      (min2, max2) <- min_max( s[length(s)/2..length(s)-1] )
      min <- min1 < min2 ? min1 : min2
      max <- max1 > max2 ? max1 : max2
    FIN
    RETOURNER (min, max)
  FIN

1.

Quelle précondition doit être satisfaite pour que l'algorithme fonctionne correctement?

2.

Quelle est la complexité asymptotique de cet algorithme? Justifiez.

4. Files de priorité (11 pts)

La classe concrète présentée plus bas, dont les noms de méthode ont été changés, met en oeuvre un des types abstraits vus en classe.

Quelques éléments à souligner:

• La classe concrète IntegerComparator met en oeuvre, pour le cas particulier des Integer, l'interface Comparator, donc permet de comparer des objets Integer.
• La valeur Integer.MAX_VALUE dénote le plus grand entier pouvant être représenté par un Integer.
• L'opérateur ``%'' est la version Java de l'opérateur MOD (reste de la division entière).

[6] a) De quel type s'agit-il? Y-a-t-il des restrictions non présentes dans le type original? Expliquez brièvement.

[5] b) Quelle est la complexité asymptotique de chacune des opérations (m1, ..., m5), en supposant que la file de priorité est mise en oeuvre à l'aide d'un tas.

public class C implements T {
  private PriorityQueue pq;
  private int suivant;

  public C() {
    pq = new PriorityQueue( new IntegerComparator() );
    suivant = 1;
  }

  public int m1() { return pq.size(); }

  public boolean m2() { return pq.isEmpty(); }

  public Object m3() throws TException {
    try {
      return pq.minElement();
    }
    catch( RuntimeException ce ) {
      throw new TException( "??" );
    }
  }
  
  public void m4( Object element ) {
    pq.insertItem( new Integer(suivant), element );
    suivant = (suivant % Integer.MAX_VALUE) + 1;
  }

  public Object m5() throws TException {
    if ( ! pq.isEmpty() ) {
      return pq.removeMinElement();
    } else {
      throw new TException( "??" );
    }
  }
}

5. Séquences et fouilles (10 pts)

Soit la méthode Java suivante qui effectue une fouille dans une séquence ordonnée d'items, séquence utilisée pour représenter un dictionnaire:

  private Object trouver( Sequence s, Object k, int low, int high ) {
    // On suppose qu'un Comparator c est accessible pour comparer les cles.
    if ( low > high )
     return NO_SUCH_KEY;
    else if ( low == high ) {
      Item item = ((Item) s.elemAtRank(low));
      return item.key() == k ? item.element() : NO_SUCH_KEY;
    } else {
      Item iteml = ((Item) s.elemAtRank(low));
      Item itemh = ((Item) s.elementAtRank(high));
      if ( c.isEqualTo(k, iteml.key()) )
        return iteml.element();
      if ( c.isEqualTo(k, itemh.key()) )
        return itemh.element();
      if ( c.isGreaterThan(k, iteml.key()) && c.isLessThan(l, itemh.key()) )
        return trouver( s, k, low+1, high-1 );
      return NO_SUCH_KEY;
    }
  }

L'appel initial à cette procédure pour fouiller une séquence s se fait alors comme suit:

  return trouver( s, k, 0, s.size()-1 );

Quelle sera la complexité asymptotique de cette méthode (en fonction de la taille de s, qu'on suppose égale à n) si la séquence s est mise en oeuvre avec une liste doublement chaînée plutôt qu'avec un tableau d'items? Justifiez votre réponse.

6. Tas (16 pts)

Note: Dans les questions qui suivent, la structure de tas est toujours telle que la clé minimum est conservée à la racine de l'arbre (conceptuellement) associé au tas.

[4] a) Dans une structure de tas vue comme un arbre binaire complet partiellement ordonné, que peut-on dire concernant la position dans le tas de la clé la plus grande, en supposant que chaque clé est unique? Expliquez birèvement.

[4] b) Dans une structure de tas représentée par un tableau d'items, est-ce qu'un tableau trié en ordre croissant forme effectivement un tas? Expliquez!

[8] c) Soit l'algorithme suivant qui calcule la somme des k plus petits éléments de A, un tableau d'entiers naturels:

  Algorithme sommePartielle( A: array[1..n] OF nat, k: nat ) somme: nat
  DEBUT
    construireTas( A )      // Definition omise: cf. plus bas.
    somme <- 0
    POUR j <- 1 A k FAIRE
      somme <- somme + A[1]
      echanger A[1] <-> A[n-j+1]
      entasser( A, 1, n-j )
    FIN
    RETOURNER somme
  FIN

  Algorithme entasser( A: array[1..n] OF nat, i: nat, k: nat )
  DEBUT
    SI 2*i <= k & A[2*i] < A[i] 
      ALORS min <- 2*i
      SINON min <- i
    SI 2*i+1 <= k & A[2*i+1] < A[min]
      ALORS min <- 2*i+1
    SI min != i 
      ALORS echanger A[i] <-> A[min]
            entasser( A, min, k )
  FIN

1.

Que contiendront les k dernières positions de A après l'exécution de l'algorithme?

2.

Supposons que l'algorithme utilisé pour construire le tas soit semblable à celui vu en classe (construireTas3), donc soit de complexité ${\cal O}({\tt n})$. Quelle sera alors la complexité asymptotique de l'algorithme sommePartielle, en fonction de n et k?

7. Arbres (10 pts)

Une représentation souvent utilisée pour les arbres avec un nombre variable d'enfants est la représentation ``premier enfant/frère'': chaque noeud possède, en plus d'un pointeur vers son parent, un pointeur vers son premier enfant ainsi qu'un pointeur vers son frère. La figure 1 présente la classe Java pour de tels noeuds.

  

Figure 1: Noeud d'un arbre représenté avec la technique premier enfant/frère

Supposons alors une classe Arbre définie (partiellement) comme suit:

  public class Arbre implements SimpleTree {
    private NoeudEF racine;
    private int taille;

    ...
  }

Écrivez (en Java) la classe locale permettant, pour un noeud donné, d'énumerer ses enfants. Plus précisément, définissez la classe locale EnumerationChildren dont une instance est créée lors d'un appel à children.

  public Enumeration children( Position p ) {
    return new EnumerationChildren(p);
  }