k plus proches voisins, dichotomie et gloutons

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

1. b) Indiquer le variant de la boucle.

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

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

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

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

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

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

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

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

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

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

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

1. c) Comparer les deux résultats.

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

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

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

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