\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{Calculabilité et décidabilité}
\subtitle{QCM}
\author{Terminale}
\date{\today}

\begin{document}

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

% Q1 - Réponse en D
\begin{frame}[fragile]{Question 1 \textemdash{} Programme et donnée}
    Pourquoi peut-on dire qu'\textbf{un programme est aussi une
donnée} ?\medskip
    \begin{itemize}
        \item[A.] Cette affirmation est fausse
        \item[B.] Parce qu'un programme contient toujours des données en entrée
        \item[C.] Parce qu'il occupe de la mémoire vive
        \item[\alert<2>{D.}] \alert<2>{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{itemize}
\end{frame}

% Q2 - Réponse en A
\begin{frame}[fragile]{Question 2 \textemdash{} Programme manipulé par un autre}
    Lequel des exemples suivants illustre \textbf{un programme
manipulé comme une donnée} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Un compilateur qui lit un fichier \texttt{.c} et produit un fichier exécutable}
        \item[B.] Un programme qui calcule un déterminant de matrice
        \item[C.] Un programme qui affiche « Bonjour »
        \item[D.] Un programme qui calcule la somme de deux nombres saisis par l'utilisateur
    \end{itemize}
\end{frame}

% Q3 - Réponse en D
\begin{frame}[fragile]{Question 3 \textemdash{} Fonction calculable}
    Que signifie qu'une fonction $f$ est \textbf{calculable}
au sens informatique ?\medskip
    \begin{itemize}
        \item[A.] La fonction est continue
        \item[B.] La fonction s'exécute en moins d'une seconde
        \item[C.] La fonction renvoie toujours un entier
        \item[\alert<2>{D.}] \alert<2>{Il existe un algorithme qui, pour toute entrée valide, calcule $f$ en un nombre fini d'étapes}
    \end{itemize}
\end{frame}

% Q4 - Réponse en D
\begin{frame}[fragile]{Question 4 \textemdash{} Exemple de fonction calculable}
    Lequel des éléments suivants définit une fonction
\textbf{calculable} ?\medskip
    \begin{itemize}
        \item[A.] Une fonction qui prend en entrée un programme et renvoie « oui » s'il s'arrête, « non » sinon
        \item[B.] Une fonction qui à un texte associe « oui » s'il représente un programme correct
        \item[C.] La fonction qui à un programme associe le nombre exact d'instructions qu'il exécutera dans tous les cas
        \item[\alert<2>{D.}] \alert<2>{La fonction qui à un entier $n$ associe son carré $n^2$}
    \end{itemize}
\end{frame}

% Q5 - Réponse en C
\begin{frame}[fragile]{Question 5 \textemdash{} Indépendance du langage}
    Une fonction est calculable. Que peut-on en
déduire sur les langages de programmation ?\medskip
    \begin{itemize}
        \item[A.] Le résultat de la fonction varie selon le langage utilisé
        \item[B.] Elle ne peut être écrite qu'en Python
        \item[\alert<2>{C.}] \alert<2>{Elle peut être implémentée dans n'importe quel langage de programmation universel (Python, C, Java, OCaml...)}
        \item[D.] Elle nécessite obligatoirement un langage récursif
    \end{itemize}
\end{frame}

% Q6 - Réponse en A
\begin{frame}[fragile]{Question 6 \textemdash{} Problème décidable}
    Qu'appelle-t-on un \textbf{problème décidable} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{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}
        \item[B.] Un problème dont la réponse est connue par avance
        \item[C.] Un problème qui n'a pas de solution
        \item[D.] Un problème facile à résoudre
    \end{itemize}
\end{frame}

% Q7 - Réponse en C
\begin{frame}[fragile]{Question 7 \textemdash{} Exemple de problème décidable}
    Lequel de ces problèmes est clairement \textbf{décidable} ?\medskip
    \begin{itemize}
        \item[A.] Étant donné un programme, dire s'il contient un bug logique
        \item[B.] Étant donné un programme Python, dire s'il s'arrêtera sur l'entrée $0$
        \item[\alert<2>{C.}] \alert<2>{Étant donné un entier $n$, déterminer s'il est divisible par $7$}
        \item[D.] Étant donné deux programmes, dire s'ils calculent la même fonction sur toute entrée
    \end{itemize}
\end{frame}

% Q8 - Réponse en D
\begin{frame}[fragile]{Question 8 \textemdash{} Problème indécidable}
    Qu'est-ce qu'un \textbf{problème indécidable} ?\medskip
    \begin{itemize}
        \item[A.] Un problème qui demande beaucoup de mémoire
        \item[B.] Un problème dont la réponse change selon la machine utilisée
        \item[C.] Un problème difficile, qu'on n'a pas encore résolu
        \item[\alert<2>{D.}] \alert<2>{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{itemize}
\end{frame}

% Q9 - Réponse en D
\begin{frame}[fragile]{Question 9 \textemdash{} Énoncé du problème de l'arrêt}
    Comment énonce-t-on le \textbf{problème de l'arrêt} ?\medskip
    \begin{itemize}
        \item[A.] Comment savoir combien de temps un programme va s'exécuter ?
        \item[B.] Comment arrêter un programme qui boucle sans fin ?
        \item[C.] À quel moment faut-il interrompre une compilation ?
        \item[\alert<2>{D.}] \alert<2>{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{itemize}
\end{frame}

% Q10 - Réponse en B
\begin{frame}[fragile]{Question 10 \textemdash{} Statut du problème de l'arrêt}
    Le problème de l'arrêt est :\medskip
    \begin{itemize}
        \item[A.] Décidable, mais coûteux
        \item[\alert<2>{B.}] \alert<2>{Indécidable}
        \item[C.] Décidable, et résolu par les antivirus
        \item[D.] Inconnu de la communauté scientifique
    \end{itemize}
\end{frame}

% Q11 - Réponse en C
\begin{frame}[fragile]{Question 11 \textemdash{} Idée de la démonstration}
    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 à :\medskip
    \begin{itemize}
        \item[A.] Mesurer le temps d'exécution de tous les programmes possibles
        \item[B.] Programmer le décideur en plusieurs langages et comparer
        \item[\alert<2>{C.}] \alert<2>{Construire un programme qui « se contredit » lui-même en utilisant le décideur sur sa propre entrée}
        \item[D.] Réécrire les programmes en machine de Turing
    \end{itemize}
\end{frame}

% Q12 - Réponse en B
\begin{frame}[fragile]{Question 12 \textemdash{} Conséquence pratique}
    Quelle conséquence pratique l'indécidabilité du
problème de l'arrêt a-t-elle sur le développement
logiciel ?\medskip
    \begin{itemize}
        \item[A.] Plus aucun nouveau bug ne peut être trouvé
        \item[\alert<2>{B.}] \alert<2>{On ne peut pas écrire un programme qui détecte toutes les boucles infinies dans n'importe quel autre programme}
        \item[C.] Les ordinateurs ne peuvent pas exécuter de programmes
        \item[D.] Les langages modernes ne contiennent plus jamais de boucles infinies
    \end{itemize}
\end{frame}

% Q13 - Réponse en C
\begin{frame}[fragile]{Question 13 \textemdash{} Calculable ou décidable}
    Quelle est la différence entre \textbf{calculable} et
\textbf{décidable} ?\medskip
    \begin{itemize}
        \item[A.] « Calculable » signifie « facile », « décidable » signifie « difficile »
        \item[B.] « Calculable » concerne les nombres, « décidable » concerne les chaînes
        \item[\alert<2>{C.}] \alert<2>{« Calculable » s'applique aux fonctions, « décidable » aux problèmes de décision (à réponse oui/non)}
        \item[D.] Aucune différence, ce sont des synonymes
    \end{itemize}
\end{frame}

% Q14 - Réponse en A
\begin{frame}[fragile]{Question 14 \textemdash{} Cas particuliers}
    Pour \textbf{certains} programmes, on peut savoir
facilement s'ils s'arrêtent. Ce qui est
indécidable, c'est :\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{De le faire pour tous les programmes possibles, avec un seul algorithme général}
        \item[B.] De le faire pour les programmes écrits en Python
        \item[C.] De le faire en moins d'une heure
        \item[D.] De le faire pour les programmes courts
    \end{itemize}
\end{frame}

% Q15 - Réponse en A
\begin{frame}[fragile]{Question 15 \textemdash{} Machine universelle}
    L'idée d'\textbf{ordinateur universel} repose sur
laquelle des affirmations suivantes ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Un même dispositif peut exécuter n'importe quel programme, à condition de lui fournir le code de ce programme en entrée}
        \item[B.] Tous les programmes peuvent s'écrire sans boucles
        \item[C.] Tous les ordinateurs ont le même processeur
        \item[D.] Tout calcul peut s'effectuer instantanément
    \end{itemize}
\end{frame}

% Q16 - Réponse en D
\begin{frame}[fragile]{Question 16 \textemdash{} Interpréteur écrit dans son langage}
    On peut écrire un interpréteur Python en Python
(par exemple via la fonction \texttt{exec}). Que
montre cet exemple ?\medskip
    \begin{itemize}
        \item[A.] Que Python est plus rapide que les autres langages
        \item[B.] Que \texttt{exec} rend Python incalculable
        \item[C.] Que \texttt{exec} est une fonction obsolète
        \item[\alert<2>{D.}] \alert<2>{Qu'un programme peut prendre un autre programme comme donnée et l'exécuter, illustrant la dualité programme/donnée}
    \end{itemize}
\end{frame}

% Q17 - Réponse en B
\begin{frame}[fragile]{Question 17 \textemdash{} Détection de logiciels malveillants}
    Pourquoi est-il \textbf{impossible} d'écrire un
antivirus parfait qui détecterait tous les
logiciels malveillants sans aucune erreur ?\medskip
    \begin{itemize}
        \item[A.] Parce que les antivirus sont mal programmés
        \item[\alert<2>{B.}] \alert<2>{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}
        \item[C.] Parce que les antivirus sont trop lents
        \item[D.] Parce que les antivirus ne peuvent pas analyser un fichier
    \end{itemize}
\end{frame}

% Q18 - Réponse en B
\begin{frame}[fragile]{Question 18 \textemdash{} Identifier des problèmes décidables}
    Parmi les problèmes suivants, lesquels sont
\textbf{décidables} ? Sélectionnez la proposition
correcte.\medskip
    \begin{itemize}
        \item[A.] Les trois sont décidables
        \item[\alert<2>{B.}] \alert<2>{« 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}
        \item[C.] Aucun de ces problèmes n'est décidable
        \item[D.] Tous les problèmes énoncés en français sont décidables
    \end{itemize}
\end{frame}

% Q19 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 19 \textemdash{} Programme à terminaison non triviale}
    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} ?\medskip
    \begin{itemize}
        \item[A.] Personne ne sait, à ce jour, démontrer qu'il termine pour tout $n$ positif (conjecture de Syracuse)
        \item[B.] Il termine en au plus $100$ étapes
        \item[C.] Il termine si et seulement si $n$ est pair
        \item[D.] On a démontré qu'il ne termine jamais
    \end{itemize}
\end{frame}

% Q19 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 19 \textemdash{} Programme à terminaison non triviale}
    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} ?\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{Personne ne sait, à ce jour, démontrer qu'il termine pour tout $n$ positif (conjecture de Syracuse)}
        \item[B.] Il termine en au plus $100$ étapes
        \item[C.] Il termine si et seulement si $n$ est pair
        \item[D.] On a démontré qu'il ne termine jamais
    \end{itemize}
\end{frame}

% Q20 - Réponse en D
\begin{frame}[fragile]{Question 20 \textemdash{} Une fonction non calculable}
    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} ?\medskip
    \begin{itemize}
        \item[A.] Parce que les programmes ne sont pas tous écrits en Python
        \item[B.] Parce qu'on ne sait pas représenter un programme comme une donnée
        \item[C.] Parce que la fonction renvoie un entier
        \item[\alert<2>{D.}] \alert<2>{Parce que la calculer reviendrait à décider le problème de l'arrêt, ce qui est impossible en général}
    \end{itemize}
\end{frame}

% Q21 - Réponse en A
\begin{frame}[fragile]{Question 21 \textemdash{} Histoire : Alan Turing}
    Quelle contribution majeure Alan Turing a-t-il
apportée en $1936$ ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Il a posé les fondements de la calculabilité moderne et démontré l'indécidabilité du problème de l'arrêt}
        \item[B.] Il a inventé Internet
        \item[C.] Il a écrit le premier compilateur
        \item[D.] Il a inventé le langage Python
    \end{itemize}
\end{frame}

% Q22 - Réponse en B
\begin{frame}[fragile]{Question 22 \textemdash{} Calculabilité et complexité}
    Un problème \textbf{décidable} mais qui demande un
temps astronomique en pratique :\medskip
    \begin{itemize}
        \item[A.] Disparaît automatiquement après quelques années
        \item[\alert<2>{B.}] \alert<2>{Reste décidable. La calculabilité ne dit rien sur le temps d'exécution}
        \item[C.] N'est plus un problème
        \item[D.] Devient indécidable
    \end{itemize}
\end{frame}

% Q23 - Réponse en A
\begin{frame}[fragile]{Question 23 \textemdash{} Programme qui lit son propre code}
    Pourquoi est-il important, en théorie de la
calculabilité, qu'un programme \textbf{puisse lire ou
manipuler son propre code source} ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Parce que c'est l'auto-référence qui rend possible l'argument d'indécidabilité du problème de l'arrêt}
        \item[B.] Parce que cela permet d'écrire des programmes plus rapides
        \item[C.] Parce que cela rend les programmes immortels
        \item[D.] Parce que cela évite les bugs
    \end{itemize}
\end{frame}

% Q24 - Réponse en C
\begin{frame}[fragile]{Question 24 \textemdash{} Langages équivalents}
    Deux langages de programmation $A$ et $B$ sont
dits \textbf{équivalents en calculabilité} si :\medskip
    \begin{itemize}
        \item[A.] Ils s'exécutent à la même vitesse
        \item[B.] Ils sont compilés par le même compilateur
        \item[\alert<2>{C.}] \alert<2>{Toute fonction calculable dans $A$ l'est aussi dans $B$, et réciproquement}
        \item[D.] Ils ont la même syntaxe
    \end{itemize}
\end{frame}

% Q25 - Réponse en C
\begin{frame}[fragile]{Question 25 \textemdash{} Synthèse : Limites de la calculabilité}
    Laquelle des affirmations suivantes résume le
mieux l'apport de la calculabilité à
l'informatique ?\medskip
    \begin{itemize}
        \item[A.] La calculabilité dépend du processeur utilisé
        \item[B.] La calculabilité ne sert à rien dans la pratique
        \item[\alert<2>{C.}] \alert<2>{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é}
        \item[D.] Tout problème pourra finir par être résolu avec des ordinateurs assez puissants
    \end{itemize}
\end{frame}

% Q26 - Réponse en D
\begin{frame}[fragile]{Question 26 \textemdash{} Frontière calculable / décidable / faisable}
    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 ?\medskip
    \begin{itemize}
        \item[A.] Les trois sont indécidables
        \item[B.] Les trois sont décidables et faciles
        \item[C.] (a) facile, (b) indécidable, (c) décidable

        \item[\alert<2>{D.}] \alert<2>{(a) décidable et facile, (b) décidable mais
potentiellement coûteux à résoudre, (c)
indécidable
}
    \end{itemize}
\end{frame}

% Q27 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 27 \textemdash{} L'argument d'auto-référence en pratique}
    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)} ?\medskip
    \begin{itemize}
        \item[A.] 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

        \item[B.] Le programme \texttt{arrete?} retournerait simplement
une erreur, ce qui résoudrait la situation

        \item[C.] Le programme \texttt{D(D)} ne pose aucun problème :
\texttt{arrete?} répond simplement par défaut

        \item[D.] La contradiction n'apparaît que si Python est
compilé, pas interprété

    \end{itemize}
\end{frame}

% Q27 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 27 \textemdash{} L'argument d'auto-référence en pratique}
    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)} ?\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{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
}
        \item[B.] Le programme \texttt{arrete?} retournerait simplement
une erreur, ce qui résoudrait la situation

        \item[C.] Le programme \texttt{D(D)} ne pose aucun problème :
\texttt{arrete?} répond simplement par défaut

        \item[D.] La contradiction n'apparaît que si Python est
compilé, pas interprété

    \end{itemize}
\end{frame}

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

\end{document}
