X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-mesi.git/blobdiff_plain/f4fb6abd4d0ca7a866d0cba93347244e9797040a..d1778cd1db87ac86b892c6d65935e6ee1abc95a3:/complexite.tex?ds=sidebyside diff --git a/complexite.tex b/complexite.tex index dff2985..4fdf00d 100644 --- 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^*_+$. @@ -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 $ @@ -123,7 +146,7 @@ $f + f_1 \in \Theta(g)$. \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. @@ -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$}. -\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 @@ -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} @@ -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$. -\subsubsection{Un second algo} +\subsection{Un second algo} 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} - \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,9 +297,9 @@ peut-il être lent pour des données de petite taille? \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 @@ -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. -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