Remerciez-le!

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

Fiche Pédagogique Etablissement : Cité Erriadh Bouficha A.S : 2016/2017 Enseign

Fiche Pédagogique Etablissement : Cité Erriadh Bouficha A.S : 2016/2017 Enseignant : Mme. Monia FERJANI Classe : 4ème Scientifiques Chapitre : Les algorithmes Avancées Objectifs :  Connaitre une méthode de résolution de problème de tri et de recherche.  Connaître les 3 types de méthodes de tri: o Tri par sélection o Tri à bulle o Tri par insertion.  • Savoir choisir la méthode de recherche la plus adaptée au problème traité PLAN DU COURS ACTIVITES INTRODUCTIVES EXPLOITATION DES ORDINATEURS I. Introduction : A quoi consiste un algorithme de tri Activité : discussion : exemples des problèmes II. Problème de tri 1. Tri par séléction 2. Tri à bulle 3. Tri par insertion * Explication * Présentation d’un exemple * Activité : tri par ordre croissant d'une suite de valeurs entières. + Exécution sur machine. III. Problème de recherche 1. Recherche Séquentielle 2. Recherche Dichotomique * Explication * Présentation d’un exemple * Activité : Recherche d'une valeur donnée dans un tableau. + Exécution sur machine. IV. Applications Activité : Exemples sur machine Exécution sur machine de quelques exercices. Observation après la fin de cours : …………………………………………………………………………………………………………. …………………………………………………………………………………………………………… …………………………………………………………………………………………………………… … Méthodes de Tri page 1/7 Chapitre 6 4ème Maths Méthode de Tri Introduction : Le mot TRI est employé en informatique pour désigner l’action d’……………… des objets selon un …………………... Première méthode : Tri à Bulle : A) Spécification : Le principe du tri bulle (bubble sort) est de comparer deux à deux les éléments e1 et e2 consécutifs d'un tableau et d'effecteur une permutation si e1 > e2. On continue de trier jusqu'à ce qu'il n'y ait plus de permutation. B) Algorithme : 0. Début Algorithme Tri_a_Bulles 1. pour i de n jusqu’à 1 faire pour j de 2 jusqu’à i faire si T[ j-1 ] > T[ j ] alors temp  T[ j-1 ] ; T[ j-1 ]  T[ j ] ; T[ j ]  temp Finsi finpour finpour 3. Fin Tri_a_Bulles Exemple : Soit le tableau (5, 4, 2, 3, 7, 1), appliquons le tri à bulles sur ce tableau d'entiers. Visualisons les différents états de la liste pour chaque itération externe contrôlée par l'indice i  i = 6 / pour j de 2 jusqu’ à 6 faire  i = 5 / pour j de 2 jusqu’à 5 faire  i = 4 / pour j de 2 jusqu’à 4 faire Méthodes de Tri page 2/7  i = 3 / pour j de 2 jusqu’à 3 faire  i = 2 / pour j de 2 jusqu’ à 2 faire  i = 1 / pour j de 2 jusqu’ à 1 faire (boucle vide) C) Programme pascal : Méthodes de Tri page 3/7 program TriParBulle; const N = 10; Type TTab = array [1..N] of integer; var Tab : TTab ; procedure TriBulle (var Tab:TTab) ; var i, j, t : integer; begin for i := N downto 1 do for j := 2 to i do if Tab[j-1] > Tab[j] then begin t := Tab[j-1]; Tab[j-1] := Tab[j]; Tab[j] := t; end; end; procedure Initialisation(var Tab:TTab) ; var i : integer; begin for i := 1 to N do begin write(‘ donner T[‘,i,’]: ’); readln(Tab[i]); end; end; procedure affichage(Tab:TTab) ; var i : integer; begin writeln('------------------------'); for i:= 1 to N do write(Tab[i] : 3, ' | '); writeln; end; begin Initialisation(Tab); writeln('TRI PAR BULLE'); writeln; Affichage(Tab); TriBulle(Tab); Affichage(Tab); writeln('----------------------'); end. Méthodes de Tri page 4/7 Deuxième méthode : Tri par sélection : A)Spécification Le principe du tri par sélection/échange (ou tri par extraction) est d'aller chercher le plus petit élément du vecteur pour le mettre en premier, puis de repartir du second élément et d'aller chercher le plus petit élément du vecteur pour le mettre en second, etc... B) Algorithme : Algorithme Tri_Selection début pour i de 1 à n-1 faire m  i ; pour j de i+1 à n faire si T[ j ] < T[ m ] alors m  j ; temp T[ m ] ; T[ m ]  T[ i ] ; T[ i ]  temp m i ; Fsi fpour fpour Fin Tri_Selection Troisième méthode : Tri par Insertion : A) Spécification : Le principe du tri par insertion est d'insérer à la n-ième itération le n-ième élément à la bonne place. B) Algorithme : Algorithme Tri_Insertion Début pour i de2 jusquà n faire v  T[ i ] ; j  i ; Tantque Tab[ j-1 ] > v faire T[ j ]  T[ j-1 ]; j  j-1; FinTant ; T[ j ]  v fpour Méthodes de Tri page 5/7 Fin Tri_Insertion Fiche Pédagogique Etablissement : Cité Erriadh Bouficha A.S : 2016/2017 Enseignant : Mme. Monia FERJANI Classe : 4ème Scientifiques Chapitre : Les algorithmes Avancées Objectifs de la séance :  Connaitre une méthode de résolution de problème de tri et de recherche.  Connaître les 3 types de méthodes de tri: o Tri par sélection o Tri à bulle o Tri par insertion.  • Savoir choisir la méthode de recherche la plus adaptée au problème traité PLAN DU COURS ACTIVITES INTRODUCTIVES EXPLOITATION DES ORDINATEURS III. Introduction : A quoi consiste un algorithme de tri Activité : discussion : exemples des problèmes IV. Problème de tri 4. Tri par séléction 5. Tri à bulle 6. Tri par insertion * Explication * Présentation d’un exemple * Activité : tri par ordre croissant d'une suite de valeurs entières. + Exécution sur machine. III. Problème de recherche 3. Recherche Séquentielle 4. Recherche Dichotomique * Explication * Présentation d’un exemple * Activité : Recherche d'une valeur donnée dans un tableau. + Exécution sur machine. Méthodes de Tri page 6/7 IV. Applications Activité : Exemples sur machine Exécution sur machine de quelques exercices. Observation après la fin de cours : …………………………………………………………………………………………………………. ………………………………………………………………………………………………………………… ………………………………………………………………………………………………………………… … Méthodes de Tri page 7/7 uploads/Science et Technologie/ tri-2010.pdf