L3 – Algorithmique 1 (Année 2016/2017) Luc Pellissier & Pierre Pradic
TD 5 – Algorithmes gloutons & programmation dynamique
Exercice 1. Gloutonneries matroïdesques
Définition. Soit S un ensemble fini et I une famille de parties de S. Alors (S, I) est un matroïde si
— hérédité : pour tout X ∈ I , pour tout Y ⊂ X, Y ∈ I ;
— échange : ∀ X, Y ∈ I tels que | X | < |Y |, ∃ x ∈ Y \ X tel que X ∪ { x } ∈ I .
Les éléments de I sont appelés les indépendants du matroïde.
1. Montrer que si (S, I) est un matroïde et T une partie de S, alors si X et Y sont deux indépendants
de S inclus dans T et qu’ils sont maximaux pour l’inclusion dans T, alors | X | = |Y |.
Soit S un ensemble fini et I un ensemble de parties de S. Une fonction de coût pour S est une fonction
c : S → R+ . Elle est naturellement étendue à I en posant c( X ) = ∑ x∈X c( x ). On considère l’algorithme
suivant :
Algorithme : Glouton(S, I , c)
1 Ordonner les éléments de S = {s1 , . . . , sn } par coût décroissant
2 X←∅
3 pour i de 1 à n faire
4 si X ∪ {si } ∈ I alors
5 X ← X ∪ { si }
2. Montrer que si Glouton trouve un ensemble X ∈ I de coût maximal quelque soit la fonction de
coût c, alors (S, I) est un matroïde.
3. Soit (S, I) un matroïde. On considère une fonction de coût c ainsi qu’un ensemble de coût maxi-
mal Xopt ∈ I . On suppose que Glouton renvoie X avec c( X ) < c( Xopt ).
(a) Montrer qu’on peut supposer que | X | = | Xopt |.
(b) On note X = { x1 , . . . , x p } et Xopt = {y1 , . . . , y p }, rangés par coût décroissant. Montrer que
c ( x1 ) ≥ c ( y1 ).
(c) Soit i le plus petit indice tel que c( xi ) < c(yi ), et Y = {s ∈ S : c(s) ≥ c(yi )}. Montrer que
{ x1 , . . . , xi−1 } est un indépendant maximal pour l’inclusion dans Y.
(d) Conclure.
Exercice 2. Bibliothèque
La bibliothèque planifie son déménagement. Elle comprend une collection de n livres b1 , b2 , . . . , bn . Le
livre bi est de largeur wi et de hauteur hi . Les livres doivent être rangés dans l’ordre donné (par valeur
de i croissante) sur des étagères identiques de largeur L.
1. On suppose que tous les livres ont la même hauteur h = hi , 1 ≤ i ≤ n. Montrer que l’algorithme
glouton qui range les livres côte à côte tant que c’est possible minimise le nombre d’étagères
utilisées.
2. Maintenant les livres ont des hauteurs différentes, mais la hauteur entre les étagères peut se
régler. Le critère à minimiser est alors l’encombrement, défini comme la somme des hauteurs du
plus grand livre de chaque étagère utilisée.
(a) Donner un exemple où l’algorithme glouton précédent n’est pas optimal.
(b) Proposer un algorithme optimal pour résoudre le problème, et donner son coût.
1
3. On revient au cas où tous les livres ont la même hauteur h = hi , 1 ≤ i ≤ n. On veut désormais
ranger les n livres sur k étagères de même longueur L à minimiser, où k est un paramètre du
problème. Il s’agit donc de partitionner les n livres en k tranches, de telle sorte que la largeur de
la plus large des k tranches soit la plus petite possible.
(a) Proposer un algorithme pour résoudre le problème, et donner son coût en fonction de n et k.
(b) On suppose maintenant que la la taille d’un livre est en 2o(kn) . Trouver un algorithme plus
rapide que le précédent pour répondre à la même question.
Exercice 3. Plus grand et plus petit de n entiers
Dans cet exercice, on s’intéresse au calcul (simultané) du maximum et du minimum de n entiers. On
mesure la complexité dans le pire des cas et en nombre de comparaisons des algorithmes.
1. Donner un algorithme naïf et sa complexité.
Une idée pour améliorer l’algorithme est de regrouper par paires les éléments à comparer, de manière
à diminuer ensuite le nombre de comparaisons à effectuer.
2. Décrire un algorithme fonctionnant selon ce principe et analyser sa complexité.
Nous allons étudier l’optimalité d’un tel algorithme en fournissant une borne inférieure sur le nombre
de comparaisons à effectuer. Nous utiliserons la méthode de l’adversaire.
Soit A un algorithme qui trouve le maximum et le minimum. Pour une donnée fixée, au cours du
déroulement de l’algorithme, on appelle novice (N) un élément qui n’a jamais subi de comparaisons,
gagnant (G) un élément qui a été comparé au moins une fois et a toujours été supérieur aux éléments
auxquels il a été comparé, perdant (P) un élément qui a été comparé au moins une fois et a toujours été
inférieur aux éléments auxquels il a été comparé, et moyens (M) les autres. Le nombre de ces éléments
est représenté par un quadruplet d’entiers (i, j, k, l ) qui vérifie bien sûr i + j + k + l = n.
3. Donner la valeur de ce quadruplet au début et à la fin de l’algorithme. Exhiber une stratégie pour
l’adversaire, de sorte à maximiser la durée de l’exécution de l’algorithme. En déduire une borne
inférieure sur le nombre de tests à effectuer.
Exercice 4. Tris tas
Le tri par tas est réalisé en deux étapes : insertion des n éléments dans le tas, puis déconstruction du
tas en extrayant à chaque fois le plus petit élément.
La construction du tas se fait en O(n log n), et la suppression des éléments du tas se fait également en
O(n log n).
Il est possible d’améliorer la complexité de la construction du tas, elle peut se faire en O(n) (cependant
la suppression des n éléments du tas reste en O(n log n)). Proposez un algorithme pour construire le
tas en temps linéaire.