Licence Informatique
Algorithmique Avancée

Lundi, 24 mai 2004

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₁ < x₂ < ¼ < x_i £ n-1 avec T[x₁] £ T[x₂] £ ¼ £ 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 comment 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 P1 et P2 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.