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

Description

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 ...

Informations

• Publié par: shura
• Nombre de lectures: 166
• Langue: Français

Extrait

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. Var… DÈbut … Fin b) Ecrivezun 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) 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