Adloun

informatique (MP2I/MPI) · Chapitre 26 · Application directe du cours

Problème — Des plus proches voisins au choix de

Apprentissage automatique · niveau 3 (difficile)

Énoncé

Le cours écrit knn en supposant deux fonctions prendre et majoritaire.

  • Les écrire, avec leurs spécifications.
  • Le cours annonce une complexité en . Est-elle atteinte par le code tel qu'il est écrit ? Sinon, corriger.
  • Comment choisir sans tricher ?
  • Que coûte la prédiction si l'on ne veut que les plus proches, et non l'ordre complet ?

Corrigé de la question 1

1. Les deux fonctions manquantes.


(* Les k premiers éléments de l, ou l entière si elle est plus courte.
   Précondition : k >= 0. Terminaison : k décroît strictement, ou l se vide.
   Complexité : Theta(min(k, |l|)). *)
let rec prendre k l = match k, l with
  | 0, _ | _, [] -> []
  | k, x :: r -> x :: prendre (k - 1) r

(* Étiquette majoritaire d'une liste de booléens ; None en cas d'égalité.
   Précondition : l non vide. Complexité : Theta(|l|). *)
let majoritaire l =
  let o = List.length (List.filter (fun b -> b) l) in
  let n = List.length l in
  if 2 * o > n then Some true else if 2 * o < n then Some false else None

Le type de retour bool option n'est pas une coquetterie : c'est l'égalité de l'exercice 26.2, rendue visible dans le type. Une fonction qui renverrait bool devrait inventer une réponse, et l'appelant ne saurait jamais qu'elle a été inventée. C'est la discipline du chapitre chap:abstraction : ce qui peut échouer le dit dans sa signature.

Question 2 : comment l'IA t'aide

2. Le cours annonce une complexité en . Est-elle atteinte par le code tel qu'il est écrit ? Sinon, corriger.

Élève

Le code calcule les distances puis trie : distances en chacune, plus un tri en . Je retrouve donc la complexité annoncée, alors que l'énoncé laisse entendre le contraire.

IA

Regarde où la distance est calculée dans le code du cours : avant le tri, ou à l'intérieur de la fonction de comparaison passée à List.sort ? Combien de fois cette fonction est-elle appelée pendant un tri ?

Élève

Elle est dans le comparateur, et un tri fait de l'ordre de comparaisons. Chaque comparaison recalcule donc des distances, en chacune.

IA

Quel coût total obtiens-tu alors ? Et comment modifier le code pour que le tri ne paie plus ce surcoût, sans changer d'algorithme de tri ?

L'IA ne donne pas la réponse : elle pose la question qui fait avancer. À toi de continuer.

Continue cet exercice avec l'IA

Reprends la question 2 là où le dialogue s'arrête, puis la suite de l'exercice.

Continuer avec l'IA — gratuit, sans inscription

Gratuit, sans inscription. L'IA te guide pas à pas, sans te donner la réponse.

Le cours du chapitre · Tous les exercices du chapitre

Continuer avec l'IA, gratuit →