Algorithmique – Notions avancées

Arbre

Dans un arbre, les données sont organisées de manière à former une arborescence. Il est souvent nécessaire de :

• calculer la taille de l’arbre ;
• calculer la hauteur de l’arbre ;
• effectuer une opération de recherche ou de traitement sur les données de l’arbre.

Pour effectuer ces opérations, il faut être en mesure de parcourir l’arbre : cela permettra de compter le nombre de nœuds (pour connaître la taille de l’arbre), la profondeur maximale (pour connaître sa hauteur) ou d’analyser/traiter les nœuds. Un arbre peut être parcouru en largeur ou en profondeur.

Parcours en largeur

On commence par parcourir tous les nœuds de niveau 0, puis tous ceux de niveau 1, etc.

Parcours en profondeur 

On descend le plus en profondeur possible, en explorant les arêtes de gauche de l’arbre. Une fois arrivé sur une feuille, on remonte jusqu’à tomber sur un nœud possédant une arête droite, qu’on va explorer, et ainsi de suite.

Dans un parcours en profondeur, les nœuds seront traversés plusieurs fois pendant le parcours. On peut décider d’analyser/traiter les données d’un nœud :

• lors de l’arrivée sur le nœud, en descendant l’arbre : on parle alors de parcours préfixe ;
• entre la fin de l’exploration de l’arête gauche du nœud (y compris si elle est vide) et le début de l’exploration de l’arête droite du nœud : on parle alors de parcours infixe ;
• lorsque l’on quitte le nœud, pour remonter dans l’arbre : on parle alors de parcours postfixe.

Graphe

Dans un graphe, les données sont organisées de manière à former un réseau. Il est souvent nécessaire de :

• calculer la taille du graphe ;
• identifier les cycles du graphe ;
• chercher un chemin pour aller d’un sommet à un autre.

Pour effectuer ces opérations, il faut être en mesure de parcourir le graphe : cela permettra de compter le nombre de sommets (pour connaître la taille du graphe), et d’identifier les cycles et chemins reliant certains sommets. Un graphe peut être parcouru en largeur ou en profondeur.

Parcours en largeur 

On choisit un sommet de départ, puis on commence par parcours ses sommets voisins. Ensuite, on parcourt les voisins de chaque voisin du sommet de départ, et ainsi de suite.

Parcours en profondeur

On choisit un sommet de départ, puis on se dirige vers un de ses voisins. Ensuite, on va se diriger vers un voisin du voisin, et ainsi de suite. À chaque fois qu’un sommet est parcouru, on le marque.

Pour chaque sommet traversé, le prochain voisin parcouru sera choisi, si possible, parmi les sommets voisins qui n’ont pas encore été explorés.

Algorithme récursif

Un algorithme récursif est un algorithme qui s’appelle lui-même. Chaque auto-appel permet de résoudre un sous-problème, qui est une version plus petite du problème que l’algorithme de base doit régler, selon le principe « Diviser pour régner ».

Programmation dynamique

La programmation dynamique est une technique de programmation permettant d’améliorer l’efficacité de certains algorithmes récursifs, en supprimant les auto-appels redondants. Elle consiste à mémoriser les résultats renvoyés par chaque auto-appel : ce principe s’appelle la mémoïsation.

Par la suite, à chaque tentative d’auto-appel, l’algorithme vérifiera s'il a mémoïsé le résultat d’un auto-appel identique :

• si c’est le cas, il récupérera ce résultat et ne lancera pas l’auto-appel ;
• si ce n’est pas le cas, il lancera l’auto-appel, puis mémoïsera son résultat.

Texte et motif

Les algorithmes de recherches textuelles servent à identifier un motif (suite de caractères) dans un texte.

Il existe plusieurs algorithmes permettant de recherche le motif dans un texte, comme les algorithmes de recherche « naïfs » et l’algorithme de Boyer-Moore.

Algorithmes de recherche naïfs 

Ces algorithmes consistent à superposer le motif et les premiers caractères du texte, puis à comparer un à un chaque caractère du motif et du fragment du texte.

Si le motif est différent, on le décalera d’un cran vers la droite, puis on comparera de nouveau motif et texte, et ainsi de suite.

Exemple : recherche du motif nsi dans un texte

Algorithme de Boyer-Moore 

L’algorithme de Boyer-Moore utilise le même principe de base que les algorithmes naïfs, mais il permet parfois de décaler le motif de plusieurs crans d’un coup, ce qui le rend plus efficace.

Avec l’algorithme de Boyer-Moore, la comparaison entre le motif et le segment de texte commence par le caractère de droite du motif.

Pour déterminer le nombre de crans de décalage, on repère le caractère de la chaîne qui ne correspond pas au motif :

• si ce caractère existe dans le motif, alors on place le motif de manière à ce qu’il soit aligné avec ce caractère, puis on essaie une nouvelle comparaison ;
• si ce caractère n’existe pas dans le motif, on décale le motif pour le placer à droite du caractère.

Exemple : recherche du motif nsi dans un texte