\documentclass[a4paper]{article}
% \documentclass{feuilleTD}


\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}

\usepackage[bistream-charter]{mathdesign}

\usepackage[francais,bloc,completemulti]{automultiplechoice}
\usepackage{multicol}
\usepackage{fp}
\usepackage[french,vlined,linesnumbered]{algorithm2e}
\newcommand\algo\textsc
\usepackage{lastpage}

\usepackage{graphicx}
\graphicspath{{../../fig/}}
\newcommand\svg[2][\textwidth]{\def\svgwidth{#1}\input{../../fig/#2.svg_tex}}


\renewcommand\multiSymbole{}

\begin{document}


\setdefaultgroupmode{withreplacement}

\element{grandO1}{
\begin{questionmult}{grandO1a}\bareme{b=.2,m=-.4,p=0}
\FPeval\VQe{trunc(2+random*3,0)}
\FPeval\VQelog{trunc(10+random*10,0)}
Soit $f(n) = \VQe n^3  + \log(n)^{\VQelog} - 4$ et $g(n) = n(n+1)(2n-1)/6$. Alors
\begin{multicols}{2}
\begin{reponses}[o]
  \mauvaise{$\lim_{+\infty}(f/g) = 0$}
  \bonne{$\lim_{+\infty}(f/g)\in ]0, +\infty[$}
  \mauvaise{$\lim_{+\infty} (f/g) = +\infty$}
  \bonne{$f = O(g)$}
  \bonne{$g = O(f)$}
\end{reponses}\end{multicols}
\end{questionmult}
}

\element{grandO1}{
\begin{questionmult}{grandO1b}\bareme{b=.2,m=-.4,p=0}
\FPeval\VQe{trunc(2+random*3,0)}
\FPeval\VQelog{trunc(10+random*10,0)}
Soit $f(n) =n(n+1)(2n-1)/6$ et $g(n) =  \VQe n^3  + \log(n)^{\VQelog} + 1$. Alors
\begin{multicols}{2}
\begin{reponses}[o]
  \mauvaise{$\lim_{+\infty}(f/g) = 0$}
  \bonne{$\lim_{+\infty}(f/g)\in ]0, +\infty[$}
  \mauvaise{$\lim_{+\infty} (f/g) = +\infty$}
  \bonne{$f = O(g)$}
  \bonne{$g = O(f)$}
\end{reponses}\end{multicols}
\end{questionmult}
}


\element{grandO2}{
\begin{questionmult}{grandO2a}\bareme{b=.2,m=-.4,p=0}
\FPeval\VQa{trunc(3+random*4,0)}
  Soit $f(n) = \log(n)^{\VQa}$ et $g(n) = (1+n^{1/20})\times(1+\sqrt n)$. Alors
    \begin{multicols}{2}
  \begin{reponses}[o]
    \bonne{$\lim_{+\infty}(f/g) = 0$}
    \mauvaise{$\lim_{+\infty}(f/g)\in ]0, +\infty[$}
    \mauvaise{$\lim_{+\infty} (f/g) = +\infty$}
    \bonne{$f = O(g)$}
    \mauvaise{$g = O(f)$}
  \end{reponses}
\end{multicols}
\end{questionmult}
}
\element{grandO2}{
\begin{questionmult}{grandO2b}\bareme{b=.2,m=-.4,p=0}
\FPeval\VQa{trunc(3+random*4,0)}
  Soit $f(n) = (1+n^{1/20})\times(1+\sqrt n)$ et $g(n) = \log(n)^{\VQa}$. Alors
    \begin{multicols}{2}
  \begin{reponses}[o]
    \mauvaise{$\lim_{+\infty}(f/g) = 0$}
    \mauvaise{$\lim_{+\infty}(f/g)\in ]0, +\infty[$}
    \bonne{$\lim_{+\infty} (f/g) = +\infty$}
    \mauvaise{$f = O(g)$}
    \bonne{$g = O(f)$}
  \end{reponses}
\end{multicols}
\end{questionmult}
}
\element{grandO3}{
\begin{questionmult}{grandO3a}\bareme{default.EXACT=0,formula=(NMC>0 || EXACT==0)?0:((NBC == NB)?1:0.75)}
  Soit $f(n) = 2^{3\log(n) + 2}$. Alors
    \begin{multicols}{3}
  \begin{reponses}[o]\AMCnoCompleteMulti
    \mauvaise{$f(n) = O(\log(n))$}
    \mauvaise{$f(n) = O(n\log(n))$}
    \mauvaise{$f(n) = O(n^2)$}
    \mauvaise{$f(n) = O(n^2\log(n))$}
    \bonne{$f(n) = O(n^3)$}\bareme{set.EXACT = 1}
    \bonne{$f(n) = O(2^n)$}
    \bonne{$f(n) = O(n^3\log(n))$}
    \bonne{$f(n) = O(2^{n\log(n)})$}
    \bonne{$f(n) = O(2^{n^2})$}
  \end{reponses}
\end{multicols}
\end{questionmult}
}

\element{grandO3}{
\begin{questionmult}{grandO3b}\bareme{default.EXACT=0,formula=(NMC>0 || EXACT==0)?0:((NBC == NB)?1:0.75)}
  Soit $f(n) = 2^{2\log(n) + 3}$. Alors
    \begin{multicols}{3}
  \begin{reponses}[o]\AMCnoCompleteMulti
    \mauvaise{$f(n) = O(\log(n))$}
    \mauvaise{$f(n) = O(n\log(n))$}
    \bonne{$f(n) = O(n^2)$}\bareme{set.EXACT = 1}
    \bonne{$f(n) = O(n^2\log(n))$}
    \bonne{$f(n) = O(n^3)$}
    \bonne{$f(n) = O(2^n)$}
    \bonne{$f(n) = O(n^3\log(n))$}
    \bonne{$f(n) = O(2^{n\log(n)})$}
    \bonne{$f(n) = O(2^{n^2})$}
  \end{reponses}
\end{multicols}
\end{questionmult}
}

\element{algo1}{
  \begin{questionmult}{algo1a}\bareme{default.EXACT=0,formula=(NMC>0 || EXACT==0)?0:((NBC == NB)?1:0.75)}
    Quelle est la complexité de l'algorithme ci-dessous ?
    \begin{multicols}{2}
      \begin{algorithm}[H]
        \TitleOfAlgo{$\algo{Algo}(n)$}
        \Pour{$i = n-1$ à $0$}{
          \texttt{<op elem>}\;
          \Pour{$j = 0$ à $n/2$}{
            \texttt{<op elem>}\;
          }
          \Pour{$k = i$ à $n-1$}{
            \texttt{<op elem>}\;
          }
        }
      \end{algorithm}

    \begin{reponses}[o]\AMCnoCompleteMulti
      \mauvaise{$O(\log n)$}
      \mauvaise{$O(n)$}
      \mauvaise{$O(n\log n)$}
      \bonne{$O(n^2)$}\bareme{set.EXACT=1}
      \bonne{$O(n^3)$}
      \bonne{$O(2^n)$}
    \end{reponses}
  \end{multicols}
  \end{questionmult}
}

\element{algo1}{
  \begin{questionmult}{algo1b}\bareme{default.EXACT=0,formula=(NMC>0 || EXACT==0)?0:((NBC == NB)?1:0.75)}
    Quelle est la complexité de l'algorithme ci-dessous ?
    \begin{multicols}{2}
      \begin{algorithm}[H]
        \TitleOfAlgo{$\algo{Algo}(n)$}
        \Pour{$i = 0$ à $n-1$}{
          \Pour{$j = n-1$ à $i$}{
            \texttt{<op elem>}\;
            \Pour{$k = n/2$ à $n$}{
              \texttt{<op elem>}\;
            }
          }
        }
      \end{algorithm}

    \begin{reponses}[o]\AMCnoCompleteMulti
      \mauvaise{$O(\log n)$}
      \mauvaise{$O(n)$}
      \mauvaise{$O(n\log n)$}
      \mauvaise{$O(n^2)$}
      \bonne{$O(n^3)$}\bareme{set.EXACT=1}
      \bonne{$O(2^n)$}
    \end{reponses}
  \end{multicols}
  \end{questionmult}
}

\element{algo2}{
  \begin{questionmult}{algo2a}\bareme{default.EXACT=0,formula=(NMC>0 || EXACT==0)?0:((NBC == NB)?1:0.75)}
    Quelle est la complexité de l'algorithme ci-dessous ?
    \begin{multicols}{3}
      \begin{algorithm}[H]
        \TitleOfAlgo{$\algo{Algo}(n)$}
        $i\gets 1$\;
        \Tq{$i < n$}{
          \texttt{<op elem>}\;
          $i\gets 2i$\;
        }
      \end{algorithm}

    \begin{reponses}[o]\AMCnoCompleteMulti
      \bonne{$O(\log n)$}\bareme{set.EXACT=1}
      \bonne{$O(n)$}
      \bonne{$O(n\log n)$}
      \bonne{$O(n^2)$}
      \bonne{$O(n^3)$}
      \bonne{$O(2^n)$}
    \end{reponses}
  \end{multicols}
  \end{questionmult}
}

\element{algo2}{
  \begin{questionmult}{algo2b}\bareme{default.EXACT=0,formula=(NMC>0 || EXACT==0)?0:((NBC == NB)?1:0.75)}
    Quelle est la complexité de l'algorithme ci-dessous ?
    \begin{multicols}{3}
      \begin{algorithm}[H]
        \TitleOfAlgo{$\algo{Algo}(n)$}
        $j\gets 1$\;
        \Tq{$n > j$}{
          $j\gets 2j$\;
          \texttt{<op elem>}\;
          }
      \end{algorithm}

    \begin{reponses}[o]\AMCnoCompleteMulti
      \bonne{$O(\log n)$}\bareme{set.EXACT=1}
      \bonne{$O(n)$}
      \bonne{$O(n\log n)$}
      \bonne{$O(n^2)$}
      \bonne{$O(n^3)$}
      \bonne{$O(2^n)$}
    \end{reponses}
  \end{multicols}
  \end{questionmult}
}



\element{tas}{
    \begin{question}{tas1}
    Soit $T = [2, 0, 5, 8, 4, 1, 3, 6, 7, 9]$. Quel tableau obtient-on après $\algo{Entasser}(T, 0)$ ?
    \begin{reponseshoriz}
    \bonne{$[5, 0, 3, 8, 4, 1, 2, 6, 7, 9]$}
    \mauvaise{$[9, 8, 3, 7, 4, 1, 2, 6, 5, 0]$}
    \mauvaise{$[5, 0, 2, 8, 4, 1, 3, 6, 7, 9]$}
    \end{reponseshoriz}
    \end{question}
}

\element{tas}{
    \begin{question}{tas2}
    Soit $T = [0, 8, 4, 1, 7, 9, 2, 3, 5, 6]$. Quel tableau obtient-on après $\algo{Entasser}(T, 0)$ ?
    \begin{reponseshoriz}
    \bonne{$[8, 7, 4, 1, 6, 9, 2, 3, 5, 0]$}
    \mauvaise{$[9, 7, 8, 5, 6, 4, 2, 3, 1, 0]$}
    \mauvaise{$[8, 0, 4, 1, 7, 9, 2, 3, 5, 6]$}
    \end{reponseshoriz}
    \end{question}
}

\element{tasoupas}{
    \begin{questionmult}{tasoupas1}\bareme{b = 0.2, m=-0.4, p=0,MAX=1}
    Cocher les tableaux qui sont des tas.
    \begin{reponseshoriz}\AMCnoCompleteMulti
    \mauvaise{$[1, 3, 4, 8, 9, 7, 2, 5, 6, 0]$}
    \mauvaise{$[1, 8, 4, 3, 7, 2, 9, 6, 5, 0]$}
       \bonne{$[0, 1, 2, 5, 3, 7, 4, 8, 6, 9]$}
    \mauvaise{$[0, 2, 3, 5, 6, 7, 4, 8, 1, 9]$}
       \bonne{$[9, 8, 7, 6, 3, 2, 4, 5, 0, 1]$}
    \mauvaise{$[9, 8, 7, 5, 3, 2, 4, 6, 0, 1]$}
    \end{reponseshoriz}
    \end{questionmult}
}

\element{tasoupas}{
    \begin{questionmult}{tasoupas2}\bareme{b = 0.2, m=-0.4, p=0,MAX=1}
    Cocher les tableaux qui sont des tas.
    \begin{reponseshoriz}\AMCnoCompleteMulti
    \mauvaise{$[7, 2, 1, 4, 6, 0, 8, 9, 5, 3]$}
    \mauvaise{$[1, 3, 0, 5, 4, 8, 6, 2, 7, 9]$}
    \mauvaise{$[0, 3, 1, 4, 5, 8, 6, 2, 7, 9]$}
    \mauvaise{$[9, 7, 8, 5, 2, 1, 6, 0, 3, 4]$}
    \bonne{$[0, 2, 1, 3, 4, 8, 6, 5, 7, 9]$}
    \bonne{$[9, 7, 8, 5, 4, 1, 6, 0, 3, 2]$}
    \end{reponseshoriz}
    \end{questionmult}
}

\element{aff}{
\begin{questionmult}{affirmations}\bareme{b = 0.2, m=-0.4, p=0,MAX=1}
Cocher toutes les affirmations correctes (ABR : arbre binaire de recherche).
\begin{reponses}\AMCnoCompleteMulti
\bonne{Un arbre binaire de hauteur $h$ a moins de $2^{h+1}$ nœuds.}
\bonne{Un ABR à $n$ nœuds peut avoir une hauteur $n-1$.}
\bonne{L'insertion d'un élément dans un ABR de hauteur $h$ s'effectue en $O(h)$.}
\mauvaise{On peut trouver l'élément maximal d'un ABR à $n$ nœuds en temps $O(\log n)$.}
\mauvaise{Il existe un unique ABR représentant un ensemble donné de $n$ valeurs.}
\mauvaise{Le maximum et le minimum d'un ABR sont des feuilles.}
\end{reponses}
\end{questionmult}
}

\element{abr}{
    \begin{questionmult}{abr1}\bareme{b = 0.2, m=-0.4, p=0,MAX=1}
    On insère (dans cet ordre) les entiers $7$, $4$, $8$, $5$, $2$, $9$, $3$, $1$, $0$ et $6$ dans un ABR initialement vide. Quelles affirmations sont correctes ?
    \begin{reponses}\AMCnoCompleteMulti
    \bonne{L'arbre a une hauteur $4$.}
    \bonne{Le nœud de valeur $5$ est à hauteur $2$.}
    \bonne{Le nœud de valeur $3$ est un fils du nœud de valeur $2$.}
    \mauvaise{L'ABR possède $3$ feuilles.}
    \mauvaise{Le nœud de valeur $8$ n'a pas de fils droit.}
    \bonne{Les nœuds de valeur $4$ et $8$ sont à la même hauteur.}
    \end{reponses}
    \end{questionmult}
}

\element{abr}{
    \begin{questionmult}{abr2}\bareme{b = 0.2, m=-0.4, p=0,MAX=1}
    On insère (dans cet ordre) les entiers $3$, $4$, $7$, $6$, $0$, $5$, $9$, $1$, $2$ et $8$ dans un ABR initialement vide. Quelles affirmations sont correctes ?
    \begin{reponses}\AMCnoCompleteMulti
    \bonne{L'arbre a une hauteur $4$.}
    \mauvaise{Le nœud de valeur $5$ est à hauteur $2$.}
    \mauvaise{Le nœud de valeur $3$ est un fils du nœud de valeur $2$.}
    \bonne{L'ABR possède $3$ feuilles.}
    \bonne{Le nœud de valeur $8$ n'a pas de fils droit.}
    \mauvaise{Les nœuds de valeur $4$ et $8$ sont à la même hauteur.}
    \end{reponses}
    \end{questionmult}
}

\element{sad}{
    \begin{questionmult}{sad1}\AMCnoCompleteMulti\bareme{b=.25,m=-.25,p=0}
    L'algorithme glouton du sac-à-dos est
    \begin{reponses}
    \bonne{utilisable pour le sac-à-dos fractionnaire.}
    \bonne{utilisable pour le sac-à-dos non fractionnaire.}
    \lastchoices
    \bonne{optimal pour le sac-à-dos fractionnaire.}
    \mauvaise{optimal pour le sac-à-dos non fractionnaire.}
    \end{reponses}
    \end{questionmult}
}

\element{supprABR}{
    \begin{questionmult}{supprABR1}\AMCnoCompleteMulti\bareme{b=.25,m=-.25,p=0}
    On supprime la racine de l'ABR ci-dessous. Cocher les affirmations correctes.
    \begin{multicols}{2}
    \svg[4cm]{repABR}

    \begin{reponses}
    \bonne{Les nœuds $3$ et $8$ gardent les mêmes fils.}
    \bonne{La hauteur du nœud $8$ diminue de $1$.}
    \mauvaise{La hauteur de l'ABR diminue de $1$.}
    \mauvaise{La nouvelle racine est le nœud $7$.}
    \end{reponses}
    \end{multicols}
    \end{questionmult}
}

\element{supprABR}{
    \begin{questionmult}{supprABR2}\AMCnoCompleteMulti\bareme{b=.25,m=-.25,p=0}
    On supprime la racine de l'ABR ci-dessous. Cocher les affirmations correctes.
    \begin{multicols}{2}
    \svg[4cm]{repABR}

    \begin{reponses}
    \mauvaise{Le nœud $8$ perd l'un de ses fils.}
    \mauvaise{La hauteur du nœud $8$ est inchangée.}
    \bonne{La hauteur de l'ABR est inchangée.}
    \bonne{La nouvelle racine est le nœud $6$.}
    \end{reponses}
    \end{multicols}
    \end{questionmult}
}

\element{supprTas}{
    \begin{question}{supprTas1}
    On supprime la racine du tas $[9, 7, 8, 2, 6, 5, 4, 1, 0, 3]$. On obtient le tas
    \begin{reponseshoriz}
    \bonne{$[8, 7, 5, 2, 6, 3, 4, 1, 0]$.}
    \mauvaise{$[7, 8, 2, 6, 5, 4, 1, 0, 3]$.}
    \mauvaise{$[8, 7, 4, 6, 5, 2, 1, 0, 3]$.}
    \end{reponseshoriz}
    \end{question}
}

\element{supprTas}{
    \begin{question}{supprTas2}
    On supprime la racine du tas $[9, 8, 6, 5, 7, 1, 2, 3, 0, 4]$. On obtient le tas
    \begin{reponseshoriz}
    \bonne{$[8, 7, 6, 5, 4, 1, 2, 3, 0]$.}
    \mauvaise{$[8, 6, 5, 7, 1, 2, 3, 0, 4]$.}
    \mauvaise{$[8, 7, 5, 6, 1, 2, 3, 0, 4]$.}
    \end{reponseshoriz}
    \end{question}
}


\exemplaire{150}{

%%% debut de l'en-tête des copies :

{\centering \Large\textbf{Exercice 1 -- QCM} }

\noindent\emph{Chaque question peut admettre \textbf{zéro, une ou plusieurs réponses}.
Des points négatifs pourront être affectés à de \emph{très mauvaises} réponses.}

\noindent\emph{Vous devez \textbf{cocher} les cases pour répondre. Pour annuler une case cochée, il faut la noircir complètement.}

% \noindent{\bf QCM  \hfill TEST}
%
% \vspace*{.5cm}
% \begin{minipage}{.4\linewidth}
% \centering\large\bf Test\\ Examen du 01/01/2008\end{minipage}

\AMCcodeHspace=.25em
\AMCcodeVspace=.15em

{\setlength{\parindent}{0pt}\hspace*{\fill}\AMCcodeGridInt{etu}{8}\hspace*{\fill}
\begin{minipage}[b]{6.5cm}
$\longleftarrow{}$\hspace{0pt plus 1cm} codez votre numéro d'étu\-diant ci-contre,
et inscrivez votre nom et prénom ci-dessous.

\vspace{3ex}

\hfill\champnom{\fbox{
    \begin{minipage}{.9\linewidth}
      Nom et prénom :

      \vspace*{.5cm}\dotfill

      \vspace*{.5cm}\dotfill
      \vspace*{1mm}
    \end{minipage}
  }}\hfill\vspace{5ex}\end{minipage}\hspace*{\fill}

}


% \champnom{\fbox{
%                 \begin{minipage}{.5\linewidth}
%                   Nom et prénom :
%
%                   \vspace*{.5cm}\dotfill
%                   \vspace*{1mm}
%                 \end{minipage}
%          }}

% \begin{center}\em
% Durée : 10 minutes.
%
%   Aucun document n'est autorisé.
%   L'usage de la calculatrice est interdit.
%
%   Les questions faisant apparaître le symbole \multiSymbole{} peuvent
%   présenter zéro, une ou plusieurs bonnes réponses. Les autres ont
%   une unique bonne réponse.
%
%   Des points négatifs pourront être affectés à de \emph{très
%     mauvaises} réponses.
% \end{center}
% \vspace{1ex}


%%% fin de l'en-tête

\bigskip


\cleargroup{grandO}
\copygroup[1]{grandO1}{grandO}
\copygroup[1]{grandO2}{grandO}
\copygroup[1]{grandO3}{grandO}
\restituegroupe{grandO}


\cleargroup{algo}
\copygroup[1]{algo1}{algo}
\copygroup[1]{algo2}{algo}
\restituegroupe{algo}

\restituegroupe{aff}

\cleargroup{arbre}
\copygroup[1]{abr}{arbre}
\copygroup[1]{supprABR}{arbre}
\restituegroupe{arbre}

\cleargroup{lestas}
\copygroup[1]{tas}{lestas}
\copygroup[1]{tasoupas}{lestas}
\copygroup[1]{supprTas}{lestas}
\restituegroupe{lestas}

\restituegroupe{sad}


% \AMCaddpagesto{3}

}

\end{document}
