From: couchot <jf.couchot@gmail.com>
Date: Thu, 12 Sep 2013 08:58:48 +0000 (+0200)
Subject: quelques typos
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-mesi.git/commitdiff_plain/52672f301b364d8a75708a2d5e35256af37965ff

quelques typos
---

diff --git a/complexite.tex b/complexite.tex
index dff2985..3dd4b38 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^*_+$. 
@@ -123,7 +123,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 +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$}.
 
-\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
@@ -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$.
 
 
-\subsubsection{Un second algo}
+\subsection{Un second algo}
 
 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}
 
-\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 
@@ -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 
@@ -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}$.
 
-\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