quelques typos

[cours-mesi.git] / complexite.tex

diff --git a/complexite.tex b/complexite.tex
index dff29856c46ed6d5ea545d680f9112abd84d4622..3dd4b380bc30bbc1b3de4d55b992848167d6fc55 100644 (file)
--- 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^*_+$. 
 
 Soit $\mathcal{F}$ l'ensemble des fonctions de
 $\N$ dans $\R^*_+$. 


@@ -123,7 +123,7 @@ $f  + f_1 \in \Theta(g)$.
 \end{Prop}
 
 
 \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. 
 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 +158,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$}.
 
 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
 Soit $p$ une fonction polynôme de degré $n$ définie par 
 $
 p(x) = \sum_{i=0}^n a_i x^i


@@ -201,7 +201,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$.
 
 
 Ainsi cet algorithme a une complexité linéaire en $n$.
 
 

-\subsubsection{Un second algo}
+\subsection{Un second algo}

 
 On considère l'algorithme suivant:
 
 
 On considère l'algorithme suivant:
 


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

-\subsection{Classes de complexité de problèmes}
+\section{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 
 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,7 +286,7 @@ 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 
 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 


@@ -294,7 +294,7 @@ 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}$.
 
 un algorithme en temps polynomial. 
 On a $\emph{P} \subset \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
 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