Remerciez-le!

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

Memento INFO 104 Semestre 2 Année 2018 Professeur Maurice TCHUENTE Section 2 :

Memento INFO 104 Semestre 2 Année 2018 Professeur Maurice TCHUENTE Section 2 : Les Boucles Recherche séquentielle dans une structure qui peut être vide Trouve := faux ; < Se mettre en position initiale> Jusqu’à <Condition de sortie : trouve ou position_hors_limites> faire début Prendre él _cour ; On est placé avant l’élément suivant ; Si él_cour = val alors trouve := vrai sinon <Passer à la position suivante> fin ; <Traitement final > ; Recherche séquentielle dans une structure non vide Trouve := faux ; <Prendre le premier élément > Répéter Si él_cour = val alors trouve := vrai sinon <Passer à la position suivante> <Prendre élément suivant> Jusqu’à <Condition de sortie : trouve ou position_hors_limites> <Traitement final > Algorithmes sur les vecteurs Recherche séquentielle de val dans un vecteur V[1..n] trouve := faux ; i := 1 ; { Initialisation de la boucle } jusqu’à trouve ou (i > n) faire si V[i] = val alors trouve := vrai sinon i := i+1. Recherche séquentielle avec sentinelle de val dans un vecteur V[1..n] V[0] := val ; i := n ; { Initialisation de la boucle } jusqu’à V[i] := val faire i := i-1 ; trouve := i > 0. Recherche dichotomique de val dans un vecteur V[1..n]. i := min ; j := max ; jusqu’à i = j faire début m := (i + j) div 2 ; {i  m < j} si val  V[m] alors j := m sinon i := m+1 fin trouve := V[i] = val. Segmentation d’un vecteur V[min..max] par rapport à X = V[max] Idée : utiliser deux tamis g (gauche) et d (droite) qui :  encadrent X : V[r ]  X pour r < g, V[s ]  X pour s  d  se rapprochent (g se déplace vers la droite et d vers la gauche) jusqu’à coïncider g := min ; d := max ; V[r ]  X pour r < g, V[s ]  X pour s  d Jusqu’à g = d faire début Jusqu’à V[g]  X ou g = d faire g := g+1 ; Jusqu’à V[d]  X ou g = d faire d := d-1 ; Echanger (V[g],V[d]) V[r ]  X si r < g, V[s ]  X si s  d fin ; Echanger (V[g],V[max]). Drapeau tricolore Mettre un vecteur V[1..n] de trois couleurs dans l’ordre vert, rouge et jaune. Idée : utiliser trois pointeurs i, j, k et les faire progresser de sorte que : V[r] = vert pour r < i, V[r] = rouge pour i  r < j et V[r] = jaune pour k < r i := 1 : j := 1 ; k := n ; Jusqu’à j > k faire si V[k] = jaune alors k := k-1 sinon si V[k] = rouge alors début Echanger (V[k], V[j]) ; j :=j+1 fin sinon V[k] = vert début x:=V[i]; V[i]:=V[k] : V[k]:=V[j] ; V[k]:=x ; i:=i+1 ; j:=j+1 fin Sélection du maximum de V[1..i] et placement en position i Max := V[1 ; Pos := 1 ; Pour j := 1 à i faire si V[j >Max alors debut Pos := j ; Max := V[j fin ; Echanger (V[Pos, V[i) Tri d’un vecteur V[1..n] par sélection et placement du maximum Pour i := n à 2 faire <Sélection du maximum de V[1..i] et placement en position i> Commentaire : Tri non stable à cause de Echanger (V[Pos, V[i) qui déplace V[i. Nombre de comparaisons-échanges : O(n2) indépendant de V. Tri d’un vecteur V[1..n] par sélection via comparaisons–échanges d’éléments consécutifs Idée : Soit Pos la position du terme de gauche de la dernière comparaison-échange après un balayage. V[Pos..n contient les plus gros éléments de V . Il suffit de trier V[1..Pos. Balayage de V[1..i] par comparaisons-échanges avec calcul de Pos : Pos := 1 ; Pour j := 1 à i faire si V[j >Max alors debut Pos := j ; Echanger(V[j ; V[j+1) fin ; Tri i := n ; Jusqu’à i=1 faire debut < Balayer V[1..i] par comparaisons-échanges avec calcul de Pos> ; i := Pos fin ; Commentaire : Algorithme stable et plus rapide que le précédent, nombre de comparaisons-échanges = nombre d’inversions = O(n2) en moyenne, donc même complexité que le tri par sélection. Tri par insertion Idée : procéder par récurrence en insérant V[i] dans le vecteur trié V[1..i-1], pour i = 2, … , n. Insertion de V[i] dans le vecteur trié V[1..i-1] Idée : pousser les V[j] vers la droite jusqu’à rencontrer un élément inférieur ou égal à V[i]. On est donc ramené à chercher dans V[1..i-1] un élément V[j] inférieur ou égal à V[i]. Recherche et insertion avec sentinelle : V[0] := V[i] ; j := i-1 ; Jusqu’à V[j]  V[0] faire j := j-1 ; V[j+1] := V[0] ; Algorithme Pour i := 2 à n faire < Insérer V[i] dans V[1..i-1]> Fusion de deux sous-vecteurs triés V[a..b] et V[b+1..c] en un sous-vecteur trié V[a..c]. Idée : fusionner dans W puis recopier dans V. i := a ; j := b+1 ; k := a ; Jusqu’à i > a ou j > c faire si V[i] < V[j] alors debut w[k] := V[i] ; i := i+1 ; k := k+1 fin sinon debut w[k] := V[j] ; j := j+1 ; k := k+1fin Pour i := a à c faire V[i] := W[i] ; Tri récursif par fusions successives Idée : Pour trier V[i..j], on ne fait rien si n  m, sinon on procède en trois étapes : Découper V[i..j] en V[i..milieu] et V[milieu+1..j], avec milieu = (i+j) div 2 Trier V[i..milieu] et V[milieu+1..j] Fusionner les sous-vecteurs triés V[i..milieu] et V[milieu+1..j] Analyse des performances : T(n) = 2T(n/2) + O(n). On montre que T(n)=O(n log2 n) Défaut de cet algorithme : utilisation du vecteur intermédiaire W. Exercice : Donner une version non récurrente de cet algorithme (programmation dynamique) Tri par segmentation de V[min..max] Idée : Si min = max on ne fait rien, sinon :  Mettre V[max] = M en position k, V[i] ≤ M pour i < k, et M ≤ V[j] pour k < j  Trier ensuite V[min..M-1] et V[M+1..max] car V[M] est à sa place définitive Performance : O(n log n) en moyenne et O(n2) au pire. Tri d’un vecteur d’éléments de type énuméré V[1..n] (exemple des caractères)  Calcul du vecteur des fréquences FREQ[a..z] des lettres de V[1..n].  Calcul du vecteur des fréquences cumulées FREQ_CUMUL[a..z]  Placement des éléments triés, dans le vecteur V[1..n] Question : Cet algorithme est-il stable ? Comment procéder pour minimiser les mouvements lorsque les éléments à trier sont volumineux et coûtent cher lorsqu’on veut les échanger ? Tri par Tas (Tas : arbre binaire complet représenté par un vecteur) Un tas est un vecteur V1..n dont les éléments sont dessinés sous forme d’arbre binaire complet ainsi qu’il suit :  V1 est à la racine  V2i s’il existe, est le fils gauche de Vi, et V2i+1 s’il existe, est le fils droit de Tasi. De plus tout fils est plus petit que son père. Le plus grand élément se trouve donc à la racine. Dans un tas de profondeur h, on a 1 nœud à la racine (niveau 1), 2 nœuds de profondeur 2, 4 nœuds de profondeur 3, …, 2h-1 nœuds de profondeur, les autres nœuds étant de profondeur h. En conséquence, 1 + 2 + … + 2h-1 = 2h – 1 < n  1 + 2 + … + 2h = 2h+1-1. D’où log2 (2h – 1) < log2 n  log2(2h+1-1) < h+1. Donc h = O(log2 n) Dans un tas, le plus gros élément est V1. D’où l’algorithme suivant pour trier V1..n :  Transformer V1..n en tas ; i := n ;  Jusqu’à i = 1 faire début Echanger (V1 et Vi) ; Place V1 en bonne position i, mais perturbe la racine du tas V1..i-1 ; i := i-1 ; <Faire descendre V1 dans V1..i en l’échangeant successivement avec le plus grand de ses fils si l’un d’eux est plus grand; Descente_Tas (V, 1, i)> fin ; Transformation de V[1..n] en tas Idée : Partir de V[1..n] et considérer des tas de plus en plus grands à partir du bas. Pour i := n div 2 à 1 faire Descente_Tas (V, i, n) ; Fait descendre Vi dans V1..n Performance : O(n log2 n) au pire car on a au plus n descentes de longueurs log2 n. Procédure Descente_Tas (V, i, max) qui fait descendre V[i] dans V[i..max] Idée : insérer V[i] dans un chemin qu’on découvre au fur et à mesure. trouve := faux ; j := i ; { Initialisation de la boucle } jusqu’à trouve ou (2j > max) faire si V[j]  <tous ses fils> alors trouve := vrai sinon <Echanger V[j] et son plus grand fils et mettre à jour j> ; Recherche de Mot[1..m] dans uploads/Finance/ memento-l1-structures-de-donne-es-final-pour-e-tudiants.pdf