Le gymnase☘

Ces exercices doivent être utilisés pour vous entraîner à programmer. Ils sont généralement accompagnés d'aide et de leur solution pour vous permettre de progresser.

Avant de vous précipiter sur ces solutions dès la première difficulté, n'oubliez pas les conseils suivants :

Avez-vous bien fait un schéma au brouillon pour visualiser le problème posé ?
Avez-vous essayé de rédiger un algorithme en français, avec vos propres mots, avant de vous lancer dans la programmation sur machine ?
Avez-vous utilisé des affichages intermédiaires, des print(), pour visualiser au fur et à mesure le contenu des variables ?
Avez-vous testé le programme avec les propositions de tests donnés dans l'exercice ?
Avez-vous testé le programme avec de nouveaux tests, différents de ceux proposés ?

Rappels

Chaque programme Python doit être sauvegardé sous forme de fichier texte avec l'extension .py.
Enregistrez ce fichier dans le dossier [G05_Algo_Gloutons] avec le nom donné à l'exercice : ProgG05.61.py, ProgG05.62.py, etc...
Pour exécuter ce programme, il suffit de le sauvegarder puis d'appuyer sur la touche [F5].

Le programme principal doit contenir un appel au module doctest :

##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

Les exercices de cette page sont issus d'une situation commune.

ProgG05.61 - Problème d'organisation☘

Dans un gymnase doivent se dérouler une série d’épreuves dans une journée de 24h. Pour chaque épreuve, l’heure de début $d_i$ et la durée sont imposées (et donc l’heure de fin $f_i$ est connue).

Le problème qui se pose au propriétaire du gymnase est le suivant : il n'y a qu'une salle, il est donc impossible que deux intervalles $[d_i~;~f_i]$ se chevauchent. Comme chaque épreuve rapporte de l'argent (les épreuves qui ne pourront pas se dérouler dans ce gymnase rapporteront de l'argent... à un autre !), le propriétaire aimerait que le plus grand nombre possible d'épreuves aient lieu dans son gymnase.

L'organisateur doit donc organiser dans la même journée des épreuves pour lesquelles les intervalles [début; fin] ne se chevauchent pas, et il doit en organiser le plus grand nombre possible.

Contraintes☘

Chaque épreuve à une heure de début et une heure de fin. Ces heures sont entières.
Deux épreuves ne peuvent pas se chevaucher.
Un maximum d'épreuves doivent pouvoir être organisées.

Représentation des données☘

Une épreuve sera représentée par un couple d'entiers (d, f), où d représente l'heure de début et f représente l'heure de fin (entre 0 et 23 pour l'heure de début, entre 1 et 24 pour l'heure de fin). Évidemment, on doit avoir f>d.

Par exemple, le couple (6, 10) représente une épreuve qui commence à 6 heures et se termine à 10 heures.

Générer une liste d'épreuves☘

Tout d'abord, complétez la définition de la fonction epreuves() qui doit générer au hasard une liste d'épreuves (c'est-à-dire un tableau de couples).

from random import randint

def epreuves(n):
    """
    n - int, entier positif.
    Sortie: list - tableau de n couples d'entiers aléatoires
            [(d1, f1), (d2, f2), ..., (dn, fn)]
            où di est entier entre 0 et 23
            où fi est entier entre 1 et 24
            avec di < fi pour tout i.
    """

Exemple d'appel

>>> epreuves(5)
[(5, 17), (1, 21), (9, 16), (8, 23), (12, 18)]

Un code possible

def epreuves(n):
    """
    n - int, entier positif.
    Sortie: list - tableau de n couples d'entiers aléatoires
            [(d1, f1), (d2, f2), ..., (dn, fn)]
            où di est entier entre 0 et 23
            où fi est entier entre 1 et 24
            avec di < fi pour tout i.
    """
    resultat = []
    for i in range(n):
        d = randint(0,23)
        f = randint(d+1, 24)
        resultat.append((d,f))
    return resultat

Afin de mieux visualiser le « positionnement » de chaque épreuve au cours de la journée, vous pourrez par la suite utiliser la fonction suivante :

def affichage_epreuves(tab_epreuves):
    """
    tab_epreuves - list, Tableau de n couples d'entiers [(d1, f1), (d2, f2), ..., (dn, fn)]

    Sortie: None - Fonction d'affichage des epreuves sous la forme
            de chaînes de caractères les unes en dessous des autres
            de façon à visualiser leur "positionnement".
    """
    for couple in tab_epreuves:
        for i in range(couple[0]):
            print(' ', end='')
        for i in range(couple[0],couple[1]+1):
            print('X', end='')
        print()
    print()

Exemple d'appel

>>> tab = epreuves(5)
>>> tab
[(1, 22), (23, 24), (11, 23), (17, 23), (2, 5)]

>>> affichage_epreuves(tab)
 XXXXXXXXXXXXXXXXXXXXXX
                       XX
           XXXXXXXXXXXXX
                 XXXXXXX
  XXXX

ProgG05.62 - Identifier les intervalles compatibles☘

Pour chacun des couples d'épreuves suivants, indiquez si celles-ci sont compatibles ou pas.
- (1, 3) et (2, 4) ;
- (1, 3) et (4, 5) ;
- (3, 5) et (1, 3).
Une réponse
- les épreuves (1, 3) et (2, 4) ne sont pas compatibles : la seconde épreuve commence avant la fin de la première.
- les épreuves (1, 3) et (4, 5) sont compatibles : la seconde épreuve commence après la fin de la première.
- les épreuves (3, 5) et (1, 3) ne sont pas compatibles : la première épreuve commence au moment de la fin de la seconde.

Complétez la définition de la fonction compatibles() :

def compatibles(intervalle1, intervalle2):
    """
    intervalle1 - couple d'entiers (d1, f1) avec 0 <= d1 < f1 <= 24, 
    intervalle2 - couple  d'entiers (d2, f2) avec 0 <= d2 < f2 <= 24

    Sortie: bool - True si l'intersection entre [d1; f1] et [d2; f2] est vide,
            False sinon.
    """

Exemple de tests

>>> compatibles((1, 3), (2, 4))
False

>>> compatibles((1, 3), (4, 5))
True

>>> compatibles((3, 5), (1, 3))
False

Un code possible

def compatibles(intervalle1, intervalle2):
    """
    intervalle1 - couple d'entiers (d1, f1) avec 0 <= d1 < f1 <= 24, 
    intervalle2 - couple  d'entiers (d2, f2) avec 0 <= d2 < f2 <= 24

    Sortie: bool - True si l'intersection entre [d1; f1] et [d2; f2] est vide,
            False sinon.
    """
    (d1, f1) = intervalle1
    (d2, f2) = intervalle2 
    return d1 > f2 or d2 > f1

ProgG05.63 - Différentes stratégies possibles☘

Revenons à notre propriétaire de gymnase. Il aimerait pouvoir caser le plus grand nombre d'épreuves de la liste qu'on lui fournit. Pour cela, il procède de la façon suivante (algorithme glouton) :

il trie les épreuves selon une règle de choix (une stratégie) à définir ;
il sélectionne la première épreuve de la liste ainsi triée et élimine ensuite toutes celles qui ne lui sont pas compatibles ;
il sélectionne ensuite la première épreuve parmi celles qui restent puis élimine celles qui ne lui sont pas compatibles ;
et ainsi de suite jusqu'à épuisement de la liste...

Rappels sur les tris

En Python, la méthode .sort() permet de trier un tableau suivant un critère donné.

Par exemple, on dispose d'un tableau de triplets correspondant à des notes d'élèves : L = [(2, 5, 17), (16, 12, 13), (12, 8, 19), (7, 9, 12)]. On veut trier ce tableau dans l'ordre croissant des moyennes.

On peut procéder comme suit :

def critere_moyenne(triplet):
    return sum(triplet)/3

tab = [(2, 5, 17), (16, 12, 13), (12, 8, 19), (7, 9, 12)]
tab.sort(key=critere_moyenne)

print(tab)

Résultat :

[(2, 5, 17), (7, 9, 12), (12, 8, 19), (16, 12, 13)]

Pour trier par ordre décroissant des moyennes, il suffirait d'utiliser :

tab.sort(key=moyenne, reverse=True)

Stratégie n°1 - Tri des épreuves par ordre croissant des heures de début☘

Dans un premier temps, notre propriétaire de gymnase fait le raisonnement suivant : « Je vais trier les épreuves dans l'ordre croissant des heures de début, car ainsi je commence les épreuves le plus tôt possible et je gaspille donc le moins de temps possible »

On dispose d'une liste d'épreuves sous la forme d'un tableau de couples (debut, fin).
Définir la (ou les) fonctions nécessaires pour obtenir le tri nécessaire à la stratégie n°1. Cette fonction de tri sera nommée tri_debut()

Exemple de tests

>>> tab = [(10, 21), (15, 21), (23, 24), (13, 15), (15, 18)]
>>> affichage_epreuves(tab)
          XXXXXXXXXXXX
               XXXXXXX
                       XX
             XXX
               XXXX
>>> tri_debut(tab)
>>> affichage_epreuves(tab)
          XXXXXXXXXXXX
             XXX
               XXXXXXX
               XXXX
                       XX

Un code possible

def critere_debut(couple):
    return couple[0]


def tri_debut(tab):
    """
    tab - list, tableau de n couples d'entiers [(d1, f1), (d2, f2), ..., (dn, fn)]
    Sortie: None - tri en place le tableau par ordre croissant
            des premiers éléments de chaque couple
    """
    return tab.sort(key=critere_debut)

Le raisonnement du propriétaire est-il justifié ? En d'autres termes, en triant les épreuves par ordre croissant des heures de début puis en appliquant la sélection gloutonne correspondante, obtient-on une organisation avec le plus grand nombre d'épreuves possibles ?

Une réponse
La réponse est non.

Cette façon de procéder ne mène pas nécessairement au maximum d'épreuves comme le montre l'exemple ci-dessous :

L'algorithme glouton sélectionne, avec ce tri, une seule épreuve, la plus longue, alors que le choix des 4 épreuves courtes était possible.

Stratégie n°2 - Tri des épreuves par ordre croissant des durées☘

Notre propriétaire fait maintenant le raisonnement suivant : « Je vais trier les épreuves suivant l'ordre croissant des durées. En effet, en sélectionnant en premier lieu l'épreuve la plus courte, je laisse ainsi un maximum de temps disponible pour le reste des épreuves et je pourrai donc en caser un plus grand nombre ».

On dispose d'une liste d'épreuves sous la forme d'un tableau de couples (debut, fin).
Définir la (ou les) fonctions nécessaires pour obtenir le tri nécessaire à la stratégie n°2. Cette fonction de tri sera nommée tri_duree()

Exemple de tests

>>> tab = [(22, 23), (6, 8), (21, 23), (3, 17), (9, 20)]
>>> affichage_epreuves(tab)
                      XX
      XXX
                     XXX
   XXXXXXXXXXXXXXX
         XXXXXXXXXXXX

>>> tri_duree(tab)
>>> affichage_epreuves(tab)
                      XX
      XXX
                     XXX
         XXXXXXXXXXXX
   XXXXXXXXXXXXXXX

Un code possible

def critere_duree(couple):
    return couple[1]-couple[0]


def tri_duree(tab):
    """
    tab - list, tableau de n couples d'entiers [(d1, f1), (d2, f2), ..., (dn, fn)]
    Sortie: None - tri en place le tableau par ordre croissant
            des amplitudes de chaque couple
    """
    return tab.sort(key=critere_duree)

Ce raisonnement est-il valable, c'est-à-dire conduit-il toujours à une solution optimale ?

Une réponse
La réponse est à nouveau non.

Cette façon de procéder ne mène pas nécessairement au maximum d'épreuves comme le montre l'exemple ci-dessous :

L'algorithme glouton sélectionne, avec ce tri, une seule épreuve, la plus courte alors que le choix des deux épreuves longues était possible.

Stratégie n°3 - Ordre croissant des heures de fin☘

Notre propriétaire fait maintenant le raisonnement suivant : « Je vais trier les épreuves suivant l'ordre croissant des heures de fin. En sélectionnant en premier lieu l'épreuve se terminant au plus tôt, je laisse après cette épreuve un maximum de temps, je pourrai donc caser un plus grand nombre d'épreuves ».

Important

Dans tout ce qui suit, l'expression « l'algorithme » désignera l'algorithme glouton programmé avec cette stratégie de tri, c'est-à-dire par ordre croissant des heures de fin.

On dispose d'une liste d'épreuves sous la forme d'un tableau de couples (debut, fin).
Définir la (ou les) fonctions nécessaires pour obtenir le tri nécessaire à la stratégie n°2. Cette fonction de tri sera nommée tri_fin()

Exemple de tests

>>> tab = [(14, 22), (21, 23), (2, 15), (4, 24), (16, 17)]
>>> affichage_epreuves(tab)
              XXXXXXXXX
                     XXX
  XXXXXXXXXXXXXX
    XXXXXXXXXXXXXXXXXXXXX
                XX

>>> tri_fin(tab)
>>> affichage_epreuves(tab)
  XXXXXXXXXXXXXX
                XX
              XXXXXXXXX
                     XXX
    XXXXXXXXXXXXXXXXXXXXX

Un code possible

def critere_fin(couple):
    return couple[1]


def tri_fin(tab):
    """
    tab - list, tableau de n couples d'entiers [(d1, f1), (d2, f2), ..., (dn, fn)]
    Sortie: None - tri en place le tableau par ordre croissant
            des derniers éléments de chaque couple
    """
    return tab.sort(key=critere_fin)

Copiez, collez et complétez la définition de la fonction selectionne qui implémente l'algorithme avec ce critère de tri.

def selectionne(tab):
    """
    tab - list, tableau de n couples d'entiers [(d1, f1), (d2, f2), ..., (dn, fn)]
    Sortie: list - Sélection des épreuves par l'algorithme glouton
            sous la forme d'un tableau de couples
    """

Exemple de tests

>>> tab = [(1, 8), (21, 24), (9, 16), (20, 23), (15, 17)]
>>> tri_fin(tab)
>>> affichage_epreuves(tab)
  XXXXXXXX
         XXXXXXXX
               XXX
                    XXXX
                     XXXX
>>> selection = selectionne(tab)
>>> affichage_epreuves(selection)
 XXXXXXXX
         XXXXXXXX
                    XXXX

Un code possible

def selectionne(tab):
    """
    tab - list, tableau de n couples d'entiers [(d1, f1), (d2, f2), ..., (dn, fn)]
    Sortie: list - Sélection des épreuves par l'algorithme glouton
            sous la forme d'un tableau de couples
    """
    # On trie la liste des épreuves
    tri_fin(tab)

    # Initialisation des variables
    nb_epreuves = len(tab)
    resultat = []

    # les épreuves étant triées par ordre croissant des heures de fin, 
    # on sélectionne la première épreuve :
    indice = 0
    epreuve_selectionnee = tab[indice]
    resultat.append(epreuve_selectionnee) 

    # tant qu'il reste des épreuves non selectionnées ou non éliminées,
    # on recherche la prochaine épreuve compatible 
    # avec celle qui vient d'être ajoutée,
    # et on l'ajoute à la liste des sélectionnées.
    while indice < nb_epreuves:  
        if compatibles(tab[indice], epreuve_selectionnee):  
            epreuve_selectionnee = tab[indice]
            resultat.append(epreuve_selectionnee)

        indice += 1

    return resultat

Cet algorithme semble-t-il valable?

Une réponse
L'algorithme donne effectivement des plannings optimaux. Reste à le prouver !
C'est l'objectif de la prochaine partie.

Exercice G05.64 - Preuve de critère optimal (optionnel)☘

Définitions

Dans la suite, on appellera planning toute sélection d'épreuves (sélectionnées dans la liste initiale) compatibles entre elles.

On appellera planning optimal un planning comportant le plus grand nombre d'épreuves possible.

On appellera planning glouton un planning obtenu par l'algorithme glouton utilisant la stratégie n°3 (tri par heure de fin).

On considère un planning optimal $\mathcal{O}$ constitué des intervalles d'épreuves $o_1, o_2, \dots, o_m$ .

Les heures de fin sont toutes distinctes (sinon il y aurait incompatibilité). Quitte à réordonner, on peut donc supposer que $\text{fin}(o_1) < \text{fin}(o_2) < \dots < \text{fin}(o_m)$ .

Justifiez que l'on a $\text{début}(o_1) < \text{fin}(o_1) < \text{début}(o_2) < \text{fin}(o_2) < \dots < \text{début}(o_m) < \text{fin}(o_m).$

Une justification
L'intervalle $o_2$ étant compatible avec l'intervalle $o_1$ , il ne peut que commencer après la fin de $o_1$ : $\text{fin}(o_1) < \text{début}(o_2)$ .

De même, la fin de $o_3$ se trouvant après la fin de $o_2$ et $o_3$ étant compatible avec $o_2$ , le début de $o_3$ est nécessairement après la fin de $o_2$ : $\text{fin}(o_2) < \text{début}(o_3)$ .

Etc...
A côté de notre planning optimal $\mathcal{O}$ constitué des intervalles d'épreuves $o_1, o_2, \dots, o_m$ , on considère également un planning glouton $\mathcal{G}$ constitué des intervalles d'épreuves $g_1, g_2, g_3, ..., g_p$ .
Pourquoi peut-on affirmer que $p \leqslant m$ ?

Une justification
Le planning $\mathcal{O}$ a été choisi optimal, c'est-à-dire avec le plus grand nombre d'épreuves possible. On a ainsi forcément $p \leqslant m$ .

Dans la suite de cette partie, l'objectif sera d'établir l'égalité $p = m$ .
S'il y a au moins une épreuve dans la liste initiale, l'algorithme glouton sélectionnera au moins une épreuve.
Justifiez que l'on a $\text{fin}(g_1) \leqslant \text{fin}(o_1)$ .

Une justification
L'algorithme choisit une épreuve se terminant au plus tôt, on a donc nécessairement $\text{fin}(g_1) \leqslant \text{fin}(o_1)$ .
On suppose que le planning optimal $\mathcal{O}$ comporte au moins deux épreuves.
Justifiez que, dans ce cas, l'algorithme construit un planning glouton comportant au moins deux épreuves et que $\text{fin}(g_2) \leqslant \text{fin}(o_2)$ .

Une justification
Nous savons déjà que $\text{fin}(g_1) \leqslant \text{fin}(o_1)$ (question 3.).
En utilisant le résultat de la question 1., nous avons donc : $\text{fin}(g_1) \leqslant \text{fin}(o_1) < \text{debut}(o_2) < \text{fin}(o_2)$ .

Après avoir sélectionné $g_1$ , l'algorithme glouton passe à une phase de suppression des épreuves non compatibles avec $g_1$ . Cette étape laisse au moins une épreuve dans la liste : l'épreuve $o_2$ . L'étape suivante de l'algorithme sélectionnera donc une seconde épreuve, et cette seconde épreuve se termine au plus tôt parmi les épreuves restantes, donc plus tôt (au sens large) que $o_2$ .
On en déduit l'inégalité $\text{fin}(g_2) \leqslant \text{fin}(o_2)$ .
Supposons que le planning optimal $\mathcal{O}$ comporte au moins trois épreuves.
Justifiez que dans ce cas, l'algorithme construit un planning glouton comportant au moins trois épreuves et que $\text{fin}(g_3) \leqslant \text{fin}(o_3)$ .

Une justification
Nous savons déjà qu'il y a au moins deux épreuves dans $\mathcal{G}$ et que $\text{fin}(g_2) \leqslant \text{fin}(o_2)$ .
En utilisant le résultat de la question 1., nous avons donc : $\text{fin}(g_2) \leqslant \text{fin}(o_2) < \text{debut}(o_3) < \text{fin}(o_3)$ .

Après avoir sélectionné $g_2$ , l'algorithme passe à une phase de suppression des épreuves non compatibles avec $g_2$ . Cette étape laisse au moins une épreuve dans la liste : l'épreuve $o_3$ . L'étape suivante de l'algorithme sélectionnera donc une troisième épreuve, et cette troisième épreuve se termine au plus tôt parmi les épreuves restantes, donc plus tôt (au sens large) que $o_3$ .
On en déduit l'inégalité $\text{fin}(g_3) \leqslant \text{fin}(o_3)$ .

Conclusion

En poursuivant ainsi le raisonnement, on constate que l'algorithme construit un planning glouton comportant autant d'épreuves qu'un planning optimal.

Exercice G05.65 - Heures de début☘

Proposez une stratégie avec les heures de début qui mène à un planning optimal.

Une réponse

On choisit un tri décroissant par heure de début.
Par « symétrie » par rapport au tri croissant des heures de fin (on « renverse » le temps), notre principe glouton mènera à un planning optimal.