X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-mesi.git/blobdiff_plain/52672f301b364d8a75708a2d5e35256af37965ff..refs/heads/master:/complexite.tex?ds=sidebyside

diff --git a/complexite.tex b/complexite.tex
index 3dd4b38..6d66125 100644
--- 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)$.
+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}{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 $
@@ -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)$}
- \nllabel{laff1} $a' = a$ \; 
+ $a' = a_n$ \; \nllabel{laff1} 
  \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{laff2} $\textit{val} = a'$ \;
+$\textit{val} = a'$ \; \nllabel{laff2}
  \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}
- \nllabel{laford2}\For{$i=0$ \KwTo $n$}{
+ \For{$i=0$ \KwTo $n$} { \nllabel{laford2} 
    \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{lafori2b} }
+    }\nllabel{lafori2b}
  \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$.
-\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}
@@ -274,7 +297,7 @@ peut-il Ãªtre lent pour des donnÃ©es de petite taille?
 \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 
@@ -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. 
-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}$ 
