Dichotomie, algorithmes gloutons et k plus proches voisins
Recherche dichotomique dans un tableau trié et coût logarithmique, algorithmes gloutons (rendu de monnaie, sac à dos) et leurs limites, algorithme des k plus proches voisins pour la classification.
1. Recherche dichotomique
Méthode · Algorithme
def dichotomie(t, x):
g, d = 0, len(t) - 1
while g <= d:
m = (g + d) // 2
if t[m] == x:
return m
elif t[m] < x:
g = m + 1
else:
d = m - 1
return -1Propriété · Coût logarithmique
Le tableau doit être trié. À chaque étape, la zone de recherche est divisée par $2$ : pour $n$ éléments, au plus environ $\log_2 n$ étapes. Pour un million d'éléments : $20$ étapes au lieu d'un million.
2. Algorithmes gloutons
Définition
Un algorithme glouton construit une solution étape par étape en faisant à chaque fois le choix qui semble le meilleur sur le moment, sans revenir en arrière. Il est rapide mais ne donne pas toujours la solution optimale.
Exemple · Rendu de monnaie
Rendre $8$ € avec des pièces de $5$, $2$ et $1$ : on prend la plus grande pièce possible à chaque fois : $5 + 2 + 1$ ($3$ pièces), ce qui est optimal pour le système européen. Avec un système $\{1, 3, 4\}$ et $6$ à rendre, le glouton donne $4 + 1 + 1$ ($3$ pièces) alors que $3 + 3$ ($2$ pièces) est meilleur.
3. Les k plus proches voisins
Méthode · Algorithme kNN
Pour classer un nouvel élément : calculer sa distance à tous les éléments connus, garder les $k$ plus proches, et lui attribuer la classe majoritaire parmi eux. Le choix de $k$ et de la distance (euclidienne $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$) influence le résultat. C'est un algorithme d'apprentissage automatique.
Activité · Classer des iris
voisins = sorted(donnees, key=lambda f: distance(f, inconnue))[:5] puis comptage des espèces.⚠️ Une erreur dans ce cours ? Signalez-la
S'entraîner
Exercices corrigés
🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.
Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.
Condition
★☆☆Quelle condition doit remplir un tableau pour une recherche dichotomique ?
Dérouler la dichotomie
★★☆Avec le tableau de la figure, dérouler la recherche de $72$ (valeurs de g, d, m).
Valeur absente
★★☆Que renvoie la fonction pour $x = 10$ avec le même tableau ?
Nombre d'étapes
★★☆Combien d'étapes au maximum pour un tableau trié de $1\,000$ éléments ? d'un milliard ?
Comparaison des coûts
★★☆Comparer le nombre de comparaisons d'une recherche séquentielle et dichotomique pour $10^6$ éléments.
Terminaison
★★★Pourquoi la boucle de la dichotomie se termine-t-elle ?
Jeu du nombre
★☆☆Pour deviner un nombre entre $1$ et $100$ en recevant « plus » ou « moins », quelle stratégie ? Combien d'essais au plus ?
Rendu glouton
★☆☆Avec des pièces de $50$, $20$, $10$, $5$, $2$, $1$ centimes, rendre $87$ centimes selon l'algorithme glouton.
Programmer le rendu
★★★Écrire une fonction rendu(somme, pieces) gloutonne (pièces triées par ordre décroissant) qui renvoie la liste des pièces.
Contre-exemple
★★☆Avec les pièces $\{1, 3, 4\}$, que donne le glouton pour $6$ ? Est-ce optimal ?
Sac à dos
★★★Sac de $10$ kg ; objets (masse, valeur) : A$(6, 30)$, B$(5, 20)$, C$(5, 20)$. Glouton par valeur décroissante : quels objets ? Est-ce optimal ?
Planning glouton
★★☆Pour choisir le plus d'activités compatibles dans une journée, quelle stratégie gloutonne fonctionne ?
Distance euclidienne
★☆☆Distance entre $(1\,;\,2)$ et $(4\,;\,6)$ ?
Fonction distance
★★☆Écrire une fonction distance(a, b) pour deux couples.
Classer avec k = 3
★★☆Les $3$ plus proches voisins d'un point sont de classes A, B, B. Classe attribuée ?
Influence de k
★★☆Avec $k = 1$, le voisin le plus proche est A ; avec $k = 3$, la majorité est B. Commenter.
k pair
★★☆Pourquoi choisit-on souvent $k$ impair pour deux classes ?
Lecture de la figure
★☆☆Sur la figure kNN, le point « ? » est-il plutôt classé A ou B avec $k = 3$ ?
Coût de kNN
★★★Quel est le coût de la classification d'un point par kNN avec $n$ données connues (en utilisant un tri) ?
Vrai ou faux
★★☆a) La dichotomie fonctionne sur un tableau non trié. b) Un glouton donne toujours l'optimum. c) kNN attribue la classe majoritaire des voisins.
Vérifier
Avez-vous bien compris ?
Répondez au quiz : la correction s'affiche immédiatement.