Remerciez-le!

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

Info2033 devoir 1 Université de Yaoundé I Faculté des Sciences Département d ? Informatique Fondation FR I Task Force Formation Cours Universitaires INF Méthodes Algorithmiques et Structures de Données Devoir N ? Nove Novembre Professeur Maurice TCHUENTE

Université de Yaoundé I Faculté des Sciences Département d ? Informatique Fondation FR I Task Force Formation Cours Universitaires INF Méthodes Algorithmiques et Structures de Données Devoir N ? Nove Novembre Professeur Maurice TCHUENTE Faire les exercices ci-après de la ?che de cours sur les techniques de construction des boucles NB Comme précedemment les devoirs seront faits par groupes de La note obtenue par chaque membre du groupe sera égale au pourcentage de participation déclaré collectivement par les membres avec un total de le devoir lui ? mêe ét m ême étant évalué sur Exercice 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 n Recherche séquentielle avec sentinelle en position d ? un élément val dans un vecteur V n Recherche dichotomique d ? un élément val dans un vecteur trié V 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 i- créer un vecteur trié V i par insertion de V i Exercice 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é ?nitive 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 C- il existe entre i et j un élément supérieur ou égal à X Donner l ? initialisation de i et j 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 Exprimer la condition ?nale de la boucle globale et déduire l ? action ?nale Dire pourquoi c ? est le tamis de gauche qui doit être examiné en premier 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 Donner