\documentclass [a4paper,twoside]{article}

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



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{exercice}{Exercice \rm 8.\hspace {-.1cm}}
\newtheorem{definition}{Définition}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\meta}[1]{$\blacklozenge$-\texttt #1}
\newcommand{\hop}{\textrm{ }}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}

%\headsep=+50pt
%\oddsidemargin=10pt
%\textwidth=430pt
\topmargin=0pt
%\textheight=700pt
\oddsidemargin=+60pt
\evensidemargin=+60pt
%\footskip=+10pt

\title{\textbf {\'El\'ements d'Informatique Th\'eorique} \\
                  S\'erie 8 \\
         \textsl {}}
\date {}
\vspace {-100 mm}
\maketitle



\begin{quote}
{\sl L'espoir de cette série est d'aider à la compréhension de divers concepts vus jusqu'ici,
en posant les problèmes sous un angle un peu différent de l'angle habituel: deux points de vue vallent mieux qu'un!
Elle est destinée à être faite pendant les TPs de fa\c con interactive, et n'est donc pas un document complet en soi.}
\end{quote}



\begin{exercice}\textrm{ }

\begin{definition}
  Une TM non déterministe est un algorithme $M$ avec deux bandes d'entrées: la bande d'''entrée'' et la bande de ``choix''.
  On définit $L(M)$ par: $L(M) :=\{ x\ |\ \exists y\ M( x, y ) = 1 \}$.
\end{definition}

  Ecrire un algorithme $A$ (dans votre langage de prédilection) prenant en paramètre une TM non déterministe $M$,
  t.q. $[ \forall x\ A_M( x ) = 1 ] \Leftrightarrow [ x \in L( M ) ]$.

\end{exercice}


\begin{exercice}
  Démontrer informellement que cette définition de TM correspond à celle du cours.
\end{exercice}


\begin{exercice}
  Donner la définition informelle d'un énumérateur. Matériel à disposition: un ordinateur et une imprimante...
\end{exercice}

\begin{exercice}
  Soit $M$ une TM. Quel est le langage énuméré par un énumérateur exécutant l'algorithme $A$ suivant:
  
   
  \texttt{
    Begin(A)
    \begin{quote}
       $i := 0$; \\
       While ( $i \geq 0$ ) \{ 
       \begin{quote} 
         Compute $s_i$; \# $s_i$ est le $i$ème mot de l'ordre canonique. \\
         Compute $M( s_i )$; \\ 
         If ( $M( s_i ) = 1$ ) \{ Print $s_i$ \}; \\
         $ i := i + 1$; \\ 
       \end{quote}
       \}
    \end{quote}
   End(A)
  }
\end{exercice}


\begin{exercice}
  Montrer qu'un langage peut être énuméré par un enumerateur ssi il peut être
  accepté par une TM.
\end{exercice}


\begin{exercice}
  Quel est le ``problème'' avec la TM suivante, qui semble \underline{décider} le langage des polynômes
  avec au moins une racine.
  
  Input: $p$ un polynôme multivarié.
  \begin{itemize}
    \item Soit $p=p(X_1,\ldots,X_k)$.
    \item Essayer chaque valeurs possibles de $(x_1,\ldots,x_k)\in\mathbb{N}^k$.
    \item Evaluer $p$ sur chacunes de ces valeurs.
    \item Si $\exists$ une valeur t.q. $p(x_1,\ldots,x_k)=0$, accepter.
    \item Sinon rejeter.
  \end{itemize}
\end{exercice}

\begin{exercice}
  Imaginez un protocole permettant d'accepter les langages acceptés par une TM non déterministe.
  Matériel à disposition: un ``vérificateur'', qui est un ordinateur.
  Personel à disposition: M.Dupont, qui est capable d'intuition...
  Monsieur Dupont peut partler à l'ordinateur, (via le clavier), et est capable d'une intuition surprenante,
  néanmoins, il arrive que son intuition le trompe, et qu'il fasse une erreur. (Heureusement, le ``vérificateur''
  ne se laisse pas tromper, lui). 
\end{exercice}

\begin{exercice}
Quels sont les langages acceptés par l'AFN et la TM suivants:

\begin{figure}[h]
        \begin{center}
        \input{blub.pstex_t}
        \end{center}
\end{figure}

Attention, les deux lanagages sont différents!!!
\end{exercice}


\end{document}
% Local Variables: 
% mode: latex
% TeX-master: "main"
% End: 
