\documentclass[a4paper, 12pt]{article}
\usepackage{amsmath, amssymb}


%%%%%%% PDF 

\usepackage{ifpdf}

\ifpdf
  \usepackage[pdftex]{color,graphicx}
  \usepackage[pdftex ,colorlinks=true,
        urlcolor=blue,
        citecolor=blue,
        pdfstartview=FitH]{hyperref} 
\else
  \usepackage[dvips]{color}
  \usepackage[pagebackref,%
              colorlinks=true,urlcolor=blue,citecolor=blue]{hyperref}
\fi

%%%%%%% LISTINGS

\usepackage{listings}

\lstset{% general command to set parameter(s)
   basicstyle=\small,          % print whole listing small
   keywordstyle=\color{black}\bfseries,
                               % underlined bold black keywords
   identifierstyle=,           % nothing happens
   commentstyle=\color{white}, % white comments
   stringstyle=\ttfamily,      % typewriter type for strings % language=C,
   emphstyle=\color{red},
   showstringspaces=false}     % no special string spaces

%%%%%%%% MACROS
\definecolor{darkgreen}{rgb}{0,0.4,0}

\def\gcc#1{\texttt{\textcolor{blue}{#1}}}
\def\shell#1{\texttt{\textcolor{darkgreen}{#1}}}
\def\tty#1{\texttt{\textcolor{magenta}{#1}}}
\def\pgcd{{\textsc{pgcd}}}
\def\nullptr{\textsc{null}}


\title{Preuves et Analyses des Algorithmes S\'eances de Travaux-Pratiques}
\date{Ann\'ee Universitaire 2008}
\author{Ph. Langevin}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\maketitle

\tableofcontents
 
\section{Pr\'eambule}

L'objectif de ces s\'eances de travaux-pratiques est de faire
des exp\'eriences num\'eriques sur des implantations de quelques
algorithmes qui ont \'et\'e vus et \'etudi\'es en cours.

Vous prendrez soin d'organiser votre travail en cr\'eant un 
r\'epertoire de travail principal (\shell{tp31}, par exemple),
dans lequel vous placerez plus tard des r\'epertoires secondaires 
correspondants aux diff\'erents sujets qui seront abord\'es.

Vous utiliserez de fa\c con syst\'ematique la commande \shell{make} de
sorte \`a automatiser la construction et la compilation de vos fichiers, 
les options de compilation \gcc{-Wall} et \gcc{-g} sont obligatoires. Vous
\'eviterez de faire des programmes et commandes interactives, il s'agit
de prendre rapidement l'habitude de g\'erer les options de la ligne de 
commande avec la fonction \gcc{getopt} !


La section (\ref{exemple}) contient quelques exemples de
sources pour vous aider \`a d\'emarrer. 

Enfin, je vous sugg\`ere
d'utiliser un editeur de texte tel que \shell{nedit}, \shell{emacs}, et
\shell{vi}.

\newpage
\section{Suite de Fibonacci}

La suite de Fibonacci $F_n$ est la suite d'entiers positifs
d\'efinie par la relation de r\'ecurrence d'ordre deux~:

\begin{equation}
F_0 = 0,\quad F_1 = 1,\qquad\forall n\geq 2,\  F_n = F_{n-1} + F_{n-2}.
\end{equation}

Nous avons vu en cours que $F_n$ s'exprime \`a partir
des deux racines l'\'equation $X^2=X+1$ qui sont $\phi\approx 1.618$ 
et $\hat\phi\approx -0.6$, par~: 

\begin{equation}
F_n = \frac 1{\sqrt{5}}(\phi^n - \hat\phi^n)
\end{equation}

En particulier, $F_n$ cro\^{\i}t exponentiellement, plus
pr\'ecis\'ement, $F_n$ est \'equivalent \`a $\frac 1{\sqrt{5}} \phi^n$
au voisinage de l'infini. Par exemple $F_{10} = 55$,
$$F_{100}=354224848179261915075$$ et $F_{1000}$ est un nombre de 289 
chiffres d\'ecimaux : 
43 466 557 686 937 456 435 688 527 675 040 625 802 564 660 517 371 
780 402 481 729 089 536
555 417 949 051 890 403 879 840 079 255 169 295 922 593 080 322 634 
775 209 689 623 239 873 322
471 161 642 996 440 906 533 187 938 298 969 649 928 516 003 704 476 
137 795 166 849 228 875

L'objectif de cette s\'eance de travaux-pratiques est de comparer les
implantations it\'erative et r\'ecursive qui ont \'et\'ee vues et
analys\'ees en cours. Les calculs seront faits en utilisant des entiers
non sign\'es de 64 bits.


\subsection{Fibonacci r\'ecursif}

Commencez par implanter une fonction r\'ecursive \gcc{ullong fibrec(int n)} 
pour calculer le $n$-eme terme de la suite de Fibonacci. Ecrire une commande 
\tty{fib.exe} qui prend un entier $n$ en argument sur la ligne de commande
puis calcule et affiche la valeur de $F_n$. Assurez-vous du bon fonctionnement 
de votre fonction.


On note $T_r(n)$ le temps de calcul de cette commande. 

\begin{enumerate}
  \item Utiliser la commande \shell{/usr/bin/time} pour faire des mesures de temps de calcul.
  \item Faire une repr\'esentation graphique avec la commande \shell{gnuplot}.
  \item D\'eterminer les meilleures constantes $A$ et $B$ tel que $T_r(n) = A B^n$.
\end{enumerate}

\subsection{Fibonacci it\'eratif}


Implanter une fonction it\'erative \gcc{ullong fibiter(int n)} 
pour calculer le $n$-eme terme de la suite de Fibonacci. Modifier la
commande \tty{fib.exe} pour choisir le mode de calcul (it\'eratif ou r\'ecursif)
par un jeu d'options appropri\'e (\gcc{-r} ou \gcc{-i} ).



\begin{enumerate}
  \item Utiliser la commande \shell{/usr/bin/time} pour faire des mesures de temps de calcul.
  \item Faire une repr\'esentation graphique avec la commande \shell{gnuplot}.
  \item D\'eterminer une formule du temps de calcul de la version it\'erative.
  \item D\'eterminer le domaine de validit\'e de la fonction \gcc{fibiter( )}.
\end{enumerate}

\subsection{Chronom\'etrage}


Pour chronom\'etrer les temps de calcul, vous utiliserez la
commande \shell{/usr/sbin/time} qui envoie ses r\'esultats sur
la sortie d'erreur standard. Le chronom\'etrage
de la commande \shell{sleep 5} est obtenu par~:

\shell{/usr/bin/time --format=" duree=\%E cpu=\%U"  sleep 5}

qui affichera~:

\tty{duree=0:05.01 cpu=0.00}

L'information de chronom\'etrage passe par le canal
standard d'erreur. Pour r\'ecup\'erer ce r\'esultat
dans un fichier, il faut \emph{rediriger} ce canal 
vers la sortie standard ~:

\shell{/usr/bin/time --format=" duree=\%E cpu=\%U" sleep 5 2>\&1 | grep duree > tempo.txt}

\newpage
\section{Algorithmes Additifs}

L'objectif de cette s\'eance de travaux pratiques est de r\'ealiser
une commande \shell{fib -n: [-b:]} pour calculer le $n$-i\`eme terme 
de la suite de fibonacci dans la base sp\'ecifi\'ee.

\subsection{Registre}
Un  nombre est repr\'esent\'e par un tableau de chiffres
dans une certaine base. Pour des raisons de commodit\'es, dans 
les programme que vous r\'ealiserez, tous les nombres 
seront repr\'esent\'es dans la m\^eme base, et ils auront
la m\^eme taille; c'est l'approche \emph{registre}. La base et la taille 
seront d\'efinis par l'utilisateur. Ci-dessous un exemple
de programme qui initialise un nombre \`a une certaine valeur, puis
affiche ce nombre. 

\lstinputlisting[emph={BASE, TAILLE, NOMBRE, valeur, init, print}, language={C}]{tp2/nombre.c}

\subsection{algorithmes additifs}

Implanter les algorithmes additifs de base du cours. Les implantations
devront d\'etecter les \emph{d\'epassements de capacit\'e} (overflows).

\begin{enumerate}
  \item \gcc{Inc( NOMBRE z ) } qui r\'ealise $z\leftarrow z+1$.
  \item \gcc{Add( NOMBRE y, x )}  qui r\'ealise $y\leftarrow x+y$.
  \item \gcc{Dec( NOMBRE z )}  qui r\'ealise $z\leftarrow z+1$.
\end{enumerate}


\subsection{nombres de Fibonacci}


\begin{enumerate}
  \item Implanter la fonction \texttt{int taille(int b, n)} qui d\'etermine 
un majorant de la taille de $F_n$ en base $b$.
\item Implanter une fonction \gcc{NOMBRE fib( int n)}
\item V\'efifier le bon fonctionnement de votre programme en calculant 
$F_{1000}$ en base 10.
\item D\'eterminer une expression du temps de calcul en fonction de $n$ en base 10.
\item Pour quelles valeurs de $n$ pourrait-on calculer $F_n$ en moins de 15 minutes ?
\end{enumerate}

\newpage
\section{Algorithmes Multiplicatif}

L'objectif de cette s\'eance de travaux pratiques est de r\'ealiser
une commande \shell{fact -n: [-b:]} pour calculer le $n!$ dans la base 
sp\'ecifi\'ee.
\subsection{Algorithmes multiplicatifs}

Implanter les algorithmes additifs de base du cours. Les implantations
devront d\'etecter les \emph{d\'epassements de capacit\'e} (overflows).


\begin{enumerate}
  \item \gcc{cmul( NOMBRE z , CHIFFRE c) } qui r\'ealise $z\leftarrow c*z$.
  \item \gcc{ prd( NOMBRE y, x )}  qui r\'ealise $y\leftarrow x*y$. Cette fonction
sera utilis\'ee dans le prochain sujet. L'implantation peut \^etre diff\'er\'ee.
\end{enumerate}


\subsection{Factorielle}


\begin{enumerate}
  \item Implanter la fonction \texttt{int taille(int b, n)} qui d\'etermine 
un majorant de la taille de $n!$ en base $b$.
\item Implanter une fonction \gcc{NOMBRE fact( int n)}
\item V\'efifier le bon fonctionnement de votre programme en calculant 
$100!$ en base 10.
\item D\'eterminer une expression du temps de calcul en fonction de $n$ en base 10.
\item Pour quelles valeurs de $n$ pourrait-on calculer $n!$ en moins de 15 minutes ?
\end{enumerate}

\newpage
\section{Dichotomie}
L'objectif de cette s\'eance de travaux pratiques est de r\'ealiser
une commande \shell{racine -n: [-b:]} pour calculer la racine carr\'ee
enti\`ere du nombre $n$ dans la base 
sp\'ecifi\'ee.
\subsection{Algorithmes de base}

Implanter les algorithmes de base du cours. Les implantations
devront d\'etecter les \emph{d\'epassements de capacit\'e} (overflows).


\begin{enumerate}
   \item \gcc{int cmp( NOMBRE y, x) } pour comparer $x$ et $y$.
  \item \gcc{cdiv( NOMBRE z, CHIFFRE c) } qui r\'ealise $z\leftarrow z/c$.
  \item \gcc{ prd( NOMBRE y, x )}  qui r\'ealise $y\leftarrow x*y$.
\end{enumerate}

\subsection{Racine carr\'ee}

Implanter le calcul de la racine carr\'ee d'un nombre par une
approche dichotomique.

\begin{enumerate}
   \item \gcc{void racine( NOMBRE z ) } qui r\'ealise $z\leftarrow \sqrt{z}$.
\end{enumerate}

\newpage
\section{Algorithme d'Euclide}
L'objectif de cette s\'eance de travaux pratiques est de v\'erifier
exp\'erimentalement le comportement du temps de calcul de l'algorithme
d'Euclide. Etant donn\'es deux entiers positifs $a$ et $b$, on note
$I(a,b)$ le nombre d'it\'eration de l'algorithme d'Euclide pour
d\'eterminer $\pgcd(a,b)$.

\subsection{Nombre d'it\'eration}

\begin{enumerate}
\item Implanter \gcc{ullong pgcd(ullong a,ullong b)} en utilisant l'algorithme
it\'eratif. V\'erifier le bon fonctionnement de votre fonction.  
\item Implanter \gcc{ullong iter(ullong a,ullong b)} qui retourne le nombre
d'it\'erations de l'algorithme d'Euclide.
\item Utiliser \shell{gnuplot} pour repr\'esenter le graphe de la fonction
$$
a\mapsto \sup_{ 0\leq b \leq a} I(a,b).
$$
\end{enumerate}

\subsection{Euclide \'etendu}

\begin{enumerate}
\item Implanter une version r\'ecursive \gcc{void bbrec(ullong a, \ldots *u, ullong b, \dots *v)}  de l'algorithme d'Euclide.
\item Implanter une version it\'erative \gcc{void bbitr(ullong a, \ldots *u, ullong b, \dots *v)}  de l'algorithme d'Euclide.
\item V\'erifier le bon fonctionnement de ces deux implantations.
\item Faire des versions ``verbeuses'' qui tracent l'\'evolution des
variables au cours des \'etapes interm\'ediaires.
\end{enumerate}
\newpage
\section{Exponentiation}

\newpage
\section{Exemples}
\label{exemple}

\subsection{Source}

%% Un exemple de \href{./exemples/decomp.c}{source} en langage \gcc{C}. 

\lstinputlisting[emph={getopt}, numbers=left, language={C}]{exemples/decomp.c}

\newpage
\subsection{makefile}

%% Un mini \href{exemple/makefile}{makefile}.
\lstinputlisting[emph={-Wall, -g}, language={make}]{exemples/makefile}

\newpage
\subsection{script}

%% Un \href{exemple/script.sh}{script} pour \shell{bash}.
\lstinputlisting[language={bash}]{exemples/script.sh}

\newpage
\subsection{gnuplot}

%% Un fichier de \href{exemple/plot.com}{commandes} pour \shell{gnuplot}.

Un exemple de fichier pour tester,
\lstinputlisting[]{exemples/plot.com}

Un fichier pour construire une image au format \tty{fig} pour
la commande \shell{xfig} ou l'outil de conversion d'image \shell{fig2dev}.

\lstinputlisting[]{exemples/plot.cmd}

\begin{center}
\rotatebox{-90}{\includegraphics[scale=0.8]{exemples/data}}
\end{center}
\newpage
\subsection{latex}

Un exemple de source \shell{latex}
\lstinputlisting[language={tex}]{exemples/doc.tex}

\newpage

\end{document}
