<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/cours-mesi.git/blobdiff_plain/f4fb6abd4d0ca7a866d0cba93347244e9797040a..d6ce74e9e31c2e1c2fb0f30a9bbb0058d1e20731:/complexite.tex

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Ã© Ã&nbsp; 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 Ã&nbsp; celui-ci. 
 Cela signifie que le problÃ¨me est au moins aussi difficile
</pre></body></html>