Analyse de certains algorithmes - Chapitre 3 - Algorithmique Avancé et Complexité - PDF

Université Ferhat Abbas – Setif 1- Faculté des sciences Département d’informatique Algorithmique Avancé et Complexité Dr. Hadi Fairouz Maitre de conférences [email protected]  Chapitre 3 Analyse de c...

Université Ferhat Abbas – Setif 1- Faculté des sciences Département d’informatique Algorithmique Avancé et Complexité Dr. Hadi Fairouz Maitre de conférences [email protected]  Chapitre 3 Analyse de certains algorithmes Contenu du chapitre  Algorithmes de tri  Algorithmes pour les arbres et les graphes  Algorithmes de hachage  Algorithmique du texte Chapitre 3 Analyse de certains algorithmes Introduction L'analyse des algorithmes vise à évaluer leur efficacité en mesurant la complexité temporelle, c'est-à-dire le temps d'exécution en fonction de la taille de l'entrée, ce qui permet de prédire leur comportement à grande échelle. Elle inclut également l'évaluation de la complexité spatiale, qui mesure la mémoire utilisée par l'algorithme, essentielle dans les applications où les ressources mémoire sont limitées. Enfin, cette analyse permet de comparer différents algorithmes pour identifier celui qui est le plus adapté à un problème donné, en tenant compte de la complexité temporelle, spatiale et d'autres critères tels que la simplicité d'implémentation. I. Algorithmes de Tri  Organisation des données Les algorithmes de tri jouent un rôle fondamental dans la gestion et l'organisation des données en les réarrangeant dans un ordre spécifique, que ce soit croissant ou décroissant. Cette capacité d'organisation est essentielle dans de nombreux domaines, notamment les bases de données, l'analyse de données, et même dans des applications plus simples comme l'affichage d'une liste d'éléments.  Importance des algorithmes de tri  Facilitation de la recherche : Un ensemble de données triées permet des recherches plus rapides. Par exemple, la recherche binaire, qui nécessite un tableau trié, est beaucoup plus efficace que la recherche linéaire dans un tableau non trié.  Amélioration de la présentation : Dans des applications comme les tableaux de bord ou les rapports, trier les données améliore la lisibilité et la compréhension. Une liste de produits par prix, par exemple, permet aux utilisateurs de prendre des décisions plus éclairées.  Préparation pour d'autres algorithmes : De nombreux algorithmes, notamment ceux utilisés pour le traitement des données, nécessitent des données triées pour fonctionner correctement. Par exemple, certains algorithmes de fusion ou d'optimisation reposent sur une entrée triée. 1 Chapitre 3 Analyse de certains algorithmes  Types d'ordre de tri Les algorithmes de tri peuvent organiser les données de plusieurs manières :  Tri croissant : Les éléments sont réorganisés du plus petit au plus grand. Par exemple, les nombres ou les chaînes de caractères sont classés dans l'ordre alphabétique.  Tri décroissant : Les éléments sont organisés du plus grand au plus petit. Cela peut être utile dans des contextes où les utilisateurs souhaitent voir les valeurs les plus élevées en premier, comme dans un classement.  Exemples d'algorithmes de tri Les algorithmes de tri sont des outils essentiels pour l'organisation des données. En classant les éléments dans un ordre spécifique, ils facilitent la recherche, améliorent la présentation et préparent les données pour d'autres opérations algorithmiques. Leur diversité et leur adaptabilité en font des composants clés dans de nombreux systèmes informatiques et applications. Par exemple, des algorithmes tels que le tri à bulles (Bubble Sort), le tri par insertion (Insertion Sort) et le tri par sélection (Selection Sort) sont simples à comprendre, mais ils manquent d'efficacité pour de grands ensembles de données. Pour des volumes de données croissants, des algorithmes comme le tri fusion (Mergesort) et le tri rapide (quicksort) sont souvent préférés en raison de leur efficacité et de leur capacité à gérer de grandes quantités d'informations. Le choix de l'algorithme approprié dépend également des caractéristiques spécifiques des données, telles que la plage des valeurs, ainsi que des exigences en matière de stabilité et d'utilisation de la mémoire.  Tri Fusion (Mergesort) Le tri fusion (ou merge sort) est un algorithme de tri basé sur la stratégie de diviser pour régner. Ce principe repose sur trois étapes fondamentales : 1. Diviser : Diviser le tableau en deux sous-tableaux. 2. Régner : Trier chaque sous-tableau de manière récursive. 3. Fusionner : Combiner les deux sous-tableaux triés pour créer un tableau trié final. 2 Chapitre 3 Analyse de certains algorithmes  Étapes de l'algorithme 1. Diviser le tableau :  Le tableau est divisé en deux parties égales (ou presque égales) jusqu'à ce que chaque sous-tableau contienne un seul élément. À ce stade, chaque élément peut être considéré comme trié.  La division se fait en trouvant l'index du milieu. Si le tableau a n éléments, l'index du milieu est donné par = 2. 2. Triage Récursif :  Chaque sous-tableau est trié de manière récursive en appliquant le même algorithme. Cette étape continue jusqu'à ce que chaque sous-tableau ait une seule entrée.  La récursion crée une pile d'appels qui, une fois atteinte la base (un seul élément), commence à se dérouler. 3. Fusion :  Une fois que les sous-tableaux sont triés, l'étape suivante consiste à les fusionner. Cela se fait en comparant les éléments des deux sous-tableaux et en les plaçant dans un nouveau tableau trié.  On utilise souvent deux index pour parcourir les sous-tableaux, en ajoutant l'élément le plus petit à un tableau temporaire jusqu'à ce que tous les éléments soient fusionnés.  Exemple illustratif Considérons un tableau non trié : [38, 27, 43, 3, 9, 82, 10]. 1. Diviser :  [38, 27, 43, 3, 9, 82, 10] → [38, 27, 43] et [3, 9, 82, 10]  [38, 27, 43] → et [27, 43] → ,  [3, 9, 82, 10] → [3, 9] et [82, 10] → , , , 3 Chapitre 3 Analyse de certains algorithmes 2. Régner :  Chaque élément est maintenant considéré comme trié. 3. Fusionner :  Fusion des éléments :  et → [27, 43]  Fusion des sous-tableaux et [27, 43] → [27, 38, 43]  et → [3, 9]  Fusion des sous-tableaux et → [10, 82]  Fusion finale : [27, 38, 43] et [3, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]  L’Algorithme de Tri Fusion (Mergesort) Input : Un tableau de nombres arr[1...n], où n est la taille du tableau. Output : Une version triée du tableau arr. fonction mergeSort(tableau) si la longueur de tableau T(n−2)=T(n−3)+c(n−2) 3.En continuant ce développement, nous avons : T(n)=T(1)+c(2+3+…+n) Somme des Entiers La somme des entiers de 1 à n est donnée par : ( + 1) 1+2+3+…+ = 2 Donc, nous pouvons écrire : ( + 1) = 1 +. 2 Résultat Final Cela nous donne : T(n)=O(n2) Interprétation : Ce résultat provient du fait que le choix du pivot peut conduire à un déséquilibre total, entraînant ainsi une performance sous-optimale. Ainsi, pour éviter ce cas, des stratégies comme le choix aléatoire du pivot ou l'utilisation du médian des trois sont souvent employées pour améliorer la performance de Quicksort.  Mergesort Vs Quicksort Cette comparaison se base sur plusieurs critères, notamment la complexité temporelle, l'utilisation de la mémoire, la stabilité, et les cas d'utilisation.  Complexité Temporelle :  Le tri fusion et le tri rapide ont une complexité de O (n log n) dans tous les cas, ce qui en fait des choix sûrs pour des performances prévisibles.  Le tri rapide est généralement très efficace, mais sa complexité peut se dégrader à O(n2) si les pivots ne sont pas choisis judicieusement. 12 Chapitre 3 Analyse de certains algorithmes  Utilisation de la Mémoire :  Le tri fusion nécessite un espace supplémentaire proportionnel à la taille du tableau, ce qui peut être un inconvénient dans les environnements à mémoire limitée.  En revanche, le tri rapide peut être exécuté en place, utilisant moins de mémoire supplémentaire.  Stabilité :  La stabilité est un critère important dans certaines applications où l'ordre des éléments équivalents doit être préservé. Le tri fusion est stable, tandis que le tri rapide ne l’est pas.  Cas d'Utilisation :  Le choix de l'algorithme dépend souvent du contexte d'utilisation. Le tri fusion est idéal pour le tri externe et les grandes quantités de données, le tri rapide est souvent privilégié pour son efficacité en mémoire. Tri Fusion Tri Rapide Critère Description Divise le tableau en sous-tableaux, Choisit un pivot, partitionne le tableau les trie, puis les fusionne. autour de ce pivot, puis trie récursivement. Complexité O (n log n) O(n2) Temporelle Complexité O(n) (nécessite un espace O (log n) (en place si implémenté de Spatiale supplémentaire pour les sous- manière récursive). tableaux). Stabilité Stable (préserve l'ordre des éléments Instable (peut changer l'ordre des éléments équivalents). équivalents). Performance Efficace pour les grands ensembles Très rapide pour la plupart des cas, mais de données et dans le tri externe. peut être lent dans certains scénarios (cas défavorable). Cas Idéal pour les grandes quantités de Souvent utilisé en pratique en raison de sa d'Utilisation données, en particulier lorsque la rapidité, surtout pour les tableaux en mémoire est limitée. mémoire. Table 3.1 : tri fusion Vs tri rapide 13 Chapitre 3 Analyse de certains algorithmes II. Algorithmes pour les arbres et les graphes Les arbres et les graphes sont des structures de données essentielles en informatique, utilisées pour modéliser diverses relations et interactions. À mesure que la taille des données augmente (lorsque n tend vers l'infini), comprendre et analyser les algorithmes qui opèrent sur ces structures devient crucial.  Les arbres Les arbres sont des structures de données fondamentales en informatique, utilisés pour organiser et gérer les données de manière hiérarchique. Dans ce cours, nous analyserons deux algorithmes d'arbres parmi les plus répandus : l'insertion dans un arbre binaire de recherche (BST, ou Binary Search Tree) et les algorithmes de parcours d'un arbre binaire de recherche.  Arbre Binaire de Recherche (BST) Un arbre binaire de recherche (BST) est une structure de données où chaque nœud a au plus deux enfants, et les nœuds à gauche contiennent des valeurs inférieures à celles du nœud parent, tandis que les nœuds à droite contiennent des valeurs supérieures. L'insertion dans un BST doit respecter cette propriété pour garantir une recherche efficace.  Fonctionnement de l'insertion dans un arbre binaire de recherche L'insertion d'un nouveau nœud dans un arbre binaire de recherche (ABR) suit un processus systématique qui garantit que la structure de l'arbre reste valide après l'ajout. Voici un développement détaillé de ce fonctionnement : 1. Vérification si l'arbre est vide La première étape consiste à vérifier si l'arbre est vide :  Arbre vide : Si l'arbre ne contient aucun nœud (c'est-à-dire que la racine est null), le nouveau nœud devient la racine de l'arbre. Cela signifie que le nouvel élément est le premier à être inséré et qu'il n'y a pas besoin d'effectuer d'autres comparaisons. 14 Chapitre 3 Analyse de certains algorithmes 2. Comparaison de valeurs Si l'arbre n'est pas vide, on commence à comparer la valeur du nouveau nœud avec la valeur du nœud actuel, en commençant par la racine :  Valeur inférieure : Si la valeur du nouveau nœud est inférieure à celle du nœud actuel, cela signifie que le nouveau nœud doit être placé dans le sous-arbre gauche.  Valeur supérieure ou égale : Si la valeur du nouveau nœud est supérieure ou égale à celle du nœud actuel, on descend dans le sous-arbre droit. 3. Descente dans l'arbre À chaque étape, le processus de comparaison se répète :  On continue de comparer la valeur du nouveau nœud avec celle du nœud actuel jusqu'à atteindre un emplacement vide, c'est-à-dire jusqu'à ce que l'un des sous-arbres (gauche ou droit) soit null.  Si l'on descend dans le sous-arbre gauche, on met à jour le nœud actuel pour qu'il pointe vers le nœud gauche. Si ce nœud gauche est null, cela signifie que nous avons trouvé notre emplacement pour le nouveau nœud.  Si l'on descend dans le sous-arbre droit, le même principe s'applique. Figure 3.2 : Exemple d’arbre binaire de recherche (BST) 15 Chapitre 3 Analyse de certains algorithmes  Algorithme d’Arbre Binaire de Recherche (BST) Input:  node : Un objet de type Node qui représente le nœud courant de l'arbre.  value : Une valeur (de type approprié, par exemple un entier ou une chaîne) à insérer dans l'arbre. Output:  Retourne : Un objet de type Node, qui est le nœud racine de l'arbre (ou du sous-arbre) après l'insertion de la nouvelle valeur. fonction insert(node, value) si node est None alors // Début du test pour vérifier si le noeud est vide retourner nouveau Node(value) // créer et retourner un nouveau noeud avec la valeur Fin si si value < node.value alors // Début du test pour comparer la valeur node.gauche ← insert(node.gauche, value) // Appel récursif pour insérer à gauche sinon node.droit ← insert(node.droit, value) // Appel récursif pour insérer à droite Fin si retourner node // retourner le noeud modifié Fin //Fin de la fonction 16 Chapitre 3 Analyse de certains algorithmes  Analyse : Arbre Binaire de Recherche (BST)  Correction de l'Algorithme : L'algorithme est conçu pour insérer une valeur dans un arbre binaire de recherche (BST). Voici les points à considérer pour vérifier sa correction : 1. Conditions d'Insertion  La première condition vérifie si le nœud courant est None. Si c'est le cas, cela signifie que nous avons atteint une position où nous pouvons insérer le nouveau nœud. Dans ce cas, un nouveau nœud est créé avec la valeur donnée, ce qui est correct.  Si la valeur à insérer est inférieure à la valeur du nœud courant (node.value), l'algorithme appelle récursivement insert sur le sous-arbre gauche. C'est conforme à la propriété d'un BST, où tous les nœuds à gauche d'un nœud doivent avoir des valeurs inférieures.  Si la valeur à insérer est supérieure ou égale, l'algorithme appelle insert sur le sous- arbre droit, ce qui est également correct. 2. Retour du Nœud  À la fin de la fonction, le nœud courant est retourné. Cela est nécessaire pour maintenir la structure de l'arbre lors de l'insertion des nœuds. L'algorithme est correct : il respecte les propriétés d'un arbre binaire de recherche et gère correctement l'insertion de nouveaux nœuds.  Complexité de l'Algorithme La complexité temporelle de l'algorithme dépend de la hauteur de l'arbre. Cas Pire : Dans le pire des cas, lorsque l'arbre est déséquilibré (par exemple, en forme de liste chaînée), la hauteur de l'arbre peut atteindre n (où n est le nombre de nœuds). Dans ce cas, la complexité est O(n). Cas Moyen : Dans un arbre binaire de recherche équilibré, la complexité temporelle pour insérer un élément est O(logn) en raison de la hauteur de l'arbre. Cela garantit une 17 Chapitre 3 Analyse de certains algorithmes performance efficace, même avec un grand nombre de nœuds, ce qui est l'un des avantages clés des arbres binaires de recherche équilibrés par rapport à ceux qui ne le sont pas.  Parcours d’un Arbre Binaire de Recherche Les opérations de parcours sur un arbre binaire de recherche (ABR) sont cruciales pour accéder, manipuler et afficher les données stockées dans l'arbre. Chaque méthode de parcours a ses propres caractéristiques et applications, et il est important de comprendre ces méthodes pour travailler efficacement avec des arbres.  Parcours en Profondeur (Depth-First Search - DFS) Le parcours en profondeur est une approche qui explore aussi loin que possible le long d'un chemin avant de revenir en arrière. Ce type de parcours peut être réalisé de trois manières principales : préfixe, infixe et postfixe.  Caractéristiques :  Utilise une pile (soit explicitement, soit via la récursivité).  Visite les nœuds en profondeur, ce qui peut être utile pour des applications comme la recherche de solutions dans des problèmes combinatoires.  Parcours Préfixe (Pre-order) Le parcours préfixe visite les nœuds dans l'ordre suivant : racine, sous-arbre gauche, sous- arbre droit.  Étapes : 1. Visiter le nœud actuel (racine). 2. Parcourir récursivement le sous-arbre gauche. 3. Parcourir récursivement le sous-arbre droit.  Applications :  Utile pour copier un arbre. 18 Chapitre 3 Analyse de certains algorithmes  Permet de créer une représentation de l'arbre dans le format parenthésé. Exemple : Pour un arbre avec la racine A et des enfants B et C, le parcours préfixe donnerait : A, B, C.  Algorithme de parcours préfixe Input: un nœud de l'arbre binaire, noté a. Output: une séquence de valeurs affichées en fonction de l'ordre de parcours préfixe. Affichage_préfixe(a) si NON est_vide(a) alors Afficher val(a) Affichage_préfixe(fils_gauche(a)) Affichage_préfixe(fils_droit(a)) fin si fin  Analyse : Algorithme de parcours préfixe  Correction de l'Algorithme : Le pseudo-code est correct. Il respecte la logique d'un parcours préfixe d'un arbre binaire et gère les cas où des nœuds peuvent être vides.  Parcours Infixe (In-order) Le parcours infixe visite les nœuds dans l'ordre suivant : sous-arbre gauche, racine, sous- arbre droit.  Étapes : 1. Parcourir récursivement le sous-arbre gauche. 2. Visiter le nœud actuel (racine). 19 Chapitre 3 Analyse de certains algorithmes 3. Parcourir récursivement le sous-arbre droit.  Applications :  Permet d'obtenir une séquence triée des valeurs d'un ABR, car les valeurs sont visitées dans l'ordre croissant. Exemple : Pour un arbre avec la racine A, et des enfants B (gauche) et C (droite), le parcours infixe donnerait : B, A, C.  Algorithme de parcours Infixe Input: un nœud de l'arbre binaire, noté a. Output: une séquence de valeurs affichées en fonction de l'ordre de parcours infixe. Affichage_infixe(a) si NON est_vide(a) alors Affichage_infixe(fils_gauche(a)) Afficher val(a) Affichage_infixe(fils_droit(a)) fin si fin  Analyse : Algorithme de parcours Infixe  Correction de l'Algorithme : Le pseudo-code est correct. Il respecte la logique d'un parcours infixe d'un arbre binaire et gère les cas où des nœuds peuvent être vides.  Parcours Postfixe (Post-order) Le parcours postfixe visite les nœuds dans l'ordre suivant : sous-arbre gauche, sous-arbre droit, racine. 20 Chapitre 3 Analyse de certains algorithmes  Étapes : 1. Parcourir récursivement le sous-arbre gauche. 2. Parcourir récursivement le sous-arbre droit. 3. Visiter le nœud actuel (racine).  Applications :  Utile pour supprimer un arbre, car il visite d'abord les nœuds enfants avant de traiter le nœud parent.  Peut être utilisé pour évaluer des expressions arithmétiques représentées par un arbre. Exemple : Pour un arbre avec la racine A, et des enfants B (gauche) et C (droite), le parcours postfixe donnerait : B, C, A.  Algorithme de parcours Postfixe Input: un nœud de l'arbre binaire, noté a. Output: une séquence de valeurs affichées en fonction de l'ordre de parcours postfixe. Affichage_postfixe(a) si NON est_vide(a) alors Affichage_postfixe(fils_gauche(a)) Affichage_postfixe(fils_droit(a)) Afficher val(a) fin si fin 21 Chapitre 3 Analyse de certains algorithmes  Analyse : Algorithme de parcours Postfixe  Correction de l'Algorithme : Le pseudo-code est correct. Il respecte la logique d'un parcours postfixe d'un arbre binaire et gère les cas où des nœuds peuvent être vides.  Analyse : Parcours d’un Arbre Binaire de Recherche L'analyse des différents parcours d'un arbre binaire de recherche (ABR) — préfixe, infixe et postfixe — révèle des caractéristiques communes qui sont essentielles pour comprendre leur efficacité.  Complexité des Parcours Les trois types de parcours d'un arbre binaire — préfixe (pre-order), infixe (in-order) et postfixe (post-order) — partagent une structure de récursivité similaire. Cela signifie que le mécanisme de base pour visiter les nœuds est fondamentalement le même, même si l'ordre de visite varie.  Visite unique de chaque nœud : Dans chacun de ces parcours, chaque nœud de l'arbre est visité exactement une fois. Que ce soit pour afficher la valeur du nœud ou pour effectuer une opération sur celui-ci, tous les nœuds sont traités.  Complexité linéaire : En raison de cette visite unique, la complexité temporelle des trois algorithmes est linéaire par rapport au nombre total de nœuds n de l'arbre. En d'autres termes, le temps nécessaire pour compléter le parcours est directement proportionnel à la taille de l'arbre.  Expression de la Complexité Temporelle La complexité temporelle pour chacun de ces parcours peut être exprimée comme suit : T(n)=O(n) Cela signifie que, dans le pire des cas, le temps d'exécution de l'algorithme sera proportionnel à n, où n est le nombre de nœuds dans l'arbre.  Parcours Préfixe (Pre-order) : Lors de ce parcours, la racine est visitée en premier, suivie du sous-arbre gauche et ensuite du sous-arbre droit. Chaque nœud est traité une seule fois, donc la complexité est O(n). 22 Chapitre 3 Analyse de certains algorithmes  Parcours Infixe (In-order) : Ce parcours est souvent utilisé pour obtenir les valeurs d'un ABR dans un ordre trié. Comme pour le parcours préfixe, chaque nœud est visité exactement une fois, ce qui donne également une complexité de O(n).  Parcours Postfixe (Post-order) : Dans ce cas, les nœuds sont visités après leurs sous-arbres gauche et droit. Encore une fois, chaque nœud est traité une seule fois, entraînant une complexité de O(n).  Conséquences de la Complexité La complexité linéaire des parcours d'un arbre binaire a plusieurs implications :  Efficacité : Ces algorithmes sont très efficaces pour traiter des arbres de taille modérée à grande. Ils ne nécessitent pas de temps exponentiel, ce qui est un avantage considérable dans les applications pratiques.  Utilisation dans des applications : Les parcours préfixe, infixe et postfixe sont largement utilisés dans des applications diverses, comme l'évaluation d'expressions arithmétiques et la recherche de données. Leur efficacité en fait un choix privilégié pour ces tâches.  Simplicité d'implémentation : Les algorithmes de parcours sont généralement simples à implémenter, surtout avec la récursivité, ce qui en fait des outils puissants dans le développement de logiciels et d'algorithmes.  Parcours en Largeur (Breadth-First Search - BFS) Le parcours en largeur explore tous les nœuds d'un niveau avant de passer au niveau suivant. Cela se fait généralement à l'aide d'une file d'attente.  Caractéristiques :  Visite les nœuds par niveau.  Utile pour trouver le chemin le plus court dans un graphe ou un arbre non pondéré.  Étapes :  Commencer par la racine et l'ajouter à une file d'attente. 23 Chapitre 3 Analyse de certains algorithmes  Tant que la file d'attente n'est pas vide :  Retirer le nœud de la file d'attente.  Visiter le nœud (enregistrer ou afficher sa valeur).  Ajouter les nœuds enfants à la file d'attente (gauche puis droite).  Applications :  Utilisé dans les algorithmes de recherche de chemin, comme dans les jeux vidéo ou les réseaux. Exemple : Pour un arbre avec la racine A, et des enfants B et C, le parcours en largeur donnerait : A, B, C.  Algorithme de parcours en Largeur Input : Un nœud à partir duquel le parcours en largeur commence. Ce nœud doit être valide (non nul) pour que l'algorithme puisse s'exécuter. Output : Affichage des Valeurs des Nœuds dans l'ordre de leur visite, c'est-à-dire niveau par niveau et de gauche à droite. 24 Chapitre 3 Analyse de certains algorithmes Procédure PL(noeud: Pointeur(TNoeud)) Var N : Pointeur(TNoeud); Début Si (noeud != Nil) Alors InitFile; Enfiler(noeud); Tant que (Non(FileVide)) faire Défiler(N); Afficher(Valeur(N)); Si (FG(N) != Nil) Alors Enfiler(FG(N)); Fin Si; Si (FD(N) != Nil) Alors Enfiler(FD(N)); Fin Si; Fin Tant que; Fin Si; Fin;  Analyse : Algorithme Parcours en Largeur d’un BST L'algorithme de parcours en largeur (Breadth-First Search, BFS) est une technique fondamentale utilisée pour explorer les nœuds d'un arbre binaire de recherche (BST) ou d'un graphe.  Correction de l'Algorithme BFS L'algorithme BFS est conçu pour visiter tous les nœuds d'un arbre ou d'un graphe de manière systématique. 25 Chapitre 3 Analyse de certains algorithmes  Visite Systématique : BFS explore tous les nœuds d'un niveau avant de passer au niveau suivant. Cela garantit que chaque nœud est visité une seule fois, ce qui évite les répétitions.  Évitement des Répétitions : BFS utilise une file d'attente (queue) pour maintenir les nœuds à visiter. Chaque nœud est ajouté à la file d'attente lorsqu'il est découvert, et retiré de celle-ci lorsqu'il est traité. Cela garantit que chaque nœud est traité exactement une fois, évitant ainsi toute répétition.  Ordre de Proximité : En parcourant les nœuds niveau par niveau, BFS respecte l'ordre de proximité. Cela signifie que les nœuds les plus proches de la racine sont visités avant ceux qui sont plus éloignés, ce qui est particulièrement utile dans des applications comme la recherche de chemins les plus courts dans des graphes non pondérés.  L'algorithme BFS est correct pour les structures d'arbres et de graphes, car il garantit une exploration exhaustive et ordonnée de tous les nœuds.  Complexité Temporelle La complexité temporelle de l'algorithme BFS peut être analysée comme suit :  Visite de Chaque Nœud : Dans un arbre binaire de recherche, l'algorithme BFS visite chaque nœud exactement une fois. Si l'arbre contient n nœuds, le temps nécessaire pour visiter tous les nœuds est directement proportionnel à n.  Complexité Temporelle : Étant donné que chaque nœud est traité une seule fois et que les opérations d'ajout et de retrait dans la file d'attente se font en temps constant O(1), la complexité temporelle totale de l'algorithme est : T(n)=O(n) Cette complexité reflète l'efficacité de l'algorithme pour traiter des structures de données de taille variable. Que l'arbre soit petit ou grand, le temps de traitement augmentera linéairement avec le nombre de nœuds. 26 Chapitre 3 Analyse de certains algorithmes  Implications de la Complexité La complexité de O(n) a plusieurs implications pratiques :  Efficacité : L'algorithme BFS est efficace même pour de grands arbres binaires de recherche, ce qui le rend adapté à diverses applications, comme la recherche de chemins dans des réseaux ou la traversée de données en temps réel.  Scalabilité : Étant donné que la complexité est linéaire, l'algorithme peut être utilisé pour des structures de données qui évoluent en taille sans compromettre les performances.  Utilisation dans des Applications : BFS est souvent utilisé dans des problèmes de recherche de solutions dans des jeux, dans la navigation de réseaux, et dans les systèmes de recommandation, où il est important de traiter les nœuds de manière ordonnée et systématique.  L'algorithme de parcours en largeur (BFS) d'un arbre binaire de recherche est un outil puissant et efficace pour explorer et traiter des structures arborescentes. Sa correction repose sur sa capacité à visiter chaque nœud sans répétition et à respecter l'ordre de proximité. Avec une complexité temporelle de O(n), il est bien adapté pour des applications variées, offrant une performance stable et prévisible quelle que soit la taille de l'arbre. 27 Chapitre 3 Analyse de certains algorithmes  Les graphes Un graphe est une structure mathématique utilisée pour modéliser des relations entre des objets. Un graphe est composé de sommets (ou nœuds) et de liens (ou arêtes) qui relient les sommets. Les graphes peuvent être orientés (où les arêtes ont une direction) ou non orientés (où les arêtes n'ont pas de direction). Ils peuvent également être pondérés (où chaque arête a un poids) ou non pondérés.  Algorithme de Dijkstra L'algorithme de Dijkstra est un algorithme fondamental en théorie des graphes, utilisé pour déterminer le chemin le plus court entre un sommet source et tous les autres sommets d'un graphe pondéré. Cet algorithme est particulièrement efficace pour les applications où les poids des arêtes sont non négatifs, ce qui en fait un choix populaire pour des problèmes tels que la navigation et le routage.  Fonctionnement de l'Algorithme L'algorithme fonctionne en plusieurs étapes clés :  Initialisation :  On commence par initialiser un tableau des distances, où chaque sommet est assigné à une distance infinie, à l'exception du sommet source, qui est initialisé à 0.  Une liste ou un ensemble des sommets non visités est également maintenu.  Boucle Principale :  Tant qu'il reste des sommets non visités, on extrait le sommet avec la distance minimale (c'est-à-dire le sommet le plus proche du sommet source).  Pour chaque voisin du sommet extrait, on évalue la distance totale depuis le sommet source en passant par ce sommet. Si cette distance est inférieure à la distance déjà enregistrée pour le voisin, on met à jour cette distance. 28 Chapitre 3 Analyse de certains algorithmes  Le sommet extrait est ensuite marqué comme visité, ce qui signifie qu'il ne sera plus pris en compte dans les prochaines itérations.  Fin de l'Algorithme :  Une fois que tous les sommets ont été visités, le tableau des distances contient les distances minimales du sommet source à tous les autres sommets du graphe.  Analyse de l'Algorithme de Dijkstra  Correction L'algorithme de Dijkstra est correct pour les graphes avec des poids non négatifs. La raison en est que, à chaque itération, l'algorithme garantit que la distance minimale au sommet extrait est effectivement minimale. Cela repose sur le principe de l'induction. Une fois qu'un sommet est marqué comme visité, aucune autre voie ne pourra offrir une distance plus courte que celle déjà trouvée.  Complexité La complexité de l'algorithme de Dijkstra dépend de la structure de données utilisée pour gérer les sommets et les distances : 1. Avec une liste d'adjacence et un tableau pour les distances :  Complexité : O(∣V∣2)  Dans ce cas, le temps de recherche du sommet avec la distance minimale à chaque itération nécessite de parcourir tous les sommets non visités, ce qui peut prendre un temps proportionnel au nombre de sommets, ∣V∣. Étant donné que nous faisons cela pour chaque sommet, la complexité totale devient quadratique. 2. Avec un tas binaire (min-heap) :  Complexité : O((∣V∣+∣E∣) log∣V∣)  Lorsqu'un tas binaire est utilisé pour gérer les sommets, l'extraction du sommet avec la distance minimale et la mise à jour des distances des voisins deviennent 29 Chapitre 3 Analyse de certains algorithmes plus efficaces. La méthode de Dijkstra consiste alors à extraire un sommet (coût O(log∣V∣)) et à mettre à jour les distances pour chaque voisin, ce qui peut inclure jusqu'à ∣E∣ arêtes. Cela réduit la complexité globale, car on ne parcourt plus tous les sommets pour chaque extraction.  Algorithme de Bellman-Ford L'algorithme de Bellman-Ford est un algorithme utilisé pour trouver les chemins les plus courts à partir d'un sommet source vers tous les autres sommets d'un graphe. Il est particulièrement utile dans les situations où le graphe peut contenir des arêtes avec des poids négatifs. Contrairement à l'algorithme de Dijkstra, qui ne fonctionne que sur des graphes avec des poids non négatifs, l'algorithme de Bellman-Ford peut gérer des poids négatifs tant qu'il n'y a pas de cycles négatifs.  Fonctionnement de l'Algorithme  Initialisation :  On commence par initialiser un tableau des distances, où chaque sommet est assigné à une distance infinie, à l'exception du sommet source qui est initialisé à 0.  Un tableau (ou une liste) pour garder une trace des sommets visités peut être utilisé, mais n'est pas strictement nécessaire pour l'algorithme lui-même.  Relaxation des Arêtes :  L'algorithme effectue plusieurs passes sur toutes les arêtes du graphe. Pour chaque arête, il vérifie si la distance du sommet cible peut être améliorée en passant par le sommet source. Si le chemin passant par le sommet source est plus court que la distance actuelle du sommet cible, la distance est mise à jour.  Ce processus est répété ∣V∣−1 fois, où ∣V∣ est le nombre total de sommets dans le graphe. Cela garantit que même les chemins les plus longs (qui peuvent passer par tous les sommets) sont correctement évalués. 30 Chapitre 3 Analyse de certains algorithmes  Détection de Cycles Négatifs :  Après avoir effectué ∣V∣−1 passes, l'algorithme fait une dernière passe sur toutes les arêtes. Si une distance peut encore être améliorée, cela indique qu'il existe un cycle négatif dans le graphe.  Si aucun cycle négatif n'est détecté, les distances minimales sont considérées comme valides.  Analyse de l'Algorithme de Bellman-Ford  Correction L'algorithme de Bellman-Ford est correct pour les graphes avec des poids d'arête négatifs, tant qu'il n'y a pas de cycles négatifs. Grâce à sa méthode de relaxation, il garantit que toutes les distances minimales sont correctement calculées après ∣V∣−1 passes. La détection de cycles négatifs permet de s'assurer que l'algorithme ne retourne pas des distances erronées en raison de parcours indéfinis.  Complexité  La complexité de l'algorithme de Bellman-Ford est O(∣V∣⋅∣E∣), où ∣V∣ est le nombre de sommets et ∣E∣ est le nombre d'arêtes.  Cette complexité découle du fait que l'algorithme effectue ∣V∣−1 passes sur toutes les arêtes du graphe. Pour chaque passe, il parcourt toutes les arêtes, ce qui donne un temps d'exécution proportionnel à ∣E∣ pour chaque passe, et ainsi le temps total devient O(∣V∣⋅∣E∣).  Algorithme de Dijkstra Vs Algorithme de Bellman-Ford Les algorithmes de Dijkstra et de Bellman-Ford sont deux méthodes populaires pour résoudre le problème des chemins les plus courts dans les graphes. Bien qu'ils partagent un objectif commun, leurs approches, leurs domaines d'application et leurs performances diffèrent considérablement. Le choix entre l'algorithme de Dijkstra et l'algorithme de Bellman-Ford dépend principalement des caractéristiques du graphe à analyser. Pour des graphes avec des poids 31 Chapitre 3 Analyse de certains algorithmes d'arête non négatifs et des exigences de performance élevées, Dijkstra est souvent le meilleur choix. En revanche, lorsque des poids négatifs sont présents ou que la détection de cycles négatifs est nécessaire, Bellman-Ford est la solution appropriée. Les deux algorithmes sont des outils essentiels dans le domaine de la théorie des graphes et des applications pratiques. Algorithme de Critère Algorithme de Dijkstra Bellman-Ford Peut inclure des poids Poids des Arêtes Non négatifs négatifs Détection de Non pris en charge Prise en charge Cycles Négatifs  Avec une liste d'adjacence et un tableau pour les distances : O(∣V∣2) Complexité  Avec un tas binaire (min-heap) : O(∣V∣⋅∣E∣) Temporelle O((∣V∣+∣E∣)log∣V∣) Efficacité sur Très efficace Moins performant Graphes Denses Applications Analyse de graphes Navigation, routage, réseaux Typiques financiers, optimisation Table 3.2 : Algorithme de Dijkstra Vs Algorithme de Bellman-Ford 32 Chapitre 3 Analyse de certains algorithmes III. Algorithmes de hachage  La Structure de Données : Les Tableaux Les tableaux sont des structures de données fondamentales en informatique, utilisés pour stocker des collections d'éléments de manière contiguë en mémoire. Ils permettent un accès rapide aux éléments, ce qui les rend attrayants pour de nombreuses applications.  Pourquoi Avoir Besoin de Nouvelles Structures de Données si les Tableaux Existent Déjà ? Bien que les tableaux soient une structure de données essentielle offrant un accès rapide et une simplicité d'utilisation, ils présentent des limitations en matière de flexibilité, d'efficacité pour certaines opérations et de gestion de la mémoire. Pour ces raisons, d'autres structures de données sont nécessaires pour répondre à des besoins variés en termes de performance et de complexité des données. L'efficacité devient particulièrement significative dans le cadre de grands ensembles de données, où même de petites améliorations en termes de temps de traitement peuvent avoir un impact considérable sur les performances globales d'une application.  Réponse : Le Concept d'« Efficacité » L'efficacité est un concept clé en informatique, particulièrement en ce qui concerne la manipulation et la gestion des données. Les tableaux sont des structures de données permettant un accès rapide aux éléments en temps constant O (1), mais leur efficacité est limitée lors des recherches. Dans les tableaux non triés, la recherche nécessite un temps O(n), ce qui devient inefficace pour de grands ensembles de données, tandis que dans les tableaux triés, la recherche binaire réduit le temps à O (log n), mais nécessite un tri préalable. Avec des ensembles de données volumineux, même des recherches logarithmiques peuvent entraîner des délais significatifs. D'autres structures de données, comme les listes chaînées, qui permettent des insertions et suppressions en O (1), les tables de hachage offrant un accès en temps constant O (1), et les arbres de recherche permettant des opérations en O(log n), s'avèrent souvent plus efficaces et adaptées aux données dynamiques. Ainsi, bien que les tableaux soient utiles, leurs limitations justifient le recours à d'autres structures de données pour améliorer l'efficacité dans les applications modernes. 33 Chapitre 3 Analyse de certains algorithmes  L'Importance des Tables de Hachage Dans le monde de l'informatique, la nécessité de stocker et de récupérer des informations de manière efficace est cruciale, surtout avec l'augmentation exponentielle des données. Pour répondre à ce besoin, il est essentiel d'avoir des structures de données capables d'effectuer ces opérations en temps constant, soit O(1). C'est dans ce contexte que les tables de hachage, une structure de données de type hash, ont pris une importance prépondérante.  Le Hachage Le hachage est un processus fondamental en informatique qui permet de transformer des données d'entrée de taille variable en une sortie de taille fixe. Cette transformation est réalisée à l'aide de fonctions de hachage, qui sont des algorithmes mathématiques conçus pour produire un code ou un index unique, également appelé "hash". Ce mécanisme est largement utilisé dans diverses applications, notamment dans les tables de hachage, la sécurité des données, et le stockage efficace d'informations. Figure 3. 3 : Principe du hachage  Avantages du Hachage Le hachage présente de nombreux avantages qui en font une technique prisée dans la conception de structures de données et dans divers domaines d'application.  Support Clé-Valeur : Le hachage est particulièrement adapté pour implémenter des structures de données clé-valeur, telles que les tables de hachage. Dans cette structure, chaque élément est stocké sous une clé unique, ce qui facilite l'association des données et leur accès. Cela permet aux développeurs de créer des systèmes intuitifs et efficaces 34 Chapitre 3 Analyse de certains algorithmes pour gérer des données, que ce soit pour des bases de données, des caches ou des systèmes de configuration.  Récupération Rapide des Données : L'un des principaux atouts du hachage est sa capacité à offrir un accès rapide aux éléments. Grâce à l'utilisation d'une fonction de hachage pour déterminer l'emplacement de stockage des données, les opérations de recherche peuvent être effectuées en temps constant, soit O(1) en moyenne. Cela signifie que peu importe la taille de l'ensemble de données, le temps nécessaire pour accéder à un élément reste constant, ce qui est crucial pour les applications nécessitant des performances élevées.  Efficacité des Opérations : Les opérations d'insertion, de suppression et de recherche dans une table de hachage sont généralement très efficaces. Lorsqu'elles sont bien conçues, ces opérations peuvent être réalisées en temps constant O (1), ce qui rend le hachage idéal pour des applications dynamiques où les données changent fréquemment. Cette efficacité permet de maintenir des performances optimales même sous des charges de travail importantes.  Réduction de l'Utilisation de la Mémoire : Le hachage peut également contribuer à réduire l'utilisation de la mémoire. En allouant un espace fixe pour le stockage des éléments, il évite la fragmentation qui peut se produire avec d'autres structures de données dynamiques. Cette allocation fixe permet de gérer efficacement la mémoire, ce qui est particulièrement bénéfique dans les applications où la mémoire est une ressource limitée.  Évolutivité : Le hachage s'avère particulièrement efficace avec de grands ensembles de données. Grâce à sa capacité à maintenir un temps d'accès constant, il permet de gérer des volumes élevés de données sans dégradation significative des performances. Cela en fait une solution idéale pour des applications à grande échelle, telles que les bases de données et les systèmes de gestion de contenu, qui doivent traiter des millions d'enregistrements.  Sécurité et Cryptage : Le hachage joue un rôle crucial dans la sécurité des données. Les fonctions de hachage sont utilisées pour stocker les mots de passe de manière sécurisée, car elles permettent de convertir les mots de passe en valeurs de hachage, rendant ainsi difficile leur récupération. De plus, le hachage est essentiel pour la vérification de l'intégrité des données. Par exemple, dans les systèmes de stockage et de transmission de données, des valeurs de hachage sont souvent utilisées pour s'assurer que les données n'ont pas été altérées ou corrompues. 35 Chapitre 3 Analyse de certains algorithmes  Composants du Hachage Le processus de hachage repose sur trois composants principaux qui interagissent pour permettre le stockage efficace et l'accès rapide aux données. Ces composants sont la clé, la fonction de hachage et la table de hachage. Chacun joue un rôle crucial dans le fonctionnement global du hachage. Figure 3. 4 : Composants du Hachage 1. Clé (Key) La clé est l'élément fondamental qui est utilisé pour identifier une valeur dans la table de hachage. Elle peut être sous diverses formes, telles que :  Chaînes de caractères : Par exemple, des noms, des mots de passe, ou des identifiants d'utilisateur.  Entiers : Tels que des identifiants numériques, des numéros de série ou d'autres valeurs numériques. La clé est fournie en entrée à la fonction de hachage, qui l'utilise pour déterminer l'emplacement de stockage de l'élément correspondant dans la table de hachage. Étant unique, chaque clé doit identifier de manière distincte sa valeur associée, permettant ainsi un accès rapide et efficace. 36 Chapitre 3 Analyse de certains algorithmes 2. Fonction de Hachage (Hash Function) La fonction de hachage est un algorithme mathématique qui prend la clé en entrée et produit un index, souvent appelé "index de hachage". Ce processus comporte plusieurs caractéristiques importantes :  Déterminisme : Pour une clé donnée, la fonction de hachage renvoie toujours le même index. Cela garantit que les données peuvent être retrouvées de manière prévisible.  Rapidité : La fonction doit être suffisamment rapide pour garantir que les opérations de hachage n'introduisent pas de délais significatifs dans le traitement des données.  Uniformité : Une bonne fonction de hachage répartit uniformément les clés sur l'ensemble des indices possibles dans la table de hachage. Cela réduit le risque de collisions, où deux clés différentes génèrent le même index.  Résistance aux Collisions : Bien qu'il soit impossible d'éliminer complètement les collisions, une bonne fonction de hachage devrait minimiser leur occurrence et permettre une gestion efficace lorsqu'elles se produisent. 3. Table de Hachage (Hash Table) La table de hachage est la structure de données qui stocke les paires clé-valeur de manière associative. Voici ses caractéristiques et son fonctionnement :  Stockage Associatif : La table associe chaque clé à une valeur, ce qui permet de retrouver rapidement une valeur en fournissant sa clé.  Tableau Sous-Jacent : La table de hachage utilise un tableau pour stocker les valeurs. Les indices dans ce tableau sont déterminés par la fonction de hachage appliquée à chaque clé.  Gestion des Collisions : Les tables de hachage intègrent des mécanismes pour gérer les collisions. Les deux méthodes principales sont le chaînage, où chaque index du tableau pointe vers une liste de valeurs, et le sondage, où l'on cherche un nouvel index à utiliser en cas de collision. 37 Chapitre 3 Analyse de certains algorithmes  Types de Fonctions de Hachage Il existe de nombreuses fonctions de hachage qui utilisent des clés numériques ou alphanumériques. Les différentes fonctions de hachage offrent une variété d'approches pour gérer le stockage et la récupération des données. Le choix de la méthode dépend des exigences spécifiques de l'application, notamment en termes de sécurité, de performance et de gestion des collisions.  Développement des Types de Fonctions de Hachage 1. Méthode de Division La méthode de division est une des méthodes les plus simples et les plus courantes pour générer un index à partir d'une clé. Elle consiste à prendre la clé et à la diviser par un nombre premier p, puis à utiliser le reste comme index.  Formule : index = clé mod p  Avantages : Facilité de mise en œuvre et bonne distribution des clés si p est choisi judicieusement.  Inconvénients : Peut entraîner des collisions si plusieurs clés produisent le même reste. 2. Méthode de Multiplication La méthode de multiplication utilise un facteur constant pour multiplier la clé. Le produit est ensuite réduit par la taille de la table de hachage pour obtenir l'index.  Formule : index = ⌊clé × A⌋ mod m, où A est un constant (0 < A < 1) et m est la taille de la table.  Avantages : Cette méthode peut offrir une meilleure distribution des indices par rapport à la méthode de division.  Inconvénients : Le choix de A peut affecter la performance et la distribution. 3. Méthode du Carré Central La méthode du carré central consiste à élever la clé au carré et à extraire les chiffres du milieu pour former l'index. 38 Chapitre 3 Analyse de certains algorithmes  Formule : index = extrayez les chiffres du milieu de (clé²) mod m, où m est la taille de la table.  Avantages : Peut réduire le nombre de collisions en utilisant les chiffres du milieu, qui sont souvent plus représentatifs de la clé.  Inconvénients : Peut-être complexe à mettre en œuvre et nécessite une gestion des chiffres. 4. Méthode de Pliage La méthode de pliage consiste à diviser la clé en plusieurs parties, puis à les additionner pour obtenir un index.  Formule : index = (partie1 + partie2 +... + partieN) mod m, où m est la taille de la table  Avantages : Simple à mettre en œuvre et peut offrir une bonne distribution si les parties sont choisies correctement.  Inconvénients : Peut également entraîner des collisions, surtout si les parties sont trop similaires. 5. Fonctions de Hachage Cryptographiques Les fonctions de hachage cryptographiques sont conçues pour être sécurisées et résistantes aux collisions. Elles sont largement utilisées dans des applications telles que la sécurité des données et la vérification d'intégrité.  Exemples : MD5, SHA-1, SHA-256.  Avantages : Offrent une sécurité renforcée, ce qui les rend essentielles pour les applications sensibles.  Inconvénients : Leur complexité peut entraîner des temps de calcul plus longs. 6. Hachage Universel Le hachage universel est une technique qui vise à minimiser les collisions en utilisant une famille de fonctions de hachage. Pour chaque paire de clés, une fonction de hachage aléatoire est choisie, permettant une distribution uniforme. 39 Chapitre 3 Analyse de certains algorithmes  Avantages : Réduit le risque de collisions et améliore les performances dans des ensembles de données diversifiés.  Inconvénients : Nécessite une gestion plus complexe et peut nécessiter des ressources supplémentaires. 7. Hachage Parfait Le hachage parfait est une méthode qui garantit qu'aucune collision ne se produit. Cela est accompli en construisant une table de hachage sur un ensemble de clés connu à l'avance.  Avantages : Accès constant O(1) sans collisions, offrant des performances optimales.  Inconvénients : La construction d'une telle table peut être coûteuse en termes de temps et de mémoire, et elle n'est pas pratique pour des ensembles de données dynamiques.  Collision Une collision en hachage se produit lorsque deux clés distinctes génèrent la même valeur de hachage, c'est-à-dire que la fonction de hachage attribue le même index à des entrées différentes. Ce phénomène peut créer des problèmes significatifs lors de l'insertion, de la recherche ou de la suppression d'éléments dans une table de hachage, car il devient impossible de déterminer clairement quelle valeur est associée à une clé donnée.  Pourquoi les Collisions se Produisent-elles ? Les collisions sont inévitables dans les tables de hachage, en raison des limites de l'espace d'adressage : 1. Taille de la Table de Hachage : La table de hachage a une taille fixe (m), alors que le nombre de clés possibles peut être beaucoup plus grand. Par conséquent, plusieurs clés peuvent être mappées à un même index. 2. Fonction de Hachage : Même une bonne fonction de hachage peut produire des collisions, surtout si elle ne répartit pas uniformément les clés sur les indices disponibles. 40 Chapitre 3 Analyse de certains algorithmes 3. Réduction d’Entrées : Lorsque des clés de tailles différentes sont utilisées, la fonction de hachage réduit la taille de l'entrée à un index dans un espace limité, ce qui augmente la probabilité de collisions.  Problèmes Posés par les Collisions Les collisions peuvent entraîner plusieurs problèmes dans les opérations de hachage :  Insertion : Si une clé nouvellement insérée produit une collision, il faut déterminer où stocker la nouvelle valeur. Cela peut nécessiter une recherche dans la table pour trouver un emplacement vacant.  Recherche : Lorsqu'une clé est recherchée, si une collision a eu lieu, il faut s'assurer que l'élément trouvé correspond à la clé recherchée, ce qui peut nécessiter des comparaisons supplémentaires.  Suppression : L'élimination d'une valeur associée à une clé peut également être compliquée par le fait qu'il existe plusieurs éléments à une même position dans la table. Figure 3. 5 : Collision en hachage.  Techniques de Résolution des Collisions Les collisions dans les tables de hachage se produisent lorsque plusieurs clés sont mappées à la même valeur de hachage. Pour gérer ces collisions, il existe deux grandes catégories de techniques : le hachage ouvert et le hachage fermé. Chacune de ces approches a ses propres méthodes et mécanismes. Les techniques de résolution des collisions sont essentielles pour garantir l'efficacité et la performance des tables de hachage. Le choix entre hachage ouvert et hachage fermé dépend 41 Chapitre 3 Analyse de certains algorithmes des besoins spécifiques de l'application, notamment en termes de vitesse, d'utilisation de la mémoire et de complexité de mise en œuvre. En comprenant ces techniques, les développeurs peuvent concevoir des systèmes de hachage robustes et efficaces, capables de gérer des ensembles de données variés et dynamiques. 1. Hachage Ouvert Le hachage ouvert, également connu sous le nom de "chaining", consiste à stocker plusieurs éléments à une même position dans la table de hachage en utilisant une structure de données additionnelle, généralement une liste. Cette méthode permet de gérer les collisions en maintenant une collection d'éléments associés à un même index. Figure 3. 6 : Hachage ouvert a. Listes Chaînées  Description : Chaque index de la table de hachage contient un pointeur vers une liste (ou une autre structure) qui stocke toutes les valeurs qui ont été hachées à ce même index.  Avantages :  Facilité d'implémentation : Simple à comprendre et à mettre en œuvre.  Flexibilité : Peut gérer un nombre illimité d'éléments à un même index sans nécessiter de redimensionnement de la table.  Inconvénients :  Consommation de mémoire : Utilise plus de mémoire en raison des pointeurs et des structures de liste. 42 Chapitre 3 Analyse de certains algorithmes  Temps d'accès : Peut devenir plus lent si la liste associée à un index devient trop longue. b. Listes Triées  Description : Similaire aux listes liées, mais les éléments sont stockés dans un ordre trié.  Avantages :  Recherche plus rapide : Permet des recherches binaires dans la liste si elle est bien triée.  Inconvénients :  Coût de tri : Nécessite du temps pour maintenir l’ordre, ce qui peut ralentir les opérations d’insertion et de suppression. 2. Hachage Fermé Le hachage fermé, ou "open addressing", est une technique dans laquelle tous les éléments sont stockés directement dans la table de hachage elle-même. En cas de collision, la méthode recherche un autre emplacement dans la table pour stocker l'élément en conflit. Figure 3. 7 : Hachage fermé a. Sondage Linéaire (Linear Probing)  Description : Lorsqu'une collision se produit, l'algorithme recherche la prochaine position libre dans la table en suivant une séquence linéaire.  Avantages :  Simplicité : Facile à comprendre et à mettre en œuvre. 43 Chapitre 3 Analyse de certains algorithmes  Inconvénients :  Clustering : Peut entraîner des "clusters" de collisions, ce qui dégrade les performances au fil du temps. b. Sondage Quadratique (Quadratic Probing)  Description : Utilise une séquence quadratique pour rechercher un emplacement libre en cas de collision, par exemple, en cherchant des indices comme i2i2 (où i est le nombre d'essais).  Avantages :  Réduit le problème de clustering observé dans le sondage linéaire.  Inconvénients :  Peut encore ne pas résoudre complètement les problèmes de collisions, et la recherche peut devenir plus complexe. c. Sondage Aléatoire (Random Probing)  Description : Choisit aléatoirement un nouvel emplacement dans la table lors d'une collision.  Avantages :  Réduit la probabilité de clustering.  Inconvénients :  Moins prévisible et peut introduire des biais si le générateur de nombres aléatoires n'est pas bien conçu. d. Sondage Uniforme ( Uniform Probing)  Description : Utilise une méthode pour garantir que les emplacements sont choisis de manière uniforme, en évitant ainsi les biais.  Avantages :  Améliore la distribution des éléments dans la table. 44 Chapitre 3 Analyse de certains algorithmes  Inconvénients :  Peut nécessiter des calculs supplémentaires pour garantir l’uniformité. e. Double Hachage (Double Hashing)  Description : Utilise deux fonctions de hachage. Lorsqu’une collision se produit, la seconde fonction détermine le pas de recherche pour trouver un nouvel emplacement.  Avantages :  Réduit les risques de collisions et améliore la distribution des éléments.  Inconvénients :  Plus complexe à mettre en œuvre, car il nécessite la gestion de deux fonctions de hachage.  Analyse de la Complexité du Hachage L'analyse de la complexité des opérations sur une table de hachage est cruciale pour évaluer son efficacité. 1. Création de la Table de Hachage  Complexité : T(m)=O(m)  Explication : La création d'une table de hachage nécessite d'allouer de la mémoire pour un tableau de taille m, où m est la taille de la table. Cette opération consiste généralement à initialiser un tableau vide, ce qui implique une opération linéaire par rapport à la taille de la table. Plus la table est grande, plus le temps nécessaire pour l’allocation de la mémoire augmente. 2. Insertion  Complexité : T(n)=O(1) en moyenne  Explication : Lors de l'insertion d'un élément, la fonction de hachage est utilisée pour calculer l'index correspondant dans la table. Cette opération est généralement rapide et se fait en temps constant. Toutefois, en cas de collision (lorsque deux clés différentes produisent le même index), le temps nécessaire pour insérer l’élément peut varier en 45 Chapitre 3 Analyse de certains algorithmes fonction de la méthode de résolution des collisions. Par exemple, dans le chaînage, il peut être nécessaire de parcourir une liste, tandis que dans les méthodes de sondage, une recherche dans les emplacements adjacents peut être nécessaire. 3. Recherche  Complexité : T(n)=O(1) en moyenne  Explication : La recherche d'un élément suit un processus similaire à celui de l'insertion. On utilise la fonction de hachage pour localiser l'index. En moyenne, cette opération est très rapide, offrant un accès direct. Cependant, comme pour l'insertion, la présence de collisions peut augmenter le temps de recherche. Si plusieurs éléments sont regroupés à un même index (par exemple, dans une liste chaînée), ou si des intervalles de sondage sont nécessaires, le temps de recherche peut être allongé. 4. Suppression  Complexité : T(n)=O(1) en moyenne  Explication : La suppression d'un élément suit généralement la même logique que la recherche. On commence par localiser l'élément via la fonction de hachage, puis on le retire. En cas de collisions, on peut devoir parcourir une liste chaînée ou utiliser une méthode de sondage, ce qui pourrait rendre le temps d'opération légèrement supérieur à O(1) dans le pire des cas.  Cas Pire Il est essentiel de considérer le cas où la distribution des clés est mauvaise, ce qui peut affecter la performance :  Pour le Hachage Ouvert : T(n)=O(n) dans le pire des cas, où n est le nombre total d'éléments. Cela peut se produire si toutes les clés se hachent à la même valeur, entraînant une liste chaînée très longue à un seul index.  Pour le Hachage Fermé : T(n)=O(n) peut également se produire si la table est trop pleine et que de nombreuses collisions surviennent. Dans ce cas, les performances peuvent se dégrader rapidement, car le temps d'accès dépendra du nombre d'éléments dans la table. 46 Chapitre 3 Analyse de certains algorithmes Complexité Complexité Opération Explication Moyenne Pire Cas Création de Nécessite l'allocation de mémoire pour un tableau O(m) O(m) la Table de taille m. Utilise la fonction de hachage pour trouver Insertion O(1) O(n) l'index. Peut varier en cas de collision. Accès direct via la fonction de hachage. Temps Recherche O(1) O(n) peut augmenter en cas de collisions. Suit la même logique que la recherche. Peut Suppression O(1) O(n) nécessiter des opérations supplémentaires en cas de collision. Table 3.3 : Les différentes opérations sur une table de hachage Notes :  m est la taille de la table de hachage.  n est le nombre d'éléments dans la table de hachage.  Les complexités en moyenne sont basées sur une bonne distribution des clés et une fonction de hachage efficace. Les complexités dans le pire des cas se produisent principalement en raison de collisions excessives ou d'une mauvaise distribution des clés. 47 Chapitre 3 Analyse de certains algorithmes IV. Algorithmique du texte L'algorithmique du texte désigne l'ensemble des méthodes et techniques utilisées pour traiter, rechercher et manipuler des chaînes de caractères et des textes. Ces algorithmes sont essentiels dans divers domaines d'application, allant du traitement de texte à la bio- informatique, en passant par la recherche d'informations et la gestion des bases de données.  Principes de l'Algorithmique du Texte L'algorithmique du texte repose sur plusieurs concepts fondamentaux :  Chaînes de Caractères : Les chaînes de caractères sont des séquences de symboles ou de caractères. La manipulation de ces chaînes constitue le cœur de l'algorithmique du texte.  Opérations de Base : Les opérations courantes incluent la recherche, la comparaison, la concaténation, la séparation et la substitution de sous-chaînes. Ces opérations sont souvent implémentées dans des langages de programmation pour faciliter le traitement du texte.  Complexité Algorithmique : L'analyse de la complexité temporelle et spatiale des algorithmes est cruciale pour comprendre leur efficacité, particulièrement lorsque l'on traite de grands volumes de données textuelles.  Applications de l'Algorithmique du Texte L'algorithmique du texte trouve des applications dans de nombreux domaines :  Traitement de Texte : Les éditeurs de texte utilisent des algorithmes pour gérer le formatage, la recherche et le remplacement de texte, ainsi que la correction orthographique.  Recherche d'Informations : Les moteurs de recherche emploient des algorithmes pour indexer et retrouver des documents pertinents à partir de requêtes textuelles. Ces algorithmes incluent des méthodes de recherche de sous-chaînes et de correspondance de motifs. 48 Chapitre 3 Analyse de certains algorithmes  Bio-informatique : Dans ce domaine, l'algorithmique du texte est utilisée pour analyser des séquences d'ADN, d'ARN et de protéines, en cherchant des motifs spécifiques ou en alignant des séquences pour identifier des similarités.  Bases de Données : Les systèmes de gestion de bases de données utilisent des algorithmes pour manipuler des données textuelles, facilitant la recherche, le tri et le filtrage de grandes quantités d'informations.  Algorithmes Clés en Algorithmique du Texte Voici deux algorithmes notables qui sont couramment utilisés dans le traitement du texte :  Algorithme de Recherche de Sous-chaînes :  Algorithme de Naïf : Recherche toutes les positions possibles d'une sous- chaîne dans une chaîne de caractères donnée. Sa complexité est O(n×m), où n est la longueur de la chaîne principale et m la longueur de la sous-chaîne.  Algorithme de Knuth-Morris-Pratt (KMP) : Utilise une table de prétraitement pour éviter de comparer des caractères inutiles, avec une complexité de O(n+m).  Algorithmes de Recherche de Mot Les algorithmes de recherche de motifs sont des techniques essentielles utilisées pour localiser une sous-chaîne (ou motif) dans une chaîne de caractères (ou texte). Ces algorithmes sont largement utilisés dans divers domaines, tels que le traitement de texte, la bio- informatique et les moteurs de recherche. Dans cette section, nous allons développer deux des algorithmes les plus répandus : l'algorithme naïf et l'algorithme de Knuth-Morris-Pratt (KMP). 49 Chapitre 3 Analyse de certains algorithmes  Algorithme Naïf de Recherche de Motifs  Principe de Fonctionnement L'algorithme naïf de recherche de motifs est l'une des méthodes les plus simples et directes. Il fonctionne en parcourant le texte et en comparant le motif à chaque position possible dans le texte jusqu'à trouver une correspondance ou épuiser toutes les positions.  Étapes de l'Algorithme Naïf L'algorithme naïf de recherche de motifs suit un processus simple en plusieurs étapes. 1. Initialisation La première étape consiste à déterminer la longueur du texte n et la longueur du motif m. Ces deux valeurs sont essentielles pour définir les limites des comparaisons et éviter les erreurs d’indexation. En effet, le texte est parcouru jusqu'à la position n−m pour s'assurer que l'algorithme ne tente pas de comparer le motif avec une partie du texte qui ne contient pas suffisamment de caractères. 2. Comparaison Pour chaque position i dans le texte, qui va de 0 à n−m, l'algorithme compare les m caractères du motif avec les m caractères correspondants du texte, en commençant à la position i. Cela implique une série de comparaisons caractère par caractère, ce qui permet de vérifier si le motif est présent à cette position. Si un caractère ne correspond pas, l'algorithme abandonne cette position et passe à la suivante. 3. Correspondance Si tous les caractères du motif correspondent à ceux du texte pour une position donnée, l'algorithme enregistre cette position i comme une occurrence du motif. Cela peut se faire en ajoutant i à une liste ou en l'affichant directement, selon les besoins de l'application. Cette étape est cruciale, car elle permet de collecter toutes les occurrences du motif dans le texte. 4. Continuation L'algorithme continue de vérifier chaque position jusqu'à ce que toutes les positions possibles dans le texte aient été examinées. Cela signifie que chaque position de départ, jusqu'à n−m, est testée. Si aucune correspondance n'est trouvée après avoir exhaustivement 50 Chapitre 3 Analyse de certains algorithmes vérifié toutes les positions, l'algorithme se termine sans résultat. Cette étape garantit que toutes les occurrences potentielles du motif ont été considérées.  Exemple de l'Algorithme Naïf Considérons le texte "ababcabcab" et le motif "abc". L'algorithme vérifiera les positions suivantes :  Comparaison à la position 0 : "aba" vs "abc" → pas de correspondance.  Comparaison à la position 1 : "bab" vs "abc" → pas de correspondance.  Comparaison à la position 2 : "abc" vs "abc" → correspondance trouvée à l'index 2.  Algorithme Naïf Input: texte : Chaîne de caractères. C'est la chaîne dans laquelle nous cherchons le motif. motif : Chaîne de caractères. C'est la sous-chaîne que nous cherchons à trouver dans le texte. Output Résultat : Affichage (ou console). Lorsque le motif est trouvé dans le texte, la fonction imprime la position (index) à laquelle le motif commence dans le texte. Aucune valeur de retour : La fonction ne retourne pas de valeur (c'est une procédure), mais elle effectue des impressions sur la console pour indiquer les indices où le motif a été trouvé. 51 Chapitre 3 Analyse de certains algorithmes fonction recherche_naive(chaine, motif) // Calculer la longueur de la chaîne et du motif n  longueur(chaine) // longueur de la chaîne principale m longueur(motif) // longueur du motif à chercher // Parcourir chaque position de la chaîne où le motif peut commencer pour i de 0 à n - m faire j0 // Initialiser l'index pour comparer les caractères du motif // Comparer les caractères du motif avec la sous-chaîne correspondante tant que j < m et chaine[i + j] = motif[j] faire jj+1 // Passer au caractère suivant du motif fin tant que // Vérifier si tous les caractères du motif correspondent si j = m alors // Afficher l'index où le motif a été trouvé afficher "Motif trouvé à l'index " + i fin si fin pour fin fonction 52 Chapitre 3 Analyse de certains algorithmes  Analyse : Algorithme Naïf L'analyse de l'algorithme naïf de recherche de motifs se concentre sur deux aspects principaux : la correction de l'algorithme et sa complexité temporelle. 1. Correction L'algorithme naïf est considéré comme correct car il effectue une vérification exhaustive de chaque position du texte. Pour chaque position i dans le texte, il compare le motif avec la sous-chaîne correspondante, caractère par caractère. Cela garantit que toutes les occurrences du motif dans le texte sont détectées. Si une correspondance est trouvée, la position est enregistrée, et si aucune n'est trouvée après avoir vérifié toutes les positions possibles, l'algorithme conclut correctement qu'il n'y a pas de correspondance. Cette exhaustivité est ce qui rend l'algorithme fiable pour des applications où la précision est cruciale. 2. Complexité La complexité temporelle de l'algorithme naïf peut être analysée en tenant compte de la longueur du texte n et de la longueur du motif m.  Cas Pire : La complexité dans le pire des cas est O(n⋅m). Cela se produit, par exemple, lorsque le motif est presque identique à une grande partie du texte, ce qui entraîne de nombreuses comparaisons inutiles. Dans ce scénario, l'algorithme doit examiner chaque caractère de la chaîne principale pour chaque position, ce qui peut entraîner un grand nombre d'opérations de comparaison.  Exemple Illustratif : Considérons un texte comme "aaaaaa" et un motif "aaa". Dans ce cas, même si le motif correspond à plusieurs positions consécutives dans le texte, l'algorithme effectuera des comparaisons pour chaque position possible, conduisant à une complexité de O(n⋅m).  L'algorithme naïf de recherche de motifs est correct en ce sens qu'il vérifie toutes les positions possibles dans le texte de manière exhaustive, garantissant ainsi que toutes les occurrences du motif sont détectées. Cependant, sa complexité temporelle dans le pire des cas peut être problématique pour des chaînes de caractères longues ou des motifs fréquents, limitant son efficacité dans des applications nécessitant des performances optimales. Pour ces raisons, d'autres algorithmes de recherche plus sophistiqués, comme KMP ou Boyer-Moore, peuvent être préférés dans des contextes où la rapidité est essentielle. 53 Chapitre 3 Analyse de certains algorithmes  Algorithme de Knuth-Morris-Pratt (KMP) L'algorithme de Knuth-Morris-Pratt (KMP) est une méthode avancée pour la recherche de motifs dans une chaîne de caractères, qui se distingue par son efficacité grâce à une approche de prétraitement. Contrairement à l'algorithme naïf, qui peut effectuer de nombreuses comparaisons inutiles, le KMP utilise un tableau de "longueur de préfixe" pour optimiser le processus de recherche.  Étapes de l'Algorithme KMP L'algorithme de Knuth-Morris-Pratt (KMP) est structuré en deux étapes principales : le prétraitement du motif pour créer un tableau de préfixe, et la recherche du motif dans le texte. 1. Prétraitement La première étape de l'algorithme KMP consiste à construire un tableau de préfixe, également connu sous le nom de tableau LPS (Longest Prefix Suffix). Ce tableau joue un rôle crucial dans l'optimisation des recherches en permettant d'éviter des comparaisons inutiles.  Construction du tableau LPS :  Le tableau LPS indique, pour chaque position i du motif, la longueur du plus long préfixe qui est également un suffixe pour la sous-chaîne allant de l'index 0 à i.  Par exemple, pour le motif "ABABC", le tableau LPS serait :  Position 0 : 0 (aucun préfixe)  Position 1 : 0 (pas de suffixe qui soit un préfixe)  Position 2 : 1 (préfixe "A" est aussi suffixe)  Position 3 : 2 (préfixe "AB" est aussi suffixe)  Position 4 : 0 (pas de suffixe)  Utilité du tableau : Lorsque l'algorithme rencontre une non-correspondance après avoir comparé certains caractères, il utilise le tableau LPS pour 54 Chapitre 3 Analyse de certains algorithmes déterminer jusqu'où il peut avancer dans le motif, permettant de reprendre la comparaison à la bonne position sans revenir en arrière. 2. Recherche La deuxième étape de l'algorithme consiste à parcourir le texte à la recherche du motif en utilisant le tableau LPS construit précédemment.  Parcours du texte :  L'algorithme commence à comparer le motif avec le texte à partir du premier caractère. Il avance simultanément dans le texte et dans le motif.  Gestion des correspondances :  Si une correspondance est trouvée : Lorsque tous les caractères du motif correspondent à ceux du texte, l'algorithme enregistre la position de la correspondance. Il continue ensuite la recherche en avançant à la fois dans le texte et dans le motif.  Gestion des non-correspondances :  Si une non-correspondance est trouvée : Au lieu de revenir à la position précédente du motif, l'algorithme consulte le tableau LPS pour déterminer combien de caractères du motif peuvent être ignorés. Par exemple, si le motif a déjà été partiellement comparé, le tableau LPS permet de savoir jusqu'où sauter, ce qui réduit le nombre de comparaisons effectuées et augmente l'efficacité de l'algorithme.  Exemple de Recherche Prenons un exemple concret avec le texte T = "ABABDABACDABABCABAB" et le motif P = "ABABCABAB" : 1. Construction du tableau LPS :  Pour le motif "ABABCABAB", le tableau LPS serait : [0, 0, 1, 2, 0, 1, 2, 3, 4]. 2. Recherche : 55 Chapitre 3 Analyse de certains algorithmes  L'algorithme commence à comparer le motif avec le texte. Lorsqu'il trouve une non-correspondance après avoir comparé plusieurs caractères, il utilise le tableau LPS pour avancer dans le motif, évitant ainsi de faire des comparaisons redondantes.  Algorithme KMP Input: texte : Chaîne de caractères. C'est la chaîne dans laquelle nous cherchons le motif. motif : Chaîne de caractères. C'est la sous-chaîne que nous cherchons à trouver dans le texte. Output: Résultat : Affichage (ou console). Lorsque le motif est trouvé dans le texte, la fonction imprime la position (index) à laquelle le motif commence dans le texte. Aucune valeur de retour : La fonction ne retourne pas de valeur (c'est une procédure), mais elle effectue des impressions sur la console pour indiquer les indices où le motif a été trouvé.  Analyse : Algorithme KMP L'algorithme de Knuth-Morris-Pratt (KMP) est reconnu pour son efficacité et sa précision dans la recherche de motifs dans une chaîne de caractères. Dans cette analyse, nous allons explorer deux aspects clés : la correction de l'algorithme et sa complexité temporelle. 1. Correction L'algorithme KMP est considéré comme correct car il est conçu pour trouver toutes les occurrences du motif dans le texte de manière exhaustive et précise.  Vérification Exhaustive : L'algorithme parcourt le texte et compare les caractères du motif avec ceux de la chaîne principale, s'assurant ainsi que chaque position potentielle est examinée.  Utilisation du Tableau LPS : En intégrant le tableau de préfixe (LPS), l'algorithme optimise le processus de recherche en évitant des comparaisons inutiles. Cela permet 56 Chapitre 3 Analyse de certains algorithmes de maintenir la précision même lorsque des non-correspondances se produisent, car l'algorithme sait exactement où reprendre la comparaison.  Détection de Toutes les Occurrences : Grâce à sa structure, l'algorithme peut détecter toutes les occurrences du motif, même si elles se chevauchent. Par exemple, dans le texte "ABABAB", le motif "AB" sera trouvé à plusieurs positions, et l'algorithme les identifiera toutes sans omission. 2. Complexité La complexité temporelle de l'algorithme KMP est un de ses principaux avantages, et elle se décompose en deux phases : le prétraitement et la recherche.  Prétraitement : O(m)  Cette étape consiste à construire le tableau LPS. La complexité est proportionnelle à la longueur du motif m, car chaque caractère du motif est examiné une seule fois pour déterminer la longueur des préfixes et des suffixes. Ce processus est efficace et ne nécessite pas de comparaisons multiples.  Recherche : O(n)  L'étape de recherche dans le texte a une complexité de O(n), où n est la longueur du texte. L'algorithme parcourt chaque caractère du texte une seule fois, et grâce au tableau LPS, il évite de revenir en arrière, ce qui rend le processus très rapide.  Complexité Totale : O(n+m)  En combinant les deux phases, la complexité totale de l'algorithme KMP est O(n+m). Cela signifie que l'algorithme est linéaire par rapport à la taille du texte et du motif, ce qui le rend extrêmement efficace, même pour des textes et des motifs de grande taille. L'algorithme de Knuth-Morris-Pratt est un outil puissant pour la recherche de motifs dans des chaînes de caractères, alliant correction et efficacité. Sa capacité à détecter toutes les occurrences d'un motif sans effectuer de comparaisons inutiles le rend particulièrement adapté à des applications variées, allant du traitement de texte à l'analyse de données. Grâce à sa complexité temporelle favorable, le KMP est souvent préféré dans des contextes où la rapidité et la précision sont essentielles. 57 Chapitre 3 Analyse de certains algorithmes fonction KMP(chaine, motif) // Vérification des cas limites si longueur(chaine) = 0 ou longueur(motif) = 0 alors retourner "Aucun motif trouvé" fin si // Étape 1 : Construire le tableau LPS lps  tableau de taille longueur(motif) initialisé à 0 construireLPS(motif, lps) // Étape 2 : Rechercher le motif dans la chaîne i0 // Index pour la chaîne j0 // Index pour le motif n  longueur(chaine) // Longueur de la chaîne m  longueur(motif) // Longueur du motif résultats  [ ] // Liste pour stocker les indices des correspondances tant que i < n faire si motif[j] = chaine[i] alors // Test : Les caractères correspondent ii+1 jj+1 fin si si j = m alors // Test : Le motif complet est trouvé ajouter (i - j) à résultats // Motif trouvé j  lps[j - 1] // Rechercher les correspondances suivantes sinon si i < n et motif[j] ≠ chaine[i] alors // Test : Les caractères ne correspondent pas si j ≠ 0 alors j  lps[j - 1] sinon ii+1 fin si ; fin si ; fin si ; fin tant que retourner résultats fin fonction 58 Chapitre 3 Analyse de certains algorithmes fonction construireLPS(motif, lps) longueur  0 lps  0 i1 tant que i < longueur(motif) faire si motif[i] = motif[longueur] alors // Test : Les caractères correspondent longueur  longueur + 1 lps[i]  longueur ii+1 sinon // Test : Les caractères ne correspondent pas si longueur ≠ 0 alors longueur  lps[longueur - 1] sinon lps[i]  0 ii+1 fin si fin si fin tant que fin fonction 59 Chapitre 3 Analyse de certains algorithmes  Algorithme Naïf Vs Algorithme KMP Dans le domaine de la recherche de motifs dans des chaînes de caractères, deux algorithmes se distinguent : l'algorithme naïf et l'algorithme de Knuth-Morris-Pratt (KMP). Chacun présente des avantages et des inconvénients qui les rendent adaptés à des situations différentes.  Algorithme Naïf  Avantages :  Simplicité : L'algorithme naïf est très simple à comprendre et à mettre en œuvre. Sa logique de comparaison directe entre le motif et chaque sous-chaîne du texte est intuitive, ce qui en fait un excellent choix pour ceux qui apprennent les bases de la recherche de motifs.  Facilité d'implémentation : Grâce à sa structure simple, il peut être rapidement codé et testé, ce qui le rend utile pour des applications où la rapidité de développement est plus importante que l'efficacité d'exécution.  Inconvénients :  Inefficacité : L'algorithme naïf devient rapidement inefficace pour de grands textes ou des motifs longs. Sa complexité temporelle dans le pire des cas est O(n⋅m), ce qui signifie qu'il peut nécessiter un nombre élevé de comparaisons, particulièrement lorsque le motif est fréquemment présent dans le texte.  Comparaisons Redondantes : En cas de non-correspondance, l'algorithme recommence la comparaison depuis le début du motif, ce qui entraîne des comparaisons inutiles et augmente le temps d'exécution.  Algorithme KMP  Avantages :  Efficacité : L'algorithme KMP est bien plus efficace pour traiter des textes de grande taille et des motifs longs. Sa complexité temporelle est O(n+m), ce qui lui permet de parcourir le texte et le motif en un temps linéaire, évitant ainsi de nombreuses comparaisons inutiles. 60 Chapitre 3 Analyse de certains algorithmes  Prétraitement : Grâce à la construction du tableau de préfixe (LPS), l'algorithme peut sauter des parties du motif qui ont déjà été vérifiées, ce qui améliore considérablement l'efficacité de la recherche.  Inconvénients :  Complexité d'implémentation : L'algorithme KMP est plus complexe à mettre en œuvre. La nécessité de construire et de gérer le tableau LPS peut rendre le code plus difficile à comprendre et à maintenir, surtout pour ceux qui ne sont pas familiers avec les algorithmes avancés.  Temps de prétraitement : Bien que le prétraitement soit rapide, il ajoute une étape supplémentaire au