Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

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

2 pages
‹‹G‹¨ff„‹UTBM le 24 juin 2008Final – LO42solution(durée 1h30)Les documents ne sont pas autorisés (La copie ou les idées du voisin non plus ). 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). L’élégance de la solution sera jugée.Sauf indication contraire, dans le cas d’algorithmes les réponses doivent être rédigées en pseudo code.1)En pleine largeur, mais pas trop, é talons nous . (5p)Le parcours ou descente en largeur dans un graphe consiste à avancer par « niveau », c’est à dire visite de tous les sommets distants de i arcs avant de visiter ceux distants de i+1 arcs.Nous pouvons décrire le parcours de la façon suivante :S { x } ; /* S correspond à l’ensemble des sommets rencontrés à visiter */Y ; /* Y est l’ensemble des sommets visités */Tantque S Faire /* tant qu’il y a des sommets à visiter */Marquer tous les sommets de S9Y Y S ;S (S) \ Y ;1Ftq7 85103 426Dans le graphe ci-dessus donner le parcours en largeur depuis le sommet 5.Soit un graphe G d'ordre n, écrivez un algorithme qui réalise une descente en largeur, à partir du sommet s, dans le graphe G implanté par file de successeurs (FS/APS).• On pourra, utiliser une file d'attente gérée comme suit :- un sommet s entre dans la file au moment où il est marqué- un sommet s sort de la file au moment où tous ses successeurs sont marqués.• Pour marquer les sommets, on utilisera ...
Voir plus Voir moins
UTBM
le 24 juin 2008
Final – LO42
solution
(durée 1h30)
Les documents ne sont pas autorisés (La copie ou les idées du voisin non plus ). 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). L’élégance de la solution sera jugée.
Sauf indication contraire, dans le cas d’algorithmes les réponses doivent être rédigées en pseudo code.
1) En pleine largeur, mais pas trop, étalons nous
.
(5p)
Le parcours ou descente en largeur dans un graphe consiste à avancer par « niveau », c’est à dire visite de tous les
sommets distants de i arcs avant de visiter ceux distants de i+1 arcs.
Nous pouvons décrire le parcours de la façon suivante :
S
{ x } ;
/* S correspond à l’ensemble des sommets rencontrés à visiter */
Y
← φ
;
/* Y est l’ensemble des sommets visités */
Tantque S
≠ φ
Faire
/* tant qu’il y a des sommets à visiter */
Marquer tous les sommets de S
Y
Y
S ;
S
← Γ
(S) \ Y ;
Ftq
Dans le graphe ci-dessus donner le parcours en largeur depuis le sommet 5.
Soit un graphe
G
d'ordre
n
, écrivez un algorithme qui réalise une descente en largeur, à partir du sommet
s
, dans le
graphe
G
implanté par file de successeurs (FS/APS).
On pourra, utiliser une file d'attente gérée comme suit :
-
un sommet s entre dans la file au moment où il est marqué
-
un sommet s sort de la file au moment où tous ses successeurs sont marqués.
Pour marquer les sommets, on utilisera un tableau de booléen MARQUE initialisé à faux.
2) De l’arbre, petite, l’image donnée doit être
(8p)
Pour représenter un arbre d’Huffman nous utilisons la méthode définie par Lukasiewizc. Dans cette représentation
une feuille est représentée par un 1. En présence d'un nœud, la représentation de l'arbre est 0 suivi de la
représentation du fils gauche et de celle du fils droit.
L(A)
= 1 si A est une feuille
= 0 L(fg(A)) L(fd(A)).
Ainsi l'arbre (a, ( (b, r), (c, d) ))) est représenté :
010011011|1|"a"|"b"|"r"|"c"|"d"
Le 1 avant les caractères est un marqueur de fin de codage
de l'arbre
a) Expliquez pourquoi cette représentation est suffisante pour restituer l'arbre.
b) Écrivez la fonction
estFeuille(AB A)
qui restitue un booléen vrai si l'arbre transmis est une feuille, faux sinon.
lo42 - final P2008 - page1/3
7
6
3
2
1
5
9
8
4
10
a
b
r
c
d
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin