Voici plusieurs méthodes algorithmiques très utilisés en informatique :
- Algorithmes gloutons
- Programmation dynamique
- Diviser pour régner
- ...
Dans ce TP, on s'intéresse aux algorithmes gloutons, qui s'utilisent souvent sur des problèmes d'optimisation (où on cherche à maximiser quelque chose avec des contraintes).
Un algorithme est glouton lorsqu'il effectue, à chaque étape, le choix qui semble le meilleur à ce moment-là et qui ne revient jamais sur sa décision.
La notion d'algorithme glouton est donc assez vague : nous allons l'illustrer avec quelques exemples.
Petits exercices de rappel¶
Cette partie est seulement pour les élèves en difficulté. Les autres peuvent la passer.
Exercice
Écrire une fonction pour calculer la somme des éléments d'une liste.
Solution
def somme(L):
s = 0
for i in L:
s += i
return s
Exercice
Écrire une fonction pour déterminer si une liste est triée dans l'ordre croissant.
Solution
def croissant(L):
for i in range(len(L)-1):
if L[i] > L[i+1]:
return False
return True
Rendu de monnaie¶
On suppose avoir des pièces de valeur $p_1$, ..., $p_n$ et on veut rendre la monnaie sur $c$ euros, avec le nombre minimum de pièces. Chaque pièce est disponible en quantité infinie.
Par exemple, si on a des pièces de valeur 1, 2, 4, alors on a plusieurs possibilités pour rendre $c = 6$€ : $4 + 2$, $4 + 1 + 1$, $2 + 2 + 2$... La meilleure solution est $4 + 2$, puisqu'elle utilise le nombre minimum de pièces.
On s'intéresse à l'algorithme glouton qui consiste à rendre utiliser la plus grande pièce à chaque fois.
Par exemple, pour rendre $9$€ avec des pièces de $1$, $2$ et $4$ :
- On rend une pièce de $4$€, il reste $5$€ à rendre.
- On rend une pièce de $4$€, il reste $1$€.
- On ne peut pas rendre $4$€ (qui est supérieur à $1$).
- On ne peut pas rendre $2$€ (qui est supérieur à $1$).
- On rend $1$€, il reste $0$€ et on a terminé (en utilisant $3$ pièces).
Exercice
Écrire une fonction rendre_monnaie(c, pieces) qui rend une liste des pièces obtenues avec l'algorithme glouton pour rendre la valeur $c$ avec des pièces dans la liste pieces.
Par exemple, rendre_monnaie(6, [1, 2, 4]) doit renvoyer [4, 2] et rendre_monnaie(5, [1, 3, 7]) doit renvoyer [3, 1, 1].
On pourra s'inspirer du code suivant :
def rendre_monnaie(c, pieces):
pieces.sort(key=lambda x: -x) # tri par ordre décroissant
rendu = [] # liste des pièces utilisées par l'algo. glouton
for ...: # parcours de la liste pieces
... # à compléter
return rendu
Solution
def rendre_monnaie(c, pieces):
pieces.sort(key=lambda x: -x)
rendu = []
for p in pieces:
while p <= c:
rendu.append(p)
c -= p
return rendu
rendre_monnaie(5, [1, 3, 7])
[3, 1, 1]
Exercice
Trouver un exemple simple dans lequel l'algorithme glouton n'est pas optimal.
Il faut donc trouver des valeurs de pièces $p_1$, ..., $p_n$ et de $c$ tel que le nombre de pièces utilisées par l'algorithme glouton n'est pas le minimum possible.
Solution
On considère des pièces $1, 3, 4$ et $c = 6$. Alors l'algorithme glouton va rendre $4 + 1 + 1$ alors que l'optimum est $4 + 2$.
Remarque : Un système de monnaie est dit canonique si cet algorithme glouton est optimal. La quasi-totalité des monnaies utilisées dans le monde sont canoniques.
Allocation de salles pour des cours¶
Dans ce problème, on doit construire un emploi du temps. Il faut assigner une salle à chaque cours de façon à ne pas avoir 2 cours qui se déroulent dans la même salle au même moment.
En Python, chaque cours sera un couple $(d, f)$ avec $d$ l'heure de début et $f$ de fin et une salle sera un entier. On rappelle que si c est un couple, on accède à son premier élément avec c[0] et aux deuxième avec c[1].
Exercice
Écrire une fonction intersecte pour déterminer si deux cours se chevauchent.
Par exemple, intersecte((1, 3), (2, 4)) doit renvoyer True mais intersecte((1, 2), (3, 5)) doit renvoyer False.
Solution
def intersecte(c1, c2):
return (c1[0] <= c2[0] and c1[1] >= c2[0]) or (c2[0] <= c1[0] and c2[1] >= c1[0])
assert intersecte((1, 3), (2, 4)) and not intersecte((1, 2), (3, 5))
Voici un exemple de cours (où il y a un cours de $9$h à $11$h, un cours de $12$h à $15$h...) :
Voici un exemple d'assignement :
Chaque couleur correspond à une salle : il y a donc $6$ salles en tout.
Exercice
Trouver une solution avec $4$ classes seulement (c'est l'optimum).
On s'intéresse à un algorithme glouton qui consiste à :
- Trier les cours par ordre de début croissant
- Pour chaque cours $c$ : utiliser pour $c$ une salle déjà existante si possible, et utiliser une nouvelle salle sinon.
Ainsi, sur l'exemple ci-dessus, on considère les cours dans l'ordre $2, 0, 4, 7, 5, 9, 6, 8, 3$ (si $2$ cours commencent en même temps, on les prends dans un ordre quelconque). On commence donc d'abord par le cours $2$, qu'on assigne à la salle $0$, puis on considère le cours $0$ qu'on assigne à la salle $1$ (car le cours $0$ intersecte le cours $1$ donc on ne peut pas les mettre dans la même salle)...
Remarque : On pourrait montrer que cet algorithme glouton renvoie l'optimum.
Exercice
Écrire une fonction intersecte_list telle que, si c est un cours et L est une liste de cours, intersecte_list(c, L) renvoie True si c chevauche un des cours de L.
Par exemple, intersecte_list((1, 3), [(2, 5), (4, 6)]) renvoie True mais intersecte_list((1, 3), [(4, 6), (5, 7)]) renvoie False.
Solution
def intersecte_list(c, L):
for cours in L:
if intersecte(c, cours):
return True
return False
assert intersecte_list((1, 3), [(2, 5), (4, 6)]) and not intersecte_list((1, 3), [(4, 6), (5, 7)])
Pour stocker les assignations de salle à chaque cours, on utilisera une liste salles telle que, si i est un numéro de salle, salles[i] est une liste contenant les cours qui se déroulent dans la salle i.
Par exemple, dans l'exemple de la figure ci-dessus, si 0 correspond à la salle jaune, salles[0] est égale à [(9, 11), (12, 15)].
Exercice
Écrire une fonction choisir_salle telle que, si c est un cours, choisir_salle(c, salles) renvoie une salle disponible pour c, ou -1 si aucune salle n'est disponible.
Par exemple, choisir_salle((7, 10), [[(9, 11)], [(12, 15)]]) doit renvoyer 1 mais choisir_salle((7, 10), [[(8, 10)], [(9, 12)]]) doit renvoyer -1.
Solution
def choisir_salle(c, salles):
for s in range(len(salles)):
if not intersecte_list(c, salles[s]):
return s
return -1
assert choisir_salle((7, 10), [[(9, 11)], [(12, 15)]]) == 1
assert choisir_salle((7, 10), [[(8, 10)], [(9, 12)]]) == -1
Exercice
Écrire une fonction allocation_salles(cours) qui renvoie une liste des salles utilisées par les cours de la liste cours en appliquant l'algorithme glouton.
On pourra compléter le code suivant :
def allocation_salles(cours):
cours.sort(key=lambda c: c[0]) # trie les cours par ordre de début croissant
salles = []
for c in cours: # parcours de la liste cours
for s in range(len(salles)): # teste si on peut mettre le cours c en salle s
if ... # si on peut mettre le cours c en salle s
salles[s].append(c) # on ajoute le cours c à la liste des cours de la salle s
break # on sort de la boucle for
return salles
File "<ipython-input-11-e933b66f0ca1>", line 6 if ... # si on peut mettre le cours c en salle s ^ SyntaxError: invalid syntax
Solution
def allocation_salles(cours):
cours.sort(key=lambda c: c[0]) # trie les cours par ordre de début croissant
salles = []
for c in cours: # parcours de la liste cours
s = choisir_salle(c, salles)
if s == -1:
salles.append([c])
else:
salles[s].append(c)
return salles
allocation_salles([(8, 11), (9, 10), (12, 14), (11, 15)])
[[(8, 11), (12, 14)], [(9, 10), (11, 15)]]
Sélection d'activités (Interval scheduling)¶
Dans ce problème, on considère un ensemble d'intervalles (des activités) et on veut en sélectionner le plus possible sans avoir aucune intersection entre les intervalles.
Par exemple, si on utilise les mêmes intervalles que pour l'exercice précédent, on peut choisir au plus $4$ intervalles de temps qui ne se chevauchent pas ($7, 5, 1, 3$ par exemple) :
On admet que l'algorithme glouton suivant est optimal :
- Trier les intervalles par ordre de fin croissante (sur l'exemple ci-dessus, on considère les intervalles dans l'ordre $7, 0, 5, 2, 4, 1, 9, 6, 3, 8$)
- On considère chaque itervalle dans cet ordre et on le sélectionne s'il n'intersecte pas les autres intervalles déjà choisis.
Remarque : À nouveau, on peut montrer que cet algorithme glouton est optimal.
Exercice
Écrire cet algorithme glouton en Python.