En première

• Exemple d'introduction
• La méthode glouton
• Exemple: le rendu de monnaie
• Exercice

Télécharger le fichier maison.

Le problème : nous souhaitons placer des antennes sur les maisons d’un quartier. Une antenne peut émettre suffisamment loin pour couvrir plusieurs maisons. L’objectif est de placer le moins d’antennes possible tout en couvrant toutes les maisons.

• 1) Utiliser le programme Python fourni pour couvrir 10 maisons avec un rayon d’émission de 150. Cliquez sur les ronds pour placer les antennes. Vous pouvez cliquer sur démarrer pour générer une nouvelle carte de maisons.
• 2) Toujours avec 10 maisons, cliquer sur Solution G et comparer avec votre solution. Faites plusieurs tests.
• 3) Toujours avec 10 maisons, cliquer sur Solution Brute et comparer avec votre solution et la solution G. Faites plusieurs tests. Si vous obtenez toujours la même réponse, téléchargez l'image suivante.
• 4) Proposer une méthode logique pour placer les antennes. (à faire par 3)
• 5) Former deux équipes pour partager la classe en groupes d’environ 12 élèves. L’objectif sera de coder à 12 ! Pour cela, désignez un chef de projet qui sera capable de guider les groupes. Attention il ne devra pas coder du tout. Partagez ensuite le travail après avoir découpé la solution G en différentes fonctions à coder. Avant de commencer à coder faites une feuille de route contenant les noms des fonctions, de leur paramètres et l’algorithme du programme principal.
• 6) Deux élèves, autres que le chef de projet, feront une restitution vidéo projetée.
• 7) Reprendre le programme fourni et augmenter les maisons progressivement à partir de 11, en testant la réponse G et la réponse brute. Que constatez-vous ?

La méthode glouton est une méthode de recherche de solution locale qui va apporter une solution globale non nécessairement optimale. Le problème se ramène à chaque étape à un problème plus simple et chaque étape selectionne l'une des meilleures possibilités et ne remet jamais en cause les choix précédents.

Parmis les exemples classiques, le rendu de monnaie: on veut rendre la monnaie de façon optimale cad avec le moins de pièces possible.

Quelle est la stratégie la plus simple à adopter? Aller au plus pressé: rendre la plus grande pièce possible. Par exemple, en euros, si je dois rendre 195 ct, je rends en premier 1€ (100ct), puis 50 ct puis 20ct puis 20ct puis 5ct. Cette stratégie fonctionne avec les euros. Pouvez vous fabriquer un jeu de pieces pour lequel la stratégie glouton n'est pas optimale. Dans cet exercice, si la méthode glouton aboutit, elle est optimal puisqu'elle utilise les pièces les plus grandes en premier mais dans certains cas, la méthode Glouton ne trouve pas de solution alors qu'il en existe une. Pour d'autres problèmes (voir les maisons plus haut), la méthode n'est pas optimale car elle donne bien une solution mais pas la meilleure.

def rendu_glouton(pieces,montant):
    reponse=[]
    i=len(pieces)-1
    while i>=0 and montant>0 :
        if montant<pieces[i]:
            i=i-1
        else:
            montant=montant-pieces[i]
            reponse.append(pieces[i])
    if i<0: #on n'est pas arrivé à 0!
        reponse=[]
    return(reponse)

Voici un autre programme pour faire la même chose. Ce type de code est au programme de terminale. Que remarquez vous de particulier dans ce dernier?

def rendu_glouton_r(pieces,montant,solution):
    if montant==0:
        return(0,solution)
    for i in range(len(pieces)-1,-1,-1):
        if pieces[i]<=montant:
            solution.append(pieces[i])
            montant,solution=rendu_glouton_r(pieces,montant-pieces[i],solution)

    return(montant,solution)

Construire un planning. Plusieurs enseignants veulent présenter leur spécialité aux élèves entre 8h et 16h(pas de pause). Ils ne disponsent que d'une salle, doivent être un par salle. Les enseignants donnent aux élèves de NSI le créneaux qu'ils souhaitent sous la forme {"Pelegrina":[8,9.5]}, ce qui signifie de 8h à 9h30. Chaque enseignant fait de même et ne peux modifier son créneau. Votre but est de faire en sorte qu'il y ait le plus de présentations possibles.

1. Avec les données suivantes, quelle est la meilleure solution?
   {"prof1":[10,13],"prof2":[8,9],"prof3":[9.5,12]"prof4":[9.5,13]"prof5":[12,16]}
2. Avec les données suivantes, quelle est la meilleure solution?
   {"prof1":[8,13],"prof2":[10,11],"prof3":[11,13]"prof4":[13,15]"prof5":[13,16]}
3. On propose la méthode suivante: classer par heure de fin croissante, puis prendre le premier cours de cette liste, puis le premier cours possible suivant, etc. En quoi cette méthode est une méthode glouton? Il se trouve que dans ce cas, cette méthode est optimale! Bonne nouvelle...pas besoin d'une brute de force.