\documentclass[a4paper,12pt]{amsart}
\usepackage{kbexo}
\def\bs{{\char'134}}

\course{N1MA9W05 -- Master CSI}
\num{1}

\begin{document}
\exotitle

\exo Pour un entier $N\geq 1$, on désire construire le vecteur $[1,\dots,N]$.
\Q Quelle complexité attendez-vous ?
\Q Utiliser \kbd{gettime()} pour mesurer le temps écoulé. Quelle est la
complexité pratique des constructeurs suivants:
\qq \kbd{vector(N, i, i);}
\qq \kbd{v = vector(N); for (i=1, N, v[i] = i);}
\qq \kbd{v = [\,]; for (i=1, N, v = concat(v,i));}
\qq \kbd{v = List(); for (i=1, N, listput(v, i));}

\begin{note}
\begin{itemize}
\item Pour chronométrer une instruction trop rapide: chronométrer
une boucle qui l'exécute un grand nombre de fois (et soustraire le temps
pris par la même boucle vide, s'il a une influence).

\item Pour estimer $\alpha,\beta$ dans une fonction $f(N)$ qu'on devine de la
forme $\beta N^\alpha$, il est plus judicieux d'étudier $\ln f(N) / \ln(N)
\simeq \alpha$ d'abord, puis $f(N)/N^\alpha$. On pourrait aussi faire une
régression linéaire sur $\ln f(N) = \alpha \ln N + \ln \beta$ vue comme
fonction de $\ln N$ et trouver simultanément $\alpha$ et $\ln \beta$.
\end{itemize}
\end{note}

\Q Donner des explications possibles.

\exo Soit $n>0$ un entier; $a$, $b$ désignent deux entiers dans $[2^{n-1},
2^n[$.

\Q* Écrire une fonction \kbd{TIME} générique permettant d'estimer la complexité
pratique d'une opération binaire, comme $a,b\to a + b$, sans intervention
manuelle. 

\begin{note}
\begin{itemize}
\item On pourra utiliser \kbd{random()}.
\item Pour estimer le nombre d'itération nécessaire pour obtenir un temps
significatif (en utilisant la technique de boucle du premier exercice), 
commencer par une itération, puis doubler le nombre d'itération tant que le
temps de calcul est inférieur à $1s$ par exemple. Quel est au pire le temps
total passé à chronométrer un calcul qui prendra finalement un temps $T$ (en
comptant le calibrage)?

\item La construction suivante peut être utile (passage d'une fonction
anonyme en paramètre):
\end{itemize}
\end{note}
{\small
\bprog
        TIME(N,a,b, f) = for(i=1, N, f(a, b))
        TIME(10^6, 10,15, (a,b)->a+b)   
@eprog}
\Q Estimer la complexité pratique des opérations suivantes:

\qq $a + b$,\quad $a - b$;
\qq $a \times b$,\quad $a^2$;
\qq $a \mod b$ (opérateur \kbd{\%}),\quad $\floor{a/b}$ (opérateur \kbd{\bs});
\qq division euclidienne de $a$ par $b$ (\kbd{divrem});
\qq $a^{-1}$ dans $\ZM/b\ZM$;
\qq obtention de l'identité de Bezout $au+bv = \pgcd(a,b)$ associée à $(a,b)$.
\end{document}
