<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass{beamer}
\def\mpath{/home/guillonb/docs.enc/work/phd/write-draw/latex/macros}
\input{\mpath/common/packages.tex}
\input{\mpath/beamer/beamer.tex}
\input{\mpath/beamer/color.tex}
\input{\mpath/common/utils.tex}
\input{\mpath/common/two-way.tex}
\input{\mpath/common/tape.tex}
\input{\mpath/common/editor-utils.tex}
\input{\mpath/common/authors.tex}
\usepackage[francais]{babel}

\tikzstyle{good}=[inner xsep=2em,inner ysep=1em,fill=green!30,draw=green,rounded corners,text=black]
\tikzstyle{bad}=[inner xsep=2em,inner ysep=1em,fill=red!30,draw=red,rounded corners,text=black]
\tikzstyle{neutral}=[inner xsep=2em,inner ysep=1em,fill=blue!30,draw=blue,rounded corners,text=black]
\tikzstyle{subgood}=[fill=green!10,draw=green!50,rounded corners,text=black]
\tikzstyle{subbad}=[fill=red!20,draw=red!50,rounded corners,text=black]

\newcommand{\fa}[1][]{\textsc{#1fa}}
\newcommand{\nfa}[1][]{\ensuremath{#1}\fa[n]}
\newcommand{\dfa}[1][]{\ensuremath{#1}\fa[d]}

\newtheorem{exemple}{Exemple}

\title{Extensions d'Automates Finis}
\author{\BG\inst{1}$^{\text{,}}$\inst{2}}
\institute{\inst{1}\LIAFA\ - \UPD7\\\inst{2}\DI\ - \UNIMI}
\date{2 Avril 2015\\EJCIM - OrlĂŠans - 2015}

\begin{document}
\maketitle

\begin{frame}
	\frametitle{\onslide&lt;1-7&gt;{Machine de Turing}\onslide&lt;8-&gt;{Automate fini}}
	\begin{figure}
		\begin{tikzpicture}[scale=.5]
      \node[automaton] (automaton) at (2*\cellwidth,4.5) {\huge Programme fini};
      \path
		++(6*\cellwidth,\cellheight/2) coordinate (head)
		(automaton.south) edge[-&gt;,ultra thick,draw=none,myncbar,angle=270,arm=2em]
					node[above right,text=inoutcolor] (rw) {\textcolor{incolor}{\textsc{lire}}/\textcolor{outcolor}{\textsc{ĂŠcrire}}} (head)
		(head) 	node[above right,text=movecolor] (rarrow) {\huge$\rightarrow$}
					node[above left,text=movecolor] (larrow) {\huge$\leftarrow$};
		%TURING Machine
		\onslide&lt;1-7&gt;{
			\tape{(0,0)}[u,n]{2}[0][tapeCell,text=inoutcolor][3][1]
			\tape{++(0:4*\cellwidth)}[r,u,b,a,n]{5}[0][tapeCell,text=inoutcolor][1][1]
			\tape{++(0:11*\cellwidth)}[i,n,f,i,n,i]{6}[0][tapeCell,text=inoutcolor][1][3]
			\path (automaton.south) edge[-&gt;,ultra thick,inoutcolor,myncbar,angle=270,arm=2em] (head);
		}
		%ONE-WAY FINITE AUTOMATON
		\onslide&lt;8-&gt;{
			\path[very thick,red,draw]
			(rw.south) edge (rw.north east)
			(larrow.south west) edge (larrow.north east)
			(-2.5,-.75) edge ++(2,1.5)
			(-3.5,-.75) edge ++(2,1.5)
			(0,0) ++(0:15*\cellwidth) ++(-.5,-.75) edge ++(2,1.5)
			(0,0) ++(0:15*\cellwidth) ++(.5,-.75) edge ++(2,1.5);
			\tape{(0,0)}[u,n]{2}[0][tapeCell,text=incolor][3][1]
			\tape{++(0:4*\cellwidth)}[r,u,b,a,n]{5}[0][tapeCell,text=incolor][1][1]
			\tape{++(0:11*\cellwidth)}[f,i,n,i]{4}[0][tapeCell,text=incolor][1][3]
			\path (automaton.south) edge[-&gt;,ultra thick,incolor,myncbar,angle=270,arm=2em] (head);
		}
		%MESSAGES
		\fill[white,opacity=.5,visible on=&lt;2-6&gt;] (-5,-1) rectangle ++(25*\cellwidth,10);
		\fill[white,opacity=.5,visible on=&lt;9-&gt;] (-5,-1) rectangle ++(25*\cellwidth,10);
		\path
		(automaton.north east) ++(30:5) node[good,visible on=&lt;2-6&gt;,rotate=5] (goodTM1) {On calcule plein de choses !}
		(automaton.south west) ++(-30:6) ++(0:1) node[good,visible on=&lt;3-6&gt;,rotate=10] (goodTM2) {Correspond assez bien Ă&nbsp; l'idĂŠe de calcul}
		++(10:10) node[subgood,visible on=&lt;3-6&gt;,rotate=30] {Temps...}
		++(270:2) node[subgood,visible on=&lt;3-6&gt;,rotate=5] {Espace...}
		(automaton.north) ++(0:1) node[bad,visible on=&lt;4-6&gt;,rotate=-5] (badTM1) {Les calculs sont  trop compliquĂŠs !}
		(badTM1.east) ++(-20:2) node[subbad,visible on=&lt;4-6&gt;,rotate=-5] {\ensuremath{P=NP} ?}
		++(70:2) node[subbad,visible on=&lt;4-6&gt;,rotate=-15] {\ensuremath{L=NL} ?}
		(automaton.south east) ++(-90:3) node[bad,visible on=&lt;5-6&gt;,rotate=-10] (badTM2) {Rien n'est dĂŠcidable !}
		(badTM2.east) ++(20:3) node[subbad,visible on=&lt;5-6&gt;] {Ăquivalence ?}
		++(-80:2) node[subbad,visible on=&lt;5-6&gt;,rotate=-10] {ArrĂŞt ?}
		(goodTM1) ++(90:1) node[bad,visible on=&lt;6&gt;,rotate=-10] {On n'y arrive pas !}
		;
		\path
		(automaton.north west) ++(10:2) node[good,rotate=5,visible on=&lt;9-&gt;] (goodFA1) {C'est plus facile}
		(goodFA1.east) ++(10:3) node[subgood,rotate=10,visible on=&lt;9-&gt;] {temps linĂŠaire}
		++(-80:2) node[subgood,rotate=2,visible on=&lt;9-&gt;] {espace constant}
		(automaton.south west) ++(-70:5.5) node[good,rotate=12,visible on=&lt;10-&gt;] (goodFA2) {CaractĂŠrisations}
		(goodFA2.east) ++(-40:3) node[subgood,rotate=5,visible on=&lt;10-&gt;] {grammaire de Chomsky}
		++(90:1.5) node[subgood,rotate=0,visible on=&lt;10-&gt;] {algĂŠbrique}
		++(80:1.5) node[subgood,rotate=10,visible on=&lt;10-&gt;] {logique}
		(automaton.south east) ++(-10:3) node[good,rotate=15,visible on=&lt;11-&gt;] (goodFA3) {StabilitĂŠ}
		(goodFA3.east) ++(-60:2) node[subgood,rotate=3,visible on=&lt;11-&gt;] {OpĂŠration boolĂŠenne}
		++(100:3) node[subgood,rotate=6,visible on=&lt;11-&gt;] {Miroir...}
		(automaton.north) ++(80:3) node[good,rotate=5,visible on=&lt;12-&gt;] (goodFA4) {\Large On sait y faire !}
		(goodFA4.east) ++(10:3) node[subgood,rotate=10,visible on=&lt;12-&gt;] {Lemme de pompage}
		;
		\end{tikzpicture}
	\end{figure}
\end{frame}

\begin{frame}
	\frametitle{Ajoutons de la puissance !}
	\begin{figure}
		\begin{tikzpicture}[scale=.5]
			\node[automaton] (automaton) at (2*\cellwidth,4.5) {\huge Programme fini};
			\path
			++(6*\cellwidth,\cellheight/2) coordinate (head)
			(automaton.south) edge[-&gt;,ultra thick,draw=none,myncbar,angle=270,arm=2em]
			node[above right,text=incolor] (r) {\textsc{lire}} (head)
			(head)	node[above right,text=movecolor] (rarrow) {\huge$\rightarrow$}
			node[above left,text=movecolor,visible on=&lt;3-&gt;] (larrow) {\huge$\leftarrow$};
			\onslide&lt;3-&gt;{
				\tape{(-1,0)}[$\lend$]{1}[0][tapeCell,text=incolor][0][0]
				\tape{++(0:15*\cellwidth)}[$\rend$]{1}[0][tapeCell,text=incolor][0][0]
			}
			\tape{(0,0)}[u,n]{2}[0][tapeCell,text=incolor][0][1]
			\tape{++(0:4*\cellwidth)}[r,u,b,a,n]{5}[0][tapeCell,text=incolor][1][1]
			\tape{++(0:11*\cellwidth)}[f,i,n,i]{4}[0][tapeCell,text=incolor][1][0]
			\path (automaton.south) edge[-&gt;,ultra thick,incolor,myncbar,angle=270,arm=2em] (head);
		\end{tikzpicture}
	\end{figure}
	\pause
	\begin{itemize}
		\item&lt;+-&gt; Non-dĂŠterminisme ? (NFA)
		\item&lt;+-&gt; De la bidirectionnalitĂŠ ? (2FA)
		\item&lt;+-&gt; Les deux ? (2NFA)
		\item&lt;+-&gt; De l'ĂŠcriture ? (Ăcriture seulement Ă&nbsp; la premiĂ¨re visite d'une cellule : $1$LFA)
		\item&lt;+-&gt; ...
	\end{itemize}
	\uncover&lt;+-&gt;{\temph[1]{Tous de la mĂŞme puissance !}}
	\uncover&lt;+-&gt;{\temph[2]{\textbf{Question :} quelle diffĂŠrence ?}}
\end{frame}

\begin{frame}
	\frametitle{ComplexitĂŠ descriptionnelle}
	La taille des modĂ¨les !
	\begin{itemize}
		\item&lt;2-&gt; Bornes supĂŠrieures (algorithme simulation)
		\item&lt;3-&gt; Bornes infĂŠrieures (langages de sĂŠparation)
	\end{itemize}
	\vspace{1ex}
	\uncover&lt;4-&gt;{
		\begin{exemple}
			\vspace{-3ex}
			\begin{center}
				\temph[1]{\dfa[1] versus \nfa[1]}
			\end{center}
			\begin{itemize}
				\item&lt;5-&gt; Construction de l'ensemble des parties
				\item&lt;6-&gt;
					$L_n=\set{(a,b)^*b(a,b)^{n-1}}$
					\begin{itemize}
						\item&lt;7-&gt;acceptĂŠ par un \nfa[1] (ou un \dfa[2]) Ă&nbsp; $n$ ĂŠtats
						\item&lt;8-&gt;mais par aucun \dfa[1] Ă&nbsp; moins de $2^n$ ĂŠtats !
					\end{itemize}
			\end{itemize}
		\end{exemple}
	}
	\vspace{2ex}
	\uncover&lt;9-&gt;{\temph[2]{\textbf{Question :} \dfa[2] versus \nfa[2] ?}}
	\hspace{2em}
	\uncover&lt;10-&gt;{\temph[3]{ouvert !}}
	\newline
	\uncover&lt;11-&gt;{%
		\temph[2]{\textbf{Question :} \nfa[1] versus \dfa[2] ?}
		\hspace{2em}
		\temph[3]{ouvert !}%
	}
\end{frame}

\begin{frame}
	\frametitle{RĂŠ-ajoutons de la puissance !}
	\begin{figure}
		\begin{tikzpicture}[scale=.5]
			\node[automaton] (automaton) at (2*\cellwidth,4.5) {\huge Programme fini};
			\path
			++(6*\cellwidth,\cellheight/2) coordinate (head)
			(automaton.south) edge[-&gt;,ultra thick,draw=none,myncbar,angle=270,arm=2em] node[above right,text=incolor] (r) {\textsc{lire}} (head)
			(head)	node[above right,text=movecolor] (rarrow) {\huge$\rightarrow$}
			node[above left,text=movecolor] (larrow) {\huge$\leftarrow$};
			\tape{(-1,0)}[$\lend$]{1}[0][tapeCell,text=incolor][0][0]
			\tape{++(0:15*\cellwidth)}[$\rend$]{1}[0][tapeCell,text=incolor][0][0]
			\tape{(0,0)}[u,n]{2}[0][tapeCell,text=incolor][0][1]
			\tape{++(0:4*\cellwidth)}[r,u,b,a,n]{5}[0][tapeCell,text=incolor][1][1]
			\tape{++(0:11*\cellwidth)}[f,i,n,i]{4}[0][tapeCell,text=incolor][1][0]
			\path (automaton.south) edge[-&gt;,ultra thick,incolor,myncbar,angle=270,arm=2em] (head);
		\end{tikzpicture}
	\end{figure}
	\pause
	\begin{itemize}
		\item Non-dĂŠterminisme ? / BidirectionalitĂŠ
		\item&lt;+-&gt; MĂŠmoire supplĂŠmentaire : un compteur/une pile
		\item&lt;+-&gt; Ăcriture lors des $2$ (ou $k$) premiĂ¨res visites d'une cellule.
		\item&lt;+-&gt; Un ruban de sortie en ĂŠcriture seule
		\item&lt;+-&gt; ...
	\end{itemize}
	\uncover&lt;+-&gt;{\temph[1]{Plus puissant !}}
	\uncover&lt;+-&gt;{\temph[2]{\textbf{Question :} que calcule-t'on ? Que ne calcule-t'on pas ?}}
\end{frame}

\begin{frame}
	\frametitle{ComplexitĂŠ algorithmique}
	\begin{figure}
		\begin{tikzpicture}[scale=.5]
      %% input tape
      \path
      (0,9) coordinate (left endmarker)
      (left endmarker) ++(0:17*\cellwidth) coordinate (right endmarker);
      \tape{(left endmarker)}[$\lend$,t,h,e]{4}[0][tapeCell,text=incolor][0][1]
      \tape{(left endmarker) ++(0:6*\cellwidth)}[i,n,p,u,t]{5}[0][tapeCell,text=incolor][1][1]
      \tape{(left endmarker) ++(0:13*\cellwidth)}[w,o,r,d,$\rend$]{5}[0][tapeCell,text=incolor][1][0]
      %% automaton
      \node[automaton] (automaton) at (6*\cellwidth,4.5) {\huge\ensuremath{Automaton}};
      %% input head
      \path (left endmarker) ++(9*\cellwidth,-\cellheight/2) coordinate (lire);
      \path (automaton.north) edge[-&gt;,ultra thick,incolor,myncbar,angle=90,arm=2em] node[below right,text=incolor] {\textsc{lire}} (lire);
      %% about 2-way (on slide &lt;2-&gt; (legend only on &lt;2&gt;))
      \path
      (lire) node[below left,text=movecolor] {\huge$\leftarrow$} node[below right,text=movecolor] {\huge$\rightarrow$};
      %% output tape (on slide &lt;3-&gt;)
		\tape{(0,0)}[t,h,e]{3}[0][tapeCell,text=outcolor][0][1]
		\tape{++(0:5*\cellwidth)}[o,u,t,p,u,t]{7}[0][tapeCell,text=outcolor][1][3]
      %% output head (on slide &lt;3-&gt;)
      \path
      ++(11*\cellwidth,\cellheight/2) coordinate (ĂŠcrire)
      (automaton.south) edge[-&gt;,ultra thick,outcolor,myncbar,angle=270,arm=2em] node[above right,text=outcolor] {\textsc{ĂŠcrire}} (ĂŠcrire)
      %% about 1-way writing (on slide &lt;3-&gt;)
      (ĂŠcrire) node[above right,text=movecolor] {\huge$\rightarrow$};
		%% different power
		\fill[white,opacity=.5,visible on=&lt;2-&gt;] (-1,-1) rectangle (18*\cellwidth,10);
		\path
		(lire) node[bad,visible on=&lt;2-&gt;] {variantes $\rightarrow$ puissance de calcul diffĂŠrentes}
		++(-90:2) node[subbad,visible on=&lt;3-&gt;] { $R=\set{(\inC{w},\outC{w\cdot w}), w\in\Sigma^*}$ }
		++(-90:1.5) node[subbad,visible on=&lt;3-&gt;] { Syracuse en unaire }
		++(-90:3.5) node[neutral,visible on=&lt;4-&gt;] { \textbf{Question :} Bi- versus Unidirectionnel en unaire ? }
		++(-90:2.5) ++(0:-4) node[bad,visible on=&lt;5-&gt;] {diffĂŠrent}
		++(0:8) node[subbad,visible on=&lt;5-&gt;] { $R=\set{(a^n,a^{kn}) \mid k,n\in\mathbb{N}}$ }
		++(0:-4) ++(-90:2.5) node[good,visible on=&lt;6-&gt;] {CaractĂŠrisation algĂŠbrique};
    \end{tikzpicture}
  \end{figure}
\end{frame}

\end{document}
</pre></body></html>