\documentclass[10pt]{article}
\usepackage[height=250mm,width=183mm]{geometry}
\usepackage[euler,utf8,biblio]{preambuleTrm}



\hypersetup{
pdftitle={Automates géométriques - JΑ IREM 2015}, % title
}
%\usepackage[xcas]{pro-mat}

\usepackage{algo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}



\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/VISA_III/figures_visa/}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}}


\title{Calculer avec des points pour comprendre la machine (Collège/Lycée Maths/ISN)}

\author{Guillaume \textsc{Connan}\footnote{\href{mailto:Guillaume.Connan@univ-nantes.fr}{guillaume.connan@univ-nantes.fr}} - \textsc{Irem} de Nantes }

\date{JA de l'\textsc{Irem} de Nantes - Jeudi 9 avril 2015}


\begin{document}
\maketitle

\begin{Abstract}
La    géométrie    tend    à     disparaître    des    programmes...c'est    bien
dommage.  L'enseignement  de  l'informatique   tend  à  prendre  une  importance
croissante mais de manière assez floue  et parfois peu scientifique. L'avenir de
l'éducation est  aux \og  projets transversaux\fg{}:  faisons d'une  pierre deux
coups et apprenons le fonctionnement de la machine avec une règle et un compas.
Faisons également  découvrir aux élèves  que l'informatique peut  être théorique
voire uniquement cela.
\end{Abstract}



\section{Machine de construction géométrique}

En 1989, Ülrich \textsc{Huckenbeck}\footnote{ \cite{huck} et \cite{huck2}} décrit une machine dont les
primitives sont les  opérations géométriques usuelles que l'on  peut effectuer à
la règle et au compas.

Il  introduit  un   \textit{automate}  (\textsc{Gcm}:  Geometrical  Construction
Machine)  et donc  des  \textit{états} et  des  \textit{transitions}. La  notion
d'automate est extrêmement importante en  informatique et est souvent introduite
par les automates à  états finis sur des langages ou  plus généralement à partir
de machines de \textsc{Turing}.

Il ne s'agit  pas ici d'introduire une quelconque théorie  des automates mais de
faire  découvrir  comment en  informatique  le  papier  et  le crayon  sont  des
préalables (avec parfois des dizaines d'années  d'avance) à une mise en pratique
sur machine,  que l'informatique ne peut  être d'ailleurs que théorique,  que la
géométrie est  un champ d'investigation  informatique et qu'il est  bien dommage
qu'elle disparaisse des programmes.





Nous allons construire une \og machine\fg{} équipée de registres comme en vrai 
dont on peut définir la configuration à chaque instant.

On a des registres pour stocker:
\begin{itemize}
\item  des points (appelons-les $p_i$) qui contiennet
  des données de type $p(abs,ord)$;
\item des droites (appelons-les $d_i$)  qui contiennent des données de type
  $d(p_1,p_2)$;
\item des cercles (appelons-les $c_i$)  qui contiennent des données de type
  $c(p_1;p_2,p_3)$.
\end{itemize}

On considèrera que les registres sont initialisés et contiennent au départ:

\begin{itemize}
\item le point $(0,0)$ dans les registres $p_{3i}$
\item le point $(1,0)$ dans les registres $p_{3i + 1}$
\item le point $(0,1)$ dans les registres $p_{3i + 2}$
\item l'axe des abscisses dans les registres $d_{2i}$
\item l'axe des ordonnées dans les registres $d_{2i+1}$
\item le cercle unité centré en $(0,0)$ dns les registres $c_i$
\end{itemize}

La machine peut être dans trois états:

\begin{itemize}
\item \texttt{Non terminé}: la machine n'est pas dans un état terminal;
\item \texttt{Fini}: la machine n'attend plus d'instruction;
\item \texttt{Erreur}: il y a une erreur et la machine s'arrête.
\end{itemize}

Les deux derniers états sont dits \textit{terminaux}.

On peut effectuer  des opérations sur les registres selon  ce qu'ils contiennent
et l'état de la machine:

\begin{itemize}
\item copier une valeur d'un registre vers la sortie standard;
\item mettre dans un registre l'intersection de deux droites;
\item mettre dans un registre une  intersection d'une droite et d'un cercle avec
  la possibilité de la distinguer d'un point indiqué;
\item mettre dans un registre une intersection de deux cercles avec
  la possibilité de la distinguer d'un point indiqué;
\item mettre dans un registre la droite passant par deux points;
\item  mettre dans  un registre  le cercle  de centre  un point  et de  rayon la
  distance entre deux points;
\item copier le contenu d'un registre dans un autre;
\item indiquer que \og c'est fini\fg{}.
\end{itemize}


On  voit  déjà  poindre  plusieurs   problèmes:la  gestion  des  erreurs  et  le
non-déterminisme.

Généralement, l'informatique n'est abordée que sous l'angle déterministe.

Ici, on peut dérouler un  \textit{arbre} d'exécution qui aura éventuellement des
embranchements.

S'il n'y  a aucune \textit{feuille}  \texttt{Erreur} et que toutes  les feuilles
sont identiques, alors le \textit{programme} termine  et la sortie est celle des
feuilles 


\section{Premiers exemples}

On considère deux points distincts A et B: on voudrait calculer leur milieu.

\begin{algo}[numbered,noframe]
\STATE{$c_1$ \recoit{} $c(A; A,B)$}
\STATE{$c_2$ \recoit{} $c(B;A,B)$}
\STATE{$p_1$ \recoit{} intersection ($c_1,c_2$)}
\STATE{$p_2$ \recoit{} intersection ($c_1,c_2$) différente de $p_1$}
\STATE{$d_1$ \recoit{} $d(p_1,p_2)$}
\STATE{$d_2$ \recoit{} $d(A,B)$}
\STATE{$p_3$ \recoit{} intersection ($d_1,d_2$)}
\STATE{Écrire $p_3$ (dans un registre ou vers la sortie standard)}
\STATE{Fini}
\end{algo}


Construisez l'arbre correspondant.  Est-ce que ce programme  termine? Est-ce que
ce programme effectue la tâche prévue?

Adresse, étiquette, contenu?

Quels sont les états de la machine?

Donnez une séquence d'instructions qui construit un triangle équilatéral de base
$[A,B]$. Des remarques? Spécification?


Étant donné une droite $\Delta$, un point A de
cette droite et un point B différent de A, est-ce que la droite parallèle à $\Delta$
passant par B est \textit{constructible} par un \textsc{Gcm}?

Imaginez un problème avec des perpendiculaires.


Constructible/calculable?


\section{Opérations algébriques et théorème de Thalès}

Étant donné un point A de  coordonnées $(x,y)$, renvoyer le point de coordonnées
$(x,0)$ et le point de coordonnées $(0,y)$.

Étant  donné un  point  $(x_1,0)$  et un  point  $(x_2,0)$, quelle  construction
associer à $(x_1+x_2,0)$? Êtes-vous sûr(e)?


\begin{algo}[numbered,noframe]
\STATE{$p_1 $ \recoit{} $p(x_1,0) $}
\STATE{$p_2 $ \recoit{} $p(x_2,0) $}
\STATE{$p_3 $ \recoit{} milieu$(p_0,p_5) $}
\STATE{$d_3 $ \recoit{} $\bot (d_1,p_3)$}
\STATE{$d_4 $ \recoit{} $\bot (d_1,p_5)$}
\STATE{$d_5 $ \recoit{} $d(p_1,p_3)$}
\STATE{$p_6 $ \recoit{} $\cap (d_4,d_5)$}
\STATE{$d_6 $ \recoit{} $d(p_0,p_6) $}
\STATE{$p_7 $ \recoit{} $\cap (d_3,d_6)$}
\STATE{$d_7 $ \recoit{} $d(p_2,p_7) $}
\STATE{$p_8 $ \recoit{} $\cap (d_4,d_7)$}
\STATE{$d_8 $ \recoit{} $d(p_8,p_3) $}
\STATE{$p_9 $ \recoit{} $ \cap (d_0,d_8)$}
\STATE{Écrire $p_9$}
\STATE{Fini}
\end{algo}





Quels automates associer à $(x_1-x_2,0)$?  $(x_1\times x_2,0)$?  $(x_1/x_2,0)$?


\section{Un autre type d'automate}

Enlevons les opérations  sur le cercle mais rajoutons l'emploi  d'une équerre: on
va donc  maintenant construire à la  règle et à l'équerre:  quelle propriété \og
informatique\fg{} importante gagne-t-on?


\section{Informatique sans machine}

Une  grande part  de  l'informatique  s'étudie \og  sans  machine\fg{} mais  son
enseignement peut  également se  faire de  manière ludique  et sans  recours aux
ordinateurs. On  pourra se référer à  l'ouvrage Néo-Zélandais\footnote{\cite{cs}}
qui introduit le  programme d'informatique de Licence...à  l'école primaire mais
de manière ludique.

Pour voir au contraire des automates géométriques beaucoup plus riches et pour
l'instant  plutôt théoriques  mais dont  les implications  pourraient être  très
importantes, voir \cite{orleans}.



\section{Mathématique discrète et \og computer science\fg{}}

Nous avons du  mal en français à  trouver des termes pour  désigner les domaines
gravitant autour  de l'informatique. Ce  dernier mot est souvent  remplacé par
\textsc{Tice}  (  avec  un  T  comme  \textit{technologie}...cela  restreint  le
domaine  et permet  de  comprendre pourquoi  pendant  si longtemps  informatique
rimait avec bureautique) ou bien
par \textit{numérique} et  la dernière mode est de parler  de \textit{code}. Les
anglo-saxons parlent de \textit{Computer  Science}, désignation qui a l'avantage
de comporter le  mot \textit{science}. \textit{Computer Science}  est \textbf{en relation
avec}   les   domaines   \textit{Scientific   Computing}   et   \textit{Computer
Engineering} mais n'est pas du tout réduit à ces deux composantes proches.

Le département de \textit{Computer Science}  de l'Université de Boston s'adresse
ainsi                     à                    ses                     futur(e)s
étudiant(e)s\footnote{\href{http://www.cs.bu.edu/AboutCS/WhatIsCS.pdf}{http://www.cs.bu.edu/AboutCS/WhatIsCS.pdf}}:

\begin{quote}
  \og \textit{Computer Science is about problem solving. Thus, the qualities of a good computer scientist include a passion for
finding elegant solutions, an ability to use mathematical analysis and logical rigor to evaluate such solutions, creativity
in modeling complex problems through the use of abstractions, attention to details and hidden assumptions, an ability to
recognize variants of the same problem in different settings, and being able to retarget known efficient solutions to
problems in new settings. If you like to solve puzzles, then computer science is for you!}\fg{}
\end{quote}

Cela ressemble beaucoup à ce que l'on attend d'élèves étudiant les mathématiques!...


%%% biblio et fin 
%\renewcommand{\bibname}{Lectures recommand\'ees pour aller plus loin}
\bibliography{JA2015automata}

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