Algorithmes

I- Recherche par dichotomie

Cliquez sur Fiche dichotomie.pdf pour récupérer l'énoncé du TD.
1) Akinator
Vous jouez à essayer de deviner le nombre auquel pense votre adversaire : en début de partie, celui-ci pense à un nombre entre 0 et 100, le note sur une feuille qu’il retourne (pour éviter la triche). Vous devez trouver ce nombre en un minimum de propositions. L’adversaire ne peut dire que "c’est plus", "c’est moins" et "bravo".
  1. Essayez de décrire votre stratégie.
  2. En justifiant votre réponse, indiquez quel serait le nombre minimum de questions à poser afin de trouver le résultat de façon sûre et certaine.
  3. Écrire une fonction akinator(n) qui va chercher à deviner le nombre x auquel vous pensez (0 ≤ x ≤ n) en utilisant la même stratégie que vous.

Affiche corrigé

Cacher corrigé

  1. La meilleure méthode est de diviser systématiquement l'intervalle en deux et de prendre le milieu.
    Si par exemple le nombre à trouver est 37, commencer par demander 50 ("c'est moins"), puis 25 ("c'est plus"), puis 37 ("Bravo !").
  2. On se rend compte qu'on a une démarche binaire : comme il est possible de coder 128 nombres sur 7 bits, il est possible de deviner n'importe quel nombre en 7 questions.
  3. def akinator(n):
      mini=0
      maxi=n
      while (maxi-mini)>1 :
        milieu=(maxi+mini)//2
        print("Est-ce qu’il s’agit de :",milieu,"?")
        reponse=input("Répondre par \"+\" ou \"-\" ou \"oui\"")
        if reponse=="+":
           mini=milieu
    
        elif reponse=="-":
           maxi=milieu
        else:
           return True
    
2) Encadrer la solution d'une équation de type f(x)=0
Application : La fonction f(x)=x3-1,45x2-11,55x+5,39 admet une solution s telle que f(s)=0 avec 0 ≤ s ≤ 1
On donne
def f(x):return x**3-1.45*x**2-11.55*x+5.39
→ Proposer une adaptation de l’algorithme akinator pour trouver une valeur de s arrondie à 10-3 près.

Affiche corrigé

Cacher corrigé

def f(x):return x**3-1.45*x**2-11.55*x+5.39

def resolv(fonction,mini,maxi,intervalle):

  while (maxi-mini)>intervalle :
    milieu=(maxi+mini)/2


    if fonction(maxi)*fonction(milieu)>0:
       maxi=milieu

    elif fonction(maxi)*fonction(milieu)<0:
       mini=milieu
    else:
       return milieu

  return mini,maxi
La partie la plus compliquée de l'algorithme est mathématique : comment écrire un équivalent de "c'est plus" ou "c'est moins" ?
Il se trouve que si la fonction est strictement monotone et qu'elle admet une solution dans un intervalle, alors les 2 extrêmités de cet intervalle n'ont pas le même signe => f(mini)×f(maxi)<0.
On teste donc f(maxi)×f(milieu). Si la valeur est positive, c'est que la solution se trouve entre mini et milieu et donc que notre nouvel intervalle est [mini;milieu].
3) Rechercher une valeur dans une liste ordonnée par dichotomie
Une liste de nombres est générée par la commande
liste=[randint(0,10)]
for i in range(1,100000) :
  liste.append(liste[i-1]+randint(1,10))
On souhaite rechercher si un nombre est présent dans cette liste le plus rapidement possible.
  1. D’après ce code, la liste est-elle déjà ordonnée ? Si oui, en ordre croissant ou décroissant ?
  2. Est-il possible que la liste contienne deux fois le même nombre ?
  3. Écrire une fonction recherche_dicho(nombre,liste) qui recherche par dichotomie le nombre dans liste et retourne si elle le trouve son indice et si elle ne le trouve pas les 2 indices encadrant la position qu’il aurait dû avoir
  4. Utiliser le benchmark de la séance algorithmes01 pour vérifier si cette méthode est réellement plus rapide que l’algorithme indice(liste,valeur) écrit précédemment.
    Attention : votre fonction bench génère par défaut une liste aléatoire, ce qui n’est pas le cas de la liste ci-dessus, modifiez la fonction en conséquence !

Affiche corrigé

Cacher corrigé

  1. On voit que chaque terme est égal au terme précédent augmenté de randint(1,10). Cette liste est donc ordonnée en ordre strictement croissant.
  2. répondu juste au-dessus
  3. A vous de chercher !
  4. A vous de chercher !

II- Algorithmes gloutons

Cliquez sur Fiche algo glouton pour récupérer l'énoncé du TD.
1) Introduction
Il y a certains problèmes problèmes pour lesquels il existent un très grand nombre de solutions. Parmi ces solutions quelques unes sont optimales, mais l'écrasante majorité ne le sont pas. Il n'est dans certains cas pas possible de trouver une solution optimale car cela demanderait un nombre de calculs hors de portée ou trop coûteux par rapport aux moyens à disposition.
Dans ce cas, il peut être intéressant de disposer d'un algorithme qui, s'il ne donne pas la solution optimale, est tout du moins capable de trouver une solution, de préférence pas trop mauvaise.
Ce genre d'approche, on l'a déjà abordée au moins une fois : pour faire sortir le robot du labyrinthe : en gardant toujours le mur à droite, on s'assure de pouvoir sortir, mais on ne trouvera généralement pas le trajet le plus court vers la sortie.
Les algorithmes gloutons répondent à cette problématique. En choissant systématiquement l'option qui les rapproche le plus de l'objectif, ils permettent de trouver une solution qui si elle n'est pas systématiquement optimale est généralement satisfaisante.
2) Problème du rendu de monnaie
photo d'une caisse automatique
Vous êtes employé par l’entreprise CashExpress, spécialisée dans la vente de caisses enregistreuses automatiques : pour éviter les contacts entre les employés et la clientèle, le client dépose directement l’argent dans un automate qui se charge de lui rendre la monnaie.
On suppose que la monnaie peut-être rendue avec toutes les pièces et billets existant en euros :
[200, 100, 50, 20, 10, 5, 2, 1, 0.5, 0.2, 0.1, 0.05, 0.01]
(En effet, les billets de 500€ ne sont plus produits depuis 2018)
  • a. Un client vous présente un billet de 50€ pour payer sa chocolatine a 0,85€, indiquez le détail du rendu de monnaie que vous allez faire.
  • Un algorithme évident afin de rendre systématiquement correctement la monnaie, serait de rendre uniquement des pièces de 1 cent.
    Cela présente 2 inconvénients majeurs :
    • il est nécessaire de prévoir un très gros volume de pièce de 1 cent afin de pouvoir continuer à rendre la monnaie tout au long de la journée
    • Vous risquez d’irriter vos clients
  • b. Proposez une stratégie vous permettant systématiquement de rendre la monnaie en utilisant un nombre minimal de pièces/billets.
  • c. Écrire la fonction rendu_monnaie(montant) qui retourne un dictionnaire contenant le détail du rendu de monnaie pour un montant donné.
    Exemple : Le client a payé sa baguette à 1,05€ avec un billet de 5€ → l’automate doit lui rendre 3,95€
    rendu_monnaie(3,95) → 	{'200':0, '100':0, '50':0, '20':0, '10':0, '5':0, '2':1, '1':1, '0.5':1, '0.2':2, '0.1':0, '0.05':1, '0.01':0}
    En effet, le rendu optimal est 2€ + 1€ + 50ct + 2x20ct + 5ct
  • Une boulangerie basée en Absurdistan souhaite se procurer une de vos machine. Leur monnaie est le Plouk, dont le taux de change est proche de l’Euro : 1 Pk = 1 €.
    Leur monnaie est différemment échelonnée : [200, 100, 30, 20, 5, 2, 1, 0.3, 0.1, 0.05, 0.01]
  • d. En adaptant la fonction rendu_monnaie(montant) aux différentes valeurs disponibles dans ce pays, quel retour propose-t-elle pour 45 Pk ?
    Ce rendu est-il optimal ?
  • Affiche corrigé

    Cacher corrigé

    1. Je dois lui rendre 50 - 0.85 = 49.15€
      Le meilleur rendu est 2×20€, 1×5€, 2×2€, 1×0.10€, 1×0.05€.
    2. Pour rendre le moins de monnaie possible, il faut toujours rendre la plus grande valeur possible.
    3. monnaie=[200,100,50,20,10,5,2,1,0.5,0.2,0.1,0.05,0.02,0.01]
      
      def rendu_monnaie(montant,monnaie):
          rendu={}
          montant=int(100*montant)
          for piece in monnaie:
              if montant>=100*piece:
                  rendu[piece]=int(montant//(piece*100))
                  montant-=rendu[piece]*(piece*100)
                  
          return rendu
      Remarque : Il faut faire attention à la façon dont Python travaille sur les nombres flottants. Pour éviter un problème, il faut s'assurer que les nombres sont entiers en les mutipliant par 100.
    4. Une fois le programme ci-dessus écrit de cette façon, il suffit d'ajouter une nouvelle liste pour les pièces en Plouks.
      monnaie_Pk=[200, 100, 30, 20, 5, 2, 1, 0.3, 0.1, 0.05, 0.01]
      On lance ensuite
      rendu_monnaie(45,monnaie_Pk)
      Out[24]: {30: 1, 5: 3}
      L'algorithme propose alors de rendre 4 devises, tandis que la solution optimale était de 3 : 2×20Pk, 1×5Pk.
    3) Les fractions égyptiennes
    Si les égyptiens ne connaissaient pas la notation décimale, ils connaissaient les fractions, sous une forme particulière (voir Wikipédia ) : leurs fractions étaient de la forme 1p 1over p p * p in setN ^"*" . On parle de fraction unitaire.
    Ils pouvaient donc écrire n’importe quel nombre rationnel (un nombre qui peut s’écrire comme le quotient de 2 nombres entiers) en le décomposant d’une infinité de façons à l’aide de fractions unitaires.
    Par exemple 25 = 1 5+ 1 6+ 1 30 = 1 5+ 1 8+ 1 20+ 1 40 2over5=1over5+1over6+1over30=1over5+1over8+1over20+1over40 .
    Cette solution les satisfaisait probablement d’autant plus qu’il n’est pas sûr qu’ils savaient que certains nombres ne pouvaient être rationnels, comme √2 ou π!
    Il vous faudrait écrire un algorithme glouton egypte(nombre) qui décompose n’importe quel nombre 0<x<1 en somme de fractions unitaires…
    Bien sûr, du fait des spécificités de la prise en charge des nombres et le fait que certains nombre se décomposent nécessairement en une somme infinie de fractions, il faudra accepter une approximation de cette décomposition.

    Affiche corrigé

    Cacher corrigé

    def egypte(nombre,epsilon=1e-7):
        n=2
        sortie=""
        while nombre>epsilon:
            if 1/n<=nombre:
                nombre-=1/n
                sortie+="+1/"+str(n)
            n+=1
        return sortie[1:]
    L'algorithme est "simple" : il part de la fraction 1/2 puis comme dans le problème du rendu de monnaie, regarde s'il peut retrancher la fraction à la valeur à décomposer. Le cas échéant, il ajoute son écriture à la décomposition. Il continue jusqu'à ce que le reste soit inférieur à une valeur de référence facultative epsilon.
    In [2]: egypte(2/3)
    Out[2]: '1/2+1/7+1/43+1/1807+1/3263443'
    
    Remarque : cette façon de décomposer un nombre décimal devrait vous rappeler quelque chose, puisque c’est de cette façon que l’on détermine l’écriture binaire d’un décimal, en utilisant des fractions unitaires de la forme 1 2n 1over2 .
    4) Le voleur
    Il s'agit d'un grand classique de l'algorithme glouton, vous le retrouverez facilement sur Internet
    Marcel Lupin est un voleur prévoyant. Avant de perpétrer ses larcins, il prend soin de lister les objets de valeur présents chez ses futures malheureuses victimes. Il n’emporte sur les lieu qu’un seul sac de 50kg, il doit être sélectif !
    Il établit donc une liste (enfin, nous dirions plutôt dictionnaire, mais Marcel n’est pas informaticien) des objets présents, en indiquant tout d’abord leur masse en kg puis leur valeur en Brouzoufs (c’est la monnaie d’Andorrsbourg, riche petite principauté voisine de l’Absurdistan dans laquelle se déroule notre histoire).
    Cette liste est disponible ci-dessous :

    Affiche liste

    Cacher liste

    {'A': [4, 54], 'B': [2, 9], 'C': [14, 91], 'D': [14, 4], 'E': [8, 18], 'F': [1, 98], 'G': [5, 56], 'H': [15, 85], 'I': [7, 61], 'J': [3, 83], 'K': [2, 75], 'L': [10, 70], 'M': [7, 73], 'N': [14, 71], 'O': [7, 3], 'P': [6, 75], 'Q': [9, 91], 'R': [14, 16], 'S': [9, 48], 'T': [9, 37], 'U': [13, 83], 'V': [3, 30], 'W': [12, 81], 'X': [3, 72], 'Y': [2, 10], 'Z': [3, 24]}
    → Proposez une fonction a_voler(dictionnaire) qui pour un dictionnaire donné retourne la liste des items à voler en priorité afin d’avoir la plus grande valeur dans le sac.
    → Cette fonction calcule également la valeur du contenu du sac.

    Affiche corrigé

    Cacher corrigé

    victime={'A': [4, 54], 'B': [2, 9], 'C': [14, 91], 'D': [14, 4], 'E': [8, 18], 'F': [1, 98], 'G': [5, 56], 'H': [15, 85], 'I': [7, 61], 'J': [3, 83], 'K': [2, 75], 'L': [10, 70], 'M': [7, 73], 'N': [14, 71], 'O': [7, 3], 'P': [6, 75], 'Q': [9, 91], 'R': [14, 16], 'S': [9, 48], 'T': [9, 37], 'U': [13, 83], 'V': [3, 30], 'W': [12, 81], 'X': [3, 72], 'Y': [2, 10], 'Z': [3, 24]}
    """
    rech_max cherche la plus grande valeur d'un dictionnaire de listes
    en permettant de choisir sur quel indice de la liste on fait la comparaison
    """
    def rech_max(dictionnaire,indice):
        cles=list(dictionnaire.keys())
        max=dictionnaire[cles[0]][indice]
        cle_max=cles[0]
        for i in cles:
            if dictionnaire[i][indice]>max:
                max=dictionnaire[i][indice]
                cle_max=i
        return cle_max
    
    """
    la fonction a_voler(dictionnaire,capacite_sac) fait 3 choses
    - calcule la valeur/kg de chaque objet et l'ajoute au dictionnaire
    - ajoute récursivement l'objet le plus rentable dans le dictionnaire 'sac',
        à la condition que celui-ci puisse encore rentrer
    - supprime cet objet dans le dictionnaire
    """
    def a_voler(dictionnaire,capacite_sac):
        sac={}
        valeur=0
        for i in dictionnaire.keys():
            dictionnaire[i].append(dictionnaire[i][1]/dictionnaire[i][0])
        while capacite_sac>0 and len(dictionnaire)>0:
            cle_max=rech_max(dictionnaire,2)
            if dictionnaire[cle_max][0]<=capacite_sac:
                print("on ajoute",cle_max,dictionnaire[cle_max])
                capacite_sac-=dictionnaire[cle_max][0]
                sac[cle_max]=dictionnaire[cle_max]
                valeur+=dictionnaire[cle_max][1]
            del(dictionnaire[cle_max])
        return valeur,sac
    #lancer la fonction avec a_voler(victime,50)
    #la fonction remplira un sac de 50kg avec les objets de victime.
    	
    La principale difficulté de cet algorithme est de trouver à quel paramètre appliquer l'algorithme glouton !
    Ce n'est pas forcément la valeur de l'objet, car celui-ci peut valoir beaucoup mais remplir le sac à lui seul.
    Le paramètre de la valeur rapportée au kilogramme est plus judicieux, car il nous assure de maximiser le butin à chaque prise.
    En revanche, cet algorithme ne sera pas forcément optimal !
    Je vous laisse chercher un exemple dans lequel ce ne sera pas le cas :)

    III- Algorithme des k-plus proches voisins

    1) Intelligence Artificielle et détermination
    Un problème classique pour ce que l'on appelle "Intelligence Artificielle" est celui de la détermination : étant donné un objet, défini par une série de valeurs (taille, poids, valeur, durée, ... ) et (au moins) 2 groupes différents A et B aux caractéristiques différentes, on aimerait déterminer si l'objet appartient au groupe A ou au groupe B.
    Les applications sont très larges :
    • Le visage en photo est-il celui d'un homme ou d'une femme ?
    • Le tableau est-il de Claude Monet ou d'Edouard Manet ?
    • La balance connectée pèse-t-elle un adulte ou un enfant ?
    Il existe beaucoup d'algorithmes permettant de réaliser cette tâche, nous allons étudier l'un des plus abordables, celui des k-plus proches voisins.
    2) Principe
    Pour pouvoir déterminer l'appartenance d'un objet à un groupe, il faut à l'avance connaître les paramètres de chaque groupe. Seulement les données étant rarement complètes (et parfois les concepteurs sachant pas à l'avance quel sera le paramètre le plus judicieux), on donne plutôt un jeu de données contenant les paramètres de plusieurs objets auxquels un groupe a déjà été attribué (par un ensemble de spécialistes ou via les réponses aux Captchas que vous validez sur internet).
    On compare ensuite pour chaque nouvel objets ses dimensions par rapport aux objets de chaque groupe et on détermine le groupe de cet objet comme étant celui dont il est le plus proche.
    Il nous faut donc :
    • Un ensemble d'objets ayant des mesures et appartenant à un groupe défini
    • Un objet ayant des mesures et dont le groupe est à déterminer
    • Déterminer comment on mesure la distance des objets entre eux
    Voyons cela au travers de l'exemple le plus courant de cet algorithme :
    3) Un problème de fleurs
    a. Présentation
    Saviez-vous qu'il existe plusieurs espèces d'iris ?

    Iris Setosa

    Iris Virginica

    Iris Versicolor
    Quand on les regarde, on voit qu'effectivement, elles sont différentes, mais difficile de dire en quoi !
    Heureusement, en 1936, Edgar Anderson a mesuré des caractéristiques des différentes espèces, et notamment :

    Fleur

    Longueur et largeur d'un sépale

    Longueur et largeur d'un pétale
    b. Récupération et visualisation des données
    Le fichier iris.txt contient les dimensions des pétales de différentes fleurs ainsi que son espèce sous la forme
    [longueur du pétale, largeur du pétale, groupe],
    avec groupe : [0,1,2] → [setosa, versicolor, virginica].
    liste_fleurs=[] #On crée une liste vide
    with open("iris.txt","r",encoding="utf-8") as txt: 
        for ligne in txt: 
            liste_fleurs.append(eval(ligne[:-1])) 
    Si l'on trace rapidement un graphique par espèce avec la longueur du pétale en abscisses et sa largeur en ordonnée pour chaque fleur, on obtient le graphique suivant :
    On voit maintenant clairement 3 groupes
    • en orange, les setosa sont clairement séparées des 2 autres espèces ;
    • en vert les versicolor ;
    • enfin les virginica, plus grandes, mais dans la continuité directe des versicolor
    Ces groupes, faciles à identifier à l'oeil sont en fait le véritable enjeu de l'algorithme des k plus proches voisins.
    c. Calculer les distances
    Imaginons maintenant que nous ayons 4 nouvelles fleurs définies par les dimensions de leurs pétales :
    • A : [4,1.2]
    • B : [1.5,0.4]
    • C : [6.5,2.3]
    • D : [5,1.7]
    Les fleurs A, B et C sont faciles à placer sur le graphique ci-dessus, mais quid de D ?
    Pour déterminer leur groupe d'appartenance, il va falloir calculer pour chaque fleur A,B,C,D la "distance" à laquelle elle se trouve de chaque fleur du groupe de données.
    Cette distance peut être déterminée de plusieurs façons, considérons pour ne pas nous compliquer la tâche, la distance euclidienne classique \(AB=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2}\)
    def distance(xa,ya,xb,yb):
        return ((xb-xa)**2+(yb-ya)**2)**0.5
    
    def liste_distances(fleur_inconnue,liste):
        distances=[]
    	for fleur in liste:
    	    dist=distance(fleur_inconnue[0],fleur_inconnue[1],fleur[0],fleur[1])
    		distances.append([dist,fleur[2]])
    	return distances
    
    La commande liste_distances([5,1.7],liste_fleurs) retournera donc une liste récapitulant la distance à laquelle se trouve la fleur D de chacune des fleurs présentes dans le fichier iris.txt.
    d. Repérer les plus proches voisines
    Maintenant que l'on connait les distances à chaque fleur, on va devoir déterminer quelle est l'espèce la plus représentée parmi les plus proches voisines.
    Il faut donc :
    • Trier la liste retournée par liste_distances par ordre croissant
    • Prendre les 5 premières fleurs et en recenser l'espèce
    Pour le tri, le plus simple est de reprendre le tri par insertion (le plus rapide vu en 1ere NSI) :
    def tri_selection(liste):
        for i in range(len(liste)):
            maxi=liste[0][0]
            indice=0
            for j in range(len(liste)-i):
                if liste[j][0]>maxi:
                    maxi=liste[j][0]
                    indice=j
            liste[indice],liste[len(liste)-i-1]=liste[len(liste)-i-1],liste[indice]
        return liste
    
    Parmi les k premiers éléments de cette liste on va recenser le nombre de fleurs de chaque espèce :
    def plus_proches(liste,k=5):
        especes=dict()
        for i in liste[:5]:
            if i[1] in especes.keys():
                especes[i[1]]+=1
            else :
                especes[i[1]]=1
        return especes
    
    Finalement, il ne reste qu'à trouver l'espèce qui est la plus représentée
    def recherche_cle_max(dictionnaire):
        liste_cles=list(dictionnaire.keys())
        cle_max=liste_cles[0]
        maxi=dictionnaire[cle_max]
        for i in liste_cles[1:]:
            if dictionnaire[i]>maxi:
                maxi=dictionnaire[i]
                cle_max=i
        return cle_max
    
    Pour connaître l'espèce à laquelle appartient les fleurs A,B,C et D, il suffit donc de faire :
    for i in [[4,1.2],[1.5,0.4],[6.5,2.3],[5,1.7]]:
        print(recherche_cle_max(plus_proches(tri_selection(liste_distances(i,liste_fleurs)))))
    
    Previous page: Langages et programmation Next page: Thème A