Remerciez-le!

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

Université de Yaoundé I Fondation FR2I Faculté des Sciences Task Force Formatio

Université de Yaoundé I Fondation FR2I Faculté des Sciences Task Force Formation Département d’Informatique Cours Universitaires INF2033 , Méthodes Algorithmiques et Structures de Données Devoir N 1, Novembre 2020 ⁰1, Novembre 2020 Professeur Maurice TCHUENTE Faire les exercices ci-après de la fiche de cours sur les techniques de construction des boucles. NB: Comme précedemment, les devoirs seront faits par groupes de 4. La note obtenue par chaque membre du groupe sera égale au pourcentage de participation déclaré collectivement par les membres, avec un total de 100%, le devoir lui même étant évalué sur 100. ‐même étant évalué sur 100. Exercice 1 : Ecrire avec invariant, variant puis preuve de validité, les algorithmes permettant de résoudre les problèmes suivants :  Recherche séquentielle d’un élément val dans un vecteur V[1..n]  Recherche séquentielle avec sentinelle en position 0, d’un élément val dans un vecteur V[1..n]  Recherche dichotomique d’un élément val dans un vecteur trié V[1..n]. Indication : Réduire systématiquement l’intervalle de recherche à un point.  Fusion de deux vecteurs triés par ordre croissant A[p..q] et B[r..s] dans C[n..m].  A partir d’un sous-vecteur trié V[1..i-1], créer un vecteur trié V[1..i], par insertion de V[i] E x e r c i c e 2 (Algorithme de segmentation d’un vecteur V[min..max] ) : On se propose de concevoir un algorithme de segmentation qui, pour un vecteur V[min..max], place V[max] = X à sa place définitive k de sorte que : - pour tout r tel que r < k, on a V[r ]  X - pour tout s tel que s > k, on a V[s ]  X Indication : Considérer deux indices i et j, puis faire progresser i vers la droite et j vers la gauche en garantissant l’invariant suivant : - pour tout r tel que r  i, on a V[r ]  X. Tout se passe comme si on a un tamis dont la position dans V est représentée par i, et qui se déplace vers la droite en laissant passer uniquement les éléments plus petits que X. - pour tout s tel que s  j, on a V[s ]  X. Tout se passe comme si on a un tamis dont la position dans V est représentée par j, et qui se déplace vers la gauche en laissant passer uniquement les éléments plus grands que X 1/4 - il existe entre i et j un élément supérieur ou égal à X 2.1) Donner l’initialisation de i et j 2.2) Quelle est la condition d’arrêt de la grande boucle globale qui permet de déplacer les deux tamis jusqu’à ce que leurs positions coïncident ? 2.3) Exprimer la condition finale de la boucle globale et déduire l’action finale 2.4) Dire pourquoi c’est le tamis de gauche qui doit être examiné en premier. 2.5) Décrire les trois situations qui peuvent se présenter dans la boucle, pour le couple de tamis et donner pour chaque cas l’action à exécuter 2.6) Donner la boucle ainsi obtenue 2.7) Dire comment optimiser cet algorithme en avançant à chaque fois un tamis jusqu’au blocage et donner le corps de la grande boucle ainsi obtenu. Exercice 3 (Algorithme d’Euclide pour le calcul du pgcd) : Ecrire un algorithme de calcul du pgcd de deux nombres strictement positifs a, b, et qui est basé sur les propriétés suivantes :  Si x > 0 alors pgcd (x, 0) = x  Si x > 0 et y > 0, alors pgcd(x, y) = pgcd (y, r) où r est le reste de la division de x par y. On précisera les éléments suivants : invariant, variant, condition de sortie, condition finale. E x e r c i c e 4 : Dire ce que fait le programme suivant et le prouver : i := 1 j := n tantque i<j faire si t(i)<=t(j) alors i := i+1 sinon j := j-1 resultat := t(i) Exercice 5 (Drapeau tricolore) : On considère le tri d’un vecteur V[1..n] dont les éléments ont trois valeurs possibles : vert, rouge et jaune. Montrer qu’on peut adapter la segmentation pour trier en temps linéaire ce vecteur Indication : utiliser trois pointeurs i, j, k avec pour invariant :  V[r] = vert pour r < i  V[r] = rouge pour j+1  r  k  V[r] = jaune pour k < r La partie non triée correspond donc à l’intervalle [i..j]. 2/4 Exercice 6 (Méthode du gradient) : On s’intéresse au calcul d’une approximation de la racine x* d’une fonction continue f sur un intervalle [a, b] tel que f(a) < 0 et f(b) > 0. 6.1) Rappeler le théorème de la valeur intermédiaire 6.2) Donner l’instruction conditionnelle ci-dessous qui réduit l’intervalle [a, b] de moitié tout en garantissant qu’il contient une racine x* de f. 6.3) Dire pourquoi un intervalle [a, b] contenant une racine x* de f, permet d’avoir une approximation x’ telle que |x’ – x*| ≤ |a-b|/2. 6.4) Compléter la boucle ci-dessous qui, pour  donné, permet de calculer une approximation à /2 près de la racine x*. x1 := a ; x2 := b <invariant> Jusqu’à <condition de sortie> faire <invariant> <Mise à jour de min et max avec mise en évidence de la diminution du variant> x* := <approximation proposée> 6.5) Dire pourquoi si f’ est continue avec f’(a) < 0 et f’(b) > 0, alors le minimum x* de f est dans l’intervalle a, b. 6.6) Rappeler le théorème des accroissements finis pour les intervalles [a, x*] et [x*, b] 6.7) Déduire une valeur x’ telle que f(x’) – f(x*)  (b-a)Min (|f ‘(b)|, f ‘(a))   6.8) Dire comment on peut tenter d’améliorer x’ en utilisant a et b. On s’intéresse maintenant à une méthode itérative dite du gradient qui à chaque pas améliore l’approximant xn en évoluant dans une direction d dans laquelle f diminue. Autrement dit on prend xn+1 = xn + dn,  étant un paramètre positif. On peut alors, une fois qu’on a trouvé dn,  soit minimiser f(xn+1 = xn + dn) par rapport à   soit se contenter de prendre  assez petit 6.9) Faites une proposition pour dn en utilisant le développement de Taylor de f(xn+1 = xn + dn) au voisinage de xn On considère maintenant la méthode dite de Newton qui consiste à remplacer localement la fonction f par la parabole correspondant au développement limité à l’ordre 2. 6.10) Donner le développement limité de f(xn + ∆x) à l’ordre 2 ainsi que la valeur de ∆x qui le minimise 6.11) Déduire un algorithme itératif de calcul d’une approximation de x*. 6.12) Rappeler le développement limité f(xn + ∆x, yn + ∆y) d’une fonction différentiable f de deux variables x, y autour de (xn, yn). 6.13) Donner une condition simple paramétrée par un réel positif , pour que (xn + ∆x, yn + ∆y) soit une meilleure approximation que (xn, yn). 6.14) Proposer une méthode du gradient en dimension 2 pour la calcul d’une valeur approchée du minimum d’une fonction différentiable. Exercice 7 On considère une grammaire hors contexte, G = (, VN, S, ), où  est l’alphabet ,VN, est l’ensemble des symboles intermédiaires, S est l’axiome et ,  est un ensemble des règles de production de la forme A  , où  est un élément de (  VN)*. Donner une boucle qui marque tous les symboles intermédiaires A  VN, tels que A *  (A dérive vers ), où  est le mot vide. Exercice 8 (Exponentiation rapide) : Calcul de xn, où n est un entier strictement positif. On considère trois variables entières Res, M, E. 1) Donner une boucle pour le calcul de xn, et qui est basée sur l’invariant suivant : Res*ME = xn Exemple : n = 22 Res M E 1 x 22 3/4 1 x2 11 x2 x4 5 x6 x8 2 x6 x16 1 x22 x32 0 On remarque que, à chaque pas on effectue un test sur la parité de E puis on fait E := E div 2 . Cet algorithme utilise donc la représentation binaire (enen-1 … e1e0)2 de E, c-à-d E = en2n + en-12n + … + e12 + e0 2) Réécrire l’algorithme en utilisant cette représentation. 4/4 uploads/Litterature/ info2033-devoir-1.pdf