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 INF1042 Semestre 2 Année académique 2019-2020 Professeur Maurice TCHUEN

Memento INF1042 Semestre 2 Année académique 2019-2020 Professeur Maurice TCHUENTE Section 1 : Boucles et application aux algorithmes de recherche 1.1. Les Boucles Définition 1.1 Une boucle est une construction algorithmique qui permet d’exécuter de manière répétitive une instruction ou une suite d’instructions. Il existe trois formes de boucle :  La boucle Pour  La boucle Jusqu’à … faire  La boucle Tantque … faire  La boucle Faire … jusqu’à Boucle Pour Pour Indice := Valeur_Initiale à Valeur_Finale faire <Instruction> Ceci s’applique lorsqu’on connaît à l’avance le nombre d’exécutions et les éléments qui seront traités. L’instruction est exécutée pour les valeurs de l’indice allant de Valeur_Initiale à Valeur_Finale Boucle Tantque … faire Tantque <Condition_de_Continuation> faire <Instruction> Le contrôle se fait par la condition de continuation et avant exécution de l’instruction. Tant que cette condition est vraie on exécute l’instruction. Boucle Jusqu’à … faire Jusqu’à <Condition de Sortie> faire <Instruction> Le contrôle se fait par la condition de continuation et avant exécution de l’instruction. Tant que cette condition n’est pas vraie on exécute l’instruction. Boucle Faire … jusqu’à Faire <Instruction> Jusqu’à <Condition de Sortie> Le contrôle se fait par la condition de sortie et après chaque exécution de l’instruction. Lorsque cette condition est vraie on s’arrête. Pour cette forme de boucle, l’instruction est donc exécutée au moins une fois. Exercice 1.1 Montrer comment on peut utiliser la forme Jusqu’à <Condition de Sortie> faire <Instruction> Pour réaliser les trois autres formes de boucles Dans la suite nous privilégions la forme Jusqu’à <Condition de Sortie> faire <Instruction> car elle a l’avantage d’indiquer clairement la condition de sortie de la boucle. 1.2. Technique de conception des algorithmes basés sur les boucles Pour concevoir un algorithme basé sur une boucle pour la résolution d’un problème, il est conseillé de commencer par bricoler sur un petit exemple en respectant la structure suivante : 1. Identifier le paramètre permettant de décrire la famille d’instructions à exécuter 2. Déterminer la valeur initiale v1 du paramètre 3. Identifier les actions permettant d’initialiser les traitements pour résoudre le problème 4. Action avec paramètre v1 valeur initiale du paramètre  5. Action avec paramètre v2 ; … 6. Action avec paramètre vi ; valeur générique du paramètre  … 7. Action avec paramètre v_final ; valeur du paramètre correspondant à la condition de sortie  8. Actions permettant de finaliser les traitements pour résoudre le problème posé. On peut ensuite mettre cet algorithme sous la forme suivante : La forme générique d’un algorithme basé sur une boucle est donc la suivante <Initialisations : préparent les traitements, donnent la valeur initiale au paramètre p> Jusqu’à <Condition de Sortie(p) > faire début <Instructions comportant un traitement et la progression du paramètre p> fin ; <Actions qui finalisent les traitements> 1.2.1 Application à la recherche séquentielle de val dans un vecteur V[1..n] On désire déterminer le plus petit indice i correspondant à une occurrence de val dans un vecteur V[1..n]. Une variable booléenne trouvé, indiquera si une telle occurrence existe. L’algorithme est le suivant : trouve := faux ; i := 1 ; { Initialisations} jusqu’à trouve ou (i > n) faire si V[i] = val alors trouve := vrai sinon i := i+1. Dans cet algorithme, la condition de sortie comporte un test sur trouve et un test sur i. On peut économiser l’un de ces tests en utilisant une sentinelle comme indiqué ci-dessous, où on désire déterminer le plus grand indice i correspondant à une occurrence de val dans un vecteur V[1..n]. Une variable booléenne trouvé, indiquera si une telle occurrence existe. L’idée est de placer la valeur cherchée val dans la position où l’on se retrouvera si elle n’est pas dans V[1..n], c-à-d en position 0. On est alors certain de trouver val  soit dans une position i > 0, ce qui correspond à trouve = vrai,  soit en position i = 0, ce qui correspond à trouve = faux. Recherche séquentielle avec sentinelle de val dans un vecteur V[1..n] V[0] := val ; i := n ; { Initialisations } jusqu’à V[i] = val faire i := i-1 ; trouve := i > 0. Exercice 1.2 1.2.a Montrer que la comparaison lexicographique entre deux vecteurs V[i..j] et W[i..j] peut se ramener à un problème de recherche que l’on précisera 1.2.b Donner l’algorithme correspondant à la question 1.2.a. 1.2.3 Donner un algorithme qui cherche dans un vecteur W[1..n], un sous-vecteur W[i..i+n-1] égal à V[1..n]. Exercice 1.3 Donner un algorithme qui fusionne deux vecteurs triés U[1..n] et V[1..m] en un vecteur trié W[1..n+m]. Indication : Une solution simple comporte trois boucles Exercice 1.4 Donner un algorithme qui imprime ligne par ligne, les éléments d'une matrice triangulaire inférieure d’ordre n. Exercice 1.5 (on suppose que n est impair) 1.5.1 Donner un algorithme très simple qui calcule le minimum et le maximum d’un vecteur V[1..n]. 1.5.2 Quel est le nombre de comparaisons effectuées par l’algorithme de la question 5.1 ? On considère maintenant un algorithme qui calcule le maximum et le minimum de V[1..n] en traitant successivement les couples (V[2i], V[2i+1]), pour i = 1, … , n div 2. 1.5.3 Montrer que si on connaît le maximum et le minimum de V[1..2i-1], alors on peut calculer en 3 opérations, le minimum et le maximum de V[1..2i+1]. 1.5.4 Quel est le nombre de comparaisons effectuées par l’algorithme de la question 5.3 ? Exercice 1.6 Elimination de Gauss Dans l’algorithme de Gauss pour résoudre un système linéaire Ax = b, on commence par transformer ce système linéaire en un système triangulaire équivalent, par combinaison de lignes. Ensuite on résout le système triangulaire supérieur. Dans la suite on suppose, pour simplifier les notations, que b correspond à la (n+1)ème colonne de A. 1.6.1 Compléter l’algorithme d’élimination ci-dessous en supposant qu’il n’y a pas de pivot nul Pour k := … à … faire Elimination de ak+1,k, … , ank en utilisant akk  Pour i := … à … faire Elimination de ai,k début … Pour j := … à … faire fin ; 1.6.2 Compléter l’algorithme ci-dessous pour la résolution d’un système triangulaire obtenu à la question précédente. xn := … ; Pour i := … à … faire Calcul de xi  début xi := … ; Pour j := … à … faire xi := xi - … ; xi := … ; fin Problème A (Tri d’un vecteur) On considère un vecteur V[1..n]. A.1 Compléter la procédure Select_Max ci-dessous, qui sélectionne le maximum de V[1..i] et le met en position i par permutation avec V[i]. A.2 Compléter la procédure Tri_Select_Max ci-dessous, qui trie un vecteur V[1..n] dans l’ordre croissant. On se propose d’analyser le nombre d’opérations (comparaisons, affectations) effectuées par cet algorithme A.4 Montrer que  le nombre de comparaisons effectuées par Select_Max est i-1  le nombre de comparaisons effectuées par Tri_Select_Max est n(n-1)/2. On suppose dans la suite que V[1..n] est un vecteur d’enregistrements représentant les résultats d’examen, et de type indiqué ci-dessous Record Nom : char(10) Note : integer end ; Au départ, les enregistrements sont triés par ordre alphabétique des noms. Après saisie des notes, les résultats doivent être triés par ordre de mérite. Un algorithme de tri est dit stable s’il préserve l’ordre des éléments ex-aequo. Autrement dit, à partir d’un fichier trié par ordre alphabétique, deux étudiants ayant la même note doivent après le tri, apparaître dans l’ordre alphabétique. A.5 Donner un exemple montrant que Tri_Select_Max n’est pas stable A.6 Compléter la procédure Comp_Echange_Max ci-dessous, qui effectue des comparaisons- échanges entre V[1] et V[2], puis entre V[2] et V[3], … , puis entre V[i-1] et V[i], pour placer le maximum de V[1..i] en position i. A.7 Déduire un algorithme de tri du vecteur V[1..n] A.8 Montrer que, si dans la question précédente, la dernière comparaison-échange concerne V[j] et V[j+1], alors à la fin de la procédure on a V[j+1]  V[j+2]  …  V[i]. A.9 En tenant compte de la question A.8, compléter la procédure TRI_COMP_ECH ci- dessous pour le tri efficace du vecteur V[1..n], c-à-d dans lequel les boucles ne portent pas systématiquement sur V[1..n], V[1..n-1], … V[1..i], … V[1..2] A.10 Montrer que le tri par comparaisons-échanges est stable Les algorithmes vus jusqu’ici construisent au fur et à mesure des sous-vecteurs triés V[i..n] de plus en plus grands, c-à-c correspondant 0 des valeurs décroissantes de i. On s’intéresse maintenant au tri par insertion qui construit au fur et à mesure des sous- vecteurs triés V[1..i] de plus en plus grands. A.11 Compléter la procédure Insertion ci-dessous qui, à partir d’un sous-vecteur trié V[1..i-1], crée un vecteur trié V[1..i], par insertion de V[i, en faisant des comparaisons-échanges V[i- 1]V[i], V[i-2] V[i], V[i-3] V[i], …. BV noter la présence de la position sentinelle 0. A.12 Déduire une procédure Tri_Insertion pour le tri d’un vecteur V[1..n]. A.13 Dire pourquoi Tri_Insertion est stable On se propose maintenant d’analyser les performances des algorithmes de tri qui effectuent des comparaisons uniquement entre des éléments consécutifs V[i] V[i+1]. A.14 Montrer que dans un tel algorithme, deux éléments uploads/Finance/ inf-1042-introduction-aux-structures-de-donnees-seance-3-boucles-algorithmes-recherche 1 .pdf