\chapterimage{estimation}
\chapter{Complexité}

\modeexercice


 \begin{exercice}[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 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  note   $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{python}{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}. 
Est-elle plus efficace?
\item Écrivez une version en Haskell de cette fonction: est-elle plus efficace?
  \end{enumerate}
  \end{exercice}





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

  \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}
Donnez l'ordre de complexité temporelle des fragments de code Java suivants:

\begin{javacode}
int sum = 0;
for (int n = N; n > 0; n /= 2)
   for (int i = 0; i < n; i++) 
      sum++;  
\end{javacode}

\pause

\begin{javacode}
int sum = 0;
for (int i = 1; i < N; i *= 2)
   for(int j = 0; j < i; j++)
      sum++;  
\end{javacode}

\pause

\begin{javacode}
int sum = 0;
for (int i = 1; i < N; i *= 2)
   for (int j = 0; j < N; j++)
      sum++;  
\end{javacode}

  \end{exercice}



  \begin{exercice}[Tri selectif]
    
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.



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}

\begin{enumerate}
\item Il s'agit de démontrer la \textbf{correction} de ces deux fonctions. 

Démontrez que 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{}.

Quel est celui de la seconde? Démontrez-le.

\item 
Nous mesurerons la complexité temporelle en
nombre de comparaisons.

Expérimentalement, nous pouvons en avoir une idée:


\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}



Démontrez-le.



\end{enumerate}

  \end{exercice}


  \begin{exercice}[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}

   
\begin{enumerate}
\item Déterminez une version impérative de la fusion.

\item Étudiez la terminaison, la correction et la complexité de cet algorithme.
\end{enumerate}


  \end{exercice}




  \begin{exercice}[Tri rapide]
 
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,
dé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$?
   
  \end{exercice}




\begin{exercice}[Tri sportif]

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}[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}[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=5cm]{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}[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=3.5cm]{Ruffini}
\caption{Paolo \textsc{Ruffini}\\(1765 - 1822)}
\end{center}
\end{figure}
\begin{figure}
\begin{center}
  \includegraphics[height=3.5cm]{horner}
\caption{William \textsc{Horner}\\(1765 - 1822)}
\end{center}
\end{figure}
\begin{figure}
\begin{center}
  \includegraphics[height=3.5cm]{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... 


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}.

\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}


\subsection{In english :-)}


\begin{exercice}[Local min]
  Write a program that, given an array a[] of N distinct integers, finds a local
  minimum: an index i such that both \texttt{a[i] < a[i-1]} and \texttt{a[i] < a[i+1]} (assuming
  the neighboring entry is in bounds). Your  program should use ~2 lg N compares
  in the worst case.  
\end{exercice}



\begin{exercice}[Bitonic search]
  An array is bitonic  if it is comprised of an  increasing sequence of integers
  followed immediately  by a  decreasing sequence of  integers. Write  a program
  that, given  a bitonic array  of N distinct  \texttt{int} values, determines  whether a
  given integer is  in the array. Your program  should use ~ 3 lg  N compares in
  the worst case. 
\end{exercice}


\begin{exercice}[Floor and ceiling]
  Given a set of  comparable elements, the ceiling of $x$  is the smallest element
  in the set  greater than or equal to  $x$, and the floor is  the largest element
  less than  or equal to $x$.  Suppose you have an  array of N items  in ascending
  order. Give an O(log N) algorithm to find the floor and ceiling of $x$.  
\end{exercice}


\begin{exercice}[Common elements]
  Given two arrays  of N 64-bit integers,  design an algorithm to  print out all
  elements that appear in both lists. The output should be in sorted order. Your
  algorithm should  run in N log  N. Hint: mergesort, mergesort,  merge. Remark:
  not possible to do better than N log N in comparison based model.  
\end{exercice}

\begin{exercice}[Mumixam]
 Given an array  a[] of N real  numbers, design a linear-time  algorithm to find
 the maximum value of a[j] - a[i] where j $\geqslant$  i.  
\end{exercice}

\begin{exercice}[DÉFI]
  Résolvez le problème suivant: \href{http://introcs.cs.princeton.edu/java/assignments/collinear.html}{http://introcs.cs.princeton.edu/java/assignments/collinear.html}
\end{exercice}


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "Poly_Comp-Maths_16"
%%% End: 
