TD d’algorithmique avancée

Ce document présente des exercices corrigés d’algorithmique avancée, destinés aux étudiants en informatique. Il couvre principalement la récursivité à travers l’étude de la suite de Fibonacci, puis aborde les opérations sur des ensembles représentés par des tableaux, en distinguant les cas d’ensembles triés et non triés. Chaque algorithme est présenté avec sa complexité et des variantes récursives.

Suite de Fibonacci

La suite de Fibonacci est définie par :

Fib(n) = {
  1           si n = 0
  1           si n = 1
  Fib(n - 1) + Fib(n - 2) sinon
}

Algorithme récursif simple

Fibonacci(n)
  si n = 0 ou n = 1 alors
    renvoyer 1
  sinon
    renvoyer Fibonacci(n - 1) + Fibonacci(n - 2)

La complexité en nombre d’additions de cet algorithme est en Ω(2^(n/2)). La démonstration se fait par récurrence en montrant qu’il existe une constante c > 0 telle que :

T(n) ≥ c × 2^(n/2)

avec T(n) le nombre d’additions pour calculer Fibonacci(n). La preuve utilise la relation :

T(n) = T(n - 1) + T(n - 2) + 1

et la vérification des cas de base pour n = 2 et n = 3.

Calcul du couple (Fibonacci(n), Fibonacci(n - 1))

Fib-Paire(n)
  si n = 1 alors
    renvoyer (1, 1)
  sinon
    (x, y) = Fib-Paire(n - 1)
    renvoyer (x + y, x)

On peut utiliser cet algorithme pour calculer Fibonacci(n) :

Fibonacci(n)
  si n = 0 alors
    renvoyer 1
  sinon
    (x, y) = Fib-Paire(n)
    renvoyer x

La complexité en nombre d’additions est alors linéaire : T(n) = n - 1.

Opérations ensemblistes

On considère des ensembles représentés par des tableaux. Certains sont triés dans l’ordre croissant, d’autres non. Toutes les solutions sont récursives.

Recherche d’appartenance

Cas des ensembles non triés

Recherche(A, rang, x)
  si rang > longueur(A) alors
    renvoyer Faux
  si A[rang] = x alors
    renvoyer Vrai
  sinon
    renvoyer Recherche(A, rang + 1, x)

L’appel initial est Recherche(A, 1, x).

Complexité : Θ(n) dans le pire cas, où n est la taille de A.

Cas des ensembles triés

Recherche(A, rang, x)
  si rang > longueur(A) ou A[rang] > x alors
    renvoyer Faux
  si A[rang] = x alors
    renvoyer Vrai
  sinon
    renvoyer Recherche(A, rang + 1, x)

L’appel initial est Recherche(A, 1, x).

Complexité : Θ(n) dans le pire cas.

Recherche dichotomique (amélioration)

Recherche(A, x, inf, sup)
  milieu ← (inf + sup) div 2
  si A[milieu] = x alors
    renvoyer Vrai
  sinon si A[milieu] > x alors
    renvoyer Recherche(A, x, inf, milieu - 1)
  sinon
    renvoyer Recherche(A, x, milieu + 1, sup)

Complexité : O(log n) où n = sup - inf + 1.

Union de deux ensembles

Cas des ensembles non triés

Union(A, B, rang, C)
  si rang > longueur(B) alors
    renvoyer C
  si Recherche(A, B[rang]) = Faux alors
    longueur(C) ← longueur(C) + 1
    C[longueur(C)] ← B[rang]
  Union(A, B, rang + 1, C)

L’appel initial est Union(A, B, 1, C), où C contient d’abord tous les éléments de A.

Complexité : Θ(n × m) où n = longueur(A), m = longueur(B).

Cas des ensembles triés

Union(A, a, B, b, C)
  si a > longueur(A) et b > longueur(B) alors
    renvoyer C
  si b > longueur(B) ou B[b] > A[a] alors
    longueur(C) ← longueur(C) + 1
    C[longueur(C)] ← A[a]
    Union(A, a + 1, B, b, C)
  sinon
    longueur(C) ← longueur(C) + 1
    C[longueur(C)] ← B[b]
    si a ≤ longueur(A) et A[a] = B[b] alors
      Union(A, a + 1, B, b + 1, C)
    sinon
      Union(A, a, B, b + 1, C)

L’appel initial est Union(A, 1, B, 1, C).

Complexité : Θ(n + m).

Intersection de deux ensembles

Cas des ensembles non triés

Intersection(A, B, rang, C)
  si rang > longueur(B) alors
    renvoyer C
  si Recherche(A, B[rang]) = Vrai alors
    longueur(C) ← longueur(C) + 1
    C[longueur(C)] ← B[rang]
  Intersection(A, B, rang + 1, C)

L’appel initial est Intersection(A, B, 1, C), où C est vide.

Complexité : Θ(n × m).

Cas des ensembles triés

Intersection(A, a, B, b, C)
  si a > longueur(A) ou b > longueur(B) alors
    renvoyer C
  si A[a] = B[b] alors
    longueur(C) ← longueur(C) + 1
    C[longueur(C)] ← A[a]
    renvoyer Intersection(A, a + 1, B, b + 1, C)
  sinon si B[b] > A[a] alors
    renvoyer Intersection(A, a + 1, B, b, C)
  sinon
    renvoyer Intersection(A, a, B, b + 1, C)

L’appel initial est Intersection(A, 1, B, 1, C).

Complexité : Θ(n + m).

Différence de deux ensembles

La différence A \ B est l’ensemble des éléments de A qui n’appartiennent pas à B.

Cas des ensembles non triés

Différence(A, rang, B, C)
  si rang > longueur(A) alors
    renvoyer C
  si Recherche(B, A[rang]) = Faux alors
    longueur(C) ← longueur(C) + 1
    C[longueur(C)] ← A[rang]
  Différence(A, rang + 1, B, C)

L’appel initial est Différence(A, 1, B, C), où C est vide.

Complexité : Θ(n × m).

Cas des ensembles triés

Différence(A, a, B, b, C)
  si a > longueur(A) alors
    renvoyer C
  si A[a] = B[b] alors
    renvoyer Différence(A, a + 1, B, b + 1, C)
  sinon si A[a] < B[b] alors
    longueur(C) ← longueur(C) + 1
    C[longueur(C)] ← A[a]
    renvoyer Différence(A, a + 1, B, b, C)
  sinon
    renvoyer Différence(A, a, B, b + 1, C)

L’appel initial est Différence(A, 1, B, 1, C).

Complexité : Θ(n + m).

Glossaire des termes clés

• Suite de Fibonacci : suite définie par Fib(0) = 1, Fib(1) = 1 et Fib(n) = Fib(n-1) + Fib(n-2) pour n ≥ 2.
• Récursivité : technique algorithmique où une fonction s’appelle elle-même.
• Complexité : mesure du nombre d’opérations effectuées par un algorithme en fonction de la taille de l’entrée.
• Recherche dichotomique : méthode de recherche dans un tableau trié en divisant l’espace de recherche par deux à chaque étape.
• Ensemble trié : ensemble dont les éléments sont ordonnés selon un critère (ici, ordre croissant).
• Ensemble non trié : ensemble dont les éléments ne sont pas ordonnés.
• Union : ensemble contenant tous les éléments de deux ensembles donnés.
• Intersection : ensemble contenant les éléments communs à deux ensembles donnés.
• Différence : ensemble des éléments présents dans un ensemble A mais pas dans un ensemble B.

Points clés à retenir

• L’algorithme récursif simple de Fibonacci a une complexité exponentielle en nombre d’additions.
• Le calcul du couple (Fib(n), Fib(n-1)) permet d’obtenir Fibonacci en temps linéaire.
• Les recherches dans des ensembles non triés sont linéaires, même avec récursivité.
• La recherche dichotomique améliore la recherche dans un ensemble trié à une complexité logarithmique.
• Les opérations ensemblistes (union, intersection, différence) sont plus efficaces sur des ensembles triés, avec une complexité linéaire.
• Les algorithmes récursifs présentés utilisent des appels avec indices pour parcourir les tableaux.