Théorie de la programmation - TDA et structures de données 2004 Génie Informatique Université de Technologie de Belfort Montbéliard

Crenaud

Description

Examen du Supérieur Université de Technologie de Belfort Montbéliard. Sujet de Théorie de la programmation - TDA et structures de données 2004. Retrouvez le corrigé Théorie de la programmation - TDA et structures de données 2004 sur Bankexam.fr.

Sujets

• 2004

Informations

• Publié par: bankexam
• Publié le: 27 janvier 2008
• Nombre de lectures: 25
• 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

UTBM

le 17 janvier 2005

fonction entier point_articulation (sommet s ; Graphe g ;Varentier compteur ;Varentier M[1..n],VarBoolÈen art[1..n] ;…) ; Var… DÈ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] ;…) ; Var… DÈ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