\documentclass[10pt,aspectratio=169]{beamer}

% --- Thème ---
\usetheme[language=french]{Celestia}

% Avec [allowframebreaks] sur les frames de questions, Beamer ajoute
% par défaut « (1) », « (2) », « (3) »... sur chaque sous-slide. On
% supprime entièrement cette annotation : un template vide pour
% « frametitle continuation ». L'enseignant identifie visuellement la
% continuation par le contenu de la slide. (Les variantes [from second]
% et [roman] interagissent mal avec un titre contenant \textemdash{}
% sous Celestia : elles déclenchent une erreur « Missing $ inserted ».)
\setbeamertemplate{frametitle continuation}{}

\subject{Numérique et sciences informatiques}
\title{k plus proches voisins (k-NN)}
\subtitle{QCM}
\author{Première}
\date{\today}

\begin{document}

\begin{frame}
    \titlepage
\end{frame}

% Q1 - Réponse en A
\begin{frame}[fragile]{Question 1 \textemdash{} k-NN : qu'est-ce que c'est ?}
    Que fait l'algorithme des \textbf{k plus proches voisins}
(k-NN, \textit{k-Nearest Neighbors}) ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Prédit la classe d'un nouvel élément en regardant les classes des k éléments les plus proches dans un jeu de données déjà étiqueté}
        \item[B.] Mesure la complexité d'un programme
        \item[C.] Cherche un élément dans une liste triée
        \item[D.] Trie une liste par ordre croissant
    \end{itemize}
\end{frame}

% Q2 - Réponse en D
\begin{frame}[fragile]{Question 2 \textemdash{} Apprentissage supervisé}
    Pourquoi parle-t-on d'apprentissage
\textbf{supervisé} pour k-NN ?\medskip
    \begin{itemize}
        \item[A.] Parce qu'il est lent à l'exécution
        \item[B.] Parce qu'il ne fonctionne qu'avec un professeur dans la salle
        \item[C.] Parce qu'un humain doit surveiller le programme pendant son exécution
        \item[\alert<2>{D.}] \alert<2>{Parce que les données d'entraînement sont étiquetées : chaque exemple est associé à sa classe connue}
    \end{itemize}
\end{frame}

% Q3 - Réponse en A
\begin{frame}[fragile]{Question 3 \textemdash{} Distance euclidienne}
    Comment calcule-t-on la \textbf{distance euclidienne}
entre deux points $A=(x_A, y_A)$ et $B=(x_B,
y_B)$ du plan ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{$d = \sqrt{(x_B - x_A)^2 + (y_B - y_A)^2}$}
        \item[B.] $d = |x_A - x_B|$
        \item[C.] $d = x_A + y_A + x_B + y_B$
        \item[D.] $d = x_A \times y_A - x_B \times y_B$
    \end{itemize}
\end{frame}

% Q4 - Réponse en C
\begin{frame}[fragile]{Question 4 \textemdash{} Vote majoritaire}
    Une fois les k plus proches voisins
identifiés, comment k-NN détermine-t-il la
classe à attribuer ?\medskip
    \begin{itemize}
        \item[A.] Au hasard
        \item[B.] En choisissant la classe du voisin le plus proche
        \item[\alert<2>{C.}] \alert<2>{Par vote majoritaire : la classe la plus représentée parmi les k voisins l'emporte}
        \item[D.] En faisant la moyenne des classes
    \end{itemize}
\end{frame}

% Q5 - Réponse en A
\begin{frame}[fragile]{Question 5 \textemdash{} Choix de k}
    Pourquoi prend-on souvent k \textbf{impair} quand
on classe en deux classes ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Pour éviter les égalités lors du vote majoritaire entre deux classes}
        \item[B.] Aucune raison particulière
        \item[C.] Parce que les nombres impairs sont plus rapides à calculer
        \item[D.] Parce que k pair ne fonctionne pas
    \end{itemize}
\end{frame}

% Q6 - Réponse en C
\begin{frame}[fragile]{Question 6 \textemdash{} Exemple typique}
    Lequel de ces problèmes est un \textbf{bon candidat}
pour l'algorithme k-NN ?\medskip
    \begin{itemize}
        \item[A.] Compresser un fichier pour gagner de la place
        \item[B.] Trier une liste de nombres
        \item[\alert<2>{C.}] \alert<2>{Reconnaître si un mail est un spam ou non, à partir d'exemples étiquetés}
        \item[D.] Calculer la racine carrée d'un nombre
    \end{itemize}
\end{frame}

% Q7 - Réponse en A
\begin{frame}[fragile]{Question 7 \textemdash{} Pas d'entraînement explicite}
    Quelle particularité de k-NN le distingue
d'autres algorithmes d'apprentissage ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Il n'a quasiment pas de phase d'entraînement : il mémorise les exemples et fait tout le calcul au moment de la prédiction}
        \item[B.] Il fonctionne sans aucune donnée d'entraînement
        \item[C.] Il a une phase d'entraînement très longue
        \item[D.] Il invente de nouveaux exemples au cours de la prédiction
    \end{itemize}
\end{frame}

% Q8 - Réponse en A
\begin{frame}[fragile]{Question 8 \textemdash{} Squelette de l'algorithme}
    Quelle est la \textbf{structure générale} de
l'algorithme k-NN pour classer un nouveau
point \texttt{p} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{1. Calculer la distance de \texttt{p} à chaque exemple connu.
2. Trier les exemples par distance croissante.
3. Garder les k premiers.
4. Retourner la classe majoritaire parmi ces k voisins.
}
        \item[B.] 1. Trier les exemples par classe.
2. Retourner la première classe.

        \item[C.] 1. Choisir un exemple au hasard.
2. Retourner sa classe.

        \item[D.] 1. Calculer la moyenne des exemples.
2. La retourner comme classe.

    \end{itemize}
\end{frame}

% Q9 - Réponse en A
\begin{frame}[fragile]{Question 9 \textemdash{} Paramètre k}
    Que se passe-t-il si l'on prend \textbf{k = 1} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{La classe prédite est celle de l'unique voisin le plus proche, l'algorithme est très sensible aux exceptions (bruit) dans le jeu d'entraînement}
        \item[B.] La complexité du calcul devient logarithmique
        \item[C.] La prédiction est plus stable
        \item[D.] L'algorithme ne fonctionne pas avec $k = 1$
    \end{itemize}
\end{frame}

% Q10 - Réponse en C
\begin{frame}[fragile]{Question 10 \textemdash{} Trace simple}
    Avec k = 3, on classe un nouveau point P. Ses
3 plus proches voisins ont les classes : A, B,
A. Quelle classe prédit k-NN pour P ?\medskip
    \begin{itemize}
        \item[A.] Aucune des deux (égalité)
        \item[B.] B (le plus proche)
        \item[\alert<2>{C.}] \alert<2>{A (deux votes contre un pour B)}
        \item[D.] Les deux à la fois
    \end{itemize}
\end{frame}

% Q11 - Réponse en A
\begin{frame}[fragile]{Question 11 \textemdash{} Code distance}
    Quel code calcule correctement la \textbf{distance
euclidienne} entre deux points 2D représentés
comme tuples \texttt{a = (xa, ya)} et \texttt{b = (xb, yb)} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{\texttt{((a[0] - b[0])  2 + (a[1] - b[1])  2)  0.5}}
        \item[B.] \texttt{a[0] \textit{ b[0] + a[1] } b[1]}
        \item[C.] \texttt{a + b}
        \item[D.] \texttt{abs(a[0] - b[0]) + abs(a[1] - b[1])}
    \end{itemize}
\end{frame}

% Q12 - Réponse en A
\begin{frame}[fragile]{Question 12 \textemdash{} Sélection des voisins}
    Pour trouver les k plus proches voisins d'un
point P parmi N exemples, quelle approche est
la plus simple ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Calculer la distance à chacun des N exemples, trier, garder les k premiers}
        \item[B.] Aucune solution n'existe pour ce problème
        \item[C.] Choisir k exemples au hasard
        \item[D.] Calculer la moyenne des exemples
    \end{itemize}
\end{frame}

% Q13 - Réponse en A
\begin{frame}[fragile]{Question 13 \textemdash{} Pourquoi normaliser ?}
    Pourquoi est-il souvent \textbf{utile de normaliser}
les caractéristiques des données avant
d'appliquer k-NN ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Parce qu'une caractéristique avec une plage de valeurs très grande (ex. revenu en €) écraserait l'influence d'une caractéristique à plus petite plage (ex. âge en années) dans le calcul de distance}
        \item[B.] Pour rendre l'algorithme déterministe
        \item[C.] Pour économiser de la mémoire
        \item[D.] Parce que c'est obligatoire en Python
    \end{itemize}
\end{frame}

% Q14 - Réponse en D
\begin{frame}[fragile]{Question 14 \textemdash{} Compromis sur k}
    Quel \textbf{risque} y a-t-il à choisir un k \textbf{trop
grand} (par exemple k = nombre total
d'exemples) ?\medskip
    \begin{itemize}
        \item[A.] Aucun risque ; un grand $k$ est toujours préférable
        \item[B.] Le coût d'un calcul explose en $n^3$
        \item[C.] L'algorithme cesse de fonctionner
        \item[\alert<2>{D.}] \alert<2>{La prédiction tend vers la classe majoritaire globale : on perd toute spécificité locale}
    \end{itemize}
\end{frame}

% Q15 - Réponse en C
\begin{frame}[fragile]{Question 15 \textemdash{} Rôle des données d'entraînement}
    Que sont les \textbf{données d'entraînement}
(training set) pour k-NN ?\medskip
    \begin{itemize}
        \item[A.] Les nouvelles données à classer
        \item[B.] Une formule mathématique
        \item[\alert<2>{C.}] \alert<2>{L'ensemble des exemples étiquetés que k-NN utilise pour comparer un nouveau point. La taille et la qualité de ce jeu déterminent la performance.}
        \item[D.] Le code source de l'algorithme
    \end{itemize}
\end{frame}

% Q16 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 16 \textemdash{} Code k-NN simple}
    Quel code en Python implémente correctement
k-NN pour classer un point \texttt{p} ?
\begin{lstlisting}
# exemples = [(point, classe), ...]
# k entier, dist(a, b) renvoie la distance
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
return exemples[0][1]
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
return min(exemples)
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
return k
\end{lstlisting}

        \item[D.]~\\
\begin{lstlisting}
from collections import Counter
paires = [(dist(p, x), c) for (x, c) in exemples]
paires.sort()
voisins = [c for (_, c) in paires[:k]]
return Counter(voisins).most_common(1)[0][0]
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q16 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 16 \textemdash{} Code k-NN simple}
    Quel code en Python implémente correctement
k-NN pour classer un point \texttt{p} ?
\begin{lstlisting}
# exemples = [(point, classe), ...]
# k entier, dist(a, b) renvoie la distance
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.]~\\
\begin{lstlisting}
return exemples[0][1]
\end{lstlisting}

        \item[B.]~\\
\begin{lstlisting}
return min(exemples)
\end{lstlisting}

        \item[C.]~\\
\begin{lstlisting}
return k
\end{lstlisting}

        \item[\alert{D.}]~\\
\begin{lstlisting}
from collections import Counter
paires = [(dist(p, x), c) for (x, c) in exemples]
paires.sort()
voisins = [c for (_, c) in paires[:k]]
return Counter(voisins).most_common(1)[0][0]
\end{lstlisting}

    \end{itemize}
\end{frame}

% Q17 - Réponse en B
\begin{frame}[fragile]{Question 17 \textemdash{} Jeu de données Iris}
    Le jeu de données \textbf{Iris} est célèbre pour
illustrer la classification. Que contient-il ?\medskip
    \begin{itemize}
        \item[A.] Des mesures de couleurs au format rouge-vert-bleu
        \item[\alert<2>{B.}] \alert<2>{150 fleurs d'iris décrites par 4 mesures (longueur/largeur des sépales et pétales) et leur espèce (setosa, versicolor, virginica)}
        \item[C.] Des graines à planter
        \item[D.] Des images de fleurs au format JPEG
    \end{itemize}
\end{frame}

% Q18 - Réponse en B
\begin{frame}[fragile]{Question 18 \textemdash{} Coût de la prédiction}
    Si l'on a N exemples d'entraînement, quel est
le \textbf{coût} d'une prédiction k-NN naïve ?\medskip
    \begin{itemize}
        \item[A.] Logarithmique en N
        \item[\alert<2>{B.}] \alert<2>{Linéaire en N (proportionnel au nombre d'exemples)}
        \item[C.] Constant, indépendant de N
        \item[D.] Quadratique en N
    \end{itemize}
\end{frame}

% Q19 - Réponse en C
\begin{frame}[fragile]{Question 19 \textemdash{} Forces et limites}
    Quelle est une \textbf{limite importante} de k-NN ?\medskip
    \begin{itemize}
        \item[A.] Il ne peut pas faire de classification
        \item[B.] Il ne fonctionne qu'en dimension 2
        \item[\alert<2>{C.}] \alert<2>{Il est lent à la prédiction sur de gros jeux d'entraînement (pas de modèle compact appris) et sensible aux échelles des caractéristiques}
        \item[D.] Il invente de nouveaux exemples au cours de la prédiction
    \end{itemize}
\end{frame}

% Q20 - Réponse en A
\begin{frame}[fragile]{Question 20 \textemdash{} Vote pondéré}
    Une variante de k-NN consiste à \textbf{pondérer le
vote} des voisins. Pourquoi ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Pour donner plus d'influence aux voisins plus proches (typiquement avec un poids proportionnel à $1/d$)}
        \item[B.] Pour économiser la mémoire
        \item[C.] Pour rendre l'algorithme aléatoire
        \item[D.] Pour ralentir intentionnellement le programme
    \end{itemize}
\end{frame}

% Q21 - Réponse en A
\begin{frame}[fragile]{Question 21 \textemdash{} Trace détaillée}
    Avec k = 3, on classe un point P. Les 5
exemples les plus proches sont (par distance
croissante) : (1.0, classe A), (1.5, B), (2.0,
A), (3.0, A), (4.0, B). Quelle classe prédit
k-NN ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{A}
        \item[B.] B
        \item[C.] Indéterminé
        \item[D.] Égalité
    \end{itemize}
\end{frame}

% Q22 - Réponse en A
\begin{frame}[fragile]{Question 22 \textemdash{} Malédiction de la dimensionnalité}
    Pourquoi k-NN devient-il \textbf{moins efficace en
haute dimension} (par exemple 1000 attributs) ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{En haute dimension, les distances entre points deviennent presque toutes égales : la notion de « proche » perd son sens. C'est la malédiction de la dimensionnalité.}
        \item[B.] La mémoire n'est plus suffisante
        \item[C.] Aucun problème particulier en haute dimension
        \item[D.] Le programme plante systématiquement
    \end{itemize}
\end{frame}

% Q23 - Réponse en D
\begin{frame}[fragile]{Question 23 \textemdash{} Évaluation de la performance}
    Pour évaluer la qualité de k-NN sur un jeu
étiqueté, quelle est la \textbf{bonne pratique} ?\medskip
    \begin{itemize}
        \item[A.] Mesurer la précision sur les exemples d'entraînement eux-mêmes
        \item[B.] Aucune évaluation n'est possible
        \item[C.] Demander l'avis d'un expert humain
        \item[\alert<2>{D.}] \alert<2>{Séparer le jeu en données d'entraînement et données de test disjointes, puis mesurer la précision sur les données de test}
    \end{itemize}
\end{frame}

% Q24 - Réponse en D
\begin{frame}[fragile]{Question 24 \textemdash{} k-NN pour la régression}
    Peut-on adapter k-NN pour \textbf{prédire un nombre}
(régression) au lieu d'une classe ?\medskip
    \begin{itemize}
        \item[A.] Oui, mais à condition de doubler la valeur de $k$
        \item[B.] Non, l'algorithme est strictement limité à la classification
        \item[C.] Non, il faut nécessairement un autre algorithme
        \item[\alert<2>{D.}] \alert<2>{Oui, en remplaçant le vote majoritaire par la moyenne (ou médiane) des valeurs des k voisins}
    \end{itemize}
\end{frame}

% Q25 - Réponse en C
\begin{frame}[fragile]{Question 25 \textemdash{} Synthèse}
    Parmi les affirmations suivantes sur k-NN,
laquelle est \textbf{fausse} ?\medskip
    \begin{itemize}
        \item[A.] La phase d'entraînement se résume essentiellement à mémoriser les exemples.
        \item[B.] La distance euclidienne est un choix courant pour la mesure de proximité.
        \item[\alert<2>{C.}] \alert<2>{Plus k est grand, plus l'algorithme est sensible au bruit local.}
        \item[D.] k-NN est un algorithme d'apprentissage supervisé.
    \end{itemize}
\end{frame}

% Q26 - Réponse en C
\begin{frame}[fragile]{Question 26 \textemdash{} Choix de la distance}
    Outre la distance euclidienne, on rencontre
souvent la \textbf{distance de Manhattan}
(|Δx| + |Δy|). Quel critère permet de choisir
entre ces deux distances ?\medskip
    \begin{itemize}
        \item[A.] Aucun critère, on choisit au hasard
        \item[B.] La distance euclidienne est toujours préférable car elle est plus précise
        \item[\alert<2>{C.}] \alert<2>{Le choix dépend de la nature du problème :
la distance euclidienne convient aux
espaces continus avec des déplacements
directs ; la distance de Manhattan
convient aux situations où l'on se déplace
sur une grille (par exemple un quadrillage
urbain ou des composantes indépendantes)
}
        \item[D.] La distance de Manhattan est plus rapide à calculer
    \end{itemize}
\end{frame}

% Q27 - Réponse en C
\begin{frame}[fragile]{Question 27 \textemdash{} Classes déséquilibrées}
    On veut détecter une maladie rare avec k-NN.
Le jeu d'entraînement contient 95 % d'exemples
« sain » et 5 % d'exemples « malade ». Avec
k = 7, que va prédire l'algorithme pour
presque tous les nouveaux patients ?\medskip
    \begin{itemize}
        \item[A.] « malade » à 5 % des nouveaux patients, par symétrie
        \item[B.] Une classe au hasard, l'algorithme étant non déterministe
        \item[\alert<2>{C.}] \alert<2>{« sain » dans la quasi-totalité des cas,
car les voisins les plus proches sont
presque toujours majoritairement « sain » à
cause du déséquilibre des classes ;
l'algorithme passe à côté des cas
« malade »
}
        \item[D.] « malade » dans la majorité des cas, par sécurité
    \end{itemize}
\end{frame}

% Q28 - Réponse en D
\begin{frame}[fragile]{Question 28 \textemdash{} Calcul concret}
    On classe le point \texttt{P = (3, 4)} avec k = 3 et
la distance euclidienne. Les exemples
étiquetés sont :
\texttt{(0, 0, A)}, \texttt{(6, 8, A)}, \texttt{(2, 1, B)},
\texttt{(5, 4, B)}, \texttt{(3, 0, A)}. Quelle classe
prédit k-NN ?\medskip
    \begin{itemize}
        \item[A.] A
        \item[B.] Égalité entre A et B
        \item[C.] Indéterminé sans plus d'informations
        \item[\alert<2>{D.}] \alert<2>{B}
    \end{itemize}
\end{frame}

\begin{frame}[standout]{}
    Fin de l'évaluation
\end{frame}

\end{document}
