\documentclass[a4paper,11pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais,bloc,completemulti]{automultiplechoice}
\usepackage[french]{babel}
\usepackage{amsmath, amssymb}

\title{Invariants et terminaison}
\date{Numérique et sciences informatiques}

\begin{document}

\noindent\textbf{Invariants et terminaison} \hfill \textit{Numérique et sciences informatiques}\\[0.4em]
Nom~: \dotfill\ Prénom~: \dotfill

\bigskip

\element{premiereinvariantsterminaison}{
  \begin{question}{q01}
    Qu'est-ce qu'un \textbf{invariant de boucle} ?
    \begin{choices}
    \wrongchoice{Une exception levée pendant l'exécution de la boucle}
    \wrongchoice{Une variable dont la valeur ne change pas dans la boucle}
    \correctchoice{Une propriété vraie au début et conservée à chaque itération de la boucle}
    \wrongchoice{Une boucle qui ne se termine pas}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q02}
    Qu'appelle-t-on \textbf{terminaison} d'un algorithme ?
    \begin{choices}
    \wrongchoice{Une variable globale nommée \texttt{fin}}
    \wrongchoice{Le moment où l'utilisateur appuie sur Ctrl+C}
    \wrongchoice{Le nom donné à la dernière instruction}
    \correctchoice{La garantie que l'algorithme s'arrête après un nombre fini d'étapes, quelle que soit l'entrée}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q03}
    Pour prouver la terminaison d'une boucle \texttt{while},
on cherche un \textbf{variant}. Quelle propriété
doit-il avoir ?
    \begin{choices}
    \wrongchoice{Croître à chaque itération}
    \correctchoice{Être un entier (ou une quantité minorée) qui décroît strictement à chaque itération}
    \wrongchoice{Rester constant}
    \wrongchoice{Être une chaîne de caractères qui change}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q04}
    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} ?
    \begin{choices}
    \wrongchoice{La cible est plus grande que tous les éléments testés}
    \wrongchoice{La cible n'est dans aucune position de la liste}
    \wrongchoice{La liste est triée}
    \correctchoice{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{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q05}
    Pour une boucle \texttt{for i in range(n):}, est-il
nécessaire de prouver la terminaison ?
    \begin{choices}
    \wrongchoice{Oui, mais seulement lorsque $n$ est pair}
    \wrongchoice{Non, mais il faut prouver l'invariant}
    \correctchoice{Non, une boucle \texttt{for} sur un itérateur fini termine automatiquement}
    \wrongchoice{Oui, comme pour toute boucle}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q06}
    Invariant et variant : quelle est la différence
essentielle ?
    \begin{choices}
    \wrongchoice{Aucune, ce sont synonymes}
    \wrongchoice{Les deux servent à compter les opérations}
    \correctchoice{L'invariant prouve la correction, le variant prouve la terminaison}
    \wrongchoice{L'invariant est de nature mathématique, le variant est de nature physique}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q07}
    \begin{lstlisting}
somme = 0
for x in liste:
    somme += x
\end{lstlisting}
Quel est l'invariant après k itérations ?
    \begin{choices}
    \wrongchoice{\texttt{somme = 0}}
    \wrongchoice{\texttt{somme > 0}}
    \wrongchoice{\texttt{somme = liste[0]}}
    \correctchoice{\texttt{somme = somme des k premiers éléments de liste}}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q08}
    \begin{lstlisting}
n = 10
while n > 0:
    n -= 1
\end{lstlisting}
Quel est un variant valide ?
    \begin{choices}
    \correctchoice{\texttt{n} lui-même}
    \wrongchoice{La constante 10}
    \wrongchoice{La chaîne \texttt{"hello"}}
    \wrongchoice{Le booléen \texttt{n > 0}}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q09}
    \begin{lstlisting}
i = 0
while i < 10:
    print(i)
\end{lstlisting}
Pourquoi cette boucle ne termine-t-elle pas ?
    \begin{choices}
    \wrongchoice{Parce que \texttt{print} est interdit}
    \correctchoice{Parce que \texttt{i} n'est jamais modifié : il n'y a pas de variant qui décroît}
    \wrongchoice{Parce que 10 n'est pas un entier}
    \wrongchoice{Parce que Python est lent}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q10}
    Pourquoi prouver la correction d'un algorithme
au lieu de simplement le tester ?
    \begin{choices}
    \wrongchoice{Parce que les preuves sont plus rapides à écrire}
    \correctchoice{Parce qu'aucun nombre fini de tests ne couvre tous les cas possibles ; une preuve garantit la correction sur toutes les entrées valides}
    \wrongchoice{Parce que c'est obligatoire en cours}
    \wrongchoice{Parce que les tests sont chers}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q11}
    Une preuve d'invariant comporte combien
d'étapes ?
    \begin{choices}
    \wrongchoice{Aucune, une preuve d'invariant est implicite}
    \correctchoice{Trois : initialisation, hérédité (préservation), terminaison}
    \wrongchoice{Une seule}
    \wrongchoice{Cinq}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q12}
    \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 ?
    \begin{choices}
    \wrongchoice{\texttt{m == liste[0]}}
    \wrongchoice{\texttt{m == len(liste)}}
    \correctchoice{\texttt{m} est le minimum des k premiers éléments parcourus}
    \wrongchoice{\texttt{m == 0}}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q13}
    Pour la \textbf{recherche dichotomique} itérative,
quel est le variant le plus naturel ?
    \begin{choices}
    \wrongchoice{Le compteur d'itérations}
    \wrongchoice{La longueur de la liste}
    \correctchoice{La taille de l'intervalle de recherche : \texttt{d - g + 1}}
    \wrongchoice{La cible}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q14}
    \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 ?
    \begin{choices}
    \wrongchoice{Non, car n = 5 fait boucler}
    \wrongchoice{Oui, car n décroît à chaque tour}
    \wrongchoice{Oui, parce que Python le détecterait}
    \correctchoice{La terminaison n'est pas connue : c'est la fameuse conjecture de Syracuse (Collatz), non démontrée}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q15}
    Que sont les \textbf{préconditions} et
\textbf{postconditions} d'une fonction ?
    \begin{choices}
    \correctchoice{La précondition est ce que la fonction suppose sur ses arguments ; la postcondition est ce qu'elle garantit sur le résultat}
    \wrongchoice{Des décorateurs Python}
    \wrongchoice{Le code situé avant et après l'appel à la fonction}
    \wrongchoice{Des commentaires inutiles}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q16}
    Pourquoi le variant doit-il décroître
\textbf{strictement} (et pas seulement « ne pas
augmenter ») ?
    \begin{choices}
    \wrongchoice{Parce que la preuve serait plus longue à rédiger sinon}
    \correctchoice{Parce qu'une suite d'entiers minorée et qui ne décroît pas strictement peut stagner indéfiniment}
    \wrongchoice{Pour rendre la démonstration plus élégante visuellement}
    \wrongchoice{Parce que Python l'exige}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q17}
    Dans le tri par sélection, après la k-ème
itération de la boucle externe, quel est
l'invariant ?
    \begin{choices}
    \correctchoice{Les k premiers éléments sont triés et plus petits que tous les autres}
    \wrongchoice{La liste est entièrement triée}
    \wrongchoice{Les k premiers éléments sont les plus grands}
    \wrongchoice{La liste est inchangée}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q18}
    Pour la dichotomie itérative, peut-on choisir
\texttt{g} (l'indice de gauche) seul comme variant ?
    \begin{choices}
    \wrongchoice{Oui, parfait}
    \wrongchoice{Non, parce que \texttt{g} n'est pas un entier}
    \correctchoice{Non, parce que \texttt{g} ne décroît pas (il augmente ou reste constant)}
    \wrongchoice{Oui, mais seulement si la liste est triée}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q19}
    Pour qu'un invariant soit utile à la preuve,
il faut qu'il soit :
    \begin{choices}
    \wrongchoice{Long et compliqué}
    \wrongchoice{Toujours faux}
    \wrongchoice{Codé dans Python}
    \correctchoice{Vrai à l'initialisation et suffisamment fort pour impliquer la postcondition au moment de la sortie}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q20}
    Quel outil aide à \textbf{détecter} un bug dans un
invariant ?
    \begin{choices}
    \wrongchoice{Un débogueur visuel}
    \wrongchoice{Un commentaire \texttt{\# TODO}}
    \correctchoice{Un \texttt{assert} placé dans la boucle pour vérifier l'invariant à l'exécution}
    \wrongchoice{La fonction \texttt{print()}}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q21}
    Pour le tri par sélection, l'invariant
« les k premiers éléments sont triés » est-il
suffisant ?
    \begin{choices}
    \wrongchoice{Oui, à condition d'utiliser un tri stable}
    \wrongchoice{Oui, à condition que la liste soit triée à l'avance}
    \wrongchoice{Oui, c'est suffisant}
    \correctchoice{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{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q22}
    \begin{lstlisting}
while a > b:
    a = a - b
\end{lstlisting}
(avec \texttt{a, b} entiers, \texttt{b > 0}). Quel est un
variant valide ?
    \begin{choices}
    \correctchoice{\texttt{a} (qui décroît strictement à chaque tour, et est minoré par \texttt{b} à la sortie)}
    \wrongchoice{La constante 1}
    \wrongchoice{\texttt{b}}
    \wrongchoice{\texttt{a - b}}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q23}
    Pourquoi la preuve d'un invariant fait-elle
penser à une \textbf{preuve par récurrence} ?
    \begin{choices}
    \wrongchoice{Parce que les deux utilisent des indices}
    \wrongchoice{Aucun rapport entre les deux}
    \correctchoice{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}
    \wrongchoice{Parce que c'est imposé par les règles du langage}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q24}
    \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 ?
    \begin{choices}
    \wrongchoice{La boucle compte de 1 à N}
    \wrongchoice{\texttt{r} est toujours 0}
    \correctchoice{\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).}
    \wrongchoice{La boucle ne termine pas}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q25}
    Parmi les affirmations suivantes sur les
invariants et la terminaison, laquelle est
\textbf{fausse} ?
    \begin{choices}
    \correctchoice{Un programme correct est nécessairement un programme qui termine}
    \wrongchoice{Un variant doit être un entier (ou une quantité minorée) qui décroît strictement}
    \wrongchoice{Un invariant doit être vrai à chaque entrée d'itération}
    \wrongchoice{Toute boucle \texttt{for i in range(n)} se termine, sans qu'on ait besoin de prouver de variant}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q26}
    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 ?
    \begin{choices}
    \correctchoice{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}
    \wrongchoice{La liste est entièrement triée}
    \wrongchoice{Les \texttt{i} premiers éléments sont les plus grands}
    \wrongchoice{Les \texttt{i} premiers éléments sont triés et plus petits que tous les autres}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q27}
    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 ?
    \begin{choices}
    \correctchoice{La valeur de \texttt{b}}
    \wrongchoice{Le PGCD lui-même}
    \wrongchoice{La somme \texttt{a + b}}
    \wrongchoice{La valeur de \texttt{a}}
    \end{choices}
  \end{question}
}

\element{premiereinvariantsterminaison}{
  \begin{question}{q28}
    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 ?
    \begin{choices}
    \wrongchoice{Un commentaire \texttt{\# vérification de l'invariant}}
    \correctchoice{Une instruction \texttt{assert} exprimant l'invariant attendu, par exemple \texttt{assert somme == sum(liste[:i+1])}}
    \wrongchoice{Une exception \texttt{try/except} autour de la boucle}
    \wrongchoice{Un appel à \texttt{print} affichant la valeur courante de la variable}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{premiereinvariantsterminaison}
  \insertgroup{premiereinvariantsterminaison}
}

\end{document}
