\chapterimage{ZeArt}
\chaptertext{}




\chapter{Tris - Complexité}











Dans toute la suite,  on se ramènera au cas du  tri d'une permutation quelconque
de $\mathfrak{S}_n$. On étudiera les
danses  hongroises   disponibles  en
ligne, par exemple: 
\href{https://www.youtube.com/watch?v=kDgvnbUIqT4}{https://www.youtube.com/watch?v=kDgvnbUIqT4}

\section{Tri sélectif...}

On parcourt la liste, on cherche le plus grand et on l'échange avec l'élément le
plus à droite et on recommence avec la liste privée du plus grand élément.

\subsection{Version impérative}

On commence  par chercher l'indice du  maximum d'une liste.  On part de 0  et on
compare à chaque élément  de la liste en faisant évoluer  l'indice du maximum si
nécessaire.

\begin{pythoncode}
def ind_maxi(xs):
    ind_tmp = 0
    n       = len(xs)
    for i in range(n):
        if xs[i] > xs[ind_tmp]:
            ind_tmp = i
    return ind_tmp
\end{pythoncode}


Ensuite, on copie la liste donnée en argument pour ne pas l'écraser. On parcourt
la liste et on  procède aux échanges éventuels entre le  maximum et l'élément de
droite.


\begin{pythoncode}
def tri_select(xs):
    cs = xs.copy()
    n  = len(cs)
    for i in range(n - 1,0,-1):
        i_m = ind_maxi(cs[:i + 1])
        if i_m != i:
            cs[i_m],cs[i] = cs[i],cs[i_m]
        # print(cs) : pour suivre l'évolution
    return cs
\end{pythoncode}

On  va utiliser  \Colorbox{blue!10}{\lstinline{permutation}} de  la bibliothèque
\Colorbox{blue!10}{\lstinline{numpy.random}}   qui   renvoie   une   permutation
uniformément choisie par les permutations de $\mathfrak{S}_n$.

\begin{pythoncode}
In [5]: ls = list(permutation(range(10)))

In [6]: ls
Out[6]: [8, 0, 4, 3, 5, 2, 7, 1, 9, 6]

In [7]: tri_select(ls)
[8, 0, 4, 3, 5, 2, 7, 1, 6, 9]
[6, 0, 4, 3, 5, 2, 7, 1, 8, 9]
[6, 0, 4, 3, 5, 2, 1, 7, 8, 9]
[1, 0, 4, 3, 5, 2, 6, 7, 8, 9]
[1, 0, 4, 3, 2, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 0, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Out[7]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
\end{pythoncode}



\subsection{Correction}

Il s'agit de démontrer la correction des deux fonctions. 

Pour  la  première,  l'invariant  de
boucle est: \og \lstinline{ind_temp}
est   l'indice    du   maximum   des
\lstinline{i + 1} premiers termes de
la  liste  en  argument\fg{}  et  se
démontre par récurrence.


Pour    la     deuxième    fonction,
l'invariant  de  boucle est  \og  la
liste  des élements  d'indices entre
\lstinline{i}  et \lstinline{n  - 1}
est triée\fg{}.



\subsection{Complexité}

Nous  mesurerons  la  complexité  en
nombre de comparaisons.

La           complexité           de
\Colorbox{blue!10}{\lstinline{ind_maxi(xs)}}
est en  $\Theta(n)$ avec $n$  la longueur
de
\Colorbox{blue!10}{\lstinline{xs}}.

En  effet, il  y a  une comparaison
par itération et $n$ itérations.


Pour
\Colorbox{blue!10}{\lstinline{tri_select}},
on  effectue  $n-1$  itérations,  et
chacune                        lance
\Colorbox{blue!10}{\lstinline{ind_maxi}}
sur une liste de longueur $i+1$.

Or
$\displaystyle\sum_{i=1}^{n-1}i+1=\sum_{i=2}^ni=(n-2)\frac{2+n}{2}=\frac{n^2-4}{2}$

donc la complexité est en $\Theta(n^2)$.

\begin{pythoncode}
In [10]: ls = list(permutation(100))

In [11]: %timeit tri_select(ls)
1000 loops, best of 3: 561 μs per loop

In [12]: ls = list(permutation(200))

In [13]: %timeit tri_select(ls)
100 loops, best of 3: 2.03 ms per loop

In [14]: ls = list(permutation(400))

In [15]: %timeit tri_select(ls)
100 loops, best of 3: 7.89 ms per loop
\end{pythoncode}

On  observe   effectivement  que  le temps  est environ  multiplié par  4
quand la taille de la liste double.



\section{Tri par insertion}

C'est le  tri d'un jeu de  carte: on
insère un élément dans un tableau trié petit à petit en comparant le
nouvel élément à insérer aux éléments
déjà triés.

La   version  récursive   est  assez
naturelle.   On  commence par  créer
une fonction qui insère
un nouvel élément dans la liste:

\begin{pythoncode}
def ins_rec(carte,Main):
    if Main == Vide or carte <= tete(Main):
        return [carte] + Main
    return [tete(Main)] + ins_rec(carte,queue(Main))
\end{pythoncode}


Ensuite,  pour trier,  on insère  la
tête dans la queue triée...

\begin{pythoncode}
def tri_ins_rec(Pioche):
    if Pioche == Vide:
        return Vide
    return ins_rec(tete(Pioche),tri_ins_rec(queue(Pioche)))
\end{pythoncode}


Pour la version itérative, on module
aussi:

\begin{pythoncode}
def insere(y,xs):
    cs = (xs.copy()) + [y] # xs est triée et on insère y par la doite
    n = len(xs)
    i = n
    while cs[i] < cs[i - 1] and i > 0:
        cs[i - 1], cs[i] = cs[i], cs[i - 1]
        i -= 1
        # print(cs)
    return cs

def tri_insere(Pioche):
    Main = Vide
    for carte in Pioche:
        Main = insere(carte, Main)
        #print(Main)
    return Main
\end{pythoncode}

La justification et la complexité de
ces fonctions seront à travailler en
TD, mais la complexité semble encore
quadratique:

\begin{pythoncode}
In [29]: ls = list(permutation(100))

In [30]: %timeit tri_insere(ls)
1000 loops, best of 3: 941 μs per loop

In [31]: ls = list(permutation(200))

In [32]: %timeit tri_insere(ls)
100 loops, best of 3: 3.67 ms per loop

In [33]: ls = list(permutation(400))

In [34]: %timeit tri_insere(ls)
100 loops, best of 3: 13.7 ms per loop
\end{pythoncode}





\section{Tri fusion}

Cette  fois,  si le  tableau a  au plus
une  valeur, il  est trié,  sinon on
coupe  le tableau  en deux,  on trie
ces deux moitiés et on fusionne.


\begin{pythoncode}
def tri_fusion(xs):
    t = len(xs) 
    if t < 2:
        return xs
    return fusion(tri_fusion(xs[:t//2]), tri_fusion(xs[t//2:])) 
\end{pythoncode}

Il reste à définir la fusion:

\begin{pythoncode}
def fusion(xs,ys):
    if xs == Vide or ys == Vide:
        return xs + ys
    if tete(xs) < tete(ys):
        return [tete(xs)] + fusion(queue(xs),ys)
    return [tete(ys)] + fusion(xs,queue(ys))
\end{pythoncode}


La  version récursive  est naturelle
mais pose toujours  des problèmes en
Python:  vous  chercherez  donc  une
version    impérative     à    titre
d'exercice...

L'étude  de  la terminaison,  de  la
correction et de la complexité devra
également  être   conduite  par  vos
soins.

Au fait:

\begin{pythoncode}
In [46]: ls = list(permutation(100))

In [47]: %timeit tri_fusion(ls)
1000 loops, best of 3: 296 μs per loop

In [48]: ls = list(permutation(200))

In [49]: %timeit tri_fusion(ls)
1000 loops, best of 3: 642 μs per loop

In [50]: ls = list(permutation(1000))

In [51]: %timeit tri_fusion(ls)
100 loops, best of 3: 3.88 ms per loop
\end{pythoncode}

\newpage
\section{Tri rapide}



\subsection{Le tri et ses comlexités}

Observez et commentez:


\begin{pythoncode}
def partition(pivot,seq):
    p,m,g = [],[],[]
    for item in seq:
        (p if item < pivot else (g if item > pivot  else m)).append(item)
    return p,m,g

def tri_rapide(xs):
    if estVide(xs):
        return Vide
    else:
        pivot = tete(xs)
        p,m,g = partition(pivot, xs)
        return (tri_rapide(p)) + m + (tri_rapide(g))
\end{pythoncode}


Pour   la  complexité   en  moyenne,
montrez                          que
$$K(n)=n-1+\frac{1}{n}\sum_{i=0}^{n-1}(K(i)+K(n-1-i))$$

et en déduire que $$\frac{K(n)}{n+1}=2\sum_{i=2}^n\frac{i-1}{i(i+1)}$$


Que se passe-t-il dans le pire des cas?


Dans quel cas est-on sûr que le tri en $n\log n$?

\subsection{La médiane en temps linéaire}

Il serait très  pratique d'avoir une
médiane  en   temps  linéaire:  nous
aurions  alors  un   tri  rapide  en
$n\log n$ dans le pire des cas.


La  médiane  d'un   tableau  de  $n$
éléments   est  l'élément   de  rang
$\lfloor \frac{n+1}{2}\rfloor$ comme
vous l'avez appris au collège. 

L'idée est bien sûr d'éviter de trier le tableau pour trouver la médiane :-)

On  cherche  donc le  tableau  de  rang  $r_m=\lfloor \frac{n+1}{2}\rfloor$:  on  va
utiliser  la  fonction \lstinline{partition}  en  la  modifiant légèrement  pour
qu'elle renvoie  l'indice du  pivot après  partition. Si cet  indice est  égal à
$r_m$  on a  gagné, s'il  est plus  petit on  cherche la  médiane sur  la partie
droite, sinon sur la partie gauche.


Y a plus qu'à...





\vfill

\eject




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\modeexercice
\section{RECHERCHES}

\includepdf[openright=false,pages={1-6},pagecommand={}]{X2012}

\subsection{Complexité}







\begin{exercice}[Maths II CCP MP 2015: sujet 0]
{\itshape Non, non, ce n'est pas un extrait d'un livre de seconde, c'est un sujet 0
proposé pour l'épreuve de Math du concours CCP...}
  \begin{enumerate}
  \item Écrire une fonction factorielle qui  prend en argument un entier naturel
    $ n$ et renvoie $ n!$ (on n'accepetra pas bien sûr de réponse utilisant la
    propre fonction factorielle du module math de Python ou Scilab).
  \item Écrire une fonction  \lstinline{seuil} qui prend en argument un  entier $ M$ et renvoie
    le plus petit entier naturel $ n$ tel que $ n!>M$.
  \item Écrire une fonction booléenne nommée \lstinline{est_divisible}, qui pend
    en argument un entier naturel $ n$  et renvoie \lstinline{True} si $ n!$ est
    divisible par $ n+1$ et \lstinline{False} sinon.
  \item On considère la fonction suivante nommée \lstinline{mystere}:
    \begin{pythoncode}
def mystere(n):
    s = 0
    for k in range(1,n+1):
        s = s + factorielle(k)
    return s
    \end{pythoncode}
    \begin{enumerate}
    \item Quelle valeur renvoie \lstinline{mystere(4)}?
    \item Déterminer    le     nombre    de    multiplications    qu'effectue
      \lstinline{mystere(n)}.
    \item Proposer une amélioration du script de la fonction \lstinline{mystere}
      afin d'obtenir une complexité linéaire.
    \end{enumerate}
  \end{enumerate}
\end{exercice}





\begin{exercice}[Maths II CCP MP 2015]

\begin{enumerate}

\item Donnez la décomposition en binaire (base 2) de l'entier 21.

On considère la fonction \texttt{mystere} suivante:

\begin{pythoncode}
def mystere(n, b) :
    """Données : n > 0 un entier et b > 0 un entier
       Résultat : ......."""
    t = [] # tableau vide
    while n > 0 :
        c = n % b
        t.append(c)
        n = n // b
    return t
\end{pythoncode}

On  rappelle  que la  méthode  \texttt{append}  rajoute  un  élément en  fin  de
liste. Si  l'on choisit  par exemple  \texttt{t =  [4,5,6]}, alors,  après avoir
exécuté    \mintinline{python}{t.append(12)},   la    liste   a    pour   valeur
\texttt{[4,5,6,12]}.

Pour $k\in\bbn^\star$, on note $c_k$, $t_k$  et $n_k$ les valeurs prises par les
variables  \texttt{c},  \texttt{t} et  \texttt{n}  à  la  sortie de  la  $k$-ème
itération de la boucle \og while\fg{}.
\item     Quelle     est     la    valeur     renvoyée     lorsqu'on     exécute
  \mintinline{python}{mystere(256,10)} ?

On  recopiera  et  complètera  le  tableau suivant  en  rajoutant  les  colonnes
nécessaires pour tracer entièrement l'exécution:

\begin{tabular}[h]{|c|c|c|c}
\hline
  $k$&1&1&$\cdots$\\
\hline
$c_k$&&&$\cdots$\\
\hline
$t_k$&&&$\cdots$\\
\hline
$n_k$&&&$\cdots$\\
\hline
\end{tabular}

\item Soit  $n>0$ un  entier. On exécute  \mintinline{python}{mystere(n,10)}. On
  pose $n_0=n$.
  \begin{enumerate}
  \item Justifier la terminaison de la boucle \mintinline{python}{while}. 
  \item   On  ote   $p$  le   nombre   d'itérations  lors   de  l'exécution   de
    \mintinline{python}{mystere(n, 10)}. Justifiez que pour tout $k\in\llbracket
    0,  p\rrbracket$,  on  a  $n_k \leqslant  \frac{n}{10^k}$.  Déduisez-en  une
    majoration de $p$ en fonction de $n$.


  \end{enumerate}
\item En vous aidant du script de la fonction \mintinline{python}{mystere},
  écrivez  une   fonction  \mintinline{mpython}{somme_chiffres}  qui   prend  en
  argument un entier  naturel et renvoie la somme de  ses chiffres. Par exemple,
  \mintinline{python}{somme_chiffres(256)} devra renvoyer 13.
\item     Écrivez      une     version     récursive     de      la     fonction
  \mintinline{python}{somme_chiffres} que vous nommerez \mintinline{python}{somme_rec}. 





  \end{enumerate}
\end{exercice}









\begin{exercice}[Point fixe]

On dispose  d'un tableau de N  entiers (relatifs) distincts rangés  dans l'ordre
croissant.

Déterminez un algorithme qui renvoie l'éventuel indice $\mathtt{i}$ tel que $\mathtt{a[i] = i}$

  % Hint: binary search. 
\end{exercice}

\begin{exercice}[Recherche en dent de scie]

Un tableau  est constitué  d'une suite  croissante d'entiers  directement suivie
d'une   suite   décroissante  d'entiers.   Tous   les   entiers  sont   supposés
distincts. Déterminez une fonction qui détermine  si un entier appartient ou non
à un  tableau en  dent de scie.  Votre programme doit  effectuer $\sim  3\log N$
comparaisons dans le pire des cas.

% Use a version of binary search, as in BitonicMax.java, to find the maximum (in ~ 1 lg N compares); then use binary search to search in each piece (in ~ 1 lg N compares per piece). 
  
\end{exercice}



\begin{exercice}[Écart mumixam]
  Étant donné un  tableau de N réels,  déterminez un algo en  temps linéaire qui
  détermine la valeur maximum de $\mathtt{a[j]-a[i]}$ pour $j \geqslant i$.

% double best = 0.0;
% double min = a[0];
% for (int i = 0; i < N; i++) {
%     min  = Math.min(a[i], min);
%     best = Math.max(a[i] - min, béat);
% }
\end{exercice}







\begin{exercice}[Multiplication du paysan russe]




Voici ce qu'apprenaient  les petits soviétiques pour multiplier  deux entiers. Une
variante de cet
algorithme a été retrouvée  sur le papyrus de Rhind datant de  1650 avant JC, le
scribe Ahmes affirmant que cet algorithme était  à l'époque vieux de 350 ans. Il
a survécu en Europe occidentale jusqu'aux travaux de Fibonacci.

%\setindent{0cm}
%\begin{flushleft}
%%\begin{minipage}[t]{5cm}
%\begin{figure}

\begin{center}
  \includegraphics[height=7cm]{rhind.jpg}
\end{center}
  


%\end{figure}
%\end{minipage}
%\end{flushleft}
%\setindent{\indentationcours}
%\vspace{-6.3cm}
%\begin{minipage}[t]{\linewidth}
%\setindent{5cm}
\begin{algo}[numbered]
\FUNC{MULRUSSE}{\pfarg x entier ,y: entier, acc:entier}{entier}
\IF{x==0}
\RETURN{acc}
\ELSE
\IF{x est pair}
\RETURN{MULRUSSE(x/2,y*2,acc)}
\ELSE
\RETURN{MULRUSSE((x-1)/2,y*2,acc+y)}
\ENDIF
\ENDIF
\end{algo}
%\setindent{0cm}
%\end{minipage}

Que vaut \lstinline{acc} au départ?

Écrivez une  version récursive  de cet algorithme  en évitant  l'alternative des
lignes 5 à 9.

Écrivez une version impérative de cet algorithme.

Prouvez la correction de cet algorithme.

Étudiez sa complexité.

\pythonc

En python, \Colorbox{blue!10}{\lstinline{x  >> 1}} décale l'entier  $x$ d'un bit
vers la doite et \Colorbox{blue!10}{\lstinline{x << 1}} décale $x$ d'un bit vers
la gauche en complétant par  un zéro à droite, \Colorbox{blue!10}{\lstinline{x& y}}
renvoie  l'entier  obtenu en  faisant  la  conjonction  logique  bit à  bit  des
représentations  binaires de  $x$ et  $y$ et  \Colorbox{blue!10}{\lstinline{~x}}
renvoie le complément à 1 de $x$.

Ré-écrivez la  multiplication russe en  utilisant que  ces opérations bit  à bit
(pas de division ni de multiplication).
  

\end{exercice}




\begin{exercice}[Produit de matrices correct]
  
On a  deux matrices  A et B  dont on  a calculé  le produit. On  a trouvé  C. On
voudrait vérifier que le calcul a été bien mené.

Quelle est la complexité habituelle du calcul d'un produit de matrcies?

On  préfère  choisir  un  vecteur  $\mathbf{v}$  dans  $\bigl\{0,1\bigr\}^n$  et
effecteur le produit $D×\mathbf{v}$ en notant $D=A×B-C$.

D étant non nul, il a au moins un coefficient non nul. On peut se ramener au cas
$d_{11}\neq 0$.

Exprimer alors $v_1$ en fonction des autres $v_k$ et des $d_{1k}$.

En déduire que  si $D$ est non nulle, la  probabilité que $D×\mathbf{v}=0_n$ est
inférieure à 1/2.

Conclure en terme de vérification et de complexité.

\end{exercice}










\begin{exercice}[Algorithme de Strassen]
  \illmpl{En 1969 (\textit{\og Gaussian elimination is not optimal\fg{} in Nümerische mathematik}), Volker \textsc{Strassen} propose un algorithme pour calculer
    le produit de deux matrices carrées de taille $n$.


Estimez  tout d'abord  la  complexité  en nombre  d'additions  et  en nombre  de
multiplications de la multiplication usuelle que vous avez vue en Sup.


Considérons à présent le produit de deux matrices de taille $2×2$:

$$
\begin{pmatrix}
  a&b\\
  c&d
\end{pmatrix}
\times
\begin{pmatrix}
  e&f\\
  g&h
\end{pmatrix}
=
\begin{pmatrix}
  w&x\\
  y&z
\end{pmatrix}
$$
}{Strassen}{0.75}{0.2}

On note:

$$
p_1=a(f-h),\    p_2=(a+b)h,\    p_3=(c+d)e,\    p_4=d(g-e),\    p_5=(a+d)(e+h),\
p_6=(b-d)(g+h), \ p_7=(c-a)(e+f)
$$

alors:

$$
\begin{cases}
  w = p_4 + p_5 + p_6 - p_2\\
  x = p_1 + p_2\\
  y = p_3 + p_4\\
  z = p_1 + p_5 - p_3 + p_7\\
\end{cases}
$$

Comparez le nombre d'opérations effectuées.

Considérez maintenant des  matrices carrées de taille $2^t$ (si ce
n'est pas le cas, que peut-on faire?).

On peut découper  nos matrices en quatre blocs de  taille $2^{t-1}$ et appliquer
récursivement notre algorithme:  il faut quand même vérifier  quelque chose pour
passer des  formules sur les  coefficients aux  formules sur les  matrices: quoi
donc?

Comptez le nombre de multiplications et d'additions nécessaires. 

C'est  une application  de  \textit{divide  et impera}:  pourquoi  alors ne  pas
diviser nos matrices en 9 blocs trois fois plus petits? 

\end{exercice}

\newpage





\begin{exercice}[Schéma de Horner-Ruffini-Holdred-Newton-Al-Tusi-Liu-Hui...]


%\subsection*{Un peu d'histoire...}



%\vspace{-6.2cm}
%\setindent{0cm}
%\begin{flushleft}
%\begin{minipage}[t]{4.2cm}
\begin{multicols}{3}
\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{Ruffini}
\caption{Paolo \textsc{Ruffini}\\(1765 - 1822)}
\end{center}
\end{figure}
\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{horner}
\caption{William \textsc{Horner}\\(1765 - 1822)}
\end{center}
\end{figure}
\begin{figure}
\begin{center}
  \includegraphics[height=4cm]{neuf_chapitres}
\caption{Neuf chapitres sur l'art mathématique}
\end{center}
\end{figure}
\end{multicols}
% \end{minipage}
%\end{flushleft}
%\setindent{\indentationcours}
%\vspace{-5cm}
%\begin{minipage}[t]{\linewidth}


%\end{minipage}

La  méthode que nous  allons voir  porte le  nom du  britannique William
George  \textsc{Horner} (1786  - 1837)  mais  en fait  elle fut  publiée
presque  10  ans  auparavant  par  un  horloger  londonien,  Theophilius
\textsc{Holdred} et simultanément par l'italien Paolo \textsc{Ruffini} (1765 - 1822)
mais fut déjà utilisée par  \textsc{Newton} 150 ans auparavant et par le
chinois \textsc{Zhu  Shije} cinq siècles  plus tôt (vers 1300)  et avant
lui  par le Persan  \textsc{Sharaf al-Din  al-Muzaffar ibn  Muhammad ibn
al-Muzaffar al-Tusi} vers (1100) et avant lui par le
Chinois \textsc{Liu  Hui} (vers 200)  révisant un des  résultats présent
dans \textit{Les Neuf
Chapitres sur l'art mathématique} publié avant la naissance de JC...



Il faut  cependant noter que  \textsc{Ruffini} l'avait employée  en fait
comme  un moyen  de calculer  rapidement le  quotient et  le  reste d'un
polynôme  par $(X-\alpha)$.  C'est  ce que  nous allons  (re)découvrir
aujourd'hui... 

\setindent{0cm}


\subsection*{Complexité}

Dans toute  la suite, un  polynôme de dégré  $n$ sera représenté  par le
vecteur de ses coefficients. Par exemple, \texttt{[1 2 3]} correspond au
polynôme $1+2x+3x^2$. 


Prenons   l'exemple   de   $P(x)=3x^5-2x^4+7x^3+2x^2+5x-3$.  Le   calcul
classique nécessite 5 additions et 15 multiplications.




On peut faire pas mal d'économies de calcul en suivant le schéma suivant :

\begin{center}
\begin{arrayl}
P(x)&=&\ds\underbrace{a_nx^n+\cdots+a_2x^2+a_1x}_{\text{on met $x$ en facteur}}+a_0\\
            &=&\left(\ds\underbrace{a_nx^{n-1}+\cdots+a_2x}_{\text{on met $x$ en facteur}}+a_1\right)x+a_0\\
            &=& \cdots\\
            &=& \left(\cdots(((a_nx+a_{n-1})x+a_{n-2})x+a_{n-3})x+\cdots\right)x+a_0\\
\end{arrayl}
\end{center}


Ici   cela   donne   $P(x)=(((((3x)-2)x+7)x+2)x+5)x-3$  c'est-à-dire   5
multiplications et 5 additions. 


 Comparez les
complexités au  pire du calcul de $P(t)$  pour $t\in\bbk$. Vous
prendrez comme \og unité de complexité\fg{} les opérations arithmétiques
de base: \texttt{+ - *}.

Déterminez une  fonction \texttt{horner(P,t)}  qui évalue  le polynôme
\texttt{P} en \texttt{t} selon le schéma de \textsc{Horner}.

\subsection*{Dérivées successives}

On note $P_n=a_0+a_1X+\cdots+a_nX^n$ un polynôme de degré $n$.

Déterminez le lien entre  l'algorithme de \textsc{Horner} et la division
euclidienne  de $P_n$  par $(X-t)$.  On utilisera  par la  suite la
notation suivante:

$$P_n=(X-t)(b_nX^{n-1}+b_{n-1}X^{n-2}+\cdots+b_1)+b_0$$


Comment calculer  les dérivées successives $\widetilde{P_n^{(j)}}(t)$
en  utilisant  uniquement  des  schémas  de  \textsc{Horner}?  Quel  est
l'intérêt informatique? Voici un peu d'aide...


Considérons le  développement de $P_n$ selon  les puissances croissantes
de $(X-t)$:

$$P_n=t_n(X-t)^n+t_{n-1}(X-t)^{n-1}+\cdots+t_0$$

Montrez que $\widetilde{P_n^{(j)}}(t)=(j!)×t_j$.  Quel est le lien
entre les $t_j$ et nos schémas de \textsc{Horner}?

\subsubsection*{Version récursive}

Déterminez une fonction récursive \texttt{der\_j(poly,j,t)} qui calcule
$\widetilde{P_n^{(j)}}(t)$ en utilisant le schéma de \textsc{Horner}.

Pour  cela, on  pourra  commencer par  modifier  légèrement la  fonction
\texttt{horner} pour récupérer le vecteur $\mathtt{[b_0 b_1 ... b_n]}$.

Créez ensuite \texttt{quotient\_horner(poly,t)} qui renvoie
le    quotient    de    \texttt{poly}    par    \texttt{(X-t)}    puis
\texttt{reste\_horner(poly,t)}. 

Déduisez-en une  fonction récursive  \texttt{jeme\_poly(poly,j,t)} qui
renvoie $\widetilde{P_n^{(j)}}(t)$. 


\subsubsection*{Version itérative}

Prenons par exemple le  polynôme $P_4=[6,-7,1,-5,2]$. Essayez de trouver
un algorithme simple pour remplir le tableau suivant:


\begin{center}
             \begin{tabularx}{\linewidth}{IZ|ZZZZZ|ZZI}
	     \whline
Restes & 0 & 1 & 2 & 3 & 4 & $j$ & \\
\whline
 / & 6 & $-7$ & 1 & $-5$ & 2 & $a_j$ & $P_4$ \\
$-12$ & $-9$ & $-1$ & $-1$ & 2 & / & $b_j$ & $Q_3$ \\
      & & & & & &$c_j$ & $Q_2$ \\
      & & & & & &$d_j$ & $Q_1$ \\
      & & & & & &$e_j$ & $Q_0$ \\
      & & & & &  & & \\
             \whline
             \end{tabularx}
             \end{center}

En     déduire     l'écriture     de     $P_4$     sous     la     forme
$R_4+R_3(X-2)+R_2(X-2)^2+R_1(X-2)^3+R_0(X-2)^4$  et faire  le  lien avec
les dérivées successives.


Écrivez  ensuite une  fonction  qui renvoie  un  tableau similaire  puis
transformez-la un peu pour obtenir les divisions successives en $t$.


\begin{lstlisting}[caption={}]
jeme_poly_mat([6 -7 1 -5 2],5,2)

    0.     6.  - 7.    1.  - 5.    2.  
  - 12.  - 9.  - 1.  - 1.    2.    0.  
    1.     5.    3.    2.    0.    0.  
    19.    7.    2.    0.    0.    0.  
    11.    2.    0.    0.    0.    0.  
    2.     0.    0.    0.    0.    0.  
\end{lstlisting}

  
\end{exercice}







%

\begin{exercice}[Complexité de l'algorithme d'Euclide et nombre d'or...]
On suppose dans toute la suite que $a$ et $b$ sont deux entiers naturels
tels que $a \geqslant b$.
  \begin{enumerate}
  \item Rappeler le principe de l'algorithme et de sa preuve.
  \item  Soit $r_n=a\wedge  b$ avec  les notations  habituelles: $r_0=b$
        puis      $r_1=a     \modu      b$,     $r_2=      r_1     \modu
        r_0$ et plus généralement:
$$r_{k+1}=r_kq_k+r_{k-1},\quad 0 \leqslant r_{k-1}<r_k$$ 

    Montrez que
        pour  tout entier  $k\in \bigl\{1,2,...,n\bigr\}$,  on  a $q_k
        \geqslant 1$ puis que $q_n \geqslant 2$.
  \item Notons $Φ=\frac{1+\sqrt{5}}{2}$.
    Comparez $\Phi$ et $1+\frac{1}{\Phi}$.
      \item Montrez  par récurrence que $r_k  \geqslant \Phi^{n-k}$ pour
            tout entier $k\in \bigl\{0,1,...,n\bigr\}$.
\item  Déduisez-en  que $b  \geqslant  \Phi^{n}$  puis  que le  nombre
      d'appels récursifs de 
      l'algorithme d'Euclide est au maximum de $\frac{\ln b}{\ln
      \Phi}$.

  \end{enumerate}
\end{exercice}



\newpage

\subsection{Tris}



\begin{exercice}[Stupid Sort]

Que pensez-vous de  la complexité de
cet  algorithme  de tri? %  présenté  et
% expliqué ci-dessous? 

(source: \href{http://unclecode.blogspot.tw/2012/02/stupid-sort\_2390.html}{http://unclecode.blogspot.tw/2012/02/stupid-sort\_2390.html}):



\begin{minted}[linenos,breaklines,breakindent=1cm,frame=lines,framesep=2mm,fontsize=\small,fontfamily=txtt]{cpp}
void StupidSort()
{
    int i = 0;
    while(i < (size - 1))
    {
           if(data[i] > data[i+1])
          {
                int tmp   = data[i];
                data[i]   = data[i+1];
                data[i+1] = tmp;
                i = 0;
          }
          else
         {
               i++;
         }
     }
}
\end{minted}

\pythonc
\end{exercice}




\begin{exercice}[Mélange de cartes: le mélange de ASF Software]

Savoir bien trier c'est aussi savoir bien mélanger.
  
Afin de convaincre  les utilsateurs que leur algorithme de  mélange était juste,
la société ASF Software, qui produit les logiciels utilisés par de nombreux sites
de jeu, avait publié cet algorithme:

\begin{minted}[breaklines,breakindent=1cm,frame=lines,framesep=2mm,fontsize=\small,linenos,fontfamily=txtt]{delphi}
procedure TDeck.Shuffle;
var
    ctr: Byte;
    tmp: Byte;

    random_number: Byte;
begin
    { Fill the deck with unique cards }
    for ctr := 1 to 52 do
        Card[ctr] := ctr;

    { Generate a new seed based on the system clock }
    randomize;

    { Randomly rearrange each card }
    for ctr := 1 to 52 do begin
        random_number := random(51)+1;
        tmp := card[random_number];
        card[random_number] := card[ctr];
        card[ctr] := tmp;
    end;

    CurrentCard := 1;
    JustShuffled := True;
end;
\end{minted}


\begin{enumerate}
\item  Considérez un  jeu de  3  cartes. Dressez  l'arbre de  tous les  mélanges
  possibles en suivant cet algorithme. Que remarquez-vous?
\item  Proposez  un   algorithme  qui  corrige  ce   problème.  Dressez  l'arbre
  correspondant pour un jeu de trois cartes.
\item Traduisez la fonction proposée en Python puis votre version corrigée en Python.
\end{enumerate}
\end{exercice}




\begin{exercice}[Yet another sort of sort]

  \begin{algo}
\FOR{i}{1}{n}
\FORSTEP{j}{n}{i+1}{-1}
\IF{t[j]<t[j-1]}
\STATE{Échange t[j] et t[j-1]}
\ENDIF
\ENDFOR
\ENDFOR
  \end{algo}
  

Qu'est-ce que  c'est? Qu'est-ce que ça  fait? Comment ça marche?  Complexité? En
python? Donnez un nom à ce tri.

\end{exercice}


\begin{exercice}[Comparaisons de tris et révisions sur le tracé de graphiques]
  Tracez sur un même graphique les temps d'exécution des tris étudiés en fonction de la
  longueur d'une liste \og mélangée\fg{}.

  Sur un  autre graphique, comparez ces  tris avec des listes  ordonnées dans le
  sens croissant, puis avec des listes ordonnées dans le sens décroissant.

Pour cela, voici quelques rappels sur Matplotlib.

On lance  ipython avec l'option \Colorbox{blue!10}{\lstinline{-pylab}}  ou bien,
si  vous ne  travaillez  pas  dans un  confortable  terminal  Unix, vous  pouvez
toujours importer la chose:

\begin{pythoncode}
In [29]: import matplotlib.pyplot as plt

In [30]: p1 = plt.plot([1,2,3,4,5],[1,2,5,8,3], marker = 'o',label = "Idiot")

In [31]: p2 = plt.plot([1,2,3,4,5],[3,8,2,6,-1], marker = 'v',label = "Stupide")

In [32]: plt.legend()
Out[32]: <matplotlib.legend.Legend at 0x7fbc2c6b76d8>

In [33]: plt.title("Essai idiot")
Out[33]: <matplotlib.text.Text at 0x7fbc2babc668>

In [34]: plt.xlabel("Le temps")
Out[34]: <matplotlib.text.Text at 0x7fbc2c620898>

In [35]: plt.ylabel("C'est de l'amour")
Out[35]: <matplotlib.text.Text at 0x7fbc2baaa2b0>

In [36]: plt.show()

In [37]: plt.savefig("zig.pdf")

In [38]: plt.clf()
\end{pythoncode}


%\begin{figure}
\begin{center}
  \includegraphics[height=7cm]{zig}
\end{center}
%\end{figure}


Comment      mesurer     le      temps?     On      utilise     la      fonction
\Colorbox{blue!10}{\lstinline{perf_counter}}         de          la         bibliothèque
\Colorbox{blue!10}{\lstinline{time}}:



\begin{pythoncode}
from time import perf_counter

def temps(tri,p):
    debut = perf_counter()
    tri(p)
    return perf_counter() - debut
\end{pythoncode}

On devrait obtenir:


%\begin{figure}
\begin{center}
  \includegraphics[height=7cm]{benchmark}
\end{center}
%\end{figure}

et en regardant les trois plus rapides:


%\begin{figure}
\begin{center}
  \includegraphics[height=7cm]{benchmark2}
\end{center}
%\end{figure}

mais si les listes sont déjà rangées:




%\begin{figure}
\begin{center}
  \includegraphics[height=7cm]{benchmark3}
\end{center}
%\end{figure}

Comme le nombre d'appels récursifs va augmenter, on va augmenter aussi le nombre
d'appels récursifs autorisé:

\begin{pythoncode}
from sys import setrecursionlimit
setrecursionlimit(100000)
\end{pythoncode}

\end{exercice}









  \begin{exercice}[Politique américaine]



%\begin{figure}
\begin{center}
  \includegraphics[height=8cm]{smith}
\end{center}
%\end{figure}



    Le  Sénat américain  est composé  de  deux sénateurs  par  état (il  y a  50
    états...). Vous allez  récupérer les statistiques sur  46 votes du
    109\eme  congrès (2006).  Un 1  signifie  un \og  Yea\fg{}, un  $-1$ un  \og
    Nay\fg{}   et  un   0  une   abstention.  Il   manque  les   votes  de   Jon
    \textsc{Corzine}, ssénateur du New-Jersey qui a été victime d'un accident de
    voiture cette année-là (cela fait une exception à gérer :-) ).

    On                  utilisera                 les                  fonctions
    \mintinline[fontsize=\small,fontfamily=txtt]{python}{open, read, split} pour
    récupérer les données.

    \begin{enumerate}
    \item Créez un dictionnaire \texttt{vs} de type \mintinline{python}{{Nom : liste des votes}} et
      un autre, \texttt{os}, de type \mintinline{python}{Nom : [Parti, État]}.

      Par exemple:

\begin{pythoncode}
In [18]: os['Obama']
Out[18]: ['D', 'IL']

In [20]: vs['Obama']
Out[20]: [1, -1, 1, 1, 1, -1, -1,...]
\end{pythoncode}

On              pourra             utiliser              la             fonction
\mintinline[fontsize=\small,fontfamily=txtt]{python}{int} et des définitions par compréhension.


\item Comment utiliser le produit scalaire pour mesurer l'accord ou le désaccord
  entre deux sénateurs?

\item                   Écrivez                   une                   fonction
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{compare(sen1, sen2)} 
qui  mesure le  degré  d'accord  de deux  sénateurs. Par exemple:

\begin{pythoncode}
In [21]: compare('Obama', 'McCain')
Out[21]: 16
\end{pythoncode}

\item                   Écrivez                   une                   fonction
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{senat_parti(parti)}  qui
  renvoie l'ensemble  des noms des sénateurs  d'un parti donné. Créez  aussi une
  fonction qui  renvoie le  nom des  sénateurs par  état, le  nom des  états par
  parti.

\item Écrivez une fonction \mintinline[fontsize=\small,fontfamily=txtt]{python}{compare_sen_etat(etat)} 
qui mesure la cohérence des votes des deux sénateurs d'un état donné.

\begin{pythoncode}
In [23]: compare_etat('WA')
Out[23]: (39, 'WA', ('Cantwell', 'Murray'))  
\end{pythoncode}

Classez les états dans l'ordre croissant des cohérences.


\item                    Créez                   une                    fonction
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{plus_eloigne(sen, ens)} 
qui renvoie le nom et la mesure de l'écart du sénateur d'un ensemble donné le plus en désaccord avec
un sénateur donné.

\begin{pythoncode}
In [33]: plus_eloigne('Obama',senat_parti('D'))
Out[33]: (22, 'Nelson2')

In [34]: plus_eloigne('Obama',senat_parti('R'))
Out[34]: (7, 'Sununu')
\end{pythoncode}

Faites de même avec le plus en accord.


\item  Quel est  le parti  le plus  \og cohérent\fg{}?  Comment le  déterminer à
  l'aide d'une fonction calculant une moyenne de cohérence.

Par  souci d'efficacité,  on  pourra se  souvenir que  le  produit scalaire  est
distributif sur l'addition des vecteurs.

\item Écrivez une fonction \mintinline[fontsize=\small,fontfamily=txtt]{python}{moins_d_accord(ens)} 
qui renvoie le couple de sénateurs les moins d'accord d'un ensemble donné:

\begin{pythoncode}
In [50]: moins_d_accord(senateurs)
Out[50]: (('Feingold', 'Inhofe'), -3)  
\end{pythoncode}

Combien de  calculs et de  comparaisons sont effectués? Pensez-vous  pouvoir être
plus efficace?



\item Qui est le sénateur le plus Républicain? L'État le plus Démocrate? Classez
  les sénateurs/États selon ces critères.


\item                    Ouvrez                    le                    fichier
  \mintinline[fontsize=\small,fontfamily=txtt]{python}{ONU_vote.txt} et 
étudiez-le d'une manière similaire à ce qui vient d'être fait.


    \end{enumerate}




  \end{exercice}



  \begin{exercice}[Algorithme probabiliste: amélioration du tri rapide]
  On peut introduire une  dose de hasard dans un algorithme de  deux façons: on
  choisit le pivot au hasard ou on prend toujours le premier 
élément de la liste mais on permute aléatoirement les autres éléments de la liste.

On distingue  deux classes d'algorithmes  probabilistes (nous ne  rentrerons pas
dans  les   détails  des   classes  de  complexité,   des  machines   de  Turing
probabilistes,etc.):
\begin{description}
\item[les algorithmes de Monte-Carlo] : l'algorithme peut se tromper mais on connait la probabilité qu'il donne la bonne
réponse  : on  peut  donc diminuer  cette probabilité  en  augmentant le  nombre
d'exécution.
\item[les algorithmes de Las Vegas] : ils donnent toujours la bonne réponse mais le temps d'exécution est une variable
aléatoire.
\end{description}
On peut passer de  Monte-Carlo à Las Vegas à la  condition de pouvoir déterminer
si l'issue de Monte-Carlo est correcte: comment ?

Revenons au cas du tri rapide.

Notons $\{  x_1, x_2,...,x_n \}$ la  suite à trier et  $\{_1, y_2,...,y_n\}$ la
  suite triée. Soit $i < j$. On considère la var $X_{ij}$ qui vaut 1 si $y_i$ 
et $y_j$ ont été comparés et 0 sinon.

Soit $X$ le nombre total de comparaisons, alors:

$$X=\sum_{i=1}^{n-1}\sum_{j=i+1}^nX_{ij}$$

Que vaut $\bbe(X)$?
Que vaut $\bbe(X_{ij})$ compte-tenu de la nature de la var $X_{ij}$ ?
Maintenant, $y_i$ et $y_j$ sont comparés si,  et seulement si, l'un des deux est
choisi comme pivot de la sous-suite $y_i...y_j$.

En effet, si aucun des deux n'est pivot de cette suite, ils seront dans des sous-listes séparées et ne seront jamais
comparés. 
Si, l'un des deux est choisi comme pivot de la sous-suite $y_i,...,y_j$ , ils seront forcément comparés.
Écrivez plus formellement cette preuve à l'aide de la logique des propositions.
Quelle est donc la probabilité que $X_{ij}=1$ ?
En déduire $\bbe(X)$ en fonction de $H_n=\sum_{k=1}^n1/k$ .
Concluez. 

Observez et testez en vous inspirant de ce qui a été fait à l'exercice précédent.

  \end{exercice}


  \begin{exercice}[Pi au casino]
    Imaginez  un  moyen de  calculer  une  valeur  approchée  de $\pi$  avec  un
    algorithme probabiliste.
  \end{exercice}





  \begin{exercice}[MURD3RS]
    Les américains ont un goût prononcé pour les tueurs en série. Le profil psychologique de certains
de ces héros maléfiques correspond à une personne logique, froide, méthodique, dangereuse,
qui connait bien son métier, qui travaille suffisamment lentement pour bien faire son boulot et
suffisamment rapidement pour être efficace. Certains sont des sociopathes, d'autres sont très à
l'aise en société : on retrouve exactement les qualités recherchées chez un programmeur...Bref,
si on apprenait plus de Caml à l'école, les tueurs en série disparaîtraient.
Un policier canadien, Kim \textsc{Rossmo}, s'est lui aussi passionné pour les mathématiques et la pro-
grammation et devint en 1995 le premier policier canadien à obtenir un doctorat en crimonologie
(\href{https://en.wikipedia.org/wiki/Kim\_Rossmo}{https://en.wikipedia.org/wiki/Kim\_Rossmo}).
Il a publié un article 
(\href{http://www.popcenter.org/library/crimeprevention/volume\_04/10-Rossmo.pdf}{http://www.popcenter.org/library/crimeprevention/volume\_04/10-Rossmo.pdf})
sur l'analyse géographique des crimes et proposa une formule pour localiser le lieu d'habitation
d'un tueur en série, ou plutôt pour calculer le lieu le plus probable :



$$
p_{i,j} = k \sum_{n=1}^{(\mathrm{nb\; total\;de\;crimes})} \left [ \underbrace{ \frac{\phi_{ij}}{ (|X_i-x_n| + |Y_j-y_n|)^f } }_{ 1^{\mathrm{er}}\mathrm{\;terme} } + \underbrace{ \frac{(1-\phi_{ij})(B^{g-f})}{ (2B - \mid X_i - x_n \mid - \mid Y_j-y_n \mid)^g } }_{ 2^{\mathrm{nd}}\mathrm{\;terme} } \right ], 
$$


avec


$$
 \phi_{ij} = \begin{cases} 1, & \mathrm{\quad si\;} ( \mid X_i - x_n \mid + \mid Y_j - y_n \mid ) > B \quad \\ 0, & \mathrm{\quad sinon} \end{cases} 
$$
Bon, plus synthétiquement, ça peut s'écrire :

$$P(x)=\sum_{\mathrm{lieu       du      crime       c}}\frac{φ}{d(x,c)^f}      +
\frac{(1-φ)B^{g-f}}{(2B-d(x,c))^g }$$



....euh...qui est qui là-dedans ?
On discrétise un plan, de ville de préférence, à l'aide d'une grille. On calcule alors la probabilité
que le tueur habite dans la case $x$.

Comme on travaille dans une ville, la distance $d$ sera la distance du taxi de Manhattan :


%\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{manhattan}
\end{center}
%\end{figure}


ou si vous préférez:


%\begin{figure}
\begin{center}
  \includegraphics[height=5cm]{pacman}
\end{center}
%\end{figure}


B est le rayon de la \og Buffer zone \fg{}  ou zone
tampon : c'est un \og cercle \fg{} (au sens des taxis) autour du lieu du crime. La fonction $φ$ est la
fonction caractéristique de cette zone tampon: elle vaut 1 si la cellule est dans la zone et 0 sinon.
$f$ et $g$ sont des paramètres arbitraires qui permettent de s'adapter aux données des crimes
précédents.
On cherche  à présent à  dresser une carte des  probabilités. On va  utiliser la
fonction 
\mintinline{python}{pcolormesh}
de \mintinline{python}{matplotlib.pyplot} .
Vous pouvez regarder l'aide. Ce qui va motiver notre construction, c'est la nature des arguments
de cette fonction :


\begin{pythoncode}
def dessine_rossmo( lieux, vrai, B, f, g, taille_x, taille_y) :
   t_x = np.arange(taille_x)
   t_y = np.arange(taille_y)
   X, Y = np.meshgrid(t_x, t_y)
   Z = np.vectorize( proba_rossmo(lieux, B, f, g) )(X, Y)
   g = cg(lieux)
   plt.pcolormesh( X, Y, Z, cmap = cm.jet)# , shading=’gouraud’)
   plt.plot(vrai[0], vrai[1], ’ks’, mew = 7)
   plt.plot(g[0],g[1], ’ko’, mew = 7)
   plt.colorbar()
   plt.show()
\end{pythoncode}

Ici, \texttt{lieux}  est l'ensemble des  lieux des crimes, \texttt{vrai}  est le
véritable domicile du tueur, 
\texttt{taille\_x} et \texttt{taille\_y} sont les dimensions de la grille.

La fonction \texttt{cg} calcule les coordonnées du centre de gravité des lieux des crimes pour comparer
avec le candidat de la méthode Rossmo.

\texttt{colorbar} permet d'avoir une échelle de couleur pour lire la carte.
Il va falloir bien comprendre la construction de Z...À vous de menez l'enquête informatique.



\textsc{Rossmo} fournit des données pour deux tueurs en série célèbres:
\begin{itemize}

 \item le vampire de Sacramento 
(\href{https://en.wikipedia.org/wiki/Richard\_Chase}{https://en.wikipedia.org/wiki/Richard\_Chase})

\begin{pythoncode}
vampire = {(3, 17), (15, 3), (19, 27), (21, 22), (25, 18)}
vrai_vampire = ([19],[17])  
\end{pythoncode}

\item  L'étrangleur de Boston 
(\href{https://en.wikipedia.org/wiki/Albert\_DeSalvo}{https://en.wikipedia.org/wiki/Albert\_DeSalvo})

\begin{pythoncode}
boston = [[10, 48], [13, 8], [15, 11], [17, 8], [18, 7],
          [18, 9], [19, 4], [19, 8], [20, 9], [20, 10], [20, 11],
          [29, 23], [33, 28]]  
vrai_boston = ([19],[18])
\end{pythoncode}

\end{itemize}

Vous obtiendrez des cartes qui ressemblent à ça :


%\begin{figure}
\begin{center}
  \includegraphics[height=6cm]{gradientCrime}
\end{center}
%\end{figure}
\end{exercice}





%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "PolyIPT2015_16"
%%% End: 
