Aller au contenu

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).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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 :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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

  1. 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.
  2. Complétez la définition de la fonction compatibles() :

    1
    2
    3
    4
    5
    6
    7
    8
    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
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    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 :

1
2
3
4
5
6
7
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 »

  1. 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
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    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)
    
  2. 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 : des épreuves

    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 ».

  1. 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
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    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)
    
  2. 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 : des épreuves

    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.

  1. 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)
    
  2. Copiez, collez et complétez la définition de la fonction selectionne qui implémente l'algorithme avec ce critère de tri.

    1
    2
    3
    4
    5
    6
    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
    
  3. 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).

  1. 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...

  2. 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.

  3. 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).

  4. 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).

  5. 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.