From ceadb87030074840922c7616c4c22f86aba9d2c6 Mon Sep 17 00:00:00 2001 From: couchot Date: Mon, 16 Sep 2013 13:57:29 +0200 Subject: [PATCH] typos --- complexite.tex | 41 ++++++++++++++++++++++++++++++++--------- equations.tex | 19 ++++++------------- interpol.tex | 4 ++-- 3 files changed, 40 insertions(+), 24 deletions(-) diff --git a/complexite.tex b/complexite.tex index 3dd4b38..4fdf00d 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^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 $ @@ -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$ \; \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} @@ -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}$ diff --git a/equations.tex b/equations.tex index 4a76973..8fec68d 100644 --- a/equations.tex +++ b/equations.tex @@ -179,24 +179,17 @@ l'erreur avec la limite est inférieure à cet $\epsilon$. \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} diff --git a/interpol.tex b/interpol.tex index f1f9078..b5eef1f 100644 --- a/interpol.tex +++ b/interpol.tex @@ -69,7 +69,7 @@ On peut alors démontrer le résultat suivant. \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: @@ -112,7 +112,7 @@ $$ 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}) -- 2.39.5