\documentclass[a4paper,11pt]{article}

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

\title{Complexité algorithmique}
\date{Numérique et sciences informatiques}

\begin{document}

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

\bigskip

\element{premierecomplexite}{
  \begin{question}{q01}
    Que mesure la \textbf{complexité algorithmique} ?
    \begin{choices}
    \wrongchoice{Le nombre de lignes de code source}
    \correctchoice{La quantité de ressources (temps ou mémoire) consommée par un algorithme en fonction de la taille de l'entrée}
    \wrongchoice{La beauté du code}
    \wrongchoice{La difficulté de comprendre le code}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q02}
    Que signifie l'écriture \texttt{O(n)} (« grand O de n ») ?
    \begin{choices}
    \wrongchoice{L'algorithme effectue exactement \texttt{n} opérations}
    \correctchoice{Le nombre d'opérations croît proportionnellement à n (à une constante près)}
    \wrongchoice{L'algorithme utilise n octets de mémoire}
    \wrongchoice{L'algorithme se termine en moins de n secondes}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q03}
    Parmi les complexités suivantes, laquelle est la
\textbf{plus rapide} asymptotiquement ?
    \begin{choices}
    \wrongchoice{O(n²)}
    \wrongchoice{O(n log n)}
    \correctchoice{O(log n)}
    \wrongchoice{O(n)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q04}
    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}
    \begin{choices}
    \wrongchoice{O(log n)}
    \wrongchoice{O(1)}
    \correctchoice{O(n)}
    \wrongchoice{O(n²)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q05}
    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}
    \begin{choices}
    \wrongchoice{O(n)}
    \wrongchoice{O(1)}
    \wrongchoice{O(n!)}
    \correctchoice{O(n²)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q06}
    Quelle est la complexité de l'accès \texttt{liste[i]}
sur une \textbf{liste Python} ?
    \begin{choices}
    \wrongchoice{O(n²)}
    \wrongchoice{O(log n)}
    \wrongchoice{O(n)}
    \correctchoice{O(1)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q07}
    Pour une liste, qu'est-ce que la « taille de
l'entrée » \texttt{n} ?
    \begin{choices}
    \wrongchoice{Le numéro de ligne où la liste est définie}
    \wrongchoice{La valeur du plus grand élément}
    \wrongchoice{La quantité de mémoire qu'elle occupe en octets}
    \correctchoice{Le nombre d'éléments de la liste (sa longueur)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q08}
    Pourquoi distingue-t-on \textbf{pire cas, cas moyen,
meilleur cas} dans l'analyse de complexité ?
    \begin{choices}
    \wrongchoice{Pour faire les énoncés plus longs}
    \wrongchoice{Parce que les langages de programmation diffèrent}
    \correctchoice{Parce que la complexité peut dépendre du contenu de l'entrée, pas seulement de sa taille}
    \wrongchoice{Parce que l'ordinateur a parfois la flemme}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q09}
    Pour n = 1000, qui est le plus grand ?
    \begin{choices}
    \wrongchoice{n = 1000}
    \correctchoice{2ⁿ ≈ 10³⁰¹ (un nombre de plus de 300 chiffres)}
    \wrongchoice{n² = 1 000 000}
    \wrongchoice{log₂(n) ≈ 10}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q10}
    Quelle est la complexité de la \textbf{recherche
dichotomique} dans une liste triée ?
    \begin{choices}
    \wrongchoice{O(n)}
    \correctchoice{O(log n)}
    \wrongchoice{O(n²)}
    \wrongchoice{O(1)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q11}
    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}
    \begin{choices}
    \wrongchoice{O(n)}
    \wrongchoice{O(n²)}
    \wrongchoice{O(3n)}
    \correctchoice{O(n³)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q12}
    Quelle est la complexité de :
\begin{lstlisting}
for i in range(n):
    print(i)
for j in range(n):
    print(j)
\end{lstlisting}
    \begin{choices}
    \wrongchoice{O(2)}
    \wrongchoice{O(n²)}
    \correctchoice{O(n) (et non O(2n), car les constantes sont absorbées)}
    \wrongchoice{O(n × m) où m = n}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q13}
    Quelle est la complexité de l'expression
\texttt{T(n) = 3n² + 100n + 50} ?
    \begin{choices}
    \wrongchoice{O(3n²)}
    \correctchoice{O(n²)}
    \wrongchoice{O(50)}
    \wrongchoice{O(100n)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q14}
    Un algorithme en O(n²) traite n = 1000
éléments en 1 seconde. Combien de temps lui
faudra-t-il pour n = 2000 ?
    \begin{choices}
    \wrongchoice{1 seconde (le temps ne change pas)}
    \correctchoice{4 secondes (n doublé → temps quadruplé)}
    \wrongchoice{1000 secondes}
    \wrongchoice{2 secondes (n doublé → temps doublé)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q15}
    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 ?
    \begin{choices}
    \wrongchoice{On parle du cas moyen}
    \wrongchoice{On parle implicitement du meilleur cas}
    \wrongchoice{On parle du cas le plus probable}
    \correctchoice{On parle implicitement du pire cas}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q16}
    Quelle est la complexité \textbf{spatiale} (mémoire
additionnelle) du tri par insertion ?
    \begin{choices}
    \correctchoice{O(1)}
    \wrongchoice{O(n²)}
    \wrongchoice{O(log n)}
    \wrongchoice{O(n)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q17}
    Pour quel type d'algorithme la complexité
O(n log n) est-elle typique ?
    \begin{choices}
    \wrongchoice{Le calcul de la somme d'une liste}
    \wrongchoice{La recherche linéaire}
    \wrongchoice{La recherche dichotomique}
    \correctchoice{Les tris efficaces (fusion, rapide, Timsort)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q18}
    Pourquoi évite-t-on les algorithmes en O(2ⁿ) ?
    \begin{choices}
    \wrongchoice{Parce qu'ils prennent trop de place sur le disque}
    \wrongchoice{Parce qu'ils n'existent pas}
    \correctchoice{Parce que pour n modeste (n = 50), 2ⁿ ≈ 10¹⁵, ce qui est hors d'atteinte même sur un super-calculateur}
    \wrongchoice{Parce qu'ils sont mal écrits}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q19}
    Un algorithme effectue 10⁹ opérations
élémentaires. Sur un PC moderne (~ 10⁹
opérations / seconde), combien de temps
attendra-t-on ?
    \begin{choices}
    \correctchoice{Environ une seconde}
    \wrongchoice{Plusieurs années}
    \wrongchoice{Plusieurs jours}
    \wrongchoice{Quelques nanosecondes}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q20}
    Pour n petit (n = 10), un algorithme O(n²) est-il
forcément moins efficace qu'un O(n log n) ?
    \begin{choices}
    \wrongchoice{Aucun rapport entre les deux}
    \wrongchoice{Oui, O(n²) est toujours moins efficace}
    \correctchoice{Non, sur les petites entrées les constantes peuvent dominer et l'algorithme « plus simple » peut être plus rapide}
    \wrongchoice{Cela dépend de la couleur de l'écran}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q21}
    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}
    \begin{choices}
    \correctchoice{O(n²)}
    \wrongchoice{O(n log n)}
    \wrongchoice{O(n)}
    \wrongchoice{O(n³)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q22}
    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 ?
    \begin{choices}
    \wrongchoice{Quadratique}
    \wrongchoice{Constant}
    \correctchoice{Logarithmique}
    \wrongchoice{Linéaire}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q23}
    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) ?
    \begin{choices}
    \wrongchoice{Une parabole}
    \wrongchoice{Une courbe exponentielle}
    \correctchoice{Une droite de pente 2}
    \wrongchoice{Une horizontale}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q24}
    Une fonction en O(n) est-elle forcément aussi
en O(n²) ?
    \begin{choices}
    \wrongchoice{Non, ce sont des classes différentes}
    \correctchoice{Oui : O(n²) est une borne supérieure plus large, qui inclut O(n)}
    \wrongchoice{Oui, mais seulement pour des n positifs}
    \wrongchoice{Non, sauf si n est petit}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q25}
    Parmi les affirmations suivantes sur la
complexité, laquelle est \textbf{fausse} ?
    \begin{choices}
    \wrongchoice{La complexité spatiale mesure la mémoire additionnelle utilisée}
    \correctchoice{Un algorithme O(n) est toujours plus rapide qu'un algorithme O(n²)}
    \wrongchoice{Pour les boucles imbriquées, on multiplie les complexités ; pour les séquences, on prend le maximum}
    \wrongchoice{La complexité O ignore les constantes multiplicatives}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q26}
    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}
    \begin{choices}
    \wrongchoice{O(log n)}
    \wrongchoice{O(1)}
    \correctchoice{O(n)}
    \wrongchoice{O(n²)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q27}
    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é ?
    \begin{choices}
    \wrongchoice{O(n) en fonction de la valeur n}
    \wrongchoice{O(1) car n est une simple variable}
    \correctchoice{O(log n) en fonction de la valeur n (autrement dit, linéaire en fonction du nombre de chiffres)}
    \wrongchoice{O(n²)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q28}
    Parmi ces opérations sur une liste Python de
taille \texttt{n}, laquelle est la plus \textbf{coûteuse}
au pire ?
    \begin{choices}
    \wrongchoice{\texttt{liste[0]} (lecture du premier élément)}
    \correctchoice{\texttt{liste.insert(0, x)} (insertion en tête)}
    \wrongchoice{\texttt{liste.append(x)} (ajout en fin)}
    \wrongchoice{\texttt{len(liste)} (longueur de la liste)}
    \end{choices}
  \end{question}
}

\element{premierecomplexite}{
  \begin{question}{q29}
    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²) ?
    \begin{choices}
    \wrongchoice{Environ 30 (trentaine)}
    \wrongchoice{Environ 10⁸ (cent millions)}
    \correctchoice{Environ 10⁴ (dix mille)}
    \wrongchoice{Environ 10⁶ (un million)}
    \end{choices}
  \end{question}
}


\onecopy{1}{
  \shufflegroup{premierecomplexite}
  \insertgroup{premierecomplexite}
}

\end{document}
