UTBM fondements theoriques de l informatique 2006 gi

Description

Automne 2006Examen finalUtbm mt42Nb: Les deux exercices seront rediges sur des feuilles separees.RelationsExercice 11.1 Etude d'un cas particulierOn donne un ensemble E = {el, ..., e4}' Soit R4 la relation binaire interne sur E definie par:R4 = {(el, e2), (e3, e2), (el, e4), (e4, e3), (e2, e4)}'a) Fournir la matrice booleenne R4 associee a R4'b) Definir sous forme ensembliste les relations R~, Rl, Rj.c) On suppose ne pas disposer du theoreme Iiant composee de relations binaires et produit de leurs matricesbooleennes associees. On se propose de determiner R4 0 R4 par la seule definition des relations composees.On pose n = 4.• Proposer un algorithme recherche ((ei, ej» qui, a partir d'un couple (ei, ej) de E2 retourne 1 siet seulement si (ei, ej) E R4 0 R4, 0 sinon.• Exprimer en fonction de n la complexite de l'algorithme recherche 0• En deduire la complexite en fonction de n de la determination, par la seule definition des relationscomposees, de R4 0 R4.• Confronter ce resultat a celui issu du theoreme precite. Discuter brievement.1.2 Etude de chemins de longueur p (p E 1"1*)a) Soit Rune relation binaire quelconque sur E et R sa matrice booleenne associee.On donne la definition suivante:DefinitionSoit ei et ej deux elements quelconques de E.On dit qu'il existe un chemin (sous R) de longueur p de ei a ejssi il existe une suite (qO, ... qp) d'elements de E verifiant:qo=ei~qp=ej et 'v'rE{O, ... ,p-l} (q,.,qr+l)ER.a1) ExemplesFournir les chemins de ...

Informations

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

Extrait