Td corrigé Algorithmes avancés - Free pdf

Algorithmes avancés - Free

Voir TD 1 pour n impair) et on recommence l'algorithme (récursif). ..... En fait, cette technique peut être utilisé partout où la complexité des interactions entre les ...




part of the document



pivot.
On recommence cette méthode, récursivement pour les premières (inférieur au pivot) et troisièmes (supérieur au pivot) parties.
Algorithme de Tri par fusion
Méthode récursive consistant à diviser les éléments en deux parties (équilibrées), trier chaque partie, puis fusionner les parties élémentaires.
Algorithme Min-Max
L’algorithme Min-Max consiste à trouver le minimum et le maximum d’un tableau.
S’il n’y a que deux éléments dans le tableau, il suffit de les comparer.
Sinon, on divise le tableau en deux parties (identiques et paires… ce qui implique que le tableau est de longueur n avec n pair. Voir TD 1 pour n impair) et on recommence l’algorithme (récursif). Lorsqu’on a le maximum et le minimum de deux parties, on les compare.
Cette méthode fait approximativement 3n/2 comparaisons.
Algorithmes gloutons
Principe
Les algorithmes gloutons sont ceux qui trouvent une solution parmi plusieurs possibles, comparables selon un critère global. A chaque fin d’étape de l’algorithme, on choisit l’étape suivante en fonction des informations locales. La méthode gloutonne ne trouve pas forcément la meilleure solution.
Exemples
Arbre recouvrant de poids minimum
Cet algorithme permet, dans un graphe ou les arêtes ont un poids, de trouver l’arbre qui relie tous les sommets avec une somme des poids minimale.
On peut considérer deux méthodes :
Algorithme très glouton non optimal : on commence avec un arbre d’un seul sommet et on choisit toujours l’arête de poids minimum pour rejoindre le sommet suivant.
Algorithme glouton et optimal : on commence avec n arbres (n correspondant au nombre de sommet du graphe) d’un seul sommet et on choisit toujours l’arête de poids minimum qui relie deux arbres.
Sac à dos continu
Le problème consiste à remplir un containeur avec une charge la plus grande possible étant donné plusieurs matériaux, chacun avec une valeur/kilo et une quantité disponible.
Il s’agit d’un algorithme glouton : il faut toujours chercher et choisir le matériau avec le meilleur rapport valeur/poids.
Cas où la méthode gloutonne n’est pas optimale
Exemples 
On peut retenir trois exemples :
Sac à dos discret : avec des objets que l’on ne peut découper.
Coloration de graphe : on veut colorier les sommets d’un graphe avec le plus petit nombre couleurs possible sachant que deux sommets voisins (reliés par une arrête) doivent avoir des couleurs différentes.
Commis voyageur : étant donnée une carte des distances entre des paires de villes, trouver le chemin le moins coûteux qui passe par chaque ville une seule fois (et retourne au point de départ).
Commentaires sur la non existence d’algorithmes efficaces (connus) pour ces trois exemples
Ces trois problèmes sont des variantes des problèmes NP-complets. Personne ne connaît des algorithmes garantis de trouver une solution optimale en temps raisonnable (borné par un polynôme), mais il n’est pas dit que ce soit impossible.
Donc, il est utile de considérer des algorithmes qui ont une garantie de trouver une solution proche de l’optimale. Un premier essai à un tel algorithme pourrait être un algorithme glouton simple. Un deuxième essai serait d’améliorer le résultat du premier par des modifications locales gloutonnes.
Arbres
Arbres binaires de recherche
Les arbres binaires sont des structures utiles. Exemples :
La structure représente la structure logique des données (arbre syntaxique, arbre généalogique)
La structure est utilisée pour permettre les opérations nécessaires sur une structure abstraite (arbre binaire de recherche, additions, suppressions d’éléments plus efficacement qu’avec un tableau ou liste avec pointeurs).
Insertion, recherche, annulation dans un arbre binaire de recherche
La recherche dans un arbre binaire
On commence la recherche à la racine, on parcours à gauche ou à droite selon la comparaison avec la valeur à chaque nœud (échec si sous arbre vide).
Insertion d’une valeur dans un arbre binaire
Idem que pour la recherche, en remplaçant le sous-arbre vide par un nouveau sous arbre contenant la valeur à insérer.
Suppression dans un arbre binaire
La suppression est facile au niveau d’une feuille ou si le nœud n’a qu’un seul fils. S’il y a deux fils, on remplace par exemple le nœud supprimé par le sous arbre.
Remarque
Les traitements dans la hauteur de l’arbre ont toujours un nombre d’opération linéaire. Il s’agit de quelques manipulations de pointeurs
Les ordres de parcours
Il existe trois ordres de parcours (souvent utiles) permettant de visiter tous les nœuds d’un arbre (binaire) :
Ordre infixe : (par exemple, afficher les éléments d’un arbre binaire de recherche en ordre). On parcourt tous le sous arbre gauche (en parcourant les sous arbre du sous arbre dans le même ordre… récursivement), ensuite la racine, puis tout le sous arbre droit.
Ordre préfixe : (utile pour calculer la profondeur de chaque nœud) on traite d’abord la racine, puis le sous arbre gauche et enfin le sous arbre droit.
Ordre post-fixe : (pour calculer par exemple la valeur d’une expression à partir de son arbre syntaxique, ou pour calculer une hauteur) d’abord les deux sous-arbre (gauche et droit), et la racine pour finir.
Arbres équilibrés
Un arbre binaire de recherche peut avoir une hauteur près de son nombre de nœud (n), en revanche, la moyenne est O(log n). C’est cette hauteur qui détermine le temps des opérations de base.
Il existe un grand nombre possible d’arbres avec n nœuds, on en obtient un selon l’ordre des insertions.
L’idée, pour obtenir un arbre équilibré, consiste à faire un peu plus de travail (à chaque insertion) afin de garder une hauteur plus raisonnable (de préférence O(log n)).
Arbre AVL
Un arbre AVL est un arbre dont la différence entre les hauteurs des deux sous arbres est au maximum 1. Ce type d’arbre nécessite le stockage d’une petite information cachée à chaque nœud : la différence entre les deux hauteurs des sous-arbres (-1, 0, 1).
Dans ce type d’arbre, la suppression d’un élément devient donc un peu plus compliquée.
Arbres 2-3
Un arbre 2-3 est un arbre pour lequel chaque nœud a soit une valeur et un fils, soit deux valeurs et trois fils. L’ordre est : sous-arbre, valeur, sous-arbre [, valeur, sous-arbre].
Dans un tel arbre, toutes les feuilles sont à la même profondeur.
Pour ajouter une valeur dans un nœud qui n’en contient qu’un : trivial.
S’il y en a déjà deux : insérer le deuxième dans le nœud père et diviser ce nœud en deux (avec peut-être une réaction en chaîne vers la racine).
Récursivité
Idée
une fonction peut s’appeler elle-même exactement comme un appel d'une autre fonction. Dès l'appel récursif achevé l'exécution du programme continue (et sans effet sur les variables et paramètres de l'appel initial).
Cette méthode est valable pour les fonctions et procédures (fonctions void).
On parle aussi de récursivité mutuelle lorsque deux ou plusieurs fonctions s'appellent entre elles (donc appel avant déclaration pour quelques unes).
Exemples favoris
Calcul de factorielle
Fonction fact(n) : entier
Début
Si (n=0) retourner (1)
Sinon retourner (n*fact(n-1))
Fin
Fibonacci
Fonction Fb(n) : entier
Début
Si (n(2) retourner 1
Sinon retourner (Fb(n-1)+Fb(n-2))
Fin
Remarques
La fonction récursive est une méthode bizarre de calculer une factorielle. Une boucle simple suffit. La fonction récursive est une très mauvaise méthode de calculer une suite de Fibonacci car le temps de calcul est exponentiel!
Donc, ne pas oublier qu’une méthode récursive est plus élégante et claire… mais il faut aussi considérer le temps de calcul, l’efficacité.
Meilleurs exemples
Calcul de xn
Fonction Puissance (x, n) : réel
Début
Selon que :
N=1 : retourner x
N%2=0 : retourner carrée(puissance(x,n/2))
Défaut : retourner x*carrée(puissance(x,n/2))
Fin

Remarque : on saute de xi à x2i dans une seule multiplication, ce qui est plus difficile à gérer avec une boucle. Il s’agit donc d’un bon exemple d’utilisation de fonction récursive.
Tour de Hanoi
Rappel du principe
Déplacer une tour de n disques de taille différente d'une colonne à une autre en utilisant une seule colonne auxiliaire, selon la règle qu'on ne peut déplacer qu'un disque à la fois et chaque colonne a toujours ses disques en ordre décroissante de taille.
Algorithme
Procédure Hanoi(n {nombre de disques}, a, b, c {tours})
Début
Si n=0 alors exit
Hanoi(n-1,a, c, b)
Afficher(a vers b)
Hanoi (n-1, c, b, a)
Fin
L’appel initial peut être : Hanoi(64, 1, 2, 3)
Autres exemples
Affichage en (disons) binaire : une boucle simple affiche les chiffres dans l'ordre inversé
Boucles imbriquées de profondeur inconnue
Algorithmes « diviser pour régner »
Paramètres et variables locales
Les paramètres et les variables déclarées localement dans une fonction (si elle est récursive ou non) sont créés au moment de l'appel/activation de la fonction et continuent à exister jusqu’à la sortie finale de l'appel.
Ils sont inaccessibles et immuables pendant d'autres appels imbriqués (sauf utilisation de pointeurs...)
Donc, quand une fonction s'appelle récursivement, à un moment de l'exécution du programme, il existe un nombre indéfini d'occurrences de ses paramètres et variables, mais, en général une seule occurrence accessible. Il y a possibilité d'échec parce que l'espace mémoire ne suffit pas pour toutes ces variables (segmentation fault en C).
Exemples utilisant des tableaux
Listes multiplicatives
Procédure Suites(n, m, T) :
Début
Afficher (n, T[n], T[n-1], …,T[1])
T[m+1]8 ou j>8 : exit
i=1 et j=1 et n=65 afficher FIN
cas T[i,j]>0 exit {Si =0 : alors la case n’a pas encore été parcourue}
Défaut : T[i, j]Nombre[i] ou u*Valeur[i]>Tot
finrepeter;
(sauf les cas i=0 (Nombre(Total,0)=1 ou 0 selon si Total=0)
Un exemple avec temps, probabilité et stratégie: lancer des dés pour finir avec 100 points.
On lance des dés 20 fois. A chaque coup, on gagne le nombre de points sur la face visible du dé. On veut finir avec exactement 100 points. Le calcul consiste à déterminer la probabilité de réussir.
Pour ne pas faciliter le problème, on peut, à chaque coup, choisir de lancer un ou deux dés (de façon à maximiser la probabilité de réussite).
On calcule pour chaque p (nombre de points entre 0 et 100) et chaque c (nombre de coups entre 0 et 20) la probabilité de gagner si on veut encore p points après le c-ème coup, disons P(p,c) (sauf si c=20) :
Si on lance un dé : probabilité =åði=16 P(p-ði,c+1)/6
Si on lance deux dés: probabilité =åði=212 P(p-ði,c+1)×Prob[i points des 2 dés]
Et on prend le maximum des deux comme valeur de P(p,c).
Avec correction pour les cas où on essaie de calculer une valeur avec p 1):
G(n) = G(n-1) +  EMBED Equation.3 + (si n impair)G((n-1)/2) + ( G((n-1)/2)/2) .
Remarques :
arrondir vers le bas dans la division n/2
les quatre parties sont: un seul sous-arbre (forcément de taille n-1, deux sous-arbres de taille différente, le plus petit de taille i, deux sous-arbres identiques, deux sous-arbres différents de la même taille).
Mêmes principes pour codage et décodage
Des Problèmes Difficiles
Les problèmes de codage et décodage sont parfois très compliqués. On peut citer comme exemple les graphes sur n sommets de degré maximum (par exemple) 3. On peut les générer en considérant chaque sommet à son tour et ajoutant un nombre d'arêtes jusqu'à 3 - degré actuel. Mais contraintes : pas d'arête à un sommet qui a déjà comme degré 3. Donc, on se retrouve avec une multitude de possibilités de compléter?
Graphes et isomorphisme!
Souvent, on considère deux structures comme identiques si on peut transformer l'une dans l'autre par une permutation des composants. On veut générer (ou compter) un représentant canonique de chaque classe d'équivalence. Mais les classes ne sont pas toutes de la même taille! Il est donc difficile de savoir si une structure est canonique ou de décider si deux structures sont isomorphes (Pb NP-complet).
Fonctions sur les nombres
Les nombres aléatoires
Il est souvent utile d'avoir une fonction qui produit des nombres apparemment aléatoires. La fonction rand() prédéfini peut faire se genre d’opération. A chaque fois qu’elle est appelée, elle donne un nombre différent (normalement en [0..N]). En réalité, elle n’est pas vraiment aléatoire mais on considère statistiquement que le résultat est convenable.
Génération de nombres
L’algorithme suivant permet de générer des entiers de manière pseudo-aléatoires. Soient x1,...,xi,... :
On effectue un calcul simple comme xi+1 = xi*m + c (mod N) pour m bien choisi et N une puissance de 2.
On divise par N pour un réel aléatoire en [0..1]
On multiplie ensuite par R pour un réel en [0..R]
Et on arrondit pour un entier en [0..R?1]
Attention toutefois : prendre xi mod. R est très mauvais si R est une puissance de 2!!
Génération de structures
La génération de structure consiste :
Soit à générer un entier dans un bon intervalle et le décoder
Soit à générer la structure itérativement avec un entier généré chaque fois que l'algorithme doit prendre une décision .
La deuxième méthode plus facile à programmer et évite problèmes d'entiers trop grands.
Utilisation 0: interface avec l'extérieur
programme de jeu: pour ne pas toujours jouer pareil
joli écran
réseau: attendre un temps aléatoire avant de réessayer un transfert après une collision.
Utilisation 1: tester un algorithme
Générer un jeu de tests sur les cas aléatoires (Ne remplace pas les tests systématiques qui utilisent chaque branche du programme)
Attention, se rappeler que :
« Tester ne prouve jamais qu'un programme est sans fautes »
Sauf pour ceux avec un nombre fini (et petit) de données possibles
Utilisation 2: calcul numérique de statistiques
On peut donner plusieurs exemples d’applications dans ce domaine :
Calculer la superficie moyenne du polygone défini (enveloppe convexe) par 10 points choisis aléatoirement dans le carré [0,1][0,1].
Générer, disons 1000, cas aléatoires et calculer la superficie de chacun
Attention, cette utilisation peut être :
dangereuse : car très faible probabilité qu’on soit loin du vrai moyen.
très dangereuse : si la distribution est très bizarre (écart type très grand), presque certain d'être loin du vrai moyen.
Utilisation 3: Simulation de processus (naturels ...)
Exemples:
Propagation d'une maladie
Effet sur la circulation si l’on modifie une route
Résilience d'un réseau à des pannes
Comportement d'une bourse où des commandes de ventes ou d'achats sont générées par des logiciels
En fait, cette technique peut être utilisé partout où la complexité des interactions entre les composants d'un système exclut tout calcul direct.
Utilisation 4: algorithmes probabilistes
Quelques exemples :
Algorithmes de calcul exact qui utilisent des choix aléatoires
Algorithmes calculant une probabilité d'échec (mais, souvent, ils reconnaissent qu'un échec est arrivé). Donc, répéter plusieurs fois un évènement (avec choix différents) réduit exponentiellement la probabilité d'échec
Complexité des algorithmes
Complexité des algorithmes : temps et espace
Le plus souvent le temps de calcul est le plus important. Il faut considérer le temps et l’espace dans le pire des cas, c'est-à-dire définir un majorant de la complexité en temps et en espace. Pour cela, on effectue une analyse de l’algorithme (analyse souvent facile, souvent difficile et quelquefois impossible).
Comme fonction de la taille des entrées notation O( )
Le temps (ou espace) dépend des entrées. On n’a donc pas de majorant universel. Il faut considérer le temps comme fonction de la taille n des entrées, en nombres, bits, caractères et chercher à majorer cette fonction. On obtient une complexité souvent exprimée t(n)=O(f(n) c'est-à-dire il existe N et c tels que si n > =N, alors t(n) < =cf(n).
On dit aussi omicron, omega, OMEGA, THETA.
Complexité d'un algorithme, pas d'un problème
Ici, nous considérons l'analyse du temps d'un algorithme donné. La complexité d'un problème peut être défini (approximativement) comme la complexité du meilleur algorithme possible qui le résout. L'analyse d'un algorithme fournit un majorant de la complexité du problème.
Trouver un minorant est, le plus souvent, beaucoup plus difficile ...
Analyses
Analyses simples du texte du programme
Une boucle 1 à n prend le temps O(n)
Deux boucles imbriquées 1 à n prennent temps O(n2), et ensuite de suite.
Une recherche dichotomique sur n possibilités prend le temps O(logn)
Algorithme d’Euclide pour pgcd(m,n) (supposons m > =n); m remplacé en 2 itérations par m mod n prend dans le pire des cas  [(m-ð1)/2 ] c'est-à-dire O(logn). Mais est-ce vraiment possible ?
Analyses plus complexes du comportement du programme
On utilise ce type d analyse dans le cas des boucles où le nombre d'itérations n'est pas évident. On peut notamment citer les exemples suivants :
chercher quelque chose: s'il y a une borne évidente sur le nombre de cas à considérer, ça donne un majorant mais peut-être très grossier
processus itératif qui converge, peut-être, très lentement
boucles très simples mais où le calcul du nombre d'itérations semble très difficile

Par exemple l’algorithme suivant :
Tant que (n>1) si (n~pair) alors n:=n/2; sinon n:=3n+1 fin si fin tant que
Personne ne peut garantir que ce programme s’arrête pour tout n positif!
Analyses par récurrence
Prenons par exemple le problème 3SAT : expression booléenne qui est la conjonction de clauses de la forme (u ou v ou w) où u v et w sont des variables ou négations de variables. L’algorithme brut consiste à considérer les 2n affectations possibles des n variables. Dans le cas ou n=3, la manière la plus efficace consiste à diviser l’algorithme en trois sous problèmes :
u vrai,
u faux mais v vrai,
u et v faux mais w vrai
La taille des sous-problèmes est donc respectivement n-ð1, n-ð2, n-ð3. Le majorant est alors donné par t(n)=t(n-ð1+t(n-ð2)+t(n-ð3) c'est-à-dire t(n)=O(aðn) où að est la (plus grande des) racine(s) de xn=xn-ð1+xn-ð2+xn-ð3, ou 1=x-ð1+x-ð2+x-ð3 ( y
d'où on peut déduire que avant le fin on a y > x
implicitement sinon ; ne rien faire
après le sinon on a x < =y
Donc x < =y est vrai à la fin de chaque branche et x < =y est vrai à la fin de l'instruction conditionnelle.
Les boucles
Pour vérifier le bon fonctionnement des boucles, il faut prévoir et vérifier :
Un ensemble d'assertions connues avant la boucle (la précondition)
Un ensemble d'assertions souhaitées après la boucle (la postcondition)
Ajouter d'autres assertions vraies à chaque itération
L'astuce est de trouver les bonnes nouvelles assertions
Démontrer qu'une condition est vraie après une boucle
Prendre l'exemple d'une boucle :
tant que ExpressionBooleenne faire
BlocInstruction
fintantque;

Trouver une assertion ``invariante'' telle que
La pré-condition doit entraîner l'invariant au début de la première itération ;
Et l'invariant Plus la ExpressionBooleenne entraînent que l'invariant est vrai à la fin de l'itération ;
Et l'invariant Plus la négation de ExpressionBooleenne entraînent la post-condition .
Un exemple très simple
la somme des éléments d'un tableau T[1..n]:
i:=1; s:=0; tant que i 0);
facile à trouver le code qui maintient l'invariant
ajouter une dernière phase de vérification si besoin
Les procédures et fonctions
Démontrer le bon fonctionnement d’une procédure ou d’une fonction consiste à :
Démontrer pour chaque fonction () qu'elle produit le résultat souhaitée ;
En utilisant ce même fait pour les autres fonctions déjà prouvées ;
Pour les fonctions récursives, un raisonnement par récurrence (qui nécessite souvent une description minutieuse du résultat dans tous les cas).
Le problème de Fusion-Recherche
Soit un nombre n d'objets (disons les entiers 1...n). Au départ chaque objet constitue un ensemble.
Considérons deux opérations: FUSIONner deux ensembles et CHERCHer dans quel ensemble se trouve un objet donné (on peut supposer que l’on est libre de choisir comme nom d'un ensemble produit le nom qui convient parmi les deux noms des ensembles fusionnés).
Quel est le temps de faire une suite d'opérations?
Quelques méthodes
Une Méthode naïve: temps linéaire
Quand on fait la fusion de A et B, choisir comme nom celui de A et parcourir B en changeant le nom associé à chaque élément de B. Cette méthode nécessite que les éléments de chaque ensemble soient reliés (par exemple dans une liste avec pointeurs). Dans le pire cas on fusionne toujours un A d'un seul élément avec un grand B.
On obtient donc un temps n-ð1 pour la dernière fusion. Et la moyenne dépend de l'application.
Une astuce simple: temps (amorti) O(logn)
IL faut toujours choisir comme nom principal celui de l'ensemble le plus grand (ce qui nécessite le stockage de la taille de chaque ensemble. Cette taille est facile à mettre à jour après une fusion).
Remarque : un objet est renommé au plus log(i) fois dans une suite de i fusions. On obtient alors un temps (amorti) par opération O(logn).
Une astuce de plus: temps (pire cas) O(logn)
On utilise une nouvelle structure de données: un arbre où les pointeurs sont orientés vers la racine: la racine contient le nom de l'ensemble. Dans ce cas, il faut toujours fusionner selon les deux tailles : le plus grand des deux ensembles devient père de l'autre. Il n’est pas nécessaire de chercher à mettre à jour les noms (en fait ne plus les stocker).
Deux remarques :
Pour trouver le nom d'un objet, il suffit alors de suivre les pointeurs à la racine : en montant vers la racine pour trouver le nom.
La taille des ensembles double (au moins) à chaque itération. Donc, au plus, on a logn itérations.
Et encore une astuce
Chaque fois qu'on a parcouru le chemin d'un objet vers la racine, on le parcourt une deuxième fois, en remplaçant chaque pointeur par un raccourci directement à la racine !
Remarque : Le pire des cas d'une opération reste O(logn). Mais chaque recherche rend plus rapide des recherches à venir. Dans ce cas, quel est l'effet sur le temps total ?
Les fonctions log* et T
Log*(n) est une fonction qui croît très lentement avec n. Le nombre de fois qu'il faut appliquer log2 à n (avec arrondi vers le bas chaque fois) pour arriver à 1. T(n) une fonction qui croît TRES vite avec n : la valeur d'un tour de n fois 2. log* est l'inverse de T.
On va démontrer que le temps (amorti) d'une opération de fusion/recherche est O(log*(n)).
Majoration
Majorer le temps amorti: (1) les gros sauts de taille
Le temps d'une fusion est constante : on ne fait qu'ajouter un pointeur et sommer les deux tailles. Le temps de suivre un pointeur en cherchant la racine est « facturé » à l'opération de recherche ou à l'opération de fusion qui a ajouté l'objet comme un fils; selon les tailles des ensembles père et fils. Si les deux tailles ont des valeurs différentes de log*, facturer à la recherche. Le nombre facturés à une recherche est forcément O(log*(n)).
Majorer le temps amorti: (2) les petits sauts
Si les deux tailles ont la même valeur de log*, facturer à la fusion. Pour un ensemble de taille s, où T(i) ( s ( T(i+1), le nombre facturé est au plus log2 T(i+1), c'est-à-dire T(i) et donc ( s. Deux sous-arbres sont disjoints si le rapport entre leurs deux tailles (grand:petit) est inférieur à 2. Donc :
pour les s tels que T(i) ( s < 2T(i), le total facturé est inférieur à n
pour ceux tels que 2T(i) ( s < 4T(i), à n/2.
pour les s tels que T(i) ( s < T(i+1), à 2n
et enfin, pour tous les s, inférieur à 2nlog*(n)
Conclusion
On obtient donc :
temps total O((nombre de fusions + nombre de recherches)*log*(n))
temps amorti de chaque opération O(log*(n))
Il n’est pas évident que ce majorant soit strict (pour cet algorithme ou un autre).
Recherche d'occurrences d'une chaîne de caractères dans une autre
Si l’on considère une chaîne longue le texte dans un tableau T[1..n] et une chaîne courte le cible dans un tableau C[1..m] ; vérifier qu'une occurrence de C commence à T[i] prend un temps m. Donc, un algorithme simple en temps se retrouve avec la complexité O(mn).
Comment faire mieux ?
L'algorithme de Knuth-Morris-Pratt
On lit le tableau de texte T de gauche à droite. A chaque moment, on stocke la (taille de la) partie au début de C qui correspond à la partie de T qu'on vient de lire. Cette taille peut être mise à jour sans retour en arrière.
Il faut savoir, pour chaque préfixe de C, quel est son plus long suffixe qui est aussi un préfixe de C.
Un automate qui effectue la recherche du suffixe-préfixe
On créé un état pour chaque lettre de C, mettons par exemple C=C1,...,Cm . Considérons un état Ci : on a déjà lu C1,...,Ci. On continue d’avancer si la prochaine lettre x est la bonne Ci+1 (sauf si on a trouvé un C complet). Sinon on recule. Problème : De combien doit-on reculer lorsqu’on est à Cj ; où C1,...,Cj est le plus long préfixe de C qui est aussi suffixe de C1,...,Ci x.
Le pré-calcul
Le pré-calcul (du plus long préfixe de C qui est aussi suffixe de C1,...,Ci) peut se faire facilement en temps O(m2) mais ce n'est pas optimal :
Une récurrence pour Si, la longueur de ce préfixe-suffixe si Ci+1 = CSi+1, Si+1 = Si+1, sinon, si Ci+1=CSSi+1, Si+1=SSi+1, etc.
Le calcul par programmation dynamique
Le temps du pré-calcul : O(m)
Le temps total O(m+n)
L'algorithme de Boyer et Moore: l'idée
Comment faire mieux qu'un algorithme qui considère chaque lettre une seule fois? C’est impossible (dans certains cas au moins). Mais souvent, si C est de taille moyenne, on peut exclure des sections de T sans les regarder !
exemple trivial: si C est « aaaaaaaaaa », et T ne contient pas de a, on peut trouver la solution en ne regardant que chaque 10-ème lettre de T.
L'algorithme de Boyer et Moore: un peu de détail
Pour trouver les positions où une occurrence de C pourrait terminer, il faut :
Regarder d'abord la lettre T[m]
Si cette lettre n'a pas d'occurrences en C, avancer par m
Si sa dernière occurrence en C est à position j (j
 :