[cours-mesi.git] / complexite.tex

\section{Quelques définitions}

Soit $\mathcal{F}$ l'ensemble des fonctions de
$\N$ dans $\R^*_+$. 
\begin{Def}[fonctions asymptotiquement dominées]
Soit $f \in \mathcal{F}$. L'ensemble $\mathcal{O}(f)$ 
des fonctions \emph{asymptotiquement dominées par} $f$ est défini par
$$
\mathcal{O}(f) = 
\large\{ g \in \mathcal{F} \textrm{ t. q. }
\exists n_0 \in \N, 
\exists c \in \R_+,
\forall n \geq n_0,
g(n) \leq c f(n)
\large\}.
$$
Ainsi, à partir d'un rang $n_0$, $g(n)$ est majorée par $c f(n)$.
On dit que \og $g$ est dans grand  $\mathcal{O}$ de $f$ \fg{}.
\end{Def}

On considère par exemple 
$f: n \mapsto \dfrac{n^3}{2}$, 
$g_1: n \mapsto n^2 + 17n + 15$ et 
$g_2: n \mapsto 5n^3$. On a:
\begin{itemize}
\item $g_1 \in \mathcal{O}(f)$: en effet, on prend $n_0 =1$ et 
$c = 2(1+17+15)$; alors
$n^2+17n+15 \leq c.\dfrac{n^3}{2}$ si $n \geq 1$.
\item $g_2 \in \mathcal{O}(f)$: en effet, on prend $n_0 =1$ et 
$c = 10$; alors
$5n^3\leq 10.\dfrac{n^3}{2}$.
\item $f \in \mathcal{O}(g_2)$: immédiat.
\item $f \not \in \mathcal{O}(g_1)$: sinon on serait capable de trouver une 
constante $c$ telle que 
$\dfrac{n^3}{2} \leq c.(n^2 +17n + 5)$ soit encore 
$\dfrac{n^3}{2(n^2 +17n + 5)} \leq c$ et donc  
$\dfrac{n^3}{2} \leq c$ ce qui est impossible. 
\end{itemize}




\begin{Prop}
Soit $f$ et $g$ deux fonctions de $\mathcal{F}$. Si 
$\lim_{n \rightarrow + \infty} \frac{f(n)}{g(n)} = l $
alors on a 
$\mathcal{O}(f) =  
\mathcal{O}(g)$
\end{Prop}


On confond dans ce qui suit la fonction $n \mapsto f(n)$ avec $f(n)$.

\begin{Exo}
Que dire de:
\begin{enumerate}
\item  $2^{n+1}$  et $\mathcal{O}(2^{n})$?
\item  $({n+1})!$  et $\mathcal{O}(n!)$?
\end{enumerate}
\end{Exo}

\begin{Prop}
Soit deux réels $\epsilon$ et $c$ vérifiant $0 < \epsilon <  1 < c$. Alors on a 

$
\mathcal{O}(1) \subset 
\mathcal{O}(\ln(n)) \subset 
\mathcal{O}(n^{\epsilon}) \subset 
\mathcal{O}(n) \subset 
\mathcal{O}(n \ln(n)) \subset 
\mathcal{O}(n^c) \subset 
\mathcal{O}(c^n) \subset 
\mathcal{O}(n!)
$
\end{Prop}

\begin{Def}[fonctions dominant asymptotiquement]
Soit $f \in \mathcal{F}$. L'ensemble $\Omega(f)$ 
des fonctions \emph{dominant asymptotiquement} $f$ est défini par
$$
\Omega(f) = 
\large\{ g \in \mathcal{F} \textrm{ t. q. }
\exists n_0 \in \N, 
\exists c \in \R_+,
\forall n \geq n_0,
g(n) \geq c f(n)
\large\}.
$$
Ainsi, à partir d'un rang $n_0$, $g(n)$ majore $c f(n)$.
\end{Def}


\begin{Prop}
Soit $f$ et $g$ deux fonctions de $\mathcal{F}$. Si 
$\lim_{n \rightarrow + \infty} \frac{f(n)}{g(n)} = l $
alors on a 
$\Omega(f) =  
\Omega(g)$
\end{Prop}

\begin{Prop}
Soit deux réels $\epsilon$ et $c$ vérifiant $0 < \epsilon <  1 < c$. Alors on a 

$
\Omega(1) \supset 
\Omega(\ln(n)) \supset 
\Omega(n^{\epsilon}) \supset 
\Omega(n) \supset 
\Omega(n \ln(n)) \supset 
\Omega(n^c) \supset 
\Omega(c^n) \supset 
\Omega(n!)
$
\end{Prop}

\begin{Def}[fonctions asymptotiquement équivalentes]
Soit $f \in \mathcal{F}$. L'ensemble $\Theta(f)$ 
des fonctions \emph{asymptotiquement équivalentes} à  $f$ est défini par
$$
\Theta(f) = 
\large\{ g \in \mathcal{F} \textrm{ t. q. }
\exists n_0 \in \N, 
\exists c, c' \in \R_+,
\forall n \geq n_0,
c f(n) \leq g(n) \leq c' f(n)
\large\}.
$$
\end{Def}


\begin{Prop}
Soit $f$ et $g$ deux fonctions de $\mathcal{F}$. Si 
$\lim_{n \rightarrow + \infty} \frac{f(n)}{g(n)} = l $
alors on a 
$f \in \Theta(g)$ et   
$g \in \Theta(f)$.
\end{Prop}

\begin{Prop}
Soit $f$, $f_1$,  et $g$ des fonctions de $\mathcal{F}$. Si 
$f \in \Theta(g)$ et si $\lim_{n \rightarrow + \infty} \frac{f_1(n)}{g(n)} = 0 $
alors on a 
$f  + f_1 \in \Theta(g)$.
\end{Prop}


\section{Mesurer la complexité}
Soit $\mathcal{A}(n)$ un algorithme résolvant un problème sur des données 
de taille $n$, $n \in \N$. On suppose que l'exécution de $\mathcal{A}$ 
coûte $T(n)$ étapes informatiques élémentaires ou unités de temps. 

\begin{Def}[Pire des cas]
L'algorithme $\mathcal{A}(n)$ a une \emph{complexité du pire des cas}
dans $\mathcal{O}(f(n))$ si $T(n) \in \mathcal{O}(f(n))$.   
On dit que $\mathcal{A}$ est en $\mathcal{O}(f(n))$.
\end{Def}

Attention, la majoration proposée doit être la plus fine possible.
De plus, celle-ci doit être valide au delà d'une valeur $n$ supérieure 
à un seuil $n_0$. 
 

\begin{Def}[Meilleur des cas]
L'algorithme $\mathcal{A}(n)$ a une \emph{complexité du meilleur des cas}
dans $\Omega(f(n))$ si $T(n) \in \Omega(f(n))$.   
On dit que $\mathcal{A}$ est en $\Omega(f(n))$.
\end{Def}

\begin{Def}[ordre de grandeur d'un temps d'exécution]
L'algorithme $\mathcal{A}(n)$ a une \emph{complexité} en
$\Theta(f(n))$ si $T(n) \in \Theta(f(n))$.   
On dit que $\mathcal{A}$ est en $\Theta(f(n))$.
\end{Def}

On note que si $T(n) \in \Theta(f(n))$, alors 
$T(n) \in \mathcal{O}(f(n))$ et $T(n) \in \Omega(f(n))$.
Lorsque 
$T(n) \in \Theta(n)$, on dit que l'algorithme est \emph{linéaire en $n$} 
et lorsque 
$T(n) \in \Theta(n^2)$, on dit que l'algorithme est \emph{quadratique en $n$}.

\section{Exemples d'étude de complexité}

\subsection{Un premier algo}
Soit $p$ une fonction polynôme de degré $n$ définie par 
$
p(x) = \sum_{i=0}^n a_i x^i
$.
On considère tout d'abord l'algorithme suivant: 





\begin{algorithm}[H]
 \LinesNumbered 
 \SetAlgoLined
 \KwData{$n$: degré, $(a_i)_{0 \le i \le n}$: coefficients, $t$: 
   réel en lequel on évalue}
 \KwResult{$\textit{val}$: réel tel que $\textit{val}= p(t)$}
 $a' = a$ \; \nllabel{laff1} 
 \For{$i=n-1$ \KwTo $0$}{\nllabel{laford} 
    $a' = a_i + t \times a'$ \; \nllabel{lafori}
 \nllabel{laforf}}
$\textit{val} = a'$ \; \nllabel{laff2}
 \caption{Évaluation du polynôme $p$ en $t$}
\end{algorithm}

On calcule les coûts d'exécution des lignes de l'algorithme comme suit:
\begin{itemize} 
% \item $\alpha$ désigne le temps d'accès mémoire en lecture écriture;
% \item $\beta$ désigne le temps d'exécution d'une opération arithmétique ($+$,$-$,$\times$, $/$);
% \item $\gamma$ désigne le temps d'exécution d'un test.
\item les lignes \ref{laff1} et \ref{laff2} cumulées coûtent une constante 
de temps $A$ indépendante de $n$;
\item la ligne \ref{lafori} nécessite un temps d'exécution 
  $B$ indépendant de $n$; 
\item la boucle for (ligne \ref{laford}) nécessite donc un temps $nB$.
\end{itemize}

Donc $T(n)= A + nB$ et donc $\lim_{n \rightarrow + \infty} \frac{T(n)}{n} = B$.
Ainsi cet algorithme a une complexité linéaire en $n$.


\subsection{Un second algo}

On considère l'algorithme suivant:

\begin{algorithm}[H]
  \LinesNumbered 
  \SetAlgoLined
  \KwData{$n$: entier naturel, $(x_i)_{0 \le i \le n}$: abscisses réelles,
    $(y_i)_{0 \le i \le n}$: ordonnées réelles.}
 \KwResult{$d$: vecteur de $n+1$ réels}
 \For{$i=0$ \KwTo $n$} { \nllabel{laford2} 
   \nllabel{lafori2} $d_i' = y_i$ \; 
   }\nllabel{laforf2}
 \For{$i=1$ \KwTo $n$}{\nllabel{laford2b}
   \nllabel{laford2bb}\For{$j=n$ \KwTo $i$}{
     \nllabel{lafori2bb} $d_j = (d_j - d_{j-1})/(x_j - x_{j-1})$ \;
     \nllabel{laforf2b}}
    }\nllabel{lafori2b}
 \caption{Polynôme  d'approximation d'une fonction}
\end{algorithm}


On calcule les coûts d'exécution des lignes de l'algo comme suit:
\begin{itemize} 
\item la boucle for (lignes \ref{laford2}-\ref{laforf2})
  nécessite un temps $(n+1)A$.
\item la seconde boucle for (lignes \ref{laford2b}-\ref{lafori2b})
  nécessite un temps
$\sum_{i=1}^n B(n-i+1)$ soit encore 
$B\sum_{i=1}^n (n-i+1)=B\sum_{i=1}^n i= B\frac{n.(n+1)}{2}$
\end{itemize}
Ainsi $T(n) = (n+1)A + B\frac{n.(n+1)}{2}$ et donc l'algorithme proposé est 
quadratique en $n$.


\begin{Exo}
Dans un cadre industriel, on est amené à effectuer un contrôle $(P)$ sur 
les données. La durée de cette phase est limitée. 
Il existe deux méthodes $A_1(n)$ et $A_2(n)$ de traitement de $(P)$.
On a établi que le temps d'exécution $T_1(n)$ de $A_1(n)$ est en 
$\Theta(n^3)$ et que le temps d'exécution $T_2(n)$ de $A_2(n)$ est en 
$\Theta(n^2)$.
\begin{enumerate}
\item Lors d'une évaluation pratique des deux méthodes, on a 
  obtenu les mesures suivantes 
$$\begin{array}{|l|l|l|}
\hline
n & T_1(n) & T_2(n) \\
\hline
200 & 10400 & 6800 \\
\hline
\end{array}.$$

\begin{enumerate}
\item En déduire quel sera le temps nécessaire au traitement de données 
  de taille $n'=10^4$.
\item Même question avec $n'=200\lambda$ où $\lambda$ réel de $[1, +\infty[$.
\item Déterminer la taille maximale des données que peuvent traiter 
  $A_1$ et $A_2$ si le temps disponible est $t=10^5$.
\end{enumerate}
\item En fait, une étude statistique approfondie des deux algorithmes a permis 
d'établir que pour $n$ grand, on obtient: $T_1(n) \approx 0,001n^3$ et $T_2(n) \approx 0,19n^2$.
\begin{enumerate}
\item Quel est à priori l'algorithme le plus performant au vu de 
  l'étude effectuée ?
\item Montrer qu'il existe un seuil $n_0$ en dessous duquel l'algorithme réputé 
le meilleur est en fait le moins performant. Déterminer cette valeur.
\item Pourquoi un algorithme performant sur des données de grandes tailles 
peut-il être lent pour des données de petite taille?
\end{enumerate}
\end{enumerate}
\end{Exo}

\section{Quelques classes de complexité de problèmes}

\subsection{La classe \emph{P}}
Les problèmes de cette classe sont ceux qui admettent une solution 
algorithmique  \emph{déterministe} et en temps \emph{polynomial}:
lorsque la taille du problème est $n$, le 
nombre d'étapes de l'algorithme qui le résout reste plus petit 
qu'une certaine puissance de $n$ et ne contient pas d'indéterminisme.
La complexité de l'algorithme est alors en $\Theta(n^k)$ pour un certain $k$.



\subsection{La classe  \emph{NP}}
Les problèmes de cette classe sont ceux qui admettent 
une solution algorithmique \emph{non déterministe} en temps \emph{polynomial}.
De façon équivalente, c'est la classe des problèmes pour lesquels 
si une solution est proposée, on peut vérifier sa validité à l'aide d'un 
un algorithme en temps polynomial. 
On a $\emph{P} \subseteq \emph{NP}$.

\subsection{La classe \emph{NP-complet}} 
Les problèmes de cette classe sont ceux de la classe $\emph{NP}$ 
tels que tous les problèmes de la classe NP peuvent se réduire à celui-ci. 
Cela signifie que le problème est au moins aussi difficile
que tous les autres problèmes de la classe NP.

Le problème du voyageur de commerce (qui consiste à
trouver le chemin le plus court reliant une série de villes),
le problème du sac à dos (étant donné un sous-ensemble $S$
de l’ensemble des entiers naturels et $m$
un nombre positif, peut-on trouver
une partie $A$ de $S$ 
telle que la somme de ses éléments soit égale à l’entier $m$)
sont des exemples de problèmes NP-complets.