Examen deuxième session – 18 juin 2019

Durée 2h, documents autorisés

Arbres

: Dessiner l’arbre de recherche binaire résultant de l’insertion (dans l’ordre) des entiers suivants:

357, 160, 829, 232, 122, 855, 190, 23, 21, 462, 896, 87, 644, 481, 262, 166

: On suppose que des entiers compris entre 1 et 1000 sont disposés dans un arbre binaire de recherche et que l’on souhaite trouver le nombre 363. Parmi les séquences suivantes, lesquelles ne pourraient pas être la suite des nœuds parcourus ? Pourquoi ?

1. 2, 252, 401, 398, 330, 344, 397, 363.
2. 924, 220, 911, 244, 898, 258, 362, 363.
3. 925, 202, 911, 240, 912, 245, 363.
4. 2, 399, 387, 219, 266, 382, 381, 278, 363.
5. 935, 278, 347, 621, 299, 392, 358, 363.

: Proposition: soit $k$ une feuille d’un arbre binaire de recherche, soit $K$ l’ensemble des nœuds sur le chemin de la racine à $k$, soit $L$ l’ensemble des nœuds à gauche de $K$ et soit $R$ l’ensemble des nœuds à droite de $K$. Soient $a∈L, b∈K, c∈R$, alors $a ≤ b ≤ c$.

Cette proposition est fausse. Le montrer par un contre-exemple.

: Donner le nombre minimal ainsi que le nombre maximal de nœuds d’un arbre binaire de hauteur $h$. Justifier votre réponse.

: Décrire un algorithme qui calcule la somme de toutes les feuilles d’un arbre binaire. Décrire ensuite un algorithme qui calcule la moyenne de ces feuilles.

Programmation dynamique

On se donne une liste de nombres $a, b, c, \dots$ et l’opération binaire $∘$ définie par $a∘b = (a+b)/2$. On cherche le parenthésage de $a∘b∘c∘\cdots$ qui donne la valeur minimale.

Par exemple, pour la liste $4, 10, 3$, le parenthésages possibles sont $(4∘10)∘3=5$ et $4∘(10∘3)=5.25$, le premier étant donc le parenthésage de valeur minimale.

: Trouver le parenthésage minimal pour la liste $5,-3,1,8$. L’opération $∘$ est-elle associative?

: Combien de parenthésages sont possibles pour une liste de $n$ nombres?

: Prouver que la fonction $a↦a∘b$ est monotone pour tout $b$ fixé.

: Proposer un algorithme pour calculer le parenthésage minimal d’une liste. Quelle est sa complexité?

: L’algorithme précédent peut-il être optimisé par programmation dynamique? Quel est le gain en complexité?

Programmation linéaire

On considère le programme linéaire suivant :

Minimiser $-3x - 2y$
Sous
$\begin{array}{c r r r} x& + 3y& ≤& 6,\\ -3x& + 4y& ≤& 8,\\ 3x& - 2y& ≤& 7, \end{array}$

$x,y≥0$.

: Mettre le programme linéaire sous forme relaxée en ajoutant des variables de relaxation.

: Trouver la solution du programme linéaire en détaillant les étapes de l’algorithme du simplexe.

Sacs à dos

Dans cette partie on s’intéresse au problème du sac à dos (plus précisement au problème de la somme de sous-ensembles). On rappelle que le problème du sac à dos calculatoire consiste, étant donné un ensemble $S$ d’entiers positifs et un entier $t≥0$, à trouver, s’il existe, un sous-ensemble $S'⊂S$ tel que

Les exercices qui suivent étudient en particulier les sacs à dos super-croissants, qui sont à la base du cryptosystème historique de Merkle-Hellman.

: Soit l’ensemble

Trouver une solution du sac à dos pour $t=16$.

On présente ci-dessous l’algorithme glouton pour le sac à dos:

Glouton(S, t)
	si t < x pour tout x ∈ S
		ERREUR: solution non trouvée
	sinon
		x ← max(x ∈ S tel que x ≤ t)
		renvoyer [x]::Glouton(S \ x, t - x)

où S \ x indique l’ensemble S privé de x, [x, y, z] indique une liste, et A::B indique une concatenation de listes.

: Donner un exemple de sac à dos pour lequel l’algorithme glouton échoue à trouver une solution, bien qu’il en existe une.

: Vérifier que pour l’ensemble

l’algorithme glouton trouve toujours une solution, si elle existe.

: On appelle un ensemble $S$ super-croissant si pour tout $x∈S$ on a

Prouver que l’algorithme glouton trouve toujours une solution, si elle existe, aux sacs à dos super-croissants.

: Soit $n>0$, soit $p>2^n$ un nombre premier, soit $1<r<p$, et soit $S$ l’ensemble

Donner un algorithme glouton capable de résoudre toute instance de sac à dos $(S,t)$.