ajout de partiels

[cours-mesi.git] / complexite.tex

diff --git a/complexite.tex b/complexite.tex
index 3dd4b380bc30bbc1b3de4d55b992848167d6fc55..4fdf00d8a2f7e29714be2c1206576b5786d4c1eb 100644 (file)
--- a/complexite.tex
+++ b/complexite.tex
@@ -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^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 $
 \begin{Prop}
 Soit $f$ et $g$ deux fonctions de $\mathcal{F}$. Si 
 $\lim_{n \rightarrow + \infty} \frac{f(n)}{g(n)} = l $


@@ -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$ \; \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}
 


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


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

-\section{Classes de complexité de problèmes}
+\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 
 
 \subsection{La classe \emph{P}}
 Les problèmes de cette classe sont ceux qui admettent une solution 


@@ -292,7 +315,7 @@ 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. 
 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}$.

 
 \subsection{La classe \emph{NP-complet}} 
 Les problèmes de cette classe sont ceux de la classe $\emph{NP}$ 
 
 \subsection{La classe \emph{NP-complet}} 
 Les problèmes de cette classe sont ceux de la classe $\emph{NP}$