-
Cours :
- Listes, dictionnaires et lecture de fichiers
(lundi matin) - Bonnes pratiques pour les projets
(lundi après-midi)- cours 2
transparents : pdf, html - planche de TD/TP 2 (pdf)
- cours 2
- Spécification et tests
(mardi matin) - Correction partielle
(mardi après-midi)- cours 4
transparents : pdf, html - planche de TD/TP 4 (pdf)
- cours 4
- Correction de tri, et complexité en mode débranché
(mercredi matin)- transparents : pdf
- planche de TD/TP 5 (pdf)
- Comparaison des complexités des tris
(mercredi après-midi) - Complexité d'algorithmes
(jeudi matin)- transparents : pdf
- planche de TD/TP 7 (pdf)
- Recherche d'un élément majoritaire dans un tableau
(jeudi après-midi) - Algorithmes gloutons
(vendredi matin)- cours 9
transparents : pdf, html - planche de TD/TP 9 (pdf)
- cours 9
- Algorithme des k plus proches voisins
(vendredi après-midi)- cours 10
transparents : pdf, html - planche de TD/TP 10 (pdf)
- cours 10
Algorithmes gloutons
Rendu de monnaie
On considère le problème du rendu de monnaie: on cherche à faire une certaine somme (exprimée centimes, mettons) avec le moins de pièces possibles. Les valeurs de pièces sont imposées mais on n’a pas de limite sur le nombre de pièces disponibles. L’algorithme glouton consiste à prendre à chaque étape la pièce ayant la plus grosse valeur qui ne dépasse pas la somme restant à obtenir.
Montrer qu’avec les pièces usuelles de valeurs \(1\), \(2\), \(5\), \(10\), \(20\) et \(50\), l’algorithme glouton donne une solution optimale.
Indication: considérer le nombre maximum de pièces de chaque catégorie dans une solution optimale.
Trouver un ensemble de valeurs pour lesquelles l’algorithme glouton ne donne pas toujours de solution optimale.
Montrer que l’algorithme glouton donne toujours une solution optimale dans le cas où les valeurs des pièces sont les puissances successives d’une même valeur: \(1,p,p^2,\ldots,p^k\) pour \(p \geq 2\) et \(k \geq 1\) fixés.
Un problème d’ordonnancement de tâches
On considère un ensemble \(E=\{1,2,\ldots,n\}\) de tâches unitaires, c’est-à-dire que chaque tâche s’effectue en une unité de temps. Chaque tâche \(i\) a une date d’échéance \(d_i\) et une pénalité \(v_i>0\) qui doit être payée si la tâche est effectuée après la date \(d_i\). On cherche un ordonnancement des tâches, c’est-à-dire une permutation de \(E\), qui minimise le cumul des pénalités pour non respect des échéances.
On définit qu’un ensemble de tâches \(F \subseteq E\) est indépendant s’il existe un ordonnancement des tâches de \(F\) tel qu’aucune ne soit en retard sur sa date d’échéance.
Montrer que le calcul d’un ordonnancement optimal équivaut à trouver un ensemble indépendant de tâches de \(E\) dont la somme des pénalités soit le plus grand possible.
Soit \(i\) une tâche de pénalité maximale. Existe-t-il un ensemble indépendant optimal qui contient \(i\)?
En déduire un algorithme glouton qui fournit une solution optimale.