UTBM theorie de la programmation tda et structures de donnees 2004 gi

Publié par

UTBM le 17 janvier 2005 Final – LO42 Les documents de cours et TD sont autorisés (La copie ou les idées du voisin non). Le barème est indicatif. Le soin donné à la rédaction sera évalué. Toute réponse devra être claire et justifiée (toute ambiguïté sera mal interprétée). En fonction des propriétés des objets manipulés, vous choisirez la solution la plus efficace en terme de complexité. Sauf indication contraire, dans le cas d’algorithmes les réponses doivent être rédigées en pseudo code. Les questions bonus éventuelles ne sont à traitées que si le reste est traité convenablement.. 1) Arbre ou sac de nœuds ! (5) a) En vous basant sur le parcours en profondeur, écrivez une fonction "cycle" permettant de vérifier qu’un graphe non orienté est sans cycle. L’exploration s’arrêtera à la détection du premier cycle Vous utiliserez le TDA graphe. On suppose que le type sommet nous permet d’indicer un tableau. Type sommet = [1..nMax] ; Fonction Booléen cycle(sommet s ; Graphe g ; Var Booléen M[1..n] ; …) ; // vous pouvez compléter la liste de paramètres si nécessaire. Var … Début … Fin b) Ecrivez un prédicat "arbre" déterminant si un graphe est un arbre. Fonction Booléen arbre(Graphe g) ; Var … Début … Fin ; 2) Articulations fêlées ? (9) a) Dessinez l’arborescence de parcours en profondeur du graphe ci dessous avec point de départ A. (L’ordre alphabétique détermine l’ordre des successeurs d’un sommet.) Numérotez les sommets ...
Publié le : jeudi 21 juillet 2011
Lecture(s) : 163
Nombre de pages : 2
Voir plus Voir moins
UTBM
le 17 janvier 2005
Final –LO42 Les documents de cours et TD sont autorisÈs (La copie ou les idÈes du voisin non). Le barËme est indicatif. Le soin donnÈ ‡ la rÈdaction sera ÈvaluÈ. Toute rÈponse devra Ítre claire et justifiÈe (toute ambiguÔtÈ sera mal interprÈtÈe). En fonction des propriÈtÈs des objets manipulÈs, vous choisirez lasolution la plus efficaceen terme de complexitÈ. Sauf indication contraire, dans le cas d’algorithmes les rÈponses doivent Ítre rÈdigÈes en pseudo code. Les questions bonus Èventuelles ne sont ‡ traitÈes que si le reste est traitÈ convenablement.. 1) Arbre ou sac de nœuds !(5)a) Envous basant sur le parcours en profondeur, Ècrivez une fonction "cycle" permettant de vÈrifier qu’un graphe non orientÈ est sans cycle. L’exploration s’arrÍtera ‡ la dÈtection du premier cycle Vous utiliserez le TDA graphe. On suppose que le type sommet nous permet d’indicer un tableau. Type sommet = [1..nMax] ; Fonction BoolÈen cycle(sommet s ; Graphe g ; Var BoolÈen M[1..n] ;) ; // vous pouvez complÈter la liste de paramËtres si nÈcessaire. VarDÈbut Fin b) Ecrivezun prÈdicat "arbre" dÈterminant si un graphe est un arbre. Fonction BoolÈen arbre(Graphe g) ; VarDÈbut Fin ; 2) Articulations fÍlÈes ?(9)a) Dessinezl’arborescence de parcours en profondeur du graphe ci dessous avec point de dÈpart A. (L’ordre alphabÈtique dÈtermine l’ordre des successeurs d’un sommet.) NumÈrotez les sommets en fonction de leur ordre d’accËs Sur cette arborescence dessiner les arÍtes non utilisÈes en pointillÈs. G BC D E F Unpoint d’articulationdans un graphe connexe est un sommet dont la suppression dÈcompose le graphe en plusieurs composantes. Un graphe sans point d’articulation est dit2connexeou biconnexe. En d’autres termes, un graphe 2connexe prÈsente pour chaque couple de sommets deux chaÓnes disjointes adjacentes, donc reliant les deux sommets. Le graphe cidessus n’est pas 2connexe. Le point B est un point d’articulation. La composante { A, B E, F, G, H } est 2 connexe. Le point B est doncpoint d’articulationcar il a comme Ègalement comme descendants C et D. b) EnÈtudiant les arÍtes non utilisÈes, dites ce qui caractÈrise lesdescendants { C, D}par rapport aux descendants { E, F, G }. En vous basant sur l’algorithme de parcours, dÈfinissez une fonction "point_articulation" qui explore le graphe et dÈterminer les points d’articulation d’un graphe. Elle reÁoit en paramËtre un graphe, un sommet du graphe, un compteur de parcours, un tableau de marquage des sommets et un tableau permettant de noter les sommets comme point d’articulation.
Lo42  final A2004  page1/2
UTBM
le 17 janvier 2005
fonction entier point_articulation (sommet s ; Graphe g ;Varentier compteur ;Varentier M[1..n],VarBoolÈen art[1..n] ;) ; VarDÈbut Fin c) Dessinezl’arborescence de parcours en profondeur du graphe avec point de dÈpart B. A n’est pas un point d’articulation, B en est un. Que pouvezvous dire de la structure des deux arborescences au niveau des racines ? Connaissant le numÈro de la racine et en analysant la numÈrotation des sommets ‡ l’exploration du premier successeur et des successeurs suivants, Ècrivez une fonction "point_articulation2", basÈe sur l’algorithme de la prÈcÈdente, pour donner la bonne information sur le sommet de dÈpart fonction entier point_articulation2 (sommet s ; Graphe g ; Var entier compteur ; Var entier M[1..n] ;  VarBoolÈen art[1..n] ;) ; VarDÈbut Fin d) Ecrivezun prÈdicat "biconnexe" qui reÁoit en paramËtre un graphe et retournant soit la valeur boolÈenne vrai si le graphe est 2connexe, soit la valeur faux. e) Ecrivezune fonction "point_articulation3" en modifiant l’algorithme de la fonction "point_articulation2" pour interrompre l’exploration dËs la dÈtection d’un point d’articulation.(question bonus)3) Ilest parfait Monceau ?(6) Un arbremonceauuds ‡ deux fils et dont toutes lesest un arbre binaire dont tous les ÈlÈments sont soit des feuilles soit des nœ Ètiquettes des fils d’un nœud ont des valeurs infÈrieures ‡ la valeur de l’Ètiquette du nœud. Utilisez l’implantation dispersÈe avec les types suivants : Type Ab= ^noeud ;  noeud= structure dÈbut  Telementinfo ;  Abg, d ;  Fin; a) Ecrivezune fonction permettant de contrÙler si un arbre binaire transmis en paramËtre est un arbre vÈrifiant la premiËre propriÈtÈ ÈnoncÈe cidessus. Chaque nœud doit Ítre visitÈ une seule fois. b) Modifiezvotre fonction pour vÈrifier que l’arbre est monceau ou non. Le parcours doit rester unitaire c) Quellessont les diffÈrences entre un arbre monceau et un tas ou tournois parfait ? Rappelez l’implÈmentation de la hauteur d’un arbre binaire. Utilisez cette fonction pour vÈrifier qu’un arbre est parfait. d) Imaginezune solution pour tester si un arbre est parfait en un seul parcours de chaque nœud.(question bonus)
Lo42  final A2004  page2/2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.