Exercices: Diviser pour régner et programmation dynamique

On considère la liste [6, 2, 9, 1].

1. a) Appliquer l'étape de division du tri fusion jusqu'à obtenir des listes à un élément.

1. b) Fusionner deux listes triées [2, 6] et [1, 9] en détaillant les comparaisons.

1. c) Donner la liste triée finale.

On définit en Python :

def f(n):

    if n == 0:

        return 1

    return n * f(n - 1)

1. a) Identifier le cas de base et l'appel récursif.

1. b) Détailler le calcul de f(4).

1. c) Dire ce qui se passe si l'on appelle f(-1) et pourquoi.

On étudie la recherche dichotomique dans la liste triée [2, 5, 8, 12, 16, 23, 38] de la valeur 23.

1. a) Donner les indices et valeurs examinés à chaque étape.

1. b) Donner le nombre maximal de comparaisons pour une liste de 1 000 éléments.

1. c) Comparer avec une recherche séquentielle.

Le tri fusion est appliqué à la liste [7, 3, 5, 1, 8, 2, 6, 4].

1. a) Représenter l'arbre des divisions successives et donner sa hauteur.

1. b) Donner le résultat des fusions à chaque niveau.

1. c) Justifier que le coût total est proportionnel à $n \log_2 n$ pour $n = 2^k$ éléments.

La suite de Fibonacci est définie par $F_0 = 0$, $F_1 = 1$ et $F_n = F_{n-1} + F_{n-2}$.

1. a) Écrire une fonction récursive naïve fib(n) et dessiner l'arbre des appels pour fib(5).

1. b) Compter le nombre d'appels à fib(2) dans cet arbre.

1. c) Écrire une version avec mémoïsation (dictionnaire) et indiquer son coût.

Un boulanger de Toulouse dispose de pièces de 1 €, 3 € et 4 €. Il veut rendre 6 € avec un minimum de pièces.

1. a) Appliquer l'algorithme glouton et donner le résultat.

1. b) Déterminer la solution optimale.

1. c) Remplir le tableau $T[s]$ du nombre minimal de pièces pour $s = 0, \dots, 6$ par programmation dynamique.

Soit $T(n)$ le nombre de comparaisons du tri fusion dans le pire des cas pour $n = 2^k$ éléments, avec $T(1) = 0$ et $T(n) \le 2T(n/2) + n$.

1. a) Montrer par récurrence sur $k$ que $T(2^k) \le k \cdot 2^k$.

1. b) En déduire que $T(n) = O(n \log_2 n)$.

1. c) Pour $n = 1\,024$, comparer cette borne avec $n^2$ et calculer le rapport.

1. d) Expliquer pourquoi le tri par insertion peut être plus rapide sur une liste déjà triée.

On cherche la plus longue sous-séquence commune (PLSC) des chaînes X = "ABCB" et Y = "BDCAB".

1. a) Établir la relation de récurrence sur $L(i, j)$, longueur de la PLSC des $i$ premiers caractères de X et des $j$ premiers de Y.

1. b) Remplir le tableau complet de $L(i, j)$.

1. c) Donner une PLSC et sa longueur.

1. d) Donner le coût en fonction de $|X| = p$ et $|Y| = q$ et le comparer avec une approche récursive sans mémoïsation.

On considère la recherche d'un motif dans un texte par l'algorithme de Boyer-Moore-Horspool, avec le texte T = "LES ARBRES DE LA RUE" et le motif M = "ARBRE".

1. a) Construire la table de décalage des caractères du motif (distance de la dernière occurrence à la fin, hors dernier caractère).

1. b) Dérouler l'algorithme en donnant les positions testées et les décalages.

1. c) Donner le nombre de comparaisons de caractères effectuées et le comparer avec une recherche naïve.

1. d) Expliquer dans quel cas l'algorithme est le plus efficace et dans quel cas il se comporte comme la recherche naïve.