Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Quelques algorithmes de recherche 1. La recherche En informatique, on est génér

Quelques algorithmes de recherche 1. La recherche En informatique, on est généralement amener à stocker un ensemble de données présentant des caractéristiques communes. L’une des opérations les plus usuelles est la recherche de ces ensembles d’éléments selon certains critères. La recherche peut intervenir dans l’un des cas suivant : - Cas d’un annuaire téléphonique informatisé. Un annuaire téléphonique est destiné à fournir le numéro de téléphone d’un abonné étant donné son nom et éventuellement les caractéristiques complémentaires comme le prénom ou l’adresse. - Un autre exemple assez différent est celui d’un dictionnaire où l’on cherche la définition des mots en faisant d’abord la recherche du mot que l’on veut définir a. La recherche séquentielle La façon de procéder la plus naïve consiste à comparer l’élément recherché (X) successivement à tous les éléments de la liste (l) selon le schéma séquentiel suivant : - Le compteur i est compris entre 1 et la longueur de la liste - Comparer X et le ième élément On va s’intéresser dans un premier temps à la recherche d’une solution quelconque. On arrête donc la progression dans la liste lorsqu’on trouve un élément qui est égal à X. Dans le cas où la liste est remplacée par un tableau T, T[i] désignera le ième élément de la liste (tableau) et l’algorithme suivant nous dira si l’élément X se trouve dans le tableau T ou pas Algorithme recherche ; Const N=20 ; type T : tableau [0..N-1] de entier ; Var X,i :entier ; Début Ecrire ("lecture des éléments du tableau ") ; Pour (i0 à N-1) Faire Lire(T[i]) ; Finpour Ecrire ("élément à rechercher ") ; Lire(X) ; Tantque ((i<=N-1) et (X #T[i])) faire ii+1 ; fintantque si (i>N-1) alors Ecrire ("élément ", X, "inexistant ") ; Sinon Ecrire (X, "existe en position ", i) ; Finsi Fin Remarque : Dans cet algorithme la condition d’arrêt de la boucle tantque est double. On effectue donc à chaque itération un test de fin de la liste (i<=N-1), en plus de la comparaison entre les éléments (X #T[i]). Tant que ces conditions ne sont pas réunies on itère (avance) dans la case suivante. Dès que l’une des conditions est vérifiée on sort de la boucle tantque. b. La recherche dans une liste triée Supposons à présent qu’il existe un ordre total sur les éléments et que la liste est triée par ordre croissant. Pour rechercher encore un élément X, on peut encore évidemment parcourir séquentiellement la liste jusqu’à ce qu’on trouve soit X soit un élément strictement supérieur à X (auquel cas X n’est pas dans la liste puisque les éléments sont rangés dans l’ordre croissant). Ici la recherche est encore séquentielle et elle tient très peu compte du fait que les éléments de la liste sont rangés dans l’ordre croissant. 1 Un autre algorithme prenant cela en compte est appelé recherche dichotomique. Le principe de la recherche par dichotomie de l’élément X dans une liste triée est le suivant : - Comparer X avec l’élément M du milieu de la liste (tableau) Si X=T[M],on a trouvé l’élément et la recherche s’arrête. Si X>T[M] , il est impossible que X se trouve avant M dans la liste (tableau) et il ne reste qu’à traiter la moitié droite de la liste. Si X<T[M], alors l’élément ne peut se trouver que dans la moitié gauche de la liste. - On continue ainsi la recherche en diminuant de moitié le nombre d’éléments de la liste restante à traiter à chaque après chaque comparaison et si la liste ne contient pas X, la recherche se terminera par un échec. L’algorithme de recherche est le suivant : Algorithme recherche_dicho ; Const N=10 ; Type T : tableau [0..N-1] de entier ; Var X,i ,M,g,d,res : entier ; Début Ecrire ("lecture des éléments du tableau ") ; Pour (i0 à N-1) Faire Lire(T[i]) ; Finpour Ecrire ("élément à rechercher ") ; Lire(X) ; g0 ; dN-1 ; res-1 ; Tantque (g<=d et res=-1) faire m(g+d) div 2 ; si (X=T[M]) alors resM ; sinon si (X<T[M]) alors d M-1 ; sinon gM+1 ; finsi finsi fintantque si (res=-1) alors Ecrire ("élément ", X, "inexistant ") ; Sinon Ecrire ("élément existant en position ", res) ; Finsi Fin 2. Le tri La spécification du tri est la suivante : la donnée est une liste de n éléments et à chaque élément est associée une clé dont la valeur appartient à un ensemble totalement ordonné. Le résultat est une liste dont les éléments forment une permutation des éléments de la liste d’origines telles que les valeurs des clés soient croissantes quand on parcourt la liste séquentiellement. Exemple : considérons une liste d’entiers T Si on applique le tri sur T, on obtient une nouvelle liste T’ où les éléments sont rangés dans l’ordre croissant T’ 3. Méthodes de tri par sélection 2 8 -3 4 10 2 -3 2 4 8 10 a. Sélection simple Cette méthode consiste à rechercher le minimum de la liste puis le placer à la première place et recommencer le même processus sur le reste des éléments de la liste. La figure ci-dessous représente les étapes successives d’un tri par sélection sur une liste de 6 éléments Liste : | 101 115 30 63 47 20 1ère sélection ---------------------------------------------------20 Placement 20 | 115 30 63 47 101 2ème sélection ---------------------------------------------------30 Placement 20 30 | 115 63 47 101 3ème sélection ---------------------------------------------------47 Placement 20 30 47 | 63 115 101 4ème sélection ---------------------------------------------------63 Placement 20 30 47 63 | 115 101 5ème sélection ---------------------------------------------------101 Placement 20 30 47 63 101 | 101 Après la 5ème sélection la liste devient triée Remarque : on peut noter qu’après le kème placement les k plus petits éléments de la liste sont à leurs places définitives et l’algorithme est le suivant : Algorithme tri_selection ; Const N=10 ; type T : tableau [0..N-1] de entier ; Var i ,j,k,val:entier ; Début Ecrire ("lecture des éléments du tableau ") ; Pour (i0 à N-1) Faire Lire(T[i]) ; Finpour i0 ; Tantque (i<=N-1) faire ji ; Pour (ki+1 à N-1) Faire si (T[k]<T[j]) alors j k ; val T[j] ; T[j] T[i] ; T[i] val ; finsi finpour i i+1 ; fintantque Ecrire ("le tableau trié est :") ; Pour (i0 à N-1) Faire Ecrire(T[i]) ; Finpour Fin b. Le tri bulles 3 Ici, pendant qu’on parcourt la liste, une permutation est effectuée à chaque fois qu’on rencontre deux éléments successifs qui ne sont pas dans le bon ordre. L’algorithme est le suivant : Algorithme tri_bulles ; Const N=10 ; type T : tableau [0..N-1] de entier ; Var i ,j,val:entier ; Début Ecrire ("lecture des éléments du tableau ") ; Pour (i0 à N-1) Faire Lire(T[i]) ; Finpour iN-1 ; Tantque (i>1) faire Pour (j2 à i) Faire si (T[j]<T[j-1]) alors val T[j] ; T[j] T[j-1] ; T[j-1] val ; finsi finpour i i-1 ; fintantque Ecrire ("le tableau trié est : ") ; Pour (i0 à N-1) Faire Ecrire(T[i]) ; Finpour Fin 4. Méthodes de tri par insertion Dans ces méthodes, on trie successivement les premiers éléments de la liste. A la ième étape, on insère le ième élément à son rang parmi les i-1 éléments précédemment triés. La figure suivante présente le principe. La liste est : 101 115 30 63 47 20 1ère insertion : 101 115 | 30 63 47 20 2ème insertion : 30 101 115 | 63 47 20 3ème insertion : 30 63 101 115 | 47 20 4ème insertion : 30 47 63 101 115 | 20 5ème insertion : 20 30 47 63 101 115 a. Insertion séquentielle Si la recherche de la position où l’on désire insérer le nouvel élément se fait de manière séquentielle, on dit que l’on fait de l’insertion séquentielle et l’algorithme est le suivant : Algorithme tri_insert_seq ; Const N=10 ; Type T : tableau [0..N-1] de entier ; Var i ,x,k,:entier ; Début Ecrire ("lecture des éléments du tableau ") ; Pour (i0 à N-1) Faire Lire(T[i]) ; 4 Finpour Pour (i3 à N-1) Faire k i-1 ; x T[i] ; tantque (T[k]>x) faire T[k+1] T[k] ; k k-1 ; fintantque T[k+1] x ; finpour Ecrire ("le nouveau tableau est :") ; Pour (i0 à N-1) Faire Ecrire(T[i]) ; Finpour Fin b. Insertion dichotomique Nous avons vu qu’on pouvait faire une recherche dichotomique dans une liste triée. Au cours du tri par insertion, les i-1 premiers éléments sont triés et on cherche le rang du ième élément. Il est préférable de chercher ce par une méthode dichotomique dont il suffira par la suite d’effectuer un transfert Exercice : Ecrire l’algorithme correspondant 5 uploads/Science et Technologie/ algorithmes-de-recherche.pdf