\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{Invariants et terminaison}
\subtitle{QCM}
\author{Première}
\date{\today}

\begin{document}

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

% Q1 - Réponse en C
\begin{frame}[fragile]{Question 1 \textemdash{} Invariant de boucle}
    Qu'est-ce qu'un \textbf{invariant de boucle} ?\medskip
    \begin{itemize}
        \item[A.] Une exception levée pendant l'exécution de la boucle
        \item[B.] Une variable dont la valeur ne change pas dans la boucle
        \item[\alert<2>{C.}] \alert<2>{Une propriété vraie au début et conservée à chaque itération de la boucle}
        \item[D.] Une boucle qui ne se termine pas
    \end{itemize}
\end{frame}

% Q2 - Réponse en D
\begin{frame}[fragile]{Question 2 \textemdash{} Terminaison}
    Qu'appelle-t-on \textbf{terminaison} d'un algorithme ?\medskip
    \begin{itemize}
        \item[A.] Une variable globale nommée \texttt{fin}
        \item[B.] Le moment où l'utilisateur appuie sur Ctrl+C
        \item[C.] Le nom donné à la dernière instruction
        \item[\alert<2>{D.}] \alert<2>{La garantie que l'algorithme s'arrête après un nombre fini d'étapes, quelle que soit l'entrée}
    \end{itemize}
\end{frame}

% Q3 - Réponse en B
\begin{frame}[fragile]{Question 3 \textemdash{} Variant de boucle}
    Pour prouver la terminaison d'une boucle \texttt{while},
on cherche un \textbf{variant}. Quelle propriété
doit-il avoir ?\medskip
    \begin{itemize}
        \item[A.] Croître à chaque itération
        \item[\alert<2>{B.}] \alert<2>{Être un entier (ou une quantité minorée) qui décroît strictement à chaque itération}
        \item[C.] Rester constant
        \item[D.] Être une chaîne de caractères qui change
    \end{itemize}
\end{frame}

% Q4 - Réponse en D
\begin{frame}[fragile]{Question 4 \textemdash{} Exemple : recherche linéaire}
    Dans une recherche linéaire avec \texttt{for i in
range(len(liste))}, quel est l'\textbf{invariant} à
l'entrée du tour \texttt{i} ?\medskip
    \begin{itemize}
        \item[A.] La cible est plus grande que tous les éléments testés
        \item[B.] La cible n'est dans aucune position de la liste
        \item[C.] La liste est triée
        \item[\alert<2>{D.}] \alert<2>{La cible n'a pas été trouvée dans \texttt{liste[0..i-1]} (notation algorithmique pour les éléments déjà parcourus ; en Python : \texttt{liste[:i]})}
    \end{itemize}
\end{frame}

% Q5 - Réponse en C
\begin{frame}[fragile]{Question 5 \textemdash{} Variant for vs while}
    Pour une boucle \texttt{for i in range(n):}, est-il
nécessaire de prouver la terminaison ?\medskip
    \begin{itemize}
        \item[A.] Oui, mais seulement lorsque $n$ est pair
        \item[B.] Non, mais il faut prouver l'invariant
        \item[\alert<2>{C.}] \alert<2>{Non, une boucle \texttt{for} sur un itérateur fini termine automatiquement}
        \item[D.] Oui, comme pour toute boucle
    \end{itemize}
\end{frame}

% Q6 - Réponse en C
\begin{frame}[fragile]{Question 6 \textemdash{} Distinction}
    Invariant et variant : quelle est la différence
essentielle ?\medskip
    \begin{itemize}
        \item[A.] Aucune, ce sont synonymes
        \item[B.] Les deux servent à compter les opérations
        \item[\alert<2>{C.}] \alert<2>{L'invariant prouve la correction, le variant prouve la terminaison}
        \item[D.] L'invariant est de nature mathématique, le variant est de nature physique
    \end{itemize}
\end{frame}

% Q7 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 7 \textemdash{} Invariant : somme}
    \begin{lstlisting}
somme = 0
for x in liste:
    somme += x
\end{lstlisting}
Quel est l'invariant après k itérations ?\medskip
    \begin{itemize}
        \item[A.] \texttt{somme = 0}
        \item[B.] \texttt{somme > 0}
        \item[C.] \texttt{somme = liste[0]}
        \item[D.] \texttt{somme = somme des k premiers éléments de liste}
    \end{itemize}
\end{frame}

% Q7 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 7 \textemdash{} Invariant : somme}
    \begin{lstlisting}
somme = 0
for x in liste:
    somme += x
\end{lstlisting}
Quel est l'invariant après k itérations ?\medskip
    \begin{itemize}
        \item[A.] \texttt{somme = 0}
        \item[B.] \texttt{somme > 0}
        \item[C.] \texttt{somme = liste[0]}
        \item[\alert{D.}] \alert{\texttt{somme = somme des k premiers éléments de liste}}
    \end{itemize}
\end{frame}

% Q8 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 8 \textemdash{} Variant simple}
    \begin{lstlisting}
n = 10
while n > 0:
    n -= 1
\end{lstlisting}
Quel est un variant valide ?\medskip
    \begin{itemize}
        \item[A.] \texttt{n} lui-même
        \item[B.] La constante 10
        \item[C.] La chaîne \texttt{"hello"}
        \item[D.] Le booléen \texttt{n > 0}
    \end{itemize}
\end{frame}

% Q8 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 8 \textemdash{} Variant simple}
    \begin{lstlisting}
n = 10
while n > 0:
    n -= 1
\end{lstlisting}
Quel est un variant valide ?\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{\texttt{n} lui-même}
        \item[B.] La constante 10
        \item[C.] La chaîne \texttt{"hello"}
        \item[D.] Le booléen \texttt{n > 0}
    \end{itemize}
\end{frame}

% Q9 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 9 \textemdash{} Boucle infinie}
    \begin{lstlisting}
i = 0
while i < 10:
    print(i)
\end{lstlisting}
Pourquoi cette boucle ne termine-t-elle pas ?\medskip
    \begin{itemize}
        \item[A.] Parce que \texttt{print} est interdit
        \item[B.] Parce que \texttt{i} n'est jamais modifié : il n'y a pas de variant qui décroît
        \item[C.] Parce que 10 n'est pas un entier
        \item[D.] Parce que Python est lent
    \end{itemize}
\end{frame}

% Q9 - Réponse en B
\begin{frame}[fragile,allowframebreaks]{Question 9 \textemdash{} Boucle infinie}
    \begin{lstlisting}
i = 0
while i < 10:
    print(i)
\end{lstlisting}
Pourquoi cette boucle ne termine-t-elle pas ?\medskip
    \begin{itemize}
        \item[A.] Parce que \texttt{print} est interdit
        \item[\alert{B.}] \alert{Parce que \texttt{i} n'est jamais modifié : il n'y a pas de variant qui décroît}
        \item[C.] Parce que 10 n'est pas un entier
        \item[D.] Parce que Python est lent
    \end{itemize}
\end{frame}

% Q10 - Réponse en B
\begin{frame}[fragile]{Question 10 \textemdash{} Pourquoi prouver ?}
    Pourquoi prouver la correction d'un algorithme
au lieu de simplement le tester ?\medskip
    \begin{itemize}
        \item[A.] Parce que les preuves sont plus rapides à écrire
        \item[\alert<2>{B.}] \alert<2>{Parce qu'aucun nombre fini de tests ne couvre tous les cas possibles ; une preuve garantit la correction sur toutes les entrées valides}
        \item[C.] Parce que c'est obligatoire en cours
        \item[D.] Parce que les tests sont chers
    \end{itemize}
\end{frame}

% Q11 - Réponse en B
\begin{frame}[fragile]{Question 11 \textemdash{} Trois étapes de preuve}
    Une preuve d'invariant comporte combien
d'étapes ?\medskip
    \begin{itemize}
        \item[A.] Aucune, une preuve d'invariant est implicite
        \item[\alert<2>{B.}] \alert<2>{Trois : initialisation, hérédité (préservation), terminaison}
        \item[C.] Une seule
        \item[D.] Cinq
    \end{itemize}
\end{frame}

% Q12 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 12 \textemdash{} Invariant : minimum}
    \begin{lstlisting}
m = liste[0]
for x in liste[1:]:
    if x < m:
        m = x
\end{lstlisting}
Quel est l'invariant après l'itération sur les
k premiers éléments ?\medskip
    \begin{itemize}
        \item[A.] \texttt{m == liste[0]}
        \item[B.] \texttt{m == len(liste)}
        \item[C.] \texttt{m} est le minimum des k premiers éléments parcourus
        \item[D.] \texttt{m == 0}
    \end{itemize}
\end{frame}

% Q12 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 12 \textemdash{} Invariant : minimum}
    \begin{lstlisting}
m = liste[0]
for x in liste[1:]:
    if x < m:
        m = x
\end{lstlisting}
Quel est l'invariant après l'itération sur les
k premiers éléments ?\medskip
    \begin{itemize}
        \item[A.] \texttt{m == liste[0]}
        \item[B.] \texttt{m == len(liste)}
        \item[\alert{C.}] \alert{\texttt{m} est le minimum des k premiers éléments parcourus}
        \item[D.] \texttt{m == 0}
    \end{itemize}
\end{frame}

% Q13 - Réponse en C
\begin{frame}[fragile]{Question 13 \textemdash{} Variant dichotomie}
    Pour la \textbf{recherche dichotomique} itérative,
quel est le variant le plus naturel ?\medskip
    \begin{itemize}
        \item[A.] Le compteur d'itérations
        \item[B.] La longueur de la liste
        \item[\alert<2>{C.}] \alert<2>{La taille de l'intervalle de recherche : \texttt{d - g + 1}}
        \item[D.] La cible
    \end{itemize}
\end{frame}

% Q14 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 14 \textemdash{} Bug par variant}
    \begin{lstlisting}
def f(n):
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
\end{lstlisting}
Cette boucle termine-t-elle pour tout n entier ≥ 1 ?\medskip
    \begin{itemize}
        \item[A.] Non, car n = 5 fait boucler
        \item[B.] Oui, car n décroît à chaque tour
        \item[C.] Oui, parce que Python le détecterait
        \item[D.] La terminaison n'est pas connue : c'est la fameuse conjecture de Syracuse (Collatz), non démontrée
    \end{itemize}
\end{frame}

% Q14 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 14 \textemdash{} Bug par variant}
    \begin{lstlisting}
def f(n):
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
\end{lstlisting}
Cette boucle termine-t-elle pour tout n entier ≥ 1 ?\medskip
    \begin{itemize}
        \item[A.] Non, car n = 5 fait boucler
        \item[B.] Oui, car n décroît à chaque tour
        \item[C.] Oui, parce que Python le détecterait
        \item[\alert{D.}] \alert{La terminaison n'est pas connue : c'est la fameuse conjecture de Syracuse (Collatz), non démontrée}
    \end{itemize}
\end{frame}

% Q15 - Réponse en A
\begin{frame}[fragile]{Question 15 \textemdash{} Pré et post-conditions}
    Que sont les \textbf{préconditions} et
\textbf{postconditions} d'une fonction ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{La précondition est ce que la fonction suppose sur ses arguments ; la postcondition est ce qu'elle garantit sur le résultat}
        \item[B.] Des décorateurs Python
        \item[C.] Le code situé avant et après l'appel à la fonction
        \item[D.] Des commentaires inutiles
    \end{itemize}
\end{frame}

% Q16 - Réponse en B
\begin{frame}[fragile]{Question 16 \textemdash{} Décroissance stricte}
    Pourquoi le variant doit-il décroître
\textbf{strictement} (et pas seulement « ne pas
augmenter ») ?\medskip
    \begin{itemize}
        \item[A.] Parce que la preuve serait plus longue à rédiger sinon
        \item[\alert<2>{B.}] \alert<2>{Parce qu'une suite d'entiers minorée et qui ne décroît pas strictement peut stagner indéfiniment}
        \item[C.] Pour rendre la démonstration plus élégante visuellement
        \item[D.] Parce que Python l'exige
    \end{itemize}
\end{frame}

% Q17 - Réponse en A
\begin{frame}[fragile]{Question 17 \textemdash{} Invariant : tri par sélection}
    Dans le tri par sélection, après la k-ème
itération de la boucle externe, quel est
l'invariant ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Les k premiers éléments sont triés et plus petits que tous les autres}
        \item[B.] La liste est entièrement triée
        \item[C.] Les k premiers éléments sont les plus grands
        \item[D.] La liste est inchangée
    \end{itemize}
\end{frame}

% Q18 - Réponse en C
\begin{frame}[fragile]{Question 18 \textemdash{} Variant multivarié}
    Pour la dichotomie itérative, peut-on choisir
\texttt{g} (l'indice de gauche) seul comme variant ?\medskip
    \begin{itemize}
        \item[A.] Oui, parfait
        \item[B.] Non, parce que \texttt{g} n'est pas un entier
        \item[\alert<2>{C.}] \alert<2>{Non, parce que \texttt{g} ne décroît pas (il augmente ou reste constant)}
        \item[D.] Oui, mais seulement si la liste est triée
    \end{itemize}
\end{frame}

% Q19 - Réponse en D
\begin{frame}[fragile]{Question 19 \textemdash{} Bonne formulation}
    Pour qu'un invariant soit utile à la preuve,
il faut qu'il soit :\medskip
    \begin{itemize}
        \item[A.] Long et compliqué
        \item[B.] Toujours faux
        \item[C.] Codé dans Python
        \item[\alert<2>{D.}] \alert<2>{Vrai à l'initialisation et suffisamment fort pour impliquer la postcondition au moment de la sortie}
    \end{itemize}
\end{frame}

% Q20 - Réponse en C
\begin{frame}[fragile]{Question 20 \textemdash{} Outils}
    Quel outil aide à \textbf{détecter} un bug dans un
invariant ?\medskip
    \begin{itemize}
        \item[A.] Un débogueur visuel
        \item[B.] Un commentaire \texttt{\# TODO}
        \item[\alert<2>{C.}] \alert<2>{Un \texttt{assert} placé dans la boucle pour vérifier l'invariant à l'exécution}
        \item[D.] La fonction \texttt{print()}
    \end{itemize}
\end{frame}

% Q21 - Réponse en D
\begin{frame}[fragile]{Question 21 \textemdash{} Invariant insuffisant}
    Pour le tri par sélection, l'invariant
« les k premiers éléments sont triés » est-il
suffisant ?\medskip
    \begin{itemize}
        \item[A.] Oui, à condition d'utiliser un tri stable
        \item[B.] Oui, à condition que la liste soit triée à l'avance
        \item[C.] Oui, c'est suffisant
        \item[\alert<2>{D.}] \alert<2>{Non, il manque la condition que ces éléments soient plus petits que ceux de \texttt{liste[k..n-1]} (en Python : \texttt{liste[k:]})}
    \end{itemize}
\end{frame}

% Q22 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 22 \textemdash{} Trouver le variant}
    \begin{lstlisting}
while a > b:
    a = a - b
\end{lstlisting}
(avec \texttt{a, b} entiers, \texttt{b > 0}). Quel est un
variant valide ?\medskip
    \begin{itemize}
        \item[A.] \texttt{a} (qui décroît strictement à chaque tour, et est minoré par \texttt{b} à la sortie)
        \item[B.] La constante 1
        \item[C.] \texttt{b}
        \item[D.] \texttt{a - b}
    \end{itemize}
\end{frame}

% Q22 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 22 \textemdash{} Trouver le variant}
    \begin{lstlisting}
while a > b:
    a = a - b
\end{lstlisting}
(avec \texttt{a, b} entiers, \texttt{b > 0}). Quel est un
variant valide ?\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{\texttt{a} (qui décroît strictement à chaque tour, et est minoré par \texttt{b} à la sortie)}
        \item[B.] La constante 1
        \item[C.] \texttt{b}
        \item[D.] \texttt{a - b}
    \end{itemize}
\end{frame}

% Q23 - Réponse en C
\begin{frame}[fragile]{Question 23 \textemdash{} Preuve par récurrence}
    Pourquoi la preuve d'un invariant fait-elle
penser à une \textbf{preuve par récurrence} ?\medskip
    \begin{itemize}
        \item[A.] Parce que les deux utilisent des indices
        \item[B.] Aucun rapport entre les deux
        \item[\alert<2>{C.}] \alert<2>{Parce qu'on prouve l'invariant à la 1ʳᵉ itération (initialisation), puis qu'on prouve qu'il est conservé d'une itération à la suivante (hérédité), exactement comme une récurrence sur le numéro d'itération}
        \item[D.] Parce que c'est imposé par les règles du langage
    \end{itemize}
\end{frame}

% Q24 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 24 \textemdash{} Inventer l'invariant}
    \begin{lstlisting}
r = 0
n = N
while n > 0:
    n = n // 2
    r = r + 1
\end{lstlisting}
Que calcule cette boucle, et quel invariant
rend ce calcul évident ?\medskip
    \begin{itemize}
        \item[A.] La boucle compte de 1 à N
        \item[B.] \texttt{r} est toujours 0
        \item[C.] \texttt{r} compte le nombre d'itérations ; à la fin, \texttt{r} ≈ ⌊log₂(N)⌋ + 1. Invariant : \texttt{2\textasciicircum{}r * n ≥ N} (avant l'itération courante).
        \item[D.] La boucle ne termine pas
    \end{itemize}
\end{frame}

% Q24 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 24 \textemdash{} Inventer l'invariant}
    \begin{lstlisting}
r = 0
n = N
while n > 0:
    n = n // 2
    r = r + 1
\end{lstlisting}
Que calcule cette boucle, et quel invariant
rend ce calcul évident ?\medskip
    \begin{itemize}
        \item[A.] La boucle compte de 1 à N
        \item[B.] \texttt{r} est toujours 0
        \item[\alert{C.}] \alert{\texttt{r} compte le nombre d'itérations ; à la fin, \texttt{r} ≈ ⌊log₂(N)⌋ + 1. Invariant : \texttt{2\textasciicircum{}r * n ≥ N} (avant l'itération courante).}
        \item[D.] La boucle ne termine pas
    \end{itemize}
\end{frame}

% Q25 - Réponse en A
\begin{frame}[fragile]{Question 25 \textemdash{} Synthèse}
    Parmi les affirmations suivantes sur les
invariants et la terminaison, laquelle est
\textbf{fausse} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Un programme correct est nécessairement un programme qui termine}
        \item[B.] Un variant doit être un entier (ou une quantité minorée) qui décroît strictement
        \item[C.] Un invariant doit être vrai à chaque entrée d'itération
        \item[D.] Toute boucle \texttt{for i in range(n)} se termine, sans qu'on ait besoin de prouver de variant
    \end{itemize}
\end{frame}

% Q26 - Réponse en A
\begin{frame}[fragile]{Question 26 \textemdash{} Invariant : tri par insertion}
    Dans le tri par insertion, après l'itération
\texttt{i} de la boucle externe, quel invariant
caractérise correctement l'état de la liste ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{La sous-liste \texttt{liste[0..i]} (en Python : \texttt{liste[:i+1]}) contient les mêmes éléments qu'au début, mais elle est triée}
        \item[B.] La liste est entièrement triée
        \item[C.] Les \texttt{i} premiers éléments sont les plus grands
        \item[D.] Les \texttt{i} premiers éléments sont triés et plus petits que tous les autres
    \end{itemize}
\end{frame}

% Q27 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 27 \textemdash{} Terminaison de l'algorithme d'Euclide}
    L'algorithme d'Euclide pour le PGCD s'écrit :
\begin{lstlisting}
def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
\end{lstlisting}
(avec \texttt{a, b} entiers naturels, \texttt{b > 0} à
l'entrée). Quel est un variant qui prouve la
terminaison ?\medskip
    \begin{itemize}
        \item[A.] La valeur de \texttt{b}
        \item[B.] Le PGCD lui-même
        \item[C.] La somme \texttt{a + b}
        \item[D.] La valeur de \texttt{a}
    \end{itemize}
\end{frame}

% Q27 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 27 \textemdash{} Terminaison de l'algorithme d'Euclide}
    L'algorithme d'Euclide pour le PGCD s'écrit :
\begin{lstlisting}
def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
\end{lstlisting}
(avec \texttt{a, b} entiers naturels, \texttt{b > 0} à
l'entrée). Quel est un variant qui prouve la
terminaison ?\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{La valeur de \texttt{b}}
        \item[B.] Le PGCD lui-même
        \item[C.] La somme \texttt{a + b}
        \item[D.] La valeur de \texttt{a}
    \end{itemize}
\end{frame}

% Q28 - Réponse en B
\begin{frame}[fragile]{Question 28 \textemdash{} Assertion d'invariant en pratique}
    On suspecte qu'une boucle calcule mal une
somme. Quel ajout permet de \textbf{détecter
automatiquement} une violation d'invariant
pendant l'exécution ?\medskip
    \begin{itemize}
        \item[A.] Un commentaire \texttt{\# vérification de l'invariant}
        \item[\alert<2>{B.}] \alert<2>{Une instruction \texttt{assert} exprimant l'invariant attendu, par exemple \texttt{assert somme == sum(liste[:i+1])}}
        \item[C.] Une exception \texttt{try/except} autour de la boucle
        \item[D.] Un appel à \texttt{print} affichant la valeur courante de la variable
    \end{itemize}
\end{frame}

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

\end{document}
