INF4110-10 Revision pour l'intra (Automne 1998)

Revision pour l'intra -- INF4110-10

Automne 1998

Revision pour l'intra -- INF4110-10

Automne 1998

1. Induction ( pts)

Soit le type liste défini comme suit (liste à la Lisp):

  liste ::= Nil | Cons nat liste

Définissons les fonctions suivantes:

  inc :: liste -> liste
  inc(Nil) = Nil
  inc(Cons x l) = Cons (x+1) inc(l)

  somme :: liste -> nat
  somme(Nil) = 0
  somme(Cons x l) = x + somme(l)

  long :: liste -> nat
  long(Nil) = 0
  long(Cons x l) = 1 + long(l)

  dupl :: liste -> liste 
  dupl(Nil) = Nil
  dupl(Cons x l) = Cons x (Cons x dupl(l))

Prouvez les propriétés suivantes, pour n'importe quelle l de type liste:

1.

somme(l) <= somme(inc(l))

2.

somme(dupl(l)) = 2 * somme(l)

3.

somme(inc(l)) = somme(l) + long(l)

2. Induction mathématique ( pts)

Les entiers naturels nat peuvent être définis comme suit:

• 0 est un nat
• Si k est un nat, alors k+1 est un nat

Prouvez (par induction) les propriétés suivantes, pour tout entier n de type nat:

1.

$1+ 2 + \ldots + (n-2) + (n-1) + n = n (n+1) / 2$

2.

$1 + 2 + 2^2 + \ldots + 2^{n-1} + 2^n = 2^{n+1} - 1$

3. Notation ${\cal O}$ ( pts)

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, lorsque des fonctions non-définies sont utilisées (g_i, f_i), alors ces fonctions ne sont jamais négatives.

1.

3n² est ${\cal O}(n^2 + 2n)$.

2.

2ⁿ⁺¹ est ${\cal O}(3^{n-1})$.

3.

Si f₁(n) est ${\cal O}(g_1(n))$ et f₂(n) est ${\cal O}(g_2(n))$, alors $f_1(n) \times f_2(n)$ est ${\cal O}(g_1(n) \times g_2(n))$.

4. Analyse d'algorithmes ( pts)

Donnez, en utilisant la notation ${\cal O}$, une fonction donnant le temps d'exécution des algorithmes suivants (analyse du pire cas).

1.

  PROCEDURE sc( n: nat ) somme: nat
  DEBUT
    somme <- 0
    TANTQUE n > 0 FAIRE
      somme <- somme + (n MOD 10)
      n <- n / 10                // Division entiere
    FIN
    RETOURNER somme
  FIN

2.

  PROCEDURE sc_r( n: nat ): nat
  DEBUT
    SI n = 0 ALORS
      RETOURNER 0
    SINON
      RETOURNER (n MOD 10) + sc_r(n / 10)
  FIN

5. File de priorité ( pts)

Soit l'algorithme suivant:

  Algorithme fs( s: sequence{sequence{nat}} )
  // PRE
  //  s != [],
  //  ALL( i: nat SUCH THAT i IN domain(s) :: en_ordre(s) )
    r <- []
    pq <- filePrioriteVide()
    k <- length(s)
    n <- SUM( i: nat SUCH THAT i IN domain(s) :: length(s[i]) )
    POUR i <- 0 A k-1 FAIRE
      pq.insertItem( s[i][0], i )
    POUR i <- 1 A n FAIRE
      j <- pq.removeMinElement()
      r <- r || [ s[j][0] ]
      s[j] <- s[j][1..length(s[j])-1]
      SI s[j] != [] ALORS
        pq.insertItem( s[j][0], j )
    FIN
    RETOURNER r
  FIN  
  
  CONCEPT en_ordre( s: sequence{nat} ) VALUE( b: boolean )
    WHERE b <=> ALL( i: nat SUCH THAT 0 <= i < lenght(s)-1 :: s[i] <= s[i+1] )

1.

Que fait cet algorithme?

2.

Quelle est sa complexité asymptotique si on suppose que la file de priorité est mise en oeuvre à l'aide d'un tas? Justifiez.

6. Arbre ( pts)

Une représentation parfois utilisée pour les arbres avec un nombre variable d'enfants consiste simplement à associer à un noeud une séquence composée de ses enfants: chaque noeud possède alors, en plus d'un pointeur vers son container et son parent, un pointeur vers la liste de ses enfants. La figure 1 présente une classe Java pour de tels noeuds.

  

Figure 1: Noeud d'un arbre avec un nombre variable d'enfants representé avec une séquence d'enfants

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

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

    ...
  }

[] a) Écrivez (en Java) la méthode replace(v, e) qui remplace l'élément associé à v par e et qui retourne comme résultat l'ancien élément.

[] b) Écrivez (en Java) la méthode isRoot permettant de déterminer, pour un noeud donné, s'il s'agit de la racine ou non.

[] c) Écrivez (en Java) la méthode positions permettant, pour l'arbre dans son ensemble, de produire une Enumeration préfixe de toutes les positions (noeuds) de l'arbre, y compris les noeuds externes. Vous devez évidemment aussi définir la classe locale appropriée.