From 52672f301b364d8a75708a2d5e35256af37965ff Mon Sep 17 00:00:00 2001 From: couchot Date: Thu, 12 Sep 2013 10:58:48 +0200 Subject: [PATCH] quelques typos --- complexite.tex | 20 ++++++++++---------- 1 file changed, 10 insertions(+), 10 deletions(-) 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 -- 2.39.5