Algorithmique : TD 4
Date: 17 octobre 2005
Le texte est dénoté par t, de longueur n, le motif est w, de longueur m; les lettres des mots sont indicées à partir de 0. Pour toute paire (p,q) d'entiers, pour tout mot u, u[p..q] est le facteur de u situé entre (au sens large) les indices p et q; si p>q, il s'agit du mot vide. i désigne généralement une position dans w et j la position de w par rapport à t. Dans l'agorithme de Boyer-Moore, on vérifie que le motif correspond au texte en examinant les lettres de droite à gauche. Globalement, on déplace toujours le motif du début du texte vers la fin.
Pour améliorer l'algorithme naïf, on effectue des décalages sur les principes du ``bon suffixe'' et du ``mauvais caractère''.
Un parking a la configuration ci-dessous:
La méthode (I) pour garer une voiture est la suivante:
Chaque voiture arrive avec une place p qu'elle désire occuper.
Si celle-ci n'est pas libre, elle se place dans la première place libre supérieure à p.
Si elle ne trouve pas une telle place, elle sort; elle a échoué à se garer.
On considère n voitures (1,2,...,n) qui désirent se garer dans cet ordre, la voiture i visant la place p[i]. Si les n voitures parviennent à se garer, la suite (p[i]) est appelée suite de parking.
Exercice 1: La suite (2,3,1,3,2) est-elle une suite de parking? Quel est le résultat?
Exercice 2: Donner une autre suite de parking aboutissant au même résultat.
Exercice 3: Montrer que (p[i]) est une suite de parking si et seulement si
Exercice 4: La méthode (II) pour garer une voiture est la suivante:
Lorsqu'une voiture décide de se garer en p, si la place est occupée, la voiture
qui se trouve dessus est poussée sur la place p+1. Si celle-ci n'était pas libre,
son occupante est poussée sur la place p+2 et ainsi de suite. S'il faut pousser la voiture qui se trouve en n, il y a échec.
Dessiner la configuration obtenue avec la suite (2,3,1,3,2)
-->
, puis avec la suite donnée en 2.
Exercice 5: Montrer que la méthode (II) permet de garer n voitures (1,2,...,n)
si et seulement si la suite (p[i]) correspondante est une suite de parking.
Exercice 6: Pour une suite de parking (p[i]) donnée, on note (u[i]) et (v[i])
les suites (qui sont des permutations) obtenues respectivement avec les méthodes (I) et (II).
Montrer qu'à un couple de permutations (u[i]) et (v[i]) ne correspond (au plus)
qu'une suite de parking qu'on peut, le cas échéant, effectivement construire.
Exercice 7: On considère maintenant un parking un peu différent. A la sortie du parking, il y a une place supplémentaire (soit,
en tout, n+1 places). De plus,
la méthode (I) est modifiée de la façon suivante:
si une voiture n'a pas réussi à se garer (y compris dans cette dernière place),
la voiture rentre à nouveau dans le parking et prend la première place disponible. La place visée par une voiture
peut à présent être un nombre entre 1 et n+1.
Evidemment, avec cette méthode, les voitures arrivent toujours à se garer (il y a même une place vide à la fin). Comment voit-on, à la fin de l'opération, si la suite (p[i]) était une suite de parking?
Exercice 8: Montrer que si la suite (p[i]) laisse la place j libre, la suite (p'[i])
définie par
Exercice 9: En déduire le nombre de suites de parking.