Université Bordeaux 1 Département d’Informatique

Licence Informatique Algorithmique Avancée Lundi, 24 mai 2004 Durée 3 heures

Tous documents autorisés

1. Ecrire une fonction récursive qui peut être utilisée pour afficher toutes les suites d’entiers positifs avec avec n comme dernier élément et telles que chaque élément est un multiple de l’élément précédent.

(Par exemple pour n = 10 les suites sont

10
1 10
2 10
5 10
1 2 10
1 5 10

)

(Votre fonction pourrait très bien avoir d’autres paramètres; par exemple elle pourrait avoir deux paramètres auxiliaires T, i et afficher les i premiers éléments du tableau T après chaque suite; il suffirait ensuite de l’appeler avec i = 0 pour obtenir l’affichage souhaité.)

2. Etant donné un tableau T de n éléments T [0],... T [n − 1], on souhaite calculer l’ordre du plus grand sous-ensemble des éléments qui est déjà trié, c’est-à-dire le plus grand i tel qu’il existe une suite 0 ≤ x_{1} < x_{2} < ⋯ < x_{i} ≤ n − 1 avec T [x_{1}] ≤ T [x_{2}] ≤ ⋯ ≤ T [x_{i}]. Afin de faire ceci, on calcule pour chaque j l’ordre du plus grand sous-ensemble qui vérifie la propriété énoncée et aussi x_{i} = j.

Décrire comment la programmation dynamique peut aider à faire ce calcul de façon efficace.

3. On sait que n est un entier positif et que f et g sont deux fonctions vérifiant f(i) = O(p(i)) et g(i) = O(q(i)). En utilisant la notation O(), mais sans mention de f ou de g, exprimer les meilleurs majorants possibles sur le nombre d’exécutions de w + +, x + +, y + + et z + + par le code suivant:

for (i=0;i<f(n);i++)
   for (j=0;j<i;j++) w++;
for (i=0;i<f(n);i++) x++;
for (i=0;i<g(n);i++) x++;
for (i=0;i<f(n);i++)
   for (j=0;j<g(n);j++) y++;
j=1;
for (i=0;i<f(n);i++) j*=2;
for (i=0;i<j;i++) z++;

4. D’écrire l’algorithme Knuth-Morris-Pratt de recherche des occurrences d’une chaîne de caractères dans une autre en précisant en détail com-

ment il trouve les occurrences de abcabcdab en abracadabrabcabcdabcabcdab

5. Ecrire une fonction qui libère l’espace utilisé par une structure composée de noeuds, reliés par deux pointeurs P 1 et P 2 dans chaque noeud. Un noeud contient aussi deux champs i et j qui contiennent 0 à l’appel de la fonction. Le paramètre de la fonction est un pointeur vers un noeud et la fonction doit appliquer free() une fois à chaque noeud accessible à partir de ce pointeur.

La fonction peut parcourir la structure deux fois; le premier parcours peut calculer dans le champ i de chaque noeud le nombre de pointeurs au noeud et le deuxième parcours peut décrémenter i à chaque visite à un noeud et libérer le noeud quand i atteint 0.