MP2I — 2022-2023 Pierre Le Scornet Module Algorithmique

TP 15 : Algorithmes gloutons
On s’intéresse dans ce TP à un dernier problème d’ordonnancement, qui ressemble au problème “je suis en retard” du
TD 5. Je vous propose aussi deux autres problèmes gloutons à la fin.

I. Ordonnancement avec échéance (SchedulingDeadline)

On considère un entier 𝑛 ≥ 2 et un ensemble de 𝑛 tâches 𝑇 = {𝑡0 , … , 𝑡𝑛−1 }. Dans la suite, on indexera toujours les
tâches par J0, 𝑛 − 1K. Chaque tâche 𝑡𝑖 prend une unité de temps (par exemple exactement une seconde) pour être traitée
sur une unité de calcul.
Chaque tâche 𝑡 dispose d’une échéance 𝑓(𝑡) ∈ J0, 𝑛 − 1K (appelée deadline en anglais), à laquelle la tâche 𝑡 doit avoir
été traitée, sans quoi on doit payer une certaine pénalité 𝑝(𝑡) ∈ ℕ.
On appelle stratégie d’ordonnancement une fonction 𝑑 ∶ 𝑇 → J0, 𝑛 − 1K qui associe à chaque tâche 𝑡 ∈ 𝑇 un unique
temps de début 𝑑(𝑡). Évidemment, deux tâches différentes 𝑡𝑖 et 𝑡𝑗 doivent avoir un temps de début différent 𝑑(𝑡𝑖 ) ≠ 𝑑(𝑡𝑗 ).
Selon cette stratégie 𝑑, on en déduit une séparation de l’ensemble des tâches 𝑇 en deux ensembles disjoints 𝑇 = 𝑇 + (𝑑)⊔
𝑇 − (𝑑) :
— 𝑇 + (𝑑) est l’ensemble des tâches 𝑡 traitées dans les délais : 𝑡 ∈ 𝑇 + (𝑑) ssi 𝑑(𝑡) < 𝑓(𝑡) (𝑡 est commencée au temps
𝑑(𝑡) donc finit en 𝑑(𝑡) + 1 qui doit être inférieure à sa deadline 𝑓(𝑡)),
— 𝑇 − (𝑑) est l’ensemble complémentaire, autrement dit l’ensemble des tâches 𝑡 traitées en retard : 𝑡 ∈ 𝑇 − (𝑑) ssi 𝑑(𝑡) ≥
𝑓(𝑡) (finie en retard, après sa deadline).
On note alors 𝑃(𝑑) = ∑𝑡∈𝑇 −(𝑑) 𝑝(𝑡) ∈ ℕ la somme des pénalités des tâches en retard.

Exercice 1 – Exemple

On donne cet ensemble de tâches 𝑡𝑖 , avec leur deadline 𝑓(𝑡𝑖 ) et leur pénalité 𝑝(𝑡𝑖 ).

𝑡6 1
𝑡5 7
𝑡4 5
𝑡𝑖 0 1 2 3 4 5 6 𝑡3 2
𝑓(𝑡𝑖 ) 1 2 3 4 4 4 6 𝑡2 4
𝑝(𝑡𝑖 ) 3 6 4 2 5 7 1
𝑡1 6
𝑡0 3

0 1 2 3 4 5 6 7

Une stratégie d’ordonnancement est donnée dans le tableau suivant :

𝑡𝑖 0 1 2 3 4 5 6
𝑑(𝑡𝑖 ) 6 0 1 4 3 2 5

▶ Question 1 À quoi correspondent les tâches pour lesquelles 𝑑(𝑡𝑖 ) est noté en gras, dans ce tableau ?
▶ Question 2 Calculer la pénalité totale 𝑃(𝑑) pour cette stratégie d’ordonnancement 𝑑.

1
MP2I — 2022-2023 Pierre Le Scornet Module Algorithmique

Exercice 2 – Problème d’optimisation

Étant donné un ensemble de tâches 𝑇, et la donnée des deadlines 𝑓(𝑡𝑖 ) et des pénalités 𝑝(𝑡𝑖 ), on cherche à
trouver une stratégie d’ordonnancement 𝑑, de valeur 𝑃(𝑑) minimale.
▶ Question 1 Donner un exemple d’instance du problème telle que l’on puisse trouver une solution 𝑑 qui
ait une pénalité nulle.
▶ Question 2 A contrario, donner un autre exemple d’instance telle que l’on ne puisse pas trouver de solu-
tion 𝑑 avec une pénalité nulle. Quelle sera sa pénalité minimale ?
Ces deux autres exemples pourront être utiles pour tester l’implémentation, par la suite.

Exercice 3 – Résolution par force brute

Dans cette section on étudie la faisabilité d’une approche naïve d’exploration exhaustive.
▶ Question 1 Calculer le nombre de solutions 𝑑 ∶ 𝑇 → J0, 𝑛 − 1K possibles, sachant que cette application
doit ordonnancer chaque tâche sur un temps de début unique (et que |𝑇| = 𝑛).
▶ Question 2 En déduire une borne inférieure sur la complexité temporelle dans le pire cas de l’algorithme
de recherche exhaustive suivant :
— On examine chaque ordonnancement possible 𝑑, pour lequel on calcule sa valeur 𝑃(𝑑), et on garde
celui qui a la pénalité totale minimale.
— On renvoie ce dernier à la fin.

Exercice 4 – Un algorithme glouton

On peut commencer par remarquer un point intéressant : l’ordonnancement des tâches en retard (celles de
𝑇 − (𝑑)) n’a aucune importance, et on peut donc se contenter de déterminer une stratégie d’ordonnancement
𝑑 pour les tâches traitées dans les délais (celles de 𝑇 + (𝑑)) et la compléter par n’importe quel ordonnancement
des autres tâches. Autrement dit : quitte à être en retard, on s’en fiche d’à quel point.
On peut ainsi reformuler le problème : il faut déterminer un sous-ensemble de tâches 𝑇 + ⊆ 𝑇 pouvant être
traitées dans les délais, tel que ∑ 𝑝(𝑡) soit maximale. Alors, on aura bien 𝑃(𝑑) minimale.
𝑡∈𝑇 +
On va résoudre maintenant ce problème de maximisation des pénalités de 𝑇 + par l’algorithme glouton que
voici :
— On commence en posant 𝑇 + = ∅ et tous les temps de l’ensemble J0, 𝑛 − 1K sont marqués comme étant
disponibles,
— On parcourt ensuite les 𝑛 tâches, dans un certain ordre (à préciser par la suite) :
∘ Quand on considère la tâche 𝑡, s’il existe un temps 𝑖 disponible, tel que 𝑖 < 𝑓(𝑡), alors on
marque comme indisponible le plus grand de ces temps possibles : 𝑖0 = max{𝑖 ∈ J0, 𝑛 − 1K, 𝑖 <
𝑓(𝑡) et 𝑖 disponible}, et on rajoute alors la tâche 𝑡 à l’ensemble 𝑇 + , en la commençant au temps 𝑖0
(i.e., 𝑑(𝑡) ∶= 𝑖0 ),
— À la fin, on place les tâches restantes aux temps disponibles (elles sont dans 𝑇 − = 𝑇 ⧵ 𝑇 + et donc leur
ordonnancement relatif n’a pas d’importance).
On peut en envisager plusieurs manières de trier ler tâches. Celui que nous choisirons ici sera par ordre
décroissant des pénalités 𝑝(𝑡). En effet, il semble logique d’essayer de placer en premier dans 𝑇 + les tâches
ayant les plus fortes pénalités, car le problème a été réécrit comme cherchant à maximiser la somme des
pénalités ∑ 𝑝(𝑡).
𝑡∈𝑇 +
▶ Question 1 Au brouillon, exécuter l’algorithme glouton précédent, avec cet ordre initial des tâches, pour
l’exemple de la figure de la page précédente.

2
MP2I — 2022-2023 Pierre Le Scornet Module Algorithmique

Exercice 5 – Implémentation (en C)

Pour représenter une instance du problème, on se propose de définir une structure, appelée tache, qui
contient les champs suivants :
— unsigned int id : un identifiant de la tâche 𝑡, qui pourra par exemple être son numéro 1, … , 𝑛 comme
dans l’exemple étudié plus haut,
— unsigned int date_limite : la échéance (deadline) 𝑓(𝑡) ∈ ℕ,
— unsigned int penalite : la pénalité 𝑝(𝑡) ∈ ℕ,
— int debut qui sera son temps de début 𝑑(𝑡), initialement placé à -1 tant que la tâche n’est pas ordon-
nancée, puis modifié (une seule fois) quand on a trouvé le temps 𝑖0 à laquelle l’ordonnancer (ou un
autre temps dans le deuxième cas de l’algorithme glouton, pour les tâches qui ne seront pas dans 𝑇 + ).
▶ Question 1 Définir en cette structure en C. On pourra ensuite écrire typedef struct tache tache; pour
utiliser le type tache et plutôt que struct tache dans le code.
▶ Question 2 Écrire une fonction de prototype tache creer_tache(unsigned int id, unsigned int
date_limite, unsigned int penalite) qui crée un objet local (sur la pile et pas sur le tas, donc pas be-
soin de malloc) avec ces champs, et le renvoie. a
▶ Question 3 Dans la fonction main, créer les tâches de l’exemple ci-dessus, c’est-à-dire les tache0 à tache6.

▶ Question 4 Que fait la ligne suivante, à compléter et recopier dans votre programme ?

1 tache taches[7] = {tache0, ... , tache6}; C

a. On rappelle qu’il est possible de faire un return e; avec e un élément d’un type défini par struct, sans avoir besoin de passer
par des pointeurs vers des structures.

Exercice 6 – Représentation des temps disponibles et indisponibles

Pour représenter la disponibilité des temps J0, 𝑛−1K, on propose utiliser un tableau de booléens indisponible.
Les temps seront tous initialement marqués à false (c’est-à-dire qu’il ne sont pas indisponible et donc dispo-
nibles).

Tri des tâches

On dispose en C, dans la librairie standard, de la fonction qsort (qui contrairement à ce que son nom laisse
penser, n’est pas obligatoirement implémentée avec un tri rapide — quick sort en anglais). Elle s’utilise de la
manière suivante :

1 // Tri des activités par ordre décroissant des pénalités C

2 qsort(taches, nb_taches, sizeof(tache), compare_taches);

Cet appel trie par ordre croissant le tableau taches, qui contient nb_taches objets, tous de taille
sizeof(tache) en mémoire, et qui sont comparables grâce à une fonction de comparaison compare_tache
que l’on doit avoir implémenté au préalable.
La fonction compare_tache a le même rôle que la fonction de comparaison compare : 'a -> 'a -> int
en OCaml. Elle renvoie 0 si t1 == t2, un nombre strictement négatif (par exemple −1) si t1 < t2 (selon le
critère choisi), et un nombre strictement positif (par exemple +1) sinon. Son prototype doit être :

1 int compare_taches(const void* t1, const void* t2) C

Pour pouvoir utiliser la fonction qsort sur tout type d’objets, le type des paramètres t1 et t2 est void* (vous
pouvez ignorer le qualificatif const qui indique que l’on s’engage à ne pas modifier t1 et t2 pendant la procé-
dure de comparaison). Il sera donc nécessaire, dans la fonction compare_tache de transtyper (cast en anglais)

3
MP2I — 2022-2023 Pierre Le Scornet Module Algorithmique

les arguments t1 et t2 :

1 int compare_taches(const void* t1, const void* t2) { C

2 tache* tache1 = (tache*)t1;
3 tache* tache2 = (tache*)t2;
4 // On peut maintenant utiliser `tache1` et `tache2` qui sont de type `tache*`
5 ...
6 }

▶ Question 1 Implémenter cette fonction de comparaison pour pouvoir ensuite trier les tâches par ordre de
pénalité décroissante.

Algorithme glouton
On cherche maintenant à implémenter l’algorithme glouton à l’aide d’une fonction de prototype :

1 void* ordonnancement(tache* tab_taches, int nb_taches) C

— Cette fonction n’aura rien à renvoyer : quand elle décide d’ordonnancer la tâche 𝑡 au temps 𝑑(𝑡), elle
le fait en modifiant son champ debut.
— A la fin, toutes les tâches doivent avoir reçu une valeur unique et différente de J0, 𝑛 − 1K dans leur
champ debut.
— Attention à bien libérer la mémoire allouée sur le tas pendant l’algorithme (par exemple le tableau
indisponible de 𝑛 booléens).
▶ Question 2 Implémenter cette fonction.

▶ Question 3 Afficher le résultat trouvé sous la forme suivante : Tid (f:deadline, p:penalite) @ debut.
Pour l’exemple ci-dessus, on obtiendrait :

T6 (f:4, p:7) @ 3 Shell

T2 (f:2, p:6) @ 1
T5 (f:4, p:5) @ 2
T3 (f:3, p:4) @ 0
T1 (f:1, p:3) @ 4
T4 (f:4, p:2) @ 6
T7 (f:6, p:1) @ 5

▶ Question 4 Écrire une fonction de prototype unsigned int penalite_totale(tache* tab_taches,

int nb_taches) qui calcule la pénalité totale des tâches en retard. Afficher, dans la fonction main la pénalité
totale trouvée par l’algorithme glouton.
▶ Question 5 Tester cette fonction sur le tableau de tâches de l’exemple précédent, avant et après l’appel à
ordonnancement. On devrait trouver le résultat suivant :

Avant résolution, pénalité totale = 28. Shell

Après résolution, pénalité totale = 5.

▶ Question 6 Afficher la pénalité totale, à chaque étape de la boucle principale de l’algorithme glouton,
pour la voir diminuer au fur et à mesure. Par exemple, on pourra obtenir :

4
MP2I — 2022-2023 Pierre Le Scornet Module Algorithmique

La tâche T0 est placée en d = 3, et la pénalité totale = 21. Shell

La tâche T1 est placée en d = 1, et la pénalité totale = 15.
La tâche T2 est placée en d = 2, et la pénalité totale = 10.
La tâche T3 est placée en d = 0, et la pénalité totale = 6.
La tâche T6 est placée en d = 5, et la pénalité totale = 5.

▶ Question 7 Tester l’algorithme avec d’autres instances du problème.

▶ Question 8 Quelle est la complexité temporelle totale de l’algorithme glouton, en supposant que l’appel
à qsort sur un tableau de taille n correspondant à nb_taches tâches se fait en temps 𝛩(𝑛 log(𝑛)) ?

Exercice 7 – Preuve d’optimalité

Démontrons que cet algorithme glouton renvoie effectivement un ensemble 𝑇 + optimal.

Propriété 1

Avec le critère de tri par pénalités décroissantes, l’algorithme glouton renvoie un ordonnancement
optimal.

Première étape : Tout d’abord, on montre qu’il existe une solution optimale compatible avec le premier
choix de l’algorithme glouton.
▶ Question 1 Soit 𝑇 un ensemble de tâches, et 𝑡 ∈ 𝑇 une des tâches de pénalité maximale. Montrer qu’il
existe un ensemble 𝑇 + de tâches pouvant être traitées dans les délais, maximal pour la somme de ses pénalités
et tel que 𝑡 ∈ 𝑇 + .

Deuxième étape : On montre ensuite qu’en enlevant le choix glouton, on obtient une solution optimale
du sous-problème. Soit 𝑇 + ⊆ 𝑇 un ensemble de tâches pouvant être traitées, maximal pour la somme des
pénalités, et contenant une tâche 𝑡 ∈ 𝑇 + de pénalité maximale. Soit 𝑖 l’instant auquel commence cette tâche
𝑡 dans un ordonnancement de 𝑇 + . On pose 𝑇 ′ = 𝑇 ⧵ {𝑡}, avec des dates limites modifiées : ∀𝑡′ ∈ 𝑇 ′ , 𝑑𝑇 ′ (𝑡′ ) =
𝑑𝑇 (𝑡′ ) si 𝑑𝑇 (𝑡′ ) ≤ 𝑖, ou 𝑑𝑇 ′ (𝑡′ ) = 𝑑𝑇 (𝑡′ ) − 1 sinon.
▶ Question 2 Montrer que 𝑇 + ⧵ {𝑡} est maximal pour 𝑇 ′ .

▶ Question 3 Conclure.

II. Deux autres problèmes

Exercice 8 – Le bibliothécaire optimisant

Un ou une bibliothécaire souhaite ranger des collections de livres classées par auteur sur une longue étagère.
On considère ainsi une suite (𝑎1 , … , 𝑎𝑛 ) de collections, données par la taille 𝑎𝑖 de la collection 𝑖 sur l’étagère,
par exemple, en nombre de pages ou en centimètres.
Un rangement des livres consiste à ordonner les collections, de la première à la dernière, sur l’étagère. Plus
formellement, il s’agit d’une permutation 𝜎 ∈ 𝔖𝑛 , où 𝜎(𝑖) donne le numéro de la collection numéro 𝑖 dans
l’étagère.
Pour trouver l’auteur d’un livre, comme on ne les trie pas par ordre alphabétique, il est nécessaire de parcourir
linéairement l’étagère en partant de la première collection. Le coût d’accès à la 𝑘-ième collection est donc
𝑘
cout(𝑘) = ∑ 𝑎𝜍(𝑖) .
𝑖=1

5
MP2I — 2022-2023 Pierre Le Scornet Module Algorithmique

𝑛
1
Le coût moyen d’accès aux 𝑛 collections est alors donné par ∑ cout(𝑘).
𝑛 𝑘=1
▶ Question 1 Déterminer un algorithme glouton, permettant d’obtenir un rangement de coût minimal et
déterminer sa complexité.
▶ Question 2 Démontrer la validité de votre approche, c’est-à-dire que votre algorithme (glouton) renvoie
bien une solution optimale.

Exercice 9 – Un genre de « Le compte et bon » (simplifié)

On considère le processus suivant : on part de l’entier 1, et à chaque étape on peut soit doubler la valeur de
l’entier courant, soit lui ajouter 1. L’objectif est d’atteindre un entier cible donné 𝑛 ∈ ℕ∗ .
▶ Question 1 Montrer qu’il est toujours possible d’atteindre n’importe quel entier cible 𝑛 ∈ ℕ∗ .

Par exemple, on peut atteindre 10 en quatre étapes, ainsi :

+1 ×2 +1 ×2
1 −−→ 2 −−→ 4 −−→ 5 −−→ 10
▶ Question 2 Mettre au point un algorithme glouton permettant d’obtenir le nombre minimal d’étapes
nécessaires pour atteindre un entier 𝑛. Analyser sa complexité et surtout, démontrer la validité de votre ap-
proche, c’est-à-dire que cet algorithme renvoie bien le nombre minimal d’étapes nécessaires.