\documentclass[twoside,a4paper]{article}


\usepackage{amsmath,amssymb,latexsym,epsfig,delarray,graphics,graphpap,alltt,graphicx,epic,eepic}


\newtheorem {exercice} {Exercice \rm 13.\hspace {-.1cm}}
\newcommand{\sy}[1]{\mbox{\crr #1}}
\newfont{\crr}{pcrr at 11pt}
\newcommand{\tuple}[1]{{\langle{#1}\rangle}} % <.>
\newcommand{\set}[1]{\{#1\}}
\newtheorem{DEFx}{D\'efinition}
\newcommand{\codtime}[0]{\textbf{\rm co-DTIME}}
\newcommand{\dtime}[0]{\textbf{\rm DTIME}}
\newcommand{\codspace}[0]{\textbf{\rm co-DSPACE}}
\newcommand{\dspace}[0]{\textbf{\rm DSPACE}}

\begin{document}

\title{\textbf {El\'ements d' informatique th\'eorique} \\
                  S\'erie 13 \\
         \textsl {}}
\date {}
\vspace {-100 mm}
\maketitle

\begin{DEFx}{}
  La classe $\mathcal{T}$ des langages dits ``tally'' est définie comme
  \[
  \mathcal{T} = \set{L \mid L \subseteq \Sigma^* \cap \set{\sy 0}^*}
  \]
  La classe $\cal S$ des langages dits ``sparse'' est définie comme
  \[
  \mathcal{S} = \set{L \mid L \subseteq \Sigma^* \mbox{et}\ \exists c
  \forall n | \set{w \mid w \in L \cap \Sigma^n} | \leq n^c}
  \]
  La densité d'un langage $L$ est définie par la fonction
  \[
  d(n) = \frac{\text{nombre de mots de longueur } n \text{ de } L}
              {\text{nombre de mots de longueur } n \text{ de } \Sigma^*}
  \]
%\NOCLOSE
\end{DEFx}

\begin{exercice}
  En considérant $\Sigma = \{0,1\}$:
  \begin{enumerate}
  \item quelle est la densité d'un langage appartenant à $\cal T$ ?
  \item quelle est la densité d'un langage appartenant à $\cal S$ ?
  \item prouvez que $\cal T \subseteq S$!
  \end{enumerate}
\end{exercice}

\medskip

\begin{DEFx}{\rm Class complémentaire}
  Pour une classe de langages $C$, la classe associée co-$C$ est
  définie comme
  \[
  \text{co-}C = \{ L \mid \overline{L} \in C\}
  \]
%\NOCLOSE
\end{DEFx}

\begin{exercice}
  Prouvez que $\codtime(f(n)) = \dtime(f(n))$
\end{exercice}


\begin{exercice}
  
  \smallskip\noindent Prouvez que $\dspace(2^{2^n+n})$ inclut
  strictement $\dspace(2^{2^n})$ !
  
  \smallskip\noindent Que peut-on dire de $\dtime(2^{2^n + n})$ et
  $\dtime(2^{2^n})$ ?
\end{exercice}

\begin{exercice}
  Etablissez la relation entre les deux classes de complexité:
  \begin{enumerate}
  \item $\dspace(n^2)$ et $\dspace(f(n))$ où $f(n)=
    \begin{cases}
      n^3 & \text{si } n \text{ est pair,}\\
      n   & \text{sinon.}
    \end{cases}$
  \item $\dtime(2^n)$ et $ \dspace(5^n)$.
%  \item $\dspace(n)$ et $\dtime(\lceil \log_2n \rceil^n)$!
  \end{enumerate}
\end{exercice}
\end{document}



% Local Variables: 
% mode: latex
% TeX-master: "main"
% End: 
