Examen deuxième session – 15 juin 2016

Durée 2h, documents autorisés

Algorithmes de tri

Tri à bulles

Le pseudocode de l’algorithme Tri à bulles se trouve ci-dessous. On suppose que le tableau \(T\) à trier est de longueur \(n\) et ses éléments sont \(T[0], T[1], \dots, T[n-1]\).

Tri-Bulles(T)
	pour i de n-1 à 1 // (pas -1)
		pour j de 0 à i - 1
			si T[j] > T[j+1]
				T[j] <-> T[j+1] // inverser T[j] et T[j+1]

: Montrer les étapes de l’execution de cet algorithme pour trier le tableau \([5, 8, 2, 7, 3]\).

: Combien de comparaisons effectue l’algorithme en fonction de la taille du tableau en entrée ? Déduire la complexité de ce tri dans le moyen et dans le pire des cas en fonction de \(n\).

: On peut remarquer que l’algorithme dans cette forme basique peut dans certains cas effectuer des opérations inutiles. En effet, si lors d’une étape de la boucle principale, aucun échange n’est effectué dans la boucle pour interne, c’est que le tableau est trié. Il est donc inutile de poursuivre la boucle pour externe.

Proposer une nouvelle version améliorée de l’algorithme prenant en compte cette remarque.

: Donner la complexité du meilleur cas de cette seconde version de l’algorithme en fonction de \(n\). Expliquer quel est le meilleur des cas (type de tableau) pour ce tri ?

Tri-rapide

Ci-dessous est donné le pseudo-code du tri rapide. Ici, \(T\) est le tableau à trier et \(p\) et \(q\) avec \((p ≤ q)\) représentent les indices du sous-tableau de \(T\) à trier à une certaine étape. Si \(n\) est la longueur du tableau \(T\) à trier, on commence la procédure en appelant Tri-rapide(T, 0, n-1).

Tri-rapide(T, p, r)
   si p < r
      q <- Partition(T, p, r)
      Tri-rapide(T, p, q-1)
      Tri-rapide(T, q + 1, r)

Partition(T, p, r)
   pivot <- T[r] 
   i <- p-1
   pour j de p à r - 1
      si T[j] <= pivot
         i <- i + 1
         T[i] <-> T[j]
   T[i+1] <-> T[r]
   renvoyer i + 1

: Trier la tableau \(T=[5,10,11,9,3,2,15,8,7]\) en utilisant le tri-rapide. Montrer toutes les étapes de l’exécution.

: Quelle est la complexité de l’algorithme dans le pire des cas ? Donner un exemple de tableau de longueur \(n=9\) pour lequel cette complexité est atteinte.

Arbres binaires de recherche

: 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 ?

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

: Dessiner des arbres binaires de recherche de hauteur 2, 3, 4, 5 et 6 pour le même ensemble de clés \(\{1,4,5,10,16,17,21\}\).

: On considère tous les nombres compris entre 1 et 1000. Donner deux ordres d’insertion de ces nombres dans un arbre binaire de recherche :

l’un qui va donner un arbre complètement déséquilibré, c’est-à-dire de hauteur maximale ;
l’autre qui va donner un arbre équilibré, c’est-à-dire le moins haut possible.

: 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 clés d’un arbre binaire. Décrire ensuite un algorithme qui calcule la moyenne de ces clés.

Programmation linéaire

On considère le programme linéaire suivant :

Minimiser \(-2x - 5y\)
Sous
\(\begin{array}{c r r r} x& + 3y& ≤& 12,\\ x& + 2y& ≤& 9,\\ 2x& - y& ≤& 8, \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

\[t=\sum_{x∈S'} x.\]

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

\[S = \{1, 2, 3, 5, 10, 12\}.\]

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

\[S = \{1, 3, 5, 10\}\]

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

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

\[\sum_{y<x} y < x.\]

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

\[S = \{2^i · r \bmod p \;|\; 0≤i<n\}.\]

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