💻 NSI (spécialité)1ereCours

Recherche dichotomique, k plus proches voisins, algorithmes gloutons

Voir la fiche de révision →Tous les chapitres

📖

Cours

Recherche dichotomique, k plus proches voisins, algorithmes gloutons

Trois algorithmes classiques, trois méthodes de pensée.

La recherche dichotomique exploite un tableau trié pour trouver une valeur en coupant l'intervalle en deux à chaque étape.

L'algorithme des k plus proches voisins prédit la classe d'un élément à partir d'exemples déjà classés : c'est un premier algorithme d'apprentissage.

Les algorithmes gloutons construisent une solution par choix locaux successifs : ils sont rapides, mais pas toujours optimaux.

1. La recherche dichotomique

1.1 L'idée

Pour chercher un mot dans un dictionnaire papier, on ouvre au milieu, on compare, on ne garde que la moitié utile, et on recommence.

Le programme affiche l'intervalle à chaque tour. Cherche d'autres valeurs, présentes ou absentes.

def dichotomie(t, v):
    """t est trié par ordre croissant ; renvoie un index où t vaut v, ou -1."""
    debut = 0
    fin = len(t) - 1
    while debut <= fin:
        m = (debut + fin) // 2
        print("debut =", debut, " fin =", fin, " m =", m, " t[m] =", t[m])
        if t[m] == v:
            return m
        elif t[m] < v:
            debut = m + 1
        else:
            fin = m - 1
    return -1

t = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print("index :", dichotomie(t, 23))

La valeur $23$ est trouvée en $3$ comparaisons, contre $6$ avec une recherche séquentielle.

1.2 Terminaison : le variant

La boucle while n'est pas bornée : il faut prouver qu'elle s'arrête.

On considère la longueur de l'intervalle, fin - debut + 1.

À chaque tour où l'on ne renvoie rien, soit debut devient m + 1, soit fin devient m - 1.

Dans les deux cas, la longueur diminue strictement, et elle est minorée par $0$ , puisque la boucle s'arrête dès que l'intervalle est vide.

1.3 Correction : l'invariant

Initialisation. Au départ, l'intervalle est le tableau entier : la propriété est vraie.

Conservation. Le tableau est trié. Si t[m] < v, tous les éléments d'index inférieur ou égal à m sont plus petits que v : v ne peut être qu'après. Le raisonnement est symétrique si t[m] > v.

Conclusion. Si l'on sort de la boucle sans avoir trouvé, l'intervalle est vide : v est absent.

1.4 Coût logarithmique

À chaque tour, la taille de l'intervalle est au moins divisée par $2$ : de $n$ , on passe à $n/2$ , puis $n/4$ , jusqu'à $1$ .

Le nombre de tours est le nombre de fois où l'on peut diviser $n$ par $2$ , soit environ $\log_2 n$ : le plus petit $k$ tel que $2^k \geq n$ .

$n$	Recherche séquentielle (pire cas)	Dichotomie (pire cas)
$10$	$10$	$4$
$1\,000$	$1\,000$	$10$
$10^6$	$10^6$	$20$
$10^9$	$10^9$	$30$

Vérifions-le : on cherche une valeur absente, et on compte les tours.

def tours_dichotomie(t, v):
    debut, fin, tours = 0, len(t) - 1, 0
    while debut <= fin:
        tours = tours + 1
        m = (debut + fin) // 2
        if t[m] == v:
            return tours
        elif t[m] < v:
            debut = m + 1
        else:
            fin = m - 1
    return tours

for n in [10, 1000, 1000000]:
    t = list(range(n))
    print(n, "éléments :", tours_dichotomie(t, n), "tours")

def dichotomie(t, v):
    debut = 0
    fin = len(t) - 1
    # à toi : la boucle while, le milieu m, les trois cas
    return -1

2. L'algorithme des k plus proches voisins

2.1 Le problème

On dispose d'exemples déjà classés : des fleurs mesurées (longueur et largeur de pétale) avec leur espèce, des courriels étiquetés « spam » ou « normal ».

Pour un nouvel élément dont on ne connaît pas la classe, on veut la prédire.

2.2 L'algorithme

La distance la plus courante est la distance euclidienne : $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$ .

from math import sqrt

def distance(p, q):
    return sqrt((p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2)

def knn(exemples, nouveau, k):
    """exemples : tableau de dictionnaires {"x": .., "y": .., "classe": ..}."""
    for e in exemples:
        e["d"] = distance((e["x"], e["y"]), nouveau)
    voisins = sorted(exemples, key=lambda e: e["d"])[:k]
    compte = {}
    for e in voisins:
        if e["classe"] in compte:
            compte[e["classe"]] = compte[e["classe"]] + 1
        else:
            compte[e["classe"]] = 1
    meilleure = None
    for classe in compte:
        if meilleure is None or compte[classe] > compte[meilleure]:
            meilleure = classe
    return meilleure

exemples = [
    {"x": 1, "y": 1, "classe": "A"},
    {"x": 2, "y": 1, "classe": "A"},
    {"x": 5, "y": 4, "classe": "B"},
    {"x": 6, "y": 5, "classe": "B"},
    {"x": 3, "y": 3, "classe": "B"},
]
print(knn(exemples, (2, 2), 3))

Change k en $1$ , puis en $5$ : la prédiction change-t-elle ? Déplace aussi le nouveau point.

2.3 Le choix de k et ses limites

Choix	Conséquence
$k = 1$	on copie la classe du voisin le plus proche : sensible à un exemple mal classé
$k$ grand	plus stable, mais on finit par prédire toujours la classe la plus fréquente
$k$ impair	évite les égalités quand il y a deux classes

En pratique, on teste plusieurs valeurs de $k$ sur des exemples dont on connaît la réponse, et on garde la meilleure.

def manhattan(p, q):
    # à toi
    return 0

3. Les algorithmes gloutons

3.1 La méthode

C'est simple et rapide. Le résultat est parfois optimal, parfois seulement approché.

3.2 Le rendu de monnaie

On veut rendre une somme en utilisant le moins de pièces possible.

La stratégie gloutonne : prendre la plus grande pièce qui ne dépasse pas ce qui reste à rendre, et recommencer.

def rendu(somme, pieces):
    """pieces triées par ordre décroissant ; renvoie la liste des pièces rendues."""
    resultat = []
    for p in pieces:
        while somme >= p:
            resultat.append(p)
            somme = somme - p
    return resultat

print(rendu(48, [50, 20, 10, 5, 2, 1]))
print(rendu(6, [4, 3, 1]))

Avec les pièces européennes, le résultat est optimal : cinq pièces pour $48$ centimes.

Avec les pièces $\{4, 3, 1\}$ , le glouton rend $6$ avec trois pièces, $4 + 1 + 1$ , alors que $3 + 3$ n'en demande que deux.

Essaie aussi rendu(8, [6, 4, 1]) : le glouton est-il optimal ?

3.3 Le sac à dos

On dispose d'objets ayant chacun un poids et une valeur, et d'un sac de capacité limitée.

Quels objets emporter pour maximiser la valeur sans dépasser la capacité ?

Objet	Poids	Valeur	Valeur / poids
A	$5$	$60$	$12$
B	$4$	$40$	$10$
C	$6$	$54$	$9$
D	$3$	$24$	$8$

def sac_glouton(objets, capacite):
    """objets : tableau de dictionnaires {"nom", "poids", "valeur"}."""
    tries = sorted(objets, key=lambda o: o["valeur"] / o["poids"], reverse=True)
    pris = []
    poids_total = 0
    valeur_totale = 0
    for o in tries:
        if poids_total + o["poids"] <= capacite:
            pris.append(o["nom"])
            poids_total = poids_total + o["poids"]
            valeur_totale = valeur_totale + o["valeur"]
    return pris, valeur_totale

objets = [
    {"nom": "A", "poids": 5, "valeur": 60},
    {"nom": "B", "poids": 4, "valeur": 40},
    {"nom": "C", "poids": 6, "valeur": 54},
    {"nom": "D", "poids": 3, "valeur": 24},
]
print(sac_glouton(objets, 10))

Avec une capacité de $10$ , le glouton prend A puis B ( $9$ kg) : ni C ni D ne tiennent ensuite. La valeur obtenue, $100$ , est ici la meilleure possible.

3.4 Quand utiliser un glouton

Un glouton donne une solution rapide (un tri, puis un parcours) et souvent bonne.

Il est optimal quand la structure du problème s'y prête : monnaie européenne, certains problèmes de planification.

Sinon, il fournit une approximation utile. Trouver l'optimum exige alors d'autres méthodes, vues en terminale : exploration exhaustive, programmation dynamique.

4. Exemple résolu pas à pas

Cherche sur papier, puis vérifie tes réponses avec les blocs exécutables du cours.

Correction · Question a

Tour $1$ : debut = 0, fin = 8, m = 4, et t[4] = 27 < 40, donc debut = 5.
Tour $2$ : m = 6, et t[6] = 40 : trouvé à l'index $6$ , en $2$ tours.
Pour $n = 1\,000$ : $2^{10} = 1\,024 \geq 1\,000$ , donc au plus $10$ tours.

Correction · Question b

Distances à $(2, 2)$ : $(1,1)$ donne $\sqrt{2} \approx 1{,}41$ ; $(2,1)$ donne $1$ ; $(5,4)$ donne $\sqrt{13} \approx 3{,}61$ ; $(6,5)$ donne $5$ ; $(3,3)$ donne $\sqrt{2} \approx 1{,}41$ .
Les $3$ plus proches sont $(2,1)$ A, $(1,1)$ A et $(3,3)$ B.
Deux A contre un B : on prédit la classe A.

Correction · Question c

$48 \to 20$ (reste $28$ ) $\to 20$ (reste $8$ ) $\to 5$ (reste $3$ ) $\to 2$ (reste $1$ ) $\to 1$ .
Cinq pièces : $20 + 20 + 5 + 2 + 1$ . C'est optimal, car le système européen est canonique.

Correction · Question d

Glouton : $4$ , puis $1$ , puis $1$ , soit trois pièces.
Optimum : $3 + 3$ , soit deux pièces.
Le glouton n'est pas optimal pour ce système.

À retenir

Révise ce chapitre avec KlarIA

Tuteur qui t'explique pas à pas, quiz pour t'entraîner, flashcards pour mémoriser. Gratuit.

Créer mon compte gratuitement→

Besoin d'aide ?

Pose ta question gratuitement→