j

[cours-mesi.git] / complexite.tex

diff --git a/complexite.tex b/complexite.tex
index dff29856c46ed6d5ea545d680f9112abd84d4622..6d66125ba533d9007322991cb77ee6cc0b066fab 100644 (file)
--- a/complexite.tex
+++ b/complexite.tex
@@ -1,6 +1,6 @@
-\section{Complexité}

 
 

-\subsection{Quelques définitions}
+
+\section{Quelques définitions}

 
 Soit $\mathcal{F}$ l'ensemble des fonctions de
 $\N$ dans $\R^*_+$. 
 
 Soit $\mathcal{F}$ l'ensemble des fonctions de
 $\N$ dans $\R^*_+$. 


@@ -17,8 +17,31 @@ g(n) \leq c f(n)
 \large\}.
 $$
 Ainsi, à partir d'un rang $n_0$, $g(n)$ est majorée par $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}
 
 \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}{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 $
 \begin{Prop}
 Soit $f$ et $g$ deux fonctions de $\mathcal{F}$. Si 
 $\lim_{n \rightarrow + \infty} \frac{f(n)}{g(n)} = l $


@@ -123,7 +146,7 @@ $f  + f_1 \in \Theta(g)$.
 \end{Prop}
 
 
 \end{Prop}
 
 

-\subsection{Mesurer la complexité}
+\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. 
 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. 


@@ -158,9 +181,9 @@ $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$}.
 
 et lorsque 
 $T(n) \in \Theta(n^2)$, on dit que l'algorithme est \emph{quadratique en $n$}.
 

-\subsection{Exemples d'étude de complexité}
+\section{Exemples d'étude de complexité}

 
 

-\subsubsection{Un premier algo}
+\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
 Soit $p$ une fonction polynôme de degré $n$ définie par 
 $
 p(x) = \sum_{i=0}^n a_i x^i


@@ -177,11 +200,11 @@ On considère tout d'abord l'algorithme suivant:
  \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)$}
  \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)$}

- \nllabel{laff1} $a' = a$ \; 
+ $a' = a_n$ \; \nllabel{laff1} 

  \For{$i=n-1$ \KwTo $0$}{\nllabel{laford} 
  \For{$i=n-1$ \KwTo $0$}{\nllabel{laford} 

-   \nllabel{lafori} $a' = a_i + t \times a'$ \;
+    $a' = a_i + t \times a'$ \; \nllabel{lafori}

  \nllabel{laforf}}
  \nllabel{laforf}}

- \nllabel{laff2} $\textit{val} = a'$ \;
+$\textit{val} = a'$ \; \nllabel{laff2}

  \caption{Évaluation du polynôme $p$ en $t$}
 \end{algorithm}
 
  \caption{Évaluation du polynôme $p$ en $t$}
 \end{algorithm}
 


@@ -201,7 +224,7 @@ 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$.
 
 
 Ainsi cet algorithme a une complexité linéaire en $n$.
 
 

-\subsubsection{Un second algo}
+\subsection{Un second algo}

 
 On considère l'algorithme suivant:
 
 
 On considère l'algorithme suivant:
 


@@ -211,14 +234,14 @@ On considère l'algorithme suivant:
   \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}
   \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}

- \nllabel{laford2}\For{$i=0$ \KwTo $n$}{
+ \For{$i=0$ \KwTo $n$} { \nllabel{laford2} 

    \nllabel{lafori2} $d_i' = y_i$ \; 
    \nllabel{lafori2} $d_i' = y_i$ \; 

-   \nllabel{laforf2}}
- \nllabel{laford2b}\For{$i=1$ \KwTo $n$}{
+   }\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{laford2bb}\For{$j=n$ \KwTo $i$}{
      \nllabel{lafori2bb} $d_j = (d_j - d_{j-1})/(x_j - x_{j-1})$ \;
      \nllabel{laforf2b}}

-   \nllabel{lafori2b} }
+    }\nllabel{lafori2b}

  \caption{Polynôme  d'approximation d'une fonction}
 \end{algorithm}
 
  \caption{Polynôme  d'approximation d'une fonction}
 \end{algorithm}
 


@@ -257,7 +280,7 @@ n & T_1(n) & T_2(n) \\
 \begin{enumerate}
 \item En déduire quel sera le temps nécessaire au traitement de données 
   de taille $n'=10^4$.
 \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 Même question avec $n'=200\lambda$ où $\lambda$ réel de $[0, +\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 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}


@@ -274,9 +297,9 @@ peut-il être lent pour des données de petite taille?
 \end{enumerate}
 \end{Exo}
 
 \end{enumerate}
 \end{Exo}
 

-\subsection{Classes de complexité de problèmes}
+\section{Quelques classes de complexité de problèmes}

 
 

-\subsubsection{La classe \emph{P}}
+\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 
 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 


@@ -286,15 +309,15 @@ La complexité de l'algorithme est alors en $\Theta(n^k)$ pour un certain $k$.
 
 
 
 
 
 

-\subsubsection{La classe  \emph{NP}}
+\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. 
 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} \subset \emph{NP}$.
+On a $\emph{P} \subseteq \emph{NP}$.

 
 

-\subsubsection{La classe \emph{NP-complet}} 
+\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
 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