\newpage

\section{Algorithmique}
\begin{figure}
\includegraphics[scale=0.5]{img/uzb.jpg}
\caption{\label{GENEA}Les origines du mot algorithme.}
\end{figure}

L'objectif du cours est de fournir une initiation 
\`a l'algorithmique : temps de calcul, correction, 
implantation en \gcc{langage C} et expérience 
numérique sur un système \SE{GNU/linux}.

 
\subsection{étymologie}

Les organigrammes pour d\'ecrire  des  processus 
de calculs \'etaient tr\`es  \`a la mode dans les 
ann\'ees \annee{70}--\annee{80}. 
Sans vraiment comprendre pourquoi, je constate 
qu'ils ont  tendance \`a  dispara\^{\i}tre des 
enseignements d'informatique laissant le champ 
libre aux langages et algorithmes.   
Algorithme~? Une terminologie qui est rest\'ee 
un temps quelque peu myst\'erieuse. Longtemps, on 
croyait devoir  lire dans le mot algorithme 
le radical grec \emph{arithmos} qui signifie 
\emph{nombre}. Mais, la poursuite \'etymologique 
s'enlise \`a moins de croire en une certaine 
\emph{douleur des nombres}. En effet, seul le 
mot grec \emph{algos} (douleur) admet le radical 
ad\'equat~!  Possible pour les \'etudiants de 
premier cycle qui patogent parfois avec les 
logarithmes \footnote{Quel d'anagramme~!} 
mais pas pour les
arithm\'eticiens grecs~!
Le math\'ematicien italien du \siecle{11}
siècle, L\'eonard de Pise,  rapporte de ses voyages 
m\'editerran\'eens le \emph{sifr} 
de Perse. Lecteur des textes math\'ematiques arabes, il semblerait
bien que L\'eonard de
Pise, alias Fibonacci, soit  \`a l'origine du mot algorithme. 
Un terme qu'il aurait utilis\'e pour d\'ecrire les 
proc\'ed\'es de calculs qu'il peut lire dans le trait\'e {
\sl Kitab 
al-mukhtasar 
fi hisab 
al-jabr 
wa-l-muqabala} 
(r\`egles de restaurations et r\'eductions) 
\'ecrit par un certain Al-Kwarezmi médecin et math\'ematicien 
arabe du \siecle{9} dont le patronyme exact  est : 
Abu Ja'far Mohammed ibn M\^us\^a al-Kwarizmi, p\`ere de Jafar, 
Mohammed, fils de Mo\"{\i}se et  natif d'al-Kwarezmi. 
Le Kh\^oresme, ex-Khanat de Khiva,  situ\'e sur la partie
inf\'erieure du fleuve Amou-Syria est devenue  une  petite ville 
de l'Ouzb\'ekistan
bien au sud la mer d'Aral. 
Cette micro-introduction est tir\'ee de la généalogie
du cryptosystème \href{http://langevin.univ-tln.fr/notes/rsa/rsa.pdf}{RSA} 
que je propose dans \cite{PL},
les détails historiques sont dans le volume 1 de l'encyclop\'edie
{\sl The Art of Computer Programming} de Donald  Knuth \cite{KNUTH1}''.

\subsection{syntaxe}
Il existe plusieurs façons de d'écrire un algorithme :
organigramme, pseudo-code, langage \gcc{C}, et python 
trés à la mode ces temps-ci sur les forums. Quelque 
soit l'approche, il s'agit d'exposer  dans 
un langage clair et concis, prélude à la mise en oeuvre dans un langage 
de programmation, une méthode de résolution d'un problème. Le
plus ancien des algorithmes calcule le PGCD de deux entiers
postifs (nombres). 


\begin{lstlisting}[float,style=algo, label=OLD, 
title={Un algorithme ancestral pour calculer le plus grand
commun diviseur de deux nombres entiers.}]
Euclide ( a, b : nombre )
nombre r
debut
  tantque ( b > 0 ) 
       r := a mod b
       a := b
       b := r
  ftq
  retourner r
fin
\end{lstlisting}

\subsection{analyse}

L'analyse de l'algorithme à pour but
de prédire la performance du temps 
de calcul des implantations. Nous verrons
que pour des instances de taille $t$, 
le corps de la boucle de l'algorithme
d'Euclide est exécuté au plus $t$ fois. 


On peut se convaincre de ce fait mathématique
en utilisant une implantation en langage \gcc{C}
qui calcule $I(a,b)$

\penalty -10000

\begin{lstlisting}[style=gcc]
typedef unsigned int uint
uint nbiter ( uint a )
{ uint r, cpt, scr = 0, x;
  for ( x = 1; x < a; x++ ){
       b   = x;
       cpt = 0;
       while ( b ) {
          r = a % b;
          a = b;
          b = r;
       cpt++
       }
       if ( cpt > scr ) cpt = scr;
  }
  return cpt;
}
\end{lstlisting}

Notons $I(a,b)$ le nombre d'itérations,
le graphe de 
$$
        a\mapsto\sup_{0<b\leq a} I(a,b)
$$

\includegraphics[scale=0.5]{euclide/iter.png}


L'algoritme de réduction modulaire consommant
au plus $t^2$ étapes élémentaires, le temps de calcul de
l'algorithme d'Euclide sur des instances
de taille $t$ est majoré par une fonction
cubique i.e. de la forme $At^3$. 


\includegraphics[scale=0.5]{euclide/perf.png}

Une mesure empirique du temps de calcul, avec
une implantation multiprécision,
montre
que l'estimation cubique n'est pas optimale,
en réalité, la taille des nombres diminuant
au cours des itérations euclidienne. Avec
plus de finesse, on peut effectivement montrer
que l'algorithme est de complexité au plus
quadratique.

\lstinputlisting[float,style=Python]{euclide/perf.py}

\subsection{preuve}

La preuve de correction algorithmique à
s'appuie sur les notions de variant et d'invariant
de bouble. Un
variant est une grandeur qui décroit à chaque
itération sans descendre en dessous d'un certain seuil. Un
invariant est une formule logique valide aprés chaque
itération. Dans
le cas de l'algorithme d'Euclide, la fonction $b$ est
un variant,  alors que les formules logiques :
$$
0<b\leq a,
\quad
\pgcd(a,b)=\delta,
$$

sont des invariants de la boucle
euclidienne. Le variant prouve
l'arrêt de la boucle, l'invariant
permet d'élaborer une preuve.

\subsection{mise en oeuvre}

\lstinputlisting[float,title=makefile,style=make]{implantation/makefile}
\lstinputlisting[float,title=arithmos.h,style=gcc]{implantation/arithmos.h}
\lstinputlisting[float,title=arithmos.c,style=gcc]{implantation/arithmos.c}
\lstinputlisting[float,title=gcd.c,style=gcc]{implantation/gcd.c}

Le fichier de définition \gcc{arithmos.h}, 
les sources \gcc{arithmos.c} et \gcc{gcd.c} illustre 
la mise en oeuvre d'une expérience numérique maintenue
par le fichier \shell{makefile}.


\includegraphics[scale=0.5]{implantation/gcd.png}

D'aprés Knuth,
$$
	\tau(a) = \frac 1{\varphi{(a)}} 
\sum_{\substack{0\leq b<a\\{\rm gcd(a,b)=1}}} I(a,b)= \frac{12}{\pi^2} \log(2)\log(a) + C - 1 + {\rm O}( a^{-1/6-\epsilon} )
$$
où $C\approx 1.467$  désigne la constante de Porter.


\subsection{numération}

Une fois choisie une base $B>1$, 
tout nombre entier $z<B^n$ se décompose sous la forme 

$$
       z =(z_n\ldots z_2z_1)_B = \sum_{i=1}^n z_i B^{i-1},
       \quad
       0\leq z_i < B
$$

Dans ce cas, $z_1$ est le sifr des unités, et
si $z_n$ n'est pas nul alors $z$ est dit de taille
$n$ et $z_n$ est le chiffre  dominant de $z$. On
représente un nombre  par un tableau de chiffre,
pour s'intéresser aux quotient et réduction
modulo un chiffre en langage \gcc{C} :

\begin{lstlisting}[style=gcc, emph={sifr, nombre}]
#define TAILLE 1024
#define BASE   16
#typedef uint sifr 
#typedef sifr nombre[ TAILLE ]
// pour un chiffre b i.e. b < BASE
sifr    mod( nombre z, sifr b )
void    div( nombre z, sifr b )
void   init( nombre z, int  v )
\end{lstlisting}

\begin{exercice}
Implanter les primitives \gcc{mod}, \gcc{div}
et \gcc{init} en précisant le temps de calcul.
\end{exercice}

\begin{exercice}
Faire une expérience numérique pour 
mesurer le temps de calcul d'une réduction
modulaire en \tty{python}.
\end{exercice}


\subsection{débordement}

\lstinputlisting[float, style=gcc, title=ordre.c]{intro/ordre.c}

Soit $n$ un module. 
L'ordre multiplicatif modulaire d'un entier 
$x$ premier avec $n$ désigne le plus petit entier 
$f$ tel que $x^f \equiv 1 \pmod n$. Un tel entier
est bien défini  à condition que $x$ soit inversible
modulo $n$. En effet, l'entier $k$ variant, 
la suite $x^k\pmod n$ prenant ses valeurs dans un ensemble
fini, il existe $j>i$ tel que :
$$
	x^j = x^i \pmod n \Longrightarrow  x^{j-i} = 1 \pmod n,
$$
on peut alors montrer que $f$ divise $j-i$, et c'est bien
le plus petit entier qui vérifie $x^k=1 \pmod n$.



\begin{lstlisting}[style=term]
:: gcc -Wall bord.c -o bord.exe
:: x=2147483648
:: n=658812288653553079
:: ./bord.exe $x $n
ordre de 2147483648 modx 658812288653553079 > 255
:: bc <<< "( $x ^ 3 ) % $n"
1
\end{lstlisting}

\begin{exercice}
Observer les commandes passées sur le terminal.

\begin{enumerate}
\item Il y a un soucis, pourquoi ?
\item Faire un diagnostic !
\item Comment sortir de ce mauvais pas?
\end{enumerate}

{\sl Indication : } utiliser \shell{bc -l} pour calculer
le logarithme à base $2$ de $x$ et $n$.
\end{exercice}

