\documentclass[a4paper,11pt]{article}

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

\title{Calculabilité et décidabilité}
\date{Numérique et sciences informatiques}

\begin{document}

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

\bigskip

\element{terminalecalculabilite}{
  \begin{question}{q01}
    Pourquoi peut-on dire qu'\textbf{un programme est aussi une
donnée} ?
    \begin{choices}
    \wrongchoice{Cette affirmation est fausse}
    \wrongchoice{Parce qu'un programme contient toujours des données en entrée}
    \wrongchoice{Parce qu'il occupe de la mémoire vive}
    \correctchoice{Parce qu'un programme est stocké dans un fichier, manipulé, transmis et lu par d'autres programmes (compilateur, interpréteur, antivirus...) au même titre que n'importe quelle donnée}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q02}
    Lequel des exemples suivants illustre \textbf{un programme
manipulé comme une donnée} ?
    \begin{choices}
    \correctchoice{Un compilateur qui lit un fichier \texttt{.c} et produit un fichier exécutable}
    \wrongchoice{Un programme qui calcule un déterminant de matrice}
    \wrongchoice{Un programme qui affiche « Bonjour »}
    \wrongchoice{Un programme qui calcule la somme de deux nombres saisis par l'utilisateur}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q03}
    Que signifie qu'une fonction $f$ est \textbf{calculable}
au sens informatique ?
    \begin{choices}
    \wrongchoice{La fonction est continue}
    \wrongchoice{La fonction s'exécute en moins d'une seconde}
    \wrongchoice{La fonction renvoie toujours un entier}
    \correctchoice{Il existe un algorithme qui, pour toute entrée valide, calcule $f$ en un nombre fini d'étapes}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q04}
    Lequel des éléments suivants définit une fonction
\textbf{calculable} ?
    \begin{choices}
    \wrongchoice{Une fonction qui prend en entrée un programme et renvoie « oui » s'il s'arrête, « non » sinon}
    \wrongchoice{Une fonction qui à un texte associe « oui » s'il représente un programme correct}
    \wrongchoice{La fonction qui à un programme associe le nombre exact d'instructions qu'il exécutera dans tous les cas}
    \correctchoice{La fonction qui à un entier $n$ associe son carré $n^2$}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q05}
    Une fonction est calculable. Que peut-on en
déduire sur les langages de programmation ?
    \begin{choices}
    \wrongchoice{Le résultat de la fonction varie selon le langage utilisé}
    \wrongchoice{Elle ne peut être écrite qu'en Python}
    \correctchoice{Elle peut être implémentée dans n'importe quel langage de programmation universel (Python, C, Java, OCaml...)}
    \wrongchoice{Elle nécessite obligatoirement un langage récursif}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q06}
    Qu'appelle-t-on un \textbf{problème décidable} ?
    \begin{choices}
    \correctchoice{Un problème pour lequel il existe un algorithme qui répond toujours « oui » ou « non » en un nombre fini d'étapes, pour toute instance}
    \wrongchoice{Un problème dont la réponse est connue par avance}
    \wrongchoice{Un problème qui n'a pas de solution}
    \wrongchoice{Un problème facile à résoudre}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q07}
    Lequel de ces problèmes est clairement \textbf{décidable} ?
    \begin{choices}
    \wrongchoice{Étant donné un programme, dire s'il contient un bug logique}
    \wrongchoice{Étant donné un programme Python, dire s'il s'arrêtera sur l'entrée $0$}
    \correctchoice{Étant donné un entier $n$, déterminer s'il est divisible par $7$}
    \wrongchoice{Étant donné deux programmes, dire s'ils calculent la même fonction sur toute entrée}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q08}
    Qu'est-ce qu'un \textbf{problème indécidable} ?
    \begin{choices}
    \wrongchoice{Un problème qui demande beaucoup de mémoire}
    \wrongchoice{Un problème dont la réponse change selon la machine utilisée}
    \wrongchoice{Un problème difficile, qu'on n'a pas encore résolu}
    \correctchoice{Un problème de décision pour lequel il n'existe aucun algorithme qui, pour toute entrée, donne une réponse correcte en temps fini}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q09}
    Comment énonce-t-on le \textbf{problème de l'arrêt} ?
    \begin{choices}
    \wrongchoice{Comment savoir combien de temps un programme va s'exécuter ?}
    \wrongchoice{Comment arrêter un programme qui boucle sans fin ?}
    \wrongchoice{À quel moment faut-il interrompre une compilation ?}
    \correctchoice{Existe-t-il un algorithme qui, pour tout couple (programme, entrée), répond « oui » si le programme s'arrête sur cette entrée, « non » s'il boucle indéfiniment ?}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q10}
    Le problème de l'arrêt est :
    \begin{choices}
    \wrongchoice{Décidable, mais coûteux}
    \correctchoice{Indécidable}
    \wrongchoice{Décidable, et résolu par les antivirus}
    \wrongchoice{Inconnu de la communauté scientifique}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q11}
    L'argument classique de Turing pour montrer que
l'arrêt est indécidable consiste à supposer qu'on
possède un tel décideur, puis à :
    \begin{choices}
    \wrongchoice{Mesurer le temps d'exécution de tous les programmes possibles}
    \wrongchoice{Programmer le décideur en plusieurs langages et comparer}
    \correctchoice{Construire un programme qui « se contredit » lui-même en utilisant le décideur sur sa propre entrée}
    \wrongchoice{Réécrire les programmes en machine de Turing}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q12}
    Quelle conséquence pratique l'indécidabilité du
problème de l'arrêt a-t-elle sur le développement
logiciel ?
    \begin{choices}
    \wrongchoice{Plus aucun nouveau bug ne peut être trouvé}
    \correctchoice{On ne peut pas écrire un programme qui détecte toutes les boucles infinies dans n'importe quel autre programme}
    \wrongchoice{Les ordinateurs ne peuvent pas exécuter de programmes}
    \wrongchoice{Les langages modernes ne contiennent plus jamais de boucles infinies}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q13}
    Quelle est la différence entre \textbf{calculable} et
\textbf{décidable} ?
    \begin{choices}
    \wrongchoice{« Calculable » signifie « facile », « décidable » signifie « difficile »}
    \wrongchoice{« Calculable » concerne les nombres, « décidable » concerne les chaînes}
    \correctchoice{« Calculable » s'applique aux fonctions, « décidable » aux problèmes de décision (à réponse oui/non)}
    \wrongchoice{Aucune différence, ce sont des synonymes}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q14}
    Pour \textbf{certains} programmes, on peut savoir
facilement s'ils s'arrêtent. Ce qui est
indécidable, c'est :
    \begin{choices}
    \correctchoice{De le faire pour tous les programmes possibles, avec un seul algorithme général}
    \wrongchoice{De le faire pour les programmes écrits en Python}
    \wrongchoice{De le faire en moins d'une heure}
    \wrongchoice{De le faire pour les programmes courts}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q15}
    L'idée d'\textbf{ordinateur universel} repose sur
laquelle des affirmations suivantes ?
    \begin{choices}
    \correctchoice{Un même dispositif peut exécuter n'importe quel programme, à condition de lui fournir le code de ce programme en entrée}
    \wrongchoice{Tous les programmes peuvent s'écrire sans boucles}
    \wrongchoice{Tous les ordinateurs ont le même processeur}
    \wrongchoice{Tout calcul peut s'effectuer instantanément}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q16}
    On peut écrire un interpréteur Python en Python
(par exemple via la fonction \texttt{exec}). Que
montre cet exemple ?
    \begin{choices}
    \wrongchoice{Que Python est plus rapide que les autres langages}
    \wrongchoice{Que \texttt{exec} rend Python incalculable}
    \wrongchoice{Que \texttt{exec} est une fonction obsolète}
    \correctchoice{Qu'un programme peut prendre un autre programme comme donnée et l'exécuter, illustrant la dualité programme/donnée}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q17}
    Pourquoi est-il \textbf{impossible} d'écrire un
antivirus parfait qui détecterait tous les
logiciels malveillants sans aucune erreur ?
    \begin{choices}
    \wrongchoice{Parce que les antivirus sont mal programmés}
    \correctchoice{Parce que reconnaître précisément le comportement d'un programme arbitraire est lié au problème de l'arrêt, qui est indécidable}
    \wrongchoice{Parce que les antivirus sont trop lents}
    \wrongchoice{Parce que les antivirus ne peuvent pas analyser un fichier}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q18}
    Parmi les problèmes suivants, lesquels sont
\textbf{décidables} ? Sélectionnez la proposition
correcte.
    \begin{choices}
    \wrongchoice{Les trois sont décidables}
    \correctchoice{« Cet entier est-il premier ? » et « cette chaîne contient-elle un point d'interrogation ? » sont décidables ; « ce programme s'arrête-t-il ? » ne l'est pas}
    \wrongchoice{Aucun de ces problèmes n'est décidable}
    \wrongchoice{Tous les problèmes énoncés en français sont décidables}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q19}
    Considérons le programme suivant qui prend en
entrée un entier $n > 0$ :

\begin{lstlisting}
while n != 1:
    if n % 2 == 0:
        n = n // 2
    else:
        n = 3 * n + 1
\end{lstlisting}

Que peut-on dire de sa \textbf{terminaison} ?
    \begin{choices}
    \correctchoice{Personne ne sait, à ce jour, démontrer qu'il termine pour tout $n$ positif (conjecture de Syracuse)}
    \wrongchoice{Il termine en au plus $100$ étapes}
    \wrongchoice{Il termine si et seulement si $n$ est pair}
    \wrongchoice{On a démontré qu'il ne termine jamais}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q20}
    Pourquoi la fonction « $f(P)$ vaut $1$ si le
programme $P$ s'arrête sur l'entrée vide, $0$
sinon » n'est-elle \textbf{pas calculable} ?
    \begin{choices}
    \wrongchoice{Parce que les programmes ne sont pas tous écrits en Python}
    \wrongchoice{Parce qu'on ne sait pas représenter un programme comme une donnée}
    \wrongchoice{Parce que la fonction renvoie un entier}
    \correctchoice{Parce que la calculer reviendrait à décider le problème de l'arrêt, ce qui est impossible en général}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q21}
    Quelle contribution majeure Alan Turing a-t-il
apportée en $1936$ ?
    \begin{choices}
    \correctchoice{Il a posé les fondements de la calculabilité moderne et démontré l'indécidabilité du problème de l'arrêt}
    \wrongchoice{Il a inventé Internet}
    \wrongchoice{Il a écrit le premier compilateur}
    \wrongchoice{Il a inventé le langage Python}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q22}
    Un problème \textbf{décidable} mais qui demande un
temps astronomique en pratique :
    \begin{choices}
    \wrongchoice{Disparaît automatiquement après quelques années}
    \correctchoice{Reste décidable. La calculabilité ne dit rien sur le temps d'exécution}
    \wrongchoice{N'est plus un problème}
    \wrongchoice{Devient indécidable}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q23}
    Pourquoi est-il important, en théorie de la
calculabilité, qu'un programme \textbf{puisse lire ou
manipuler son propre code source} ?
    \begin{choices}
    \correctchoice{Parce que c'est l'auto-référence qui rend possible l'argument d'indécidabilité du problème de l'arrêt}
    \wrongchoice{Parce que cela permet d'écrire des programmes plus rapides}
    \wrongchoice{Parce que cela rend les programmes immortels}
    \wrongchoice{Parce que cela évite les bugs}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q24}
    Deux langages de programmation $A$ et $B$ sont
dits \textbf{équivalents en calculabilité} si :
    \begin{choices}
    \wrongchoice{Ils s'exécutent à la même vitesse}
    \wrongchoice{Ils sont compilés par le même compilateur}
    \correctchoice{Toute fonction calculable dans $A$ l'est aussi dans $B$, et réciproquement}
    \wrongchoice{Ils ont la même syntaxe}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q25}
    Laquelle des affirmations suivantes résume le
mieux l'apport de la calculabilité à
l'informatique ?
    \begin{choices}
    \wrongchoice{La calculabilité dépend du processeur utilisé}
    \wrongchoice{La calculabilité ne sert à rien dans la pratique}
    \correctchoice{Il existe des limites théoriques, démontrées dès $1936$, à ce qu'un ordinateur peut décider, indépendamment de sa puissance ou du langage utilisé}
    \wrongchoice{Tout problème pourra finir par être résolu avec des ordinateurs assez puissants}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q26}
    Considérons les trois questions suivantes :
(a) « Cet entier est-il pair ? », (b) « Existe-t-il
un sous-ensemble d'une liste de cent entiers dont
la somme vaut zéro ? », (c) « Ce programme
arbitraire s'arrête-t-il sur une entrée donnée ? ».
Comment se classent-elles ?
    \begin{choices}
    \wrongchoice{Les trois sont indécidables}
    \wrongchoice{Les trois sont décidables et faciles}
    \wrongchoice{(a) facile, (b) indécidable, (c) décidable
}
    \correctchoice{(a) décidable et facile, (b) décidable mais
potentiellement coûteux à résoudre, (c)
indécidable
}
    \end{choices}
  \end{question}
}

\element{terminalecalculabilite}{
  \begin{question}{q27}
    Supposons qu'on dispose d'un programme \texttt{arrete?(P, e)}
qui répondrait toujours \texttt{True} ou \texttt{False}. Pour
construire la contradiction, on définit :
\begin{lstlisting}
def D(P):
    if arrete?(P, P):
        while True: pass
    return
\end{lstlisting}
Que se passe-t-il quand on appelle \texttt{D(D)} ?
    \begin{choices}
    \correctchoice{Si \texttt{arrete?(D, D)} renvoie \texttt{True}, alors \texttt{D(D)}
devrait s'arrêter selon la prédiction, mais le
code entre dans la boucle infinie : contradiction.
Si \texttt{arrete?(D, D)} renvoie \texttt{False}, alors
\texttt{D(D)} ne devrait pas s'arrêter, mais le code
renvoie immédiatement : contradiction. La
double contradiction prouve que \texttt{arrete?} ne
peut exister
}
    \wrongchoice{Le programme \texttt{arrete?} retournerait simplement
une erreur, ce qui résoudrait la situation
}
    \wrongchoice{Le programme \texttt{D(D)} ne pose aucun problème :
\texttt{arrete?} répond simplement par défaut
}
    \wrongchoice{La contradiction n'apparaît que si Python est
compilé, pas interprété
}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{terminalecalculabilite}
  \insertgroup{terminalecalculabilite}
}

\end{document}
