Recherche dichotomique, algorithmes gloutons et k plus proches voisins · NSI Première (spé maths)

Recherche dichotomique

Pour trouver un mot dans un dictionnaire, tu n'as pas besoin de lire toutes les pages : tu ouvres au milieu, tu regardes si le mot est avant ou après, et tu recommences sur la bonne moitié. C'est la recherche dichotomique.

Elle ne marche que si le tableau est trié. À chaque tour, on compare la valeur cherchée x à l'élément du milieu t[milieu] :

si t[milieu] == x, c'est gagné ;
si t[milieu] < x, on cherche dans la moitié de droite (debut = milieu + 1) ;
sinon on cherche dans la moitié de gauche (fin = milieu - 1).

def dichotomie(t, x):

    debut, fin = 0, len(t) - 1

    while debut <= fin:

        milieu = (debut + fin) // 2

        if t[milieu] == x:

            return True

        elif t[milieu] < x:

            debut = milieu + 1

        else:

            fin = milieu - 1

    return False

Si la boucle se termine sans avoir trouvé x, la zone de recherche est vide (debut > fin) : x n'est pas dans le tableau.

Entraîne-toi★☆☆

On recherche par dichotomie la valeur 23 dans le tableau trié [3, 8, 12, 17, 23, 29, 35, 41] (indices de 0 à 7). a) Donner les valeurs successives des indices debut, fin…

On recherche par dichotomie la valeur 23 dans le tableau trié [3, 8, 12, 17, 23, 29, 35, 41] (indices de 0 à 7).

a) Donner les valeurs successives des indices debut, fin et milieu (avec milieu = (debut + fin) // 2).

b) Combien de valeurs du tableau sont comparées à 23 au cours de la recherche ?

Résoudre

Entraîne-toi★★☆

Écrire une fonction dichotomie(t, x) qui renvoie True si x appartient au tableau trié t, False sinon. a) Écrire la fonction avec une boucle while debut <= fin. b)…

Écrire une fonction dichotomie(t, x) qui renvoie True si x appartient au tableau trié t, False sinon.

a) Écrire la fonction avec une boucle while debut <= fin.

b) Indiquer le variant de la boucle.

c) Combien de tours de boucle au maximum pour un tableau de 1 000 éléments ?

Résoudre

Terminaison et coût : variant et invariant

Comment être sûr que la boucle while de la dichotomie s'arrête ? On cherche une quantité entière, positive, qui diminue strictement à chaque tour : c'est un variant de boucle. Ici, c'est la taille de la zone de recherche :

$$\text{fin} - \text{debut} + 1$$

À chaque tour, soit on trouve x et on sort, soit debut augmente d'au moins 1, soit fin diminue d'au moins 1 : le variant diminue strictement. Un entier positif ne peut pas diminuer indéfiniment : la boucle se termine.

Pour la correction, on utilise un invariant de boucle : une propriété vraie avant la boucle et qui reste vraie après chaque tour. Ici : « si x est dans t, alors son indice est compris entre debut et fin ». Au début, debut = 0 et fin = len(t) - 1 : c'est vrai. À chaque tour, on n'écarte que des éléments qui ne peuvent pas être égaux à x (grâce au tri) : la propriété reste vraie. À la sortie de la boucle, debut > fin : la zone est vide, donc x n'est pas dans t.

Coût. À chaque tour, la taille de la zone est divisée par 2 environ. Pour un tableau de $n$ éléments, il y a au plus $\lfloor \log_2 n \rfloor + 1$ tours. Pour $n = 1\,000$ : $2^{10} = 1\,024 > 1\,000$, donc au plus 10 tours. Pour $n = 1\,000\,000$, au plus 20 tours.

Entraîne-toi★★★

Soit l'algorithme de recherche dichotomique suivant dans un tableau trié t de n éléments : a) Montrer que la quantité $f - d + 1$ est un variant de la boucle et en…

Soit l'algorithme de recherche dichotomique suivant dans un tableau trié t de n éléments :

def recherche(t, x):

    d, f = 0, len(t) - 1

    while d <= f:

        m = (d + f) // 2

        if t[m] == x:

            return m

        elif t[m] < x:

            d = m + 1

        else:

            f = m - 1

    return -1

a) Montrer que la quantité $f - d + 1$ est un variant de la boucle et en déduire la terminaison.

b) Énoncer un invariant : si x est dans t, alors son indice est compris entre d et f. Le démontrer.

c) Montrer que le nombre de tours est au plus $\lfloor \log_2 n \rfloor + 1$.

Résoudre

Algorithmes gloutons

Un algorithme glouton construit une solution étape par étape : à chaque étape, il fait le choix qui paraît le meilleur sur le moment, sans jamais revenir en arrière.

Le rendu de monnaie

On dispose de billets et pièces de 50 €, 20 €, 10 €, 5 €, 2 € et 1 €. Pour rendre une somme, on prend à chaque fois la plus grande valeur qui ne dépasse pas ce qu'il reste à rendre.

def rendu(somme, systeme):

    # systeme : valeurs rangées de la plus grande à la plus petite

    resultat = []

    for valeur in systeme:

        while somme >= valeur:

            resultat.append(valeur)

            somme = somme - valeur

    return resultat

Avec le système français, le glouton donne toujours le rendu minimal. Mais ce n'est pas vrai pour tout système de monnaie !

Le problème du sac à dos

Un sac supporte une masse maximale. On choisit des objets (qu'on ne peut pas couper) pour maximiser la valeur totale. Deux stratégies gloutonnes : choisir par valeur décroissante, ou par rapport valeur/masse décroissant.

Exemple : capacité 10 kg, objets X (6 kg ; 9 €), Y (5 kg ; 7 €), Z (5 kg ; 7 €).

Objet	Masse	Valeur	Valeur/masse
X	6 kg	9 €	1,5
Y	5 kg	7 €	1,4
Z	5 kg	7 €	1,4

Les deux stratégies prennent X en premier (6 kg). Il reste 4 kg : ni Y ni Z n'y rentrent. Valeur obtenue : 9 €. Mais Y + Z pèsent 10 kg et valent 14 €. Le glouton n'est pas optimal ici.

Les algorithmes gloutons sont rapides et simples, ils donnent une bonne solution, parfois la meilleure. Pour prouver qu'un glouton est optimal, il faut un raisonnement particulier (par exemple montrer que prendre la plus grande valeur possible ne ferme jamais la porte à une meilleure solution).

Entraîne-toi★☆☆

On doit rendre 63 € avec des pièces et billets de 50 €, 20 €, 10 €, 5 €, 2 € et 1 €. a) Appliquer l'algorithme glouton de rendu de monnaie et donner la composition du…

On doit rendre 63 € avec des pièces et billets de 50 €, 20 €, 10 €, 5 €, 2 € et 1 €.

a) Appliquer l'algorithme glouton de rendu de monnaie et donner la composition du rendu.

b) Combien de pièces et billets sont utilisés ?

Résoudre

Entraîne-toi★★☆

Un sac à dos de capacité 15 kg doit contenir des objets de valeur maximale. Objets (masse en kg ; valeur en €) : A (12 ; 4), B (2 ; 2), C (1 ; 1), D (1 ; 2), E (4 ; 10).…

Un sac à dos de capacité 15 kg doit contenir des objets de valeur maximale. Objets (masse en kg ; valeur en €) : A (12 ; 4), B (2 ; 2), C (1 ; 1), D (1 ; 2), E (4 ; 10).

a) Appliquer l'algorithme glouton qui choisit les objets par valeur décroissante, sans fractionner les objets.

b) Appliquer l'algorithme glouton qui choisit par rapport valeur/masse décroissant.

c) Comparer les deux résultats.

Résoudre

Entraîne-toi★★★

On considère le système de monnaie $\{1, 3, 4\}$ (en unités quelconques). a) Appliquer l'algorithme glouton pour rendre 6. Donner la solution obtenue. b) Trouver une…

On considère le système de monnaie $\{1, 3, 4\}$ (en unités quelconques).

a) Appliquer l'algorithme glouton pour rendre 6. Donner la solution obtenue.

b) Trouver une solution utilisant moins de pièces. Conclure sur l'optimalité de l'algorithme glouton.

c) Vérifier que le glouton est optimal pour le système $\{1, 2, 5, 10, 20, 50\}$ pour toutes les sommes jusqu'à 20, en justifiant avec un raisonnement général sur le choix de la plus grande pièce.

Résoudre

Les k plus proches voisins

Comment une application reconnaît-elle une espèce de fleur à partir d'une mesure ? Elle compare avec des cas déjà classés. L'algorithme des k plus proches voisins (en abrégé k-NN) est un algorithme d'apprentissage : pour prédire la classe d'une donnée inconnue, on cherche les $k$ données connues les plus proches et on prend la classe majoritaire parmi elles.

La distance

Dans le plan, la distance euclidienne entre $A(x_1 ; y_1)$ et $B(x_2 ; y_2)$ est

$$d(A, B) = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$

En Python : ((x2 - x1)**2 + (y2 - y1)**2) ** 0.5.

L'algorithme

Calculer la distance entre le point inconnu et chaque donnée.
Trier les données par distance croissante.
Garder les $k$ premières.
Renvoyer la classe qui apparaît le plus souvent.

En Python, on range des couples (distance, classe) dans une liste : le tri compare d'abord la distance.

def distance(p, q):

    return ((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2) ** 0.5

def knn(donnees, p, k):

    # donnees : liste de triplets (x, y, classe)

    liste = []

    for (x, y, classe) in donnees:

        liste.append((distance(p, (x, y)), classe))

    liste.sort()

    effectifs = {}

    for i in range(k):

        classe = liste[i][1]

        if classe in effectifs:

            effectifs[classe] = effectifs[classe] + 1

        else:

            effectifs[classe] = 1

    meilleure = liste[0][1]

    for classe in effectifs:

        if effectifs[classe] > effectifs[meilleure]:

            meilleure = classe

    return meilleure

Entraîne-toi★☆☆

Dans le plan, on considère les points A(1 ; 2) et B(4 ; 6). a) Calculer la distance euclidienne $d(A, B)$. b) Donner la formule de la distance euclidienne entre…

Dans le plan, on considère les points A(1 ; 2) et B(4 ; 6).

a) Calculer la distance euclidienne $d(A, B)$.

b) Donner la formule de la distance euclidienne entre $(x_1, y_1)$ et $(x_2, y_2)$.

c) Parmi les points C(2 ; 2) et D(5 ; 5), lequel est le plus proche de A ?

Résoudre

Entraîne-toi★★☆

Un jeu de données classe des fleurs en deux espèces, A et B, d'après la longueur et la largeur de leurs pétales (en cm) : (1,0 ; 0,5) : A (1,5 ; 0,4) : A (4,5 ; 1,5) : B…

Un jeu de données classe des fleurs en deux espèces, A et B, d'après la longueur et la largeur de leurs pétales (en cm) :

(1,0 ; 0,5) : A
(1,5 ; 0,4) : A
(4,5 ; 1,5) : B
(5,0 ; 1,8) : B
(4,0 ; 1,2) : B

a) Calculer la distance de chaque donnée à la fleur inconnue (2,0 ; 0,6).

b) Appliquer l'algorithme des $k$ plus proches voisins avec $k = 3$ et donner l'espèce prédite.

c) Écrire une fonction Python qui renvoie les $k$ plus proches voisins d'un point.

Résoudre

Entraîne-toi★★★

Une table contient des relevés de températures et d'humidité pour des journées classées « pluie » ou « sec » dans une ville de Bretagne. On souhaite prédire la classe…

Une table contient des relevés de températures et d'humidité pour des journées classées « pluie » ou « sec » dans une ville de Bretagne. On souhaite prédire la classe d'une nouvelle journée par $k$ plus proches voisins.

a) Expliquer pourquoi il peut être nécessaire de normaliser les données avant de calculer les distances lorsque les deux attributs n'ont pas la même échelle.

b) Écrire une fonction knn(donnees, p, k) qui renvoie la classe majoritaire parmi les $k$ voisins les plus proches de p, où donnees est une liste de triplets (x, y, classe).

c) Discuter l'effet du choix de $k$ (trop petit, trop grand) sur la prédiction, et donner la complexité de la fonction en fonction de la taille $n$ des données.

Résoudre

Retour au début : la méthode de la caissière est un algorithme glouton, optimal pour les euros mais pas pour n'importe quel système de monnaie ; et fouiller 1 000 noms triés prend au plus 10 tours de dichotomie.

L'essentiel

Dichotomie : dans un tableau trié, on compare à l'élément du milieu et on garde la bonne moitié. Variant : $\text{fin} - \text{debut} + 1$. Au plus $\lfloor \log_2 n \rfloor + 1$ tours.
Invariant de la dichotomie : si x est dans t, son indice est entre debut et fin.
Glouton : à chaque étape, on fait le choix localement le meilleur, sans retour en arrière. Rapide, mais pas toujours optimal (système $\{1, 3, 4\}$, sac à dos).
k plus proches voisins : on calcule les distances, on garde les $k$ plus petites et on prend la classe majoritaire ; il faut penser à normaliser les données et à bien choisir $k$.

À s'entraîner ! 3 exercices de niveau moyen dans cette section

★★☆ Écrire une fonction dichotomie(t, x) qui renvoie True si x appartient au tableau trié t,…★★☆ Un jeu de données classe des fleurs en deux espèces, A et B, d'après la longueur et la…★★☆ Un sac à dos de capacité 15 kg doit contenir des objets de valeur maximale. Objets (masse…