\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{Complexité algorithmique}
\subtitle{QCM}
\author{Première}
\date{\today}

\begin{document}

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

% Q1 - Réponse en B
\begin{frame}[fragile]{Question 1 \textemdash{} Définition de la complexité}
    Que mesure la \textbf{complexité algorithmique} ?\medskip
    \begin{itemize}
        \item[A.] Le nombre de lignes de code source
        \item[\alert<2>{B.}] \alert<2>{La quantité de ressources (temps ou mémoire) consommée par un algorithme en fonction de la taille de l'entrée}
        \item[C.] La beauté du code
        \item[D.] La difficulté de comprendre le code
    \end{itemize}
\end{frame}

% Q2 - Réponse en B
\begin{frame}[fragile]{Question 2 \textemdash{} Notation O}
    Que signifie l'écriture \texttt{O(n)} (« grand O de n ») ?\medskip
    \begin{itemize}
        \item[A.] L'algorithme effectue exactement \texttt{n} opérations
        \item[\alert<2>{B.}] \alert<2>{Le nombre d'opérations croît proportionnellement à n (à une constante près)}
        \item[C.] L'algorithme utilise n octets de mémoire
        \item[D.] L'algorithme se termine en moins de n secondes
    \end{itemize}
\end{frame}

% Q3 - Réponse en C
\begin{frame}[fragile]{Question 3 \textemdash{} Classes classiques}
    Parmi les complexités suivantes, laquelle est la
\textbf{plus rapide} asymptotiquement ?\medskip
    \begin{itemize}
        \item[A.] O(n²)
        \item[B.] O(n log n)
        \item[\alert<2>{C.}] \alert<2>{O(log n)}
        \item[D.] O(n)
    \end{itemize}
\end{frame}

% Q4 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 4 \textemdash{} Boucle simple}
    Quelle est la complexité de cette fonction en
fonction de \texttt{n = len(liste)} ?
\begin{lstlisting}
def somme(liste):
    total = 0
    for x in liste:
        total += x
    return total
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] O(log n)
        \item[B.] O(1)
        \item[C.] O(n)
        \item[D.] O(n²)
    \end{itemize}
\end{frame}

% Q4 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 4 \textemdash{} Boucle simple}
    Quelle est la complexité de cette fonction en
fonction de \texttt{n = len(liste)} ?
\begin{lstlisting}
def somme(liste):
    total = 0
    for x in liste:
        total += x
    return total
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] O(log n)
        \item[B.] O(1)
        \item[\alert{C.}] \alert{O(n)}
        \item[D.] O(n²)
    \end{itemize}
\end{frame}

% Q5 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 5 \textemdash{} Double boucle}
    Quelle est la complexité de cette fonction ?
\begin{lstlisting}
def doublons(liste):
    n = len(liste)
    for i in range(n):
        for j in range(n):
            if i != j and liste[i] == liste[j]:
                return True
    return False
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] O(n)
        \item[B.] O(1)
        \item[C.] O(n!)
        \item[D.] O(n²)
    \end{itemize}
\end{frame}

% Q5 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 5 \textemdash{} Double boucle}
    Quelle est la complexité de cette fonction ?
\begin{lstlisting}
def doublons(liste):
    n = len(liste)
    for i in range(n):
        for j in range(n):
            if i != j and liste[i] == liste[j]:
                return True
    return False
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] O(n)
        \item[B.] O(1)
        \item[C.] O(n!)
        \item[\alert{D.}] \alert{O(n²)}
    \end{itemize}
\end{frame}

% Q6 - Réponse en D
\begin{frame}[fragile]{Question 6 \textemdash{} Constante}
    Quelle est la complexité de l'accès \texttt{liste[i]}
sur une \textbf{liste Python} ?\medskip
    \begin{itemize}
        \item[A.] O(n²)
        \item[B.] O(log n)
        \item[C.] O(n)
        \item[\alert<2>{D.}] \alert<2>{O(1)}
    \end{itemize}
\end{frame}

% Q7 - Réponse en D
\begin{frame}[fragile]{Question 7 \textemdash{} Taille de l'entrée}
    Pour une liste, qu'est-ce que la « taille de
l'entrée » \texttt{n} ?\medskip
    \begin{itemize}
        \item[A.] Le numéro de ligne où la liste est définie
        \item[B.] La valeur du plus grand élément
        \item[C.] La quantité de mémoire qu'elle occupe en octets
        \item[\alert<2>{D.}] \alert<2>{Le nombre d'éléments de la liste (sa longueur)}
    \end{itemize}
\end{frame}

% Q8 - Réponse en C
\begin{frame}[fragile]{Question 8 \textemdash{} Pire / moyen / meilleur cas}
    Pourquoi distingue-t-on \textbf{pire cas, cas moyen,
meilleur cas} dans l'analyse de complexité ?\medskip
    \begin{itemize}
        \item[A.] Pour faire les énoncés plus longs
        \item[B.] Parce que les langages de programmation diffèrent
        \item[\alert<2>{C.}] \alert<2>{Parce que la complexité peut dépendre du contenu de l'entrée, pas seulement de sa taille}
        \item[D.] Parce que l'ordinateur a parfois la flemme
    \end{itemize}
\end{frame}

% Q9 - Réponse en B
\begin{frame}[fragile]{Question 9 \textemdash{} Échelle de croissance}
    Pour n = 1000, qui est le plus grand ?\medskip
    \begin{itemize}
        \item[A.] n = 1000
        \item[\alert<2>{B.}] \alert<2>{2ⁿ ≈ 10³⁰¹ (un nombre de plus de 300 chiffres)}
        \item[C.] n² = 1 000 000
        \item[D.] log₂(n) ≈ 10
    \end{itemize}
\end{frame}

% Q10 - Réponse en B
\begin{frame}[fragile]{Question 10 \textemdash{} Recherche}
    Quelle est la complexité de la \textbf{recherche
dichotomique} dans une liste triée ?\medskip
    \begin{itemize}
        \item[A.] O(n)
        \item[\alert<2>{B.}] \alert<2>{O(log n)}
        \item[C.] O(n²)
        \item[D.] O(1)
    \end{itemize}
\end{frame}

% Q11 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 11 \textemdash{} Boucles imbriquées}
    Quelle est la complexité de :
\begin{lstlisting}
for i in range(n):
    for j in range(n):
        for k in range(n):
            print(i, j, k)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] O(n)
        \item[B.] O(n²)
        \item[C.] O(3n)
        \item[D.] O(n³)
    \end{itemize}
\end{frame}

% Q11 - Réponse en D
\begin{frame}[fragile,allowframebreaks]{Question 11 \textemdash{} Boucles imbriquées}
    Quelle est la complexité de :
\begin{lstlisting}
for i in range(n):
    for j in range(n):
        for k in range(n):
            print(i, j, k)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] O(n)
        \item[B.] O(n²)
        \item[C.] O(3n)
        \item[\alert{D.}] \alert{O(n³)}
    \end{itemize}
\end{frame}

% Q12 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 12 \textemdash{} Deux boucles séparées}
    Quelle est la complexité de :
\begin{lstlisting}
for i in range(n):
    print(i)
for j in range(n):
    print(j)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] O(2)
        \item[B.] O(n²)
        \item[C.] O(n) (et non O(2n), car les constantes sont absorbées)
        \item[D.] O(n × m) où m = n
    \end{itemize}
\end{frame}

% Q12 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 12 \textemdash{} Deux boucles séparées}
    Quelle est la complexité de :
\begin{lstlisting}
for i in range(n):
    print(i)
for j in range(n):
    print(j)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] O(2)
        \item[B.] O(n²)
        \item[\alert{C.}] \alert{O(n) (et non O(2n), car les constantes sont absorbées)}
        \item[D.] O(n × m) où m = n
    \end{itemize}
\end{frame}

% Q13 - Réponse en B
\begin{frame}[fragile]{Question 13 \textemdash{} Termes dominants}
    Quelle est la complexité de l'expression
\texttt{T(n) = 3n² + 100n + 50} ?\medskip
    \begin{itemize}
        \item[A.] O(3n²)
        \item[\alert<2>{B.}] \alert<2>{O(n²)}
        \item[C.] O(50)
        \item[D.] O(100n)
    \end{itemize}
\end{frame}

% Q14 - Réponse en B
\begin{frame}[fragile]{Question 14 \textemdash{} Doublement de la taille}
    Un algorithme en O(n²) traite n = 1000
éléments en 1 seconde. Combien de temps lui
faudra-t-il pour n = 2000 ?\medskip
    \begin{itemize}
        \item[A.] 1 seconde (le temps ne change pas)
        \item[\alert<2>{B.}] \alert<2>{4 secondes (n doublé → temps quadruplé)}
        \item[C.] 1000 secondes
        \item[D.] 2 secondes (n doublé → temps doublé)
    \end{itemize}
\end{frame}

% Q15 - Réponse en D
\begin{frame}[fragile]{Question 15 \textemdash{} Pire vs meilleur cas}
    La recherche linéaire est en \texttt{O(n)} au pire et
\texttt{O(1)} au meilleur. Que dire si l'on parle de
« complexité » sans précision ?\medskip
    \begin{itemize}
        \item[A.] On parle du cas moyen
        \item[B.] On parle implicitement du meilleur cas
        \item[C.] On parle du cas le plus probable
        \item[\alert<2>{D.}] \alert<2>{On parle implicitement du pire cas}
    \end{itemize}
\end{frame}

% Q16 - Réponse en A
\begin{frame}[fragile]{Question 16 \textemdash{} Complexité spatiale}
    Quelle est la complexité \textbf{spatiale} (mémoire
additionnelle) du tri par insertion ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{O(1)}
        \item[B.] O(n²)
        \item[C.] O(log n)
        \item[D.] O(n)
    \end{itemize}
\end{frame}

% Q17 - Réponse en D
\begin{frame}[fragile]{Question 17 \textemdash{} O(n log n)}
    Pour quel type d'algorithme la complexité
O(n log n) est-elle typique ?\medskip
    \begin{itemize}
        \item[A.] Le calcul de la somme d'une liste
        \item[B.] La recherche linéaire
        \item[C.] La recherche dichotomique
        \item[\alert<2>{D.}] \alert<2>{Les tris efficaces (fusion, rapide, Timsort)}
    \end{itemize}
\end{frame}

% Q18 - Réponse en C
\begin{frame}[fragile]{Question 18 \textemdash{} Algorithmes exponentiels}
    Pourquoi évite-t-on les algorithmes en O(2ⁿ) ?\medskip
    \begin{itemize}
        \item[A.] Parce qu'ils prennent trop de place sur le disque
        \item[B.] Parce qu'ils n'existent pas
        \item[\alert<2>{C.}] \alert<2>{Parce que pour n modeste (n = 50), 2ⁿ ≈ 10¹⁵, ce qui est hors d'atteinte même sur un super-calculateur}
        \item[D.] Parce qu'ils sont mal écrits
    \end{itemize}
\end{frame}

% Q19 - Réponse en A
\begin{frame}[fragile]{Question 19 \textemdash{} Estimer un temps}
    Un algorithme effectue 10⁹ opérations
élémentaires. Sur un PC moderne (~ 10⁹
opérations / seconde), combien de temps
attendra-t-on ?\medskip
    \begin{itemize}
        \item[\alert<2>{A.}] \alert<2>{Environ une seconde}
        \item[B.] Plusieurs années
        \item[C.] Plusieurs jours
        \item[D.] Quelques nanosecondes
    \end{itemize}
\end{frame}

% Q20 - Réponse en C
\begin{frame}[fragile]{Question 20 \textemdash{} Petit vs grand n}
    Pour n petit (n = 10), un algorithme O(n²) est-il
forcément moins efficace qu'un O(n log n) ?\medskip
    \begin{itemize}
        \item[A.] Aucun rapport entre les deux
        \item[B.] Oui, O(n²) est toujours moins efficace
        \item[\alert<2>{C.}] \alert<2>{Non, sur les petites entrées les constantes peuvent dominer et l'algorithme « plus simple » peut être plus rapide}
        \item[D.] Cela dépend de la couleur de l'écran
    \end{itemize}
\end{frame}

% Q21 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 21 \textemdash{} Analyse fine}
    Quelle est la complexité de :
\begin{lstlisting}
def f(n):
    for i in range(n):
        for j in range(i):
            print(i, j)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] O(n²)
        \item[B.] O(n log n)
        \item[C.] O(n)
        \item[D.] O(n³)
    \end{itemize}
\end{frame}

% Q21 - Réponse en A
\begin{frame}[fragile,allowframebreaks]{Question 21 \textemdash{} Analyse fine}
    Quelle est la complexité de :
\begin{lstlisting}
def f(n):
    for i in range(n):
        for j in range(i):
            print(i, j)
\end{lstlisting}\medskip
    \begin{itemize}
        \item[\alert{A.}] \alert{O(n²)}
        \item[B.] O(n log n)
        \item[C.] O(n)
        \item[D.] O(n³)
    \end{itemize}
\end{frame}

% Q22 - Réponse en C
\begin{frame}[fragile]{Question 22 \textemdash{} Boucle qui divise}
    Une boucle parcourt une variable \texttt{n} en la
\textbf{divisant par 2} à chaque tour, jusqu'à
atteindre 1 (à chaque tour, travail
constant). Quel est le coût total ?\medskip
    \begin{itemize}
        \item[A.] Quadratique
        \item[B.] Constant
        \item[\alert<2>{C.}] \alert<2>{Logarithmique}
        \item[D.] Linéaire
    \end{itemize}
\end{frame}

% Q23 - Réponse en C
\begin{frame}[fragile]{Question 23 \textemdash{} Mesure empirique}
    Pour vérifier la complexité d'un algorithme
empiriquement, on mesure son temps \texttt{t} pour
différentes tailles \texttt{n}. Si \texttt{t} est
proportionnel à \texttt{n²}, comment cela apparaît-il
sur un graphique log-log (axes logarithmiques) ?\medskip
    \begin{itemize}
        \item[A.] Une parabole
        \item[B.] Une courbe exponentielle
        \item[\alert<2>{C.}] \alert<2>{Une droite de pente 2}
        \item[D.] Une horizontale
    \end{itemize}
\end{frame}

% Q24 - Réponse en B
\begin{frame}[fragile]{Question 24 \textemdash{} Inclusion des classes}
    Une fonction en O(n) est-elle forcément aussi
en O(n²) ?\medskip
    \begin{itemize}
        \item[A.] Non, ce sont des classes différentes
        \item[\alert<2>{B.}] \alert<2>{Oui : O(n²) est une borne supérieure plus large, qui inclut O(n)}
        \item[C.] Oui, mais seulement pour des n positifs
        \item[D.] Non, sauf si n est petit
    \end{itemize}
\end{frame}

% Q25 - Réponse en B
\begin{frame}[fragile]{Question 25 \textemdash{} Synthèse}
    Parmi les affirmations suivantes sur la
complexité, laquelle est \textbf{fausse} ?\medskip
    \begin{itemize}
        \item[A.] La complexité spatiale mesure la mémoire additionnelle utilisée
        \item[\alert<2>{B.}] \alert<2>{Un algorithme O(n) est toujours plus rapide qu'un algorithme O(n²)}
        \item[C.] Pour les boucles imbriquées, on multiplie les complexités ; pour les séquences, on prend le maximum
        \item[D.] La complexité O ignore les constantes multiplicatives
    \end{itemize}
\end{frame}

% Q26 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Boucle while soustractive}
    Quelle est la complexité de la fonction
suivante en fonction de \texttt{n} ?
\begin{lstlisting}
def f(n):
    while n > 0:
        print(n)
        n = n - 3
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] O(log n)
        \item[B.] O(1)
        \item[C.] O(n)
        \item[D.] O(n²)
    \end{itemize}
\end{frame}

% Q26 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 26 \textemdash{} Boucle while soustractive}
    Quelle est la complexité de la fonction
suivante en fonction de \texttt{n} ?
\begin{lstlisting}
def f(n):
    while n > 0:
        print(n)
        n = n - 3
\end{lstlisting}\medskip
    \begin{itemize}
        \item[A.] O(log n)
        \item[B.] O(1)
        \item[\alert{C.}] \alert{O(n)}
        \item[D.] O(n²)
    \end{itemize}
\end{frame}

% Q27 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 27 \textemdash{} Taille vs valeur de l'entrée}
    On considère la fonction qui compte les
chiffres d'un entier positif :
\begin{lstlisting}
def chiffres(n):
    c = 0
    while n > 0:
        n = n // 10
        c += 1
    return c
\end{lstlisting}
Quelle est sa complexité ?\medskip
    \begin{itemize}
        \item[A.] O(n) en fonction de la valeur n
        \item[B.] O(1) car n est une simple variable
        \item[C.] O(log n) en fonction de la valeur n (autrement dit, linéaire en fonction du nombre de chiffres)
        \item[D.] O(n²)
    \end{itemize}
\end{frame}

% Q27 - Réponse en C
\begin{frame}[fragile,allowframebreaks]{Question 27 \textemdash{} Taille vs valeur de l'entrée}
    On considère la fonction qui compte les
chiffres d'un entier positif :
\begin{lstlisting}
def chiffres(n):
    c = 0
    while n > 0:
        n = n // 10
        c += 1
    return c
\end{lstlisting}
Quelle est sa complexité ?\medskip
    \begin{itemize}
        \item[A.] O(n) en fonction de la valeur n
        \item[B.] O(1) car n est une simple variable
        \item[\alert{C.}] \alert{O(log n) en fonction de la valeur n (autrement dit, linéaire en fonction du nombre de chiffres)}
        \item[D.] O(n²)
    \end{itemize}
\end{frame}

% Q28 - Réponse en B
\begin{frame}[fragile]{Question 28 \textemdash{} Coût des opérations sur les listes}
    Parmi ces opérations sur une liste Python de
taille \texttt{n}, laquelle est la plus \textbf{coûteuse}
au pire ?\medskip
    \begin{itemize}
        \item[A.] \texttt{liste[0]} (lecture du premier élément)
        \item[\alert<2>{B.}] \alert<2>{\texttt{liste.insert(0, x)} (insertion en tête)}
        \item[C.] \texttt{liste.append(x)} (ajout en fin)
        \item[D.] \texttt{len(liste)} (longueur de la liste)
    \end{itemize}
\end{frame}

% Q29 - Réponse en C
\begin{frame}[fragile]{Question 29 \textemdash{} Choisir selon la taille}
    Sur un PC moderne, on dispose d'\textbf{une seconde}
pour exécuter un algorithme (~ 10⁸ opérations
Python). Quelle est la \textbf{plus grande taille}
d'entrée que l'on peut traiter avec un
algorithme en O(n²) ?\medskip
    \begin{itemize}
        \item[A.] Environ 30 (trentaine)
        \item[B.] Environ 10⁸ (cent millions)
        \item[\alert<2>{C.}] \alert<2>{Environ 10⁴ (dix mille)}
        \item[D.] Environ 10⁶ (un million)
    \end{itemize}
\end{frame}

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

\end{document}
