Remerciez-le!

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

Master BioInformatique Ann´ ee : 2012/2013 Semestre de d´ ecembre 2012 PARCOURS

Master BioInformatique Ann´ ee : 2012/2013 Semestre de d´ ecembre 2012 PARCOURS : Master 1 UE J1BS7202 : Algorithmique et Programmation ´ Epreuve : Examen Date : Lundi 17 d´ ecembre 2012 Heure : 10 heures Dur´ ee : 2 heures Documents : autoris´ es ´ Epreuve de M. Alain Griffault SUJET + CORRIGE Avertissement – La plupart des questions sont ind´ ependantes. – Vous pouvez au choix utiliser un langage algorithmique ou bien le langage python pour r´ epondre aux questions. – L’espace laiss´ e pour les r´ eponses est suf- ﬁsant (sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement d´ econseill´ e). Question Points Score ABR : algorithmes et complexit´ es 20 Total: 20 Exercice 1 : ABR : algorithmes et complexit´ es (20 points) Rappels : Les Arbres Binaires de Recherche (ABR) sont des arbres binaires qui satisfont la propri´ et´ e suivante : ∀N un nœud de l’arbre, ∀G un nœud du sous arbre gauche de N, ∀D un nœud du sous arbre droit de N, G.info ≤N.info ≤D.info, o` u info est une valeur enti` ere servant ` a comparer les nœuds. Voici pour m´ emoire une version python de deux algorithmes vus en cours sur les ABR. def minimumABR(A) : i f A ==None : return None else : Aux = A while Aux . fg !=None : Aux = Aux . fg return Aux def successeurABR (A,P) : # P d o i t e tr e un noeud non n i l de A i f P. fd !=None : return minimumABR(P. fd ) else : Aux = P AuxPere = P. pere while AuxPere!=None and AuxPere . fd==Aux : Aux = AuxPere AuxPere = Aux . pere return AuxPere (a) (2 points) En vous inspirant de la fonction minimumABR(A) vue en cours, ´ ecrire une fonction it´ erative maximumABR(A) qui retourne un pointeur sur le nœud de l’arbre A poss´ edant la plus grande valeur enti` ere s’il existe, la valeur nil sinon. Solution: def maximumABR(A) : i f A ==None : return None else : Aux = A while Aux . fd !=None : Aux = Aux . fd return Aux (b) (2 points) Donner et justiﬁer les complexit´ es (pire des cas et meilleur des cas) de votre fonction maximumABR(A) en fonction du nombre de nœuds n ou de la hauteur h de l’arbre A. UE J1BS7202 : Algorithmique et Programmation Examen, Ann´ ee 2012/2013 Solution: – Meilleur des cas : Ω(1) lorsque A n’a pas de ﬁls droit. – Pire des cas : (O)(\) lorsque A n’a qu’une descendance par ses ﬁls droits. La hauteur h de l’arbre est alors ´ egale ` a n. (c) (3 points) En vous inspirant de la fonction successeurABR(A,P) vue en cours, ´ ecrire une fonction predecesseur(A,P) qui retourne un pointeur sur le nœud poss´ edant la valeur qui pr´ ec` ede la valeur contenue dans P. Solution: def predecesseurABR (A,P) : # P d o i t etr e un noeud non n i l de A i f P. fg !=None : return maximumABR(P. fg ) else : Aux = P AuxPere = P. pere while AuxPere!=None and AuxPere . fg==Aux : Aux = AuxPere AuxPere = Aux . pere return AuxPere (d) (2 points) Donner et justiﬁer les complexit´ es (pire des cas et meilleur des cas) de votre fonction predecesseurABR(A,P) en fonction du nombre de nœuds n ou de la hauteur h de l’arbre A. Solution: – Meilleur des cas : Ω(1) lorsque P a un ﬁls gauche qui n’a pas de ﬁls droit. – Pire des cas : (O)(\) lorsque P est la racine, qu’il n’a pas de ﬁls droit, qu’il a un ﬁls gauche qui n’a qu’une descendance par ses ﬁls droits. La hauteur h de l’arbre est alors ´ egale ` a n. (e) (3 points) En utilisant les fonctions minimumABR(A) et successeurABR(A,P) vues en cours, ´ ecrire une fonction it´ erative afficherCroissantABR(A) qui aﬃche les valeurs de l’arbre binaire de recherche A en ordre croissant. Solution: def afficherCroissantABR (A) : i f A!=None : Aux = minimumABR(A) while Aux!=None : print (Aux . i n f o ) Aux = successeurABR (A, Aux) (f) (2 points) Donner et justiﬁer les complexit´ es (pire des cas et meilleur des cas) de votre fonction afficherCroissantABR(A) en fonction du nombre de nœuds n ou de la hauteur h de l’arbre A. Solution: – Meilleur des cas : Ω(n). – Pire des cas : (O)(\). – Soit : Theta(n) (g) (2 points) En utilisant les fonctions maximumABR(A) et predecesseurABR(A,P) vues en cours, ´ ecrire une fonction it´ erative afficherDecroissantABR(A) qui aﬃche les valeurs de l’arbre binaire de re- cherche A en ordre d´ ecroissant. Solution: def afficherDecroissantABR (A) : i f A!=None : Aux = maximumABR(A) while Aux!=None : Page 2 sur 3 UE J1BS7202 : Algorithmique et Programmation Examen, Ann´ ee 2012/2013 print (Aux . i n f o ) Aux = predecesseurABR (A, Aux) (h) (2 points) ´ Ecrire une fonction r´ ecursive afficherDecroissantRecursifABR(A) qui aﬃche les valeurs de l’arbre binaire de recherche A en ordre d´ ecroissant. Solution: def afficherDecroissantRecursifABR (A) : i f A!=None : afficherDecroissantRecursifABR (A. fd ) : print (A. i n f o ) afficherDecroissantRecursifABR (A. fg ) : (i) (2 points) Soit A un ABR contenant au moins deux nœuds P1 et P2, et les deux s´ equences de calculs : B1 = supprimerABR (A, P1) B1 = supprimerABR (B1 , P2) B2 = supprimerABR (A, P2) B2 = supprimerABR (B2 , P1) A-t-on toujours B1 = B2 apr` es ces calculs ? Si oui, justiﬁer. Si non, donner un exemple. Solution: Non. Page 3 sur 3 uploads/S4/ corrige.pdf