Examen

Algorithmique – ENSIN3U1, janvier 2014
Luminy, St-Charles, Montperrin, Semestre 1, session 1. Dur´ee 2 heures. Examen de L2info, L2math.
Documents autoris´es : polycopi´e de cours et notes manuscrites. Pas de calculatrices ni de livres.
L’´
enon¸c´
e continue au verso.
Dans tout ce qui suit vous utiliserez les notations O(f (n)) et Θ(f (n)) pour d´ecrire le comportement
asymptotique d’un algorithme (sa complexit´e).
Arbres binaires de recherche (7 points).
Question 1. Construire l’arbre binaire de recherche correspondant aux insertions des valeurs 6, 27, 33,
7, 20, 19, 23, 21, 22 et 11 dans cet ordre, partant d’un arbre vide.
On veut maintenant construire des arbres binaires de recherche ”´equilibr´es”. Le crit`ere d’´equilibre est la
taille des sous-arbres : un arbre est ´equilibr´e si, pour tout noeud de l’arbre, la taille de son fils gauche est
´egale `a la taille de son fils droit `
a un noeud pr`es (la taille d’un arbre est son nombre de noeuds, feuilles
comprises).
Question 2. Dessinez un arbre binaire de recherche ´equilibr´e qui contient les valeurs 6, 7, 11, 19, 20,
21, 22, 23, 27, 33 (il y a plusieurs solutions).
Question 3. Ecrivez en C la fonction ConstruitArbreEquilibre(int T[], int g, int d) qui
construit et renvoie un arbre binaire de recherche ´equilibr´e contenant les valeurs T[g], T[g+1],..., T[d].
On suppose que les valeurs dans le tableau T sont d´efinies pour les indices compris entre g et d, et sont
ordonn´ees dans l’ordre croissant.
Vous pourrez utiliser le type ARBRE tel qu’il a ´et´e d´efini en cours, et la fonction creerNoeud(int x,
ARBRE fg, ARBRE fd) qui alloue et initialise un noeud, et renvoie son adresse.
Question 4. Quelle est la complexit´e de la fonction ConstruitArbreEquilibre (la taille des donn´ees
est ici le nombre de valeurs stock´ees dans le tableau T entre les indices g et d) ?
Question 5. D´emontrez qu’un arbre ´equilibr´e de taille 2k+1 − 1 est de hauteur k (ici la hauteur est le
nombre d’´etages de l’arbre, et donc un arbre r´eduit `a un seul noeud est de hauteur nulle).
Indication : faites une preuve par r´ecurrence.
Programmation dynamique (8 points).
Etant donn´ee une suite de valeurs enti`eres distinctes strictement positives S = (v1 , . . . , vn ), on cherche
une sous-s´equence croissante de S qui soit la plus longue possible. Avec la suite (2, 4, 9, 3, 7, 5, 12, 3), la
longueur d’une plus longue sous-s´equence croissante est 4 (par exemple (2, 3, 5, 12) ou (2, 4, 7, 12)).
Vous allez traiter ce probl`eme par une approche de type programmation dynamique, avec une table T
a` une dimension : T (i) repr´esente la longueur de la plus longue sous-s´equence croissante de la suite
(v1 , . . . , vi ) dont la derni`ere valeur est vi (i.e. une telle sous-s´equence est de la forme (vi1 , vi2 , . . . , vik )
avec i1 < i2 < . . . < ik = i et vi1 ≤ vi2 ≤ . . . ≤ vik = vi ).
Question 1. Dessinez la table T correspondant `a la suite (2, 4, 9, 3, 7, 5, 12, 3).
Question 2. Que vaut T (i) lorsque pour tout j ∈ {1, 2, . . . , i − 1}, vj > vi .
Question 3. Donnez (en l’expliquant) l’´equation r´ecursive qui d´efinit la valeur T (i) en fonction des
valeurs T (1), . . . T (i − 1).
Question 4. Ecrivez en C la fonction qui calcule la table T ´etant donn´e un tableau S de n valeurs
repr´esentant la suite. La fonction renverra la longueur de la plus longue sous-s´equence croissante.
Question 5. Quelle est la complexit´e de votre algorithme ?
Question 6. Quelle information faut-il m´emoriser, pour tout indice i, pour pouvoir reconstruire rapidement une plus longue sous s´equence croissante ?
Plus court chemin dans un graphe (5 points).
Un graphe orient´e pond´er´e G est donn´e par la matrice d’incidence suivante, o`
u les sommets du graphe
sont num´erot´es de 1 `
a 6 et o`
u il existe un arc du sommet s1 vers le sommet s2 si et seulement si la case
situ´ee `a l’intersection de la ligne s1 et de la colonne s2 contient un entier, ´egal `a la distance de s1 `
a s2 .
1
2
3
4
5
6
1
2
5
6
1
3
10
4
1
8
7
2
5
2
6
20
1
8
Question 1. Dessinez le graphe G.
Question 2. Calculez, au moyen de l’algorithme de Dijsktra, les distances des plus courts chemins allant
du sommet 1 `
a tous les autres sommets du graphe. Donnez toutes les ´etapes de l’algorithme.
Question 3. Quel est le plus court chemin permettant d’aller du sommet 1 au sommet 6 ?

Download Report