\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 $
\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}
- \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}
\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}
\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
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}$
\begin{figure}
+\centering{
+\begin{minipage}{0.5\textwidth}
+\vspace{7em}
\psset{xunit=3cm,yunit=0.8cm}
\savedata{\mydata}[{{0.0, -1.25}, {0.1, -1.24}, {0.2, -1.21}, {0.3, -1.16}, {0.4, -1.0899999999999999}, {0.5, -1.0}, {0.6, -0.89}, {0.7, -0.76}, {0.8, -0.6099999999999999}, {0.9, -0.43999999999999995}, {1.0, -0.25}, {1.1, -0.039999999999999813}, {1.2, 0.18999999999999995}, {1.3, 0.44000000000000017}, {1.4, 0.7099999999999997}, {1.5, 1.0}, {1.6, 1.3100000000000005}, {1.7, 1.6399999999999997}, {1.8, 1.9900000000000002}, {1.9, 2.36}, {2.0, 2.75}, {2.1, 3.16}, {2.2, 3.5900000000000007}, {2.3, 4.039999999999999}, {2.4, 4.51}}]
\dataplot[plotstyle=curve,showpoints=true]{\mydata}
\psline{<->}(0,2)(0,-2)(0,0)(3,0)
\psline{-}(1.3125,0)(2.2,3.55)
-
-\vspace{2em}
-% \begin{pspicture}(9,9)
-% \psaxes[labels=none,ticks=none]{->}(0,0)(8,8)[$x$,0][$y$,0]
-% \pscurve(1,1)(3,4)(6,6)(8,4)
-% \pscurve[linestyle=symbol,symbolStep=11.6pt,% must be positive
-% curveticks,startAngle=60](1,1)(3,4)(6,6)(8,4)
-% \end{pspicture}
-% \begin{pspicture}(8,8)
-% \psaxes[labels=none,ticks=none]{->}(0,0)(8,8)[$x$,0][$y$,0]
-% \pscurve[linestyle=symbol,symbolStep=-20,% must be negative !
-% curveticks,startAngle=60](1,1)(3,4)(6,6)(8,4)
-% \end{pspicture}
+\vspace{5em}
+\end{minipage}
+}
\caption{Représentation graphique de méthodes itératives de construction de racine}\label{fig:graphe1}
\end{figure}
\begin{Prop}[Construction iterrative selon la forme de Newton]
Pour tout $k \in \{1, \ldots, n\}$, on a:
-$$p_i(x) = p_{i-1}(x) + d_i \left[ \prod_{j=0}^{i-1} (x - x_j)\right]$$.
+$$p_i(x) = p_{i-1}(x) + d_i \left[ \prod_{j=0}^{i-1} (x - x_j)\right].$$
\end{Prop}
Ainsi pour obtenir $p$ sur $x_0$, $x_1$, \ldots, $x_n$, il suffit:
Les coefficients sur la première ligne fournissent les coefficients
de la forme de Newton de $p_n$ relative aux centres
-$x_0$, \ldots $x_{n-1}$:
+$x_0$, \ldots $x_{n}$:
$p_n(x) =
f[x_0] + f[x_0,x_1](x-x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) + \ldots
+ f[x_0,\ldots,x_n](x-x_0)(x-x_1)\ldots(x-x_{n-1})
