% Document Type: LaTeX
% Master File: TP2.tex
% Creator: Roberto DiCosmo [dicosmo@anis]
% Creation Date: Tue Oct  5 19:19:51 1993
\documentstyle[a4]{article}
% *****FULLNAME: /users/formel/dicosmo/Paperi/Miei/Definitions/tdenv.tex
% *****EXPORTBEGS: \input{tdenv}
%
% General \ignore{ . . . } macro.
%
\long\def\ignore#1{\relax}
%
% definition rules environment
%
\newenvironment{rules}{\begin{list}{}{\itemindent.3in\labelwidth0in\labelsep10pt\parskip0pt\partopsep0pt\itemsep0pt\topsep0pt\leftmargin0pt}}{\end{list}}
%
% definition of standard Article environment
%
\def\piripi{\par} % cambiare con \endgraf
\newenvironment{bodydouble}[1]{\endgraf\noindent {\bf #1}\em}{\endgraf}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{notation}[theorem]{Notation}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{rem}[theorem]{}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{exercise}{Exercice}[section]
\newtheorem{remark}[theorem]{Remark}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{exmpl}[theorem]{Example}
\newenvironment{example}{\begin{exmpl}\em}{$\qed$\end{exmpl}}
\newenvironment{tinyexample}{\begin{exmpl}\em\twocolscond{\footnotesize\endgraf\smallskip}{\endgraf}}{$\qed$\end{exmpl}}
\newtheorem{defn}[theorem]{Definition}
\newenvironment{definition}{\begin{dfntn}\em}{$\qed$\end{dfntn}}
\newtheorem{lgrthm}[theorem]{Algorithm}
\newenvironment{algorithm}{\begin{lgrthm}\em}{\end{lgrthm}}
\newtheorem{xms}[theorem]{Axioms}
\newenvironment{abstract2}[1]{\small\centerline{#1}\begin{list}{}{\rightmargin=\leftmargin} \item}{ \end{list} \normalsize }
\newenvironment{axioms}{\begin{xms}\em}{\end{xms}}
\newenvironment{proof}{\begin{trivlist}\item[]\hspace{\parindent}{\em Proof.}}{$\qed$\end{trivlist}}
%
%\newenvironment{remark}{\begin{trivlist}\item[]{\bf Remark\ \ }}{\end{trivlist}}
%
\def\qed{\proofbox}
\def\proofbox{\begin{picture}(7,7)%
  \put(0,0){\framebox(7,7){}}\end{picture}}
\def\iff{\mbox{$\leftrightarrow$}}
\def\Iff{\mbox{$\Longleftrightarrow$}}
\def\imp{\mbox{$\rightarrow$}}
\def\revimp{\mbox{$\leftarrow$}}
\def\Imp{\mbox{$\Rightarrow$}}
\def\RevImp{\mbox{$\Leftarrow$}}

\begin{document}
% tp1-enonce.tex
\parindent=0pt
MMFAI\par
Cours de programmation
\bigskip
\bigskip

\centerline {TP num\'ero 2}
\centerline {semaine du 27 octobre 1997}
\bigskip
\bigskip
\bigskip
\centerline{\bf Matrices, Arithm\'etique}%, Fichiers}


\section{Manipulation de matrices}

Nous souhaitons  nous  constituer ici  une  librairie  de fonctions  utiles pour
travailler sur des matrices de taille arbitraire.\\

Notons que en C on \`a le droit d'\'ecrire:

\begin{verbatim}
double *v;

v=(double *)malloc(sizeof(double)*100);

v[23] = 0.0;

\end{verbatim}

\begin{itemize}
  \item on d\'eclare la variable v comme pointeur sur donn\'ees de type double
  \item on alloue de la m\'emoire pour contenir 100 \'el\'ements de type double
        (comme cette taille d\'epend de la machine, on a recours \`a la fonction
         sizeof() qui donne l'espace n\'ecessaire pour m\'emoriser un type donn\'e)
  \item on demande au syst\`eme de se d\'ebrouiller avec l'arithm\'etique des pointeurs
        pour trouver l'adresse du 23\`eme \'el\'ement du vecteur (qui est \verb|v+23*sizeof(double)|)
        en \'ecrivant \verb|v[23]|.
\end{itemize}

Si on sait  que la taille du vecteur  v ne changera  pas, on  peut aussi \'ecrire,
pour  cela, le programme suivant,  qui est plus  clair et pour lequel le syst\`eme
fait tout seul l'allocation de m\'emoire.

\begin{verbatim}
double v[100];

v[23] = 0.0;
\end{verbatim}

Mais pour les matrices cela se passe diff\'eremment: on peut \'ecrire

\begin{verbatim}
double v[10][10];

v[2][3] = 0.0;

\end{verbatim}

\begin{itemize}
  \item on d\'eclare la variable v comme une matrice 10 pour 10
  \item on demande au syst\`eme de calculer le pointeur au 3\`eme
        \'el\'ement de la 2\`eme rang\'ee (qui est \verb|v+(2*10+3)*sizeof(double)|).
\end{itemize}

Mais pour cela, le syst\`eme a besoin de conna\^{\i}tre la  dimension horizontale de la
matrice (10), qui est d\'eclar\'ee explicitement.  On ne  peut pas donc s'attendre \`a
des miracle  quand on  ne  conna\^{\i}t pas \`a  priori la  taille  de  la matrice:  en
\'ecrivant qque chose comme ce qui suit, on se fait justement jeter par le compilo
\begin{verbatim}
double *v;

v=(double *)malloc(sizeof(double)*votretaillepreferee);

v[2][3] = 0.0;

\end{verbatim}

On doit alors s'organiser pour \'ecrire des fonctions adapt\'es \`a ce cas.

\begin{exercise}[get et set]
\'Ecrivez des   fonctions  \verb|get(double    *m,int i,int    j,  int   n)|    et
\verb|set(double *m,int i,int j, int n, double  v)| pour acc\'eder et modifier une
matrice de largeur $n$.
\end{exercise}

\begin{exercise}[manipulation de matrices]
\'Ecrivez les fonctions suivantes
\end{exercise}
\begin{itemize}
  \item \verb|double *id(int n)| qui renvoie la matrice identit\'e de dimension $n$
  \item \verb|double *madd(double *m1, double *m2, int m1rows, int m1cols)| 
        qui additionne deux matrices de dimensions compatibles
  \item \verb|double *mmult(double *m1, double *m2, int m1rows, int m1cols, int m2cols)| 
        qui multiplie deux matrices de dimensions compatibles
  \item \verb|void mprint(double *m, int mrows, int mcols)| qui imprime joliment
        une matrice de taille $mrows*mcols$ ligne par ligne
  \item \verb|double *minput(int mrows, int mcols)| qui lit sur l'entr\'ee standard
        une matrice de taille $mrows*mcols$ ligne par ligne
\end{itemize}

R\'efl\'echissez \`a  la fa\c{c}on de  laquelle vous g\'erez  la m\'emoire dans vos fonctions:
peut-on lib\'erer de la m\'emoire dans ces fonctions?

\section{Fibonacci et th\'eor\`eme de Jones}

On va  essayer ici, avec le peu  d'outils que l'on a en  ce moments, d'\'ecrire un
premier programme qui v\'erifie le th\'eor\`eme de Jones vu en TD la semaine pass\'ee.

Pour cela, il nous faut d'abord le g\'en\'erateur rapide de nombres de Fibonacci.

\begin{exercise}[Fibonacci: $F_n$ en $log(n)$]
\'Ecrivez une fonction \verb|int fibolog(int n)| qui calcule $F_n$ en temps $log n$
en utilisant la  multiplication de matrices vu au  cours du TD  pr\'ec\'edant et les
fonctions que vous venez d'\'ecrire.
\end{exercise}

\begin{exercise}[Tester si un entier est un nombre de Fibonacci]
\'Ecrivez un  programme  b\^ete  pour  tester si un    entier $m$ est  un nombre  de
Fibonacci  $F_n$ (retournez aussi $n$).  Pouvez vous  proposer un algorithme pas
b\^ete?
\end{exercise}

\begin{exercise}[Th\'eor\`eme de Jones]
\'Ecrivez un programme  qui affiche tous les couples  $(x,y)$ pour lesquels le
polyn\^ome
%
\[2xy^4+x^2y^3-2x^3y^2-y^5-x^4y +2y\]
%
prend des valeurs positives, la valeur et le $n$ tel que $F_n$ est cette valeur positive.
\end{exercise}

\begin{exercise}[Exponentiel modulo, pas fait la derni\`ere fois]   \'Ecrivez  un programme qui  lit trois
entiers $a,~b,~n$  et imprime $(a^b) mod~ n$. Pour cela, il peut \^etre utile
de savoir que C dispose d'op\'erateurs pour travailler sur les bits, comme
\verb|<<| et \verb|>>| qui font du roulement a gauche ou \`a droite de la
representation binaire d'un entier (par ex. \verb|1<<4| = 16).
\end{exercise}


{\bf N'oubliez pas de vous d\'econnecter avant d'abandonner le clavier (voir notes du stage Unix).}
\end{document}


\begin{exercise}[Hello World]
\end{exercise}
Essayez le cycle de production pr\'ec\'edent sur le programme suivant
(attention, un \verb|;| de perdu et \c{c}a ne marche pas, mais vous pouvez
vous passer des commentaires!):

\begin{verbatim}
/* ceci est un commentaire */
/* voyons comment imprimer */
#include <stdio.h>;

main()
{
	printf("Bonjour\n");
        exit(0);
}
\end{verbatim}

Remarquons que:
\begin{itemize}
  \item les fichiers avec extension \verb|.h| contiennent des d\'efinitions
  \item on peut inclure des d\'efinitions \`a l'aide de \verb|#include|
  \item C dispose des plusieurs types de base et de m\'ecanismes pour d\'efinir des types utilisateur.
        Pour le moment, contentons nous de savoir que \verb|void|, \verb|int|, \verb|float| et \verb|char|
        sont des types valides
  \item une d\'eclaration de fonction est de la forme
\begin{verbatim}
           TYPE_RESULTAT nom(par1, par2)
           type1 par1;
           type2 par2;
           {
                   ...
                   return RESULTAT;
           }
\end{verbatim}
ou bien, si on suit le standard ANSI,
\begin{verbatim}
           TYPE_RESULTAT nom(type1 par1, type2 par2)
           {
                   ...
                   return RESULTAT;
           }
\end{verbatim}
  \item \emph{tout} en C est une fonction qui prend des param\`etres et renvoie un
        r\'esultat, \emph{mais} on si on  veut on peut  ignorer ces r\'esultats (cas
        de printf), et quand ces r\'esultats ne sont jamais significatifs, le type
        du r\'esultat est \verb|void| (cas  de exit).  Faites donc \verb|man exit|
        et \verb|man printf|.
\end{itemize}
\begin{exercise}[Imprimer avec un \emph{format}]
\end{exercise}

Pour imprimer  un valeur en C,  il faut se  servir de la fonction \verb|printf|,
qui attend une cha\^{\i}ne de  caract\`eres (le \emph{format})  et un nombre arbitraire
de valeurs (m\^eme  0 comme   ci-dessus) qui  seront   plac\'es dans le format   aux
positions indiqu\'ees par les \emph{descripteurs  de  format} tels que  \verb|%d|,
\verb|%f| et \verb|%s|. Modifiez votre programme comme suit et testez \`a nouveau.

\begin{verbatim}
#include <stdio.h>;

main()
{
	printf("Bonjour, ceci (%d) est un entier, ceci (%f) est un flottant",300,3.1416);
	printf("et ceci (%s) est une \"string\" (chaine de caracteres)\n","blah blah");
        exit(0);
}
\end{verbatim}

Faite \verb|man printf| pour plus d'information sur les \emph{formats d'impression}.\\
Notez que \verb|\n| indique un fin de ligne (de l'anglais ``newline'').\\
Comment imprime-t-on un caract\`ere \verb|%| ? Et un \verb|\| ?

\begin{exercise}[Lire une valeur]
\end{exercise}

Pour lire une valeur sur l'entr\'ee standard en C, il faut se servir de la fonction
\verb|scanf|, qui  attend une  cha\^{\i}ne de   caract\`eres (le \emph{format})  et  un
nombre arbitraire de valeurs (m\^eme 0 comme ci-dessus)  qui seront plac\'es dans le
format aux  positions indiqu\'ees par  les \emph{descripteurs de format}  tels que
\verb|%d|, \verb|%f| et \verb|%s|. Modifiez votre programme comme suit et testez
\`a nouveau.

\begin{verbatim}
#include <stdio.h>;

main()
{
int i;
float f;
	printf("Bonjour: rentrez un entier et un flottant separes par 
                des espaces ou un retour chariot\n");
        scanf("%d %f ",&i,&f);
	printf("Bonjour, ceci (%d) est un entier, ceci (%f) est un flottant",i,f);
        exit(0);
}
\end{verbatim}

{\bf R\'emarque:} on a d\'eclar\'e une \emph{variable} \verb|i|  de type \verb|int| et
une \verb|f| de  type \verb|float|.\\ Comme  en  C le passage  de param\`etres aux
fonctions se fait par valeur, on est oblig\'e de donner \`a la fonction \verb|scanf|
l'\emph{adresse} m\'emoire o\`u sont physiquement allou\'es f et i.  Cela se fait avec
l'op\'erateur \verb|&|  qui  renvoie un entier    nomm\'e \emph{pointeur}, vu  qu'il
pointe sur une case m\'emoire.\\

\subsection*{Les instructions minimales}

En C vous pouvez utilisez d\'ej\`a les instructions suivantes:
\begin{itemize}
   \item affectation:\\\verb|i=3;|
   \item addition/soustraction de 1:\\\verb|i++;i--;|
   \item comparaison:\\
         \verb|< > <= >= == !=|
   \item arithmetique simple:\\
         \verb|+ * - / %|
   \item s\'equence:\\\verb|{ inst; inst; }|
   \item conditionnelle:\\\verb|if (expr) inst;|\\
         \verb|if (expr) inst; else inst;|\\
         \verb|expr ? inst : inst|
   \item boucle while:\\
         \verb|while (expr) inst;|
   \item boucle for:\\
         \verb|for (start; end; cont) inst;|\\
         \emph{Exemple:}\\
         \verb|for (i = 0, j = 99; i < j; i++, j--) ...;|
   \item retour d'un r\'esultat:\\\verb|return(expr);|
\end{itemize}

Bien, vous avez  maintenant  le minimum  indispensable pour pouvoir  utiliser le
langage C (on en apprendra plus au fur et \`a  mesure de nos n\'ecessit\'es, mais pour
les plus int\'eress\'es,  il serait mieux de se   procurer la r\'ef\'erence  du langage:
\emph{Kernigan,  Ritchie. Le langage  C}.  Vous pouvez  aussi  trouver un r\'esum\'e
succinct dans \verb|http://www.dmi.ens.fr/~beig/systeme/langageC.html|).\\

Passons donc aux choses s\'erieuses \ldots{}
\clearpage

\subsection*{Premiers programmes}
\begin{exercise}[Algorithme d'Euclide b\^ete]
\'Ecrivez un programme C \verb|eubete.c| qui  lit deux entiers $a,~ b$ sur l'entr\'ee
standard    et  calcule et   imprime  $pgcd(a,b)$   en   utilisant seulement  la
soustraction.
\end{exercise}

\begin{exercise}[Algorithme d'Euclide]
En sachant  que  en C les op\'erations   \verb|+,*,/,-| sur les entiers  sont bien
d\'efinies, \'ecrivez  maintenant un programme  C \verb|eu.c|  qui lit deux  entiers
$a,~ b$ sur l'entr\'ee standard et   calcule  et imprime $pgcd(a,b)$ en   utilisant
l'algorithme vu en cours.
\end{exercise}

\begin{exercise}[Algorithme d'Euclide \'etendu]
\'Ecrivez un programme  C qui r\'ealise l'algorithme d'Euclide \'etendu.
\end{exercise}

\begin{exercise}[Les nombres de Fibonacci]   \'Ecrivez  un programme qui  lit   un
entier $n$  et imprime $F_n$, le  $n$-i\`eme  nombre de Fibonacci.\\  Essayez avec
$40$.  Si au but de  quelques  secondes vous n'avez pas  de  r\'esultat, arr\^etez le
programme (tapez Ctrl-C) et r\'efl\'echissez \`a votre algorithme.
\end{exercise}

\begin{exercise}[Exponentiel modulo]   \'Ecrivez  un programme qui  lit trois
entiers $a,~b,~n$  et imprime $(a^b) mod~ n$. Pour cela, il peut \^etre utile
de savoir que C dispose d'op\'erateurs pour travailler sur les bits, comme
\verb|<<| et \verb|>>| qui font du roulement a gauche ou \`a droite de la
representation binaire d'un entier (par ex. \verb|1<<4| = 16).
\end{exercise}


{\bf N'oubliez pas de vous d\'econnecter avant d'abandonner le clavier (voir notes du stage Unix).}

\end{document}
