\documentclass[11pt]{article}
\usepackage{fullpage}

\usepackage{epsf}

\title{\vskip -2cm Structures combinatoires et fractales.\\
\small
(R\'edaction en Pascal d'un programme \\
reconnaissant divers objets combinatoires.)\vskip -1cm}

\date{21 avril 2000\vskip -3cm}

\begin{document}\maketitle
\section{Contrat}
Ceci est le projet num\'ero 2 de th\'eorie des langages / Compilation.\\
Vous faites donc au choix \\
soit le sujet de CAML,\\
soit le sujet TL num\'ero 1 (orient\'e compilation),\\
soit le sujet de TL num\'ero 2 (orient\'e th\'eorie des langages).\\


Ces 4 pages servent seulement \`a vous donner un aper\c cu de ce que peut
\^etre ce projet, afin de pouvoir choisir CAML {\em ou} TL en
connaissance de cause. Pour ceux qui opteront pour ce sujet, de plus
amples pr\'ecisions seront donn\'ees en TP.
%En plus des deux autres enseignants de TL, je serai
%toujours disponieble pour tout probl\`eme/question 
%lors des s\'eances de TD/TP le vendredi
%apr\`es-midi ou encore par mail \`a Cyril.Banderier@inria.fr

\vskip 3mm
\noindent
M\'emoire \'ecrit (3 pages r\'esumant le projet+ code source) \`a rendre le 7 juin.\\
Soutenance orale le 15 juin.\\
Travail en bin\^ome autoris\'e.

\begin{center}
\leavevmode\epsfxsize=7truecm\epsfysize=10truecm\epsfbox{Flocon.ps}
\leavevmode\epsfxsize=7truecm\epsfysize=10truecm\epsfbox{Over1b.ps}
\end{center}



\section{Introduction}
De nombreux ph\'enom\`enes en physique, en chimie ou encore en
biologie et en botanique se mod\'elisent par des proc\'ed\'es de
r\'e\'ecritures ({\em i.e.} des grammaires) d'une forme un peu
sp\'eciale, on parle  de ph\'enom\`enes d'{\bf auto-similarit\'e}. 
La venue de l'ordinateur permit d'esth\'etiques repr\'esentations
graphiques, et Beno\^{\i}t Mandelbrot, l'initiateur de ce domaine, 
donna \`a ces dessins le nom de {\bf fractales}.

Par ailleurs, de nombreuses {\bf structures combinatoires} (arbres,
graphes, marches al\'eatoires, g\'enome, polyominos...) peuvent 
\'egalement \^etre g\'en\'er\'ees par des grammaires. 

Puisque ces objets sont essentiellement des ``dessins'', des objets 
tr\`es ``visuel'', une question se pose : 
comment rentrer (=d\'ecrire) de tels objets sur un ordinateur ?


Heureusement (et cela justifie en particulier les quelques mois que
vous venez de passer \`a faire de la TL~!), il est tout \`a fait
 possible d'associer un mot (au sens TL) \`a chacun de ces objets, de
ces dessins. De plus, pour la plupart des structures cit\'ees ci-dessus, 
on conna\^{\i}t m\^eme les grammaires qui les engendrent !

Par exemple, les arbres binaires sont engendr\'es par la
grammaire 
$$B\rightarrow f | BnB$$ (qui refl\`ete la d\'efinition ``un arbre
binaire, c'est soit une feuille, soit un n{\oe}ud avec des sous-arbres
droit et gauche qui sont aussi des arbres binaires'').
Voyez ci-dessus d'autres types d'arbres qui tombe soient dans le
domaine de la combinatoire ou des fractales.
\begin{center}
\leavevmode\epsfxsize=7truecm\epsfysize=9truecm\epsfbox{birch-color.ps}
\leavevmode\epsfxsize=7truecm\epsfysize=9truecm\epsfbox{pre.ps}\\
\leavevmode\epsfxsize=4truecm\epsfysize=5truecm\epsfbox{fern.ps}
\leavevmode\epsfxsize=8truecm\epsfysize=8truecm\epsfbox{schroeder.ps}\\
%\leavevmode\epsfxsize=16truecm\epsfysize=14truecm\epsfbox{bst.ps}\\
%\leavevmode\epsfxsize=17truecm\epsfysize=14truecm\epsfbox{chemins.ps}
%\leavevmode\epsfxsize=17truecm\epsfysize=14truecm\epsfbox{polyomino.ps}
\end{center}

\newpage
Un autre exemple est reli\'e aux figures du jeu T\'etris
qui sont constitu\'ee de 4 carr\'es, on les appelle parfois
``t\'etramino'' (par extension de ``domino''), 
les polyominos sont la g\'en\'eralisation avec un nombre quelconque 
de carr\'es agglutin\'es. 

Voici par exemple la liste des pentaminos
\begin{center}\vskip -4mm
\leavevmode\epsfxsize=17truecm\epsfysize=9truecm\epsfbox{pentaminos.ps}
\end{center}


L\`a encore, on est heureux car il y a 
des grammaires qui engendrent certaines familles pr\'ecises de 
polyominos (mais trouver une grammaire non ambig\"ue pour tous les polyominos 
est toujours un probl\`eme ouvert). 

\section{Le projet en soi}

Quatre feuilles d'annexes d\'ecrivant (grammaire et dessins) les objets combinatoires \`a reconna\^{\i}tre ou engendrer  par Lex/Yacc seront distribu\'es aux int\'eress\'es en TP.

Le projet consiste, \'etant donn\'e un type de structure combinatoire
(arbre binaire, fractale, graphe, polyomino...),
\begin{itemize}
\item[*] \`a permettre \`a l'utilisateur de saisir un mot au clavier
\item[*] de d\'eterminer alors si le mot rentr\'e est bien du type voulu
\item[*] et si oui, donner quelques caract\'eristiques de l'objet (du genre : ``oui, c'est un arbre binaire et il a 4 feuilles'')
\item[*] puis au final dessiner la structure correspondante.
\end{itemize}

%\vskip 1cm
Par exemple, l'utilisateur rentre ``fnf'',
votre programme doit reconna\^{\i}tre l\`a l'arbre binaire \`a un n{\oe}ud
et deux racines et dessiner (grossi\`erement) cet arbre.
Autre exemple~: l'utilisateur rentre 
{\tt Mafractale\{Angle 8, Axiom L--F--L--F, L=+R-F-R+,R=-L+F+L-\}}
ou {\tt Pentigree\{Angle 5, Axiom F-F-F-F-F,F=F-F++F+F-F-F\}}
et votre programme 
doit reconna\^{\i}tre l\`a une fractale de type $L$-system (d\'etails
donn\'es en TP) et  dessiner les courbes suivantes
\begin{center}
\leavevmode\epsfxsize=6truecm\epsfysize=6truecm\epsfbox{sierpnew.ps}
\leavevmode\epsfxsize=6truecm\epsfysize=6truecm\epsfbox{pentigre.ps}
\end{center}

Suivants les go\^uts des personnes prenant ce sujet, les structures
\`a reconna\^{\i}tre peuvent varier, vous pourrez vous-m\^eme en
choisir. De plus, il existe de nombreux sites web consacr\'es \`a ce
sujet et qui pourront \'eventuellement vous inspirer. Un tr\`es bon
 logiciel gratuit dessinant des fractales se trouve d'ailleurs sous
{\tt http://spanky.triumf.ca/www/fractint/fractint.html}

\section{Conclusion}

La t\^ache vous est grandement simplifi\'ee car les grammaires vous
seront fournies et car vous pourrez vous appuyez sur le couple
 Lex/Yacc (qui m\^ache 69,13\% du boulot), quant \`a 
la partie ``graphique'', vous pourrez utiliser des proc\'edures 
d\'ej\`a fournies par la ``graph unit'' de Pascal, l'ensemble de 
ce projet peut donc rentrer en 5 pages de code.

Ce projet ``Structures combinatoires et fractales'' se veut un peu
moins ax\'e sur la compilation (que le sujet de TL num\'ero 1), 
a une saveur peut-\^etre un peu math\'ematique et est plut\^ot 
orient\'e vers la partie ``th\'eorie des langages''. Des extensions 
possibles (pour les bin\^omes ?) consisteraient \`a dessiner 
avec plus de soin les structures consid\'er\'ees, ou pour les 
matheux \`a \'etudier plus profond\'ement divers param\`etres 
des structures consid\'er\'ees (d\'etails en TP).

\vskip 5mm

L'int\'er\^et de ce sujet est \\
\indent $\bullet$ d'une part de clarifier l'utilit\'e de l'analyseur 
lexical ``Lex'' et de l'analyseur syntaxique ``Yacc'' \`a travers des 
exemples simples et ludiques\\
\indent  $\bullet$ et d'autre part de vous faire d\'ecouvrir des
structures combinatoires qui ne sont pas seulement des ``jouets''
 mais \'egalement les objets fondamentaux, les ``atomes'' de presque 
tout algorithme digne de ce nom en informatique et qui sont de fait 
toujours l'objet de recherches actives et au carrefour de multiples disciplines.

\begin{center}
\leavevmode\epsfxsize=5truecm\epsfysize=6truecm\epsfbox{weed.ps}
\leavevmode\epsfxsize=5truecm\epsfysize=6truecm\epsfbox{bush.ps}
\leavevmode\epsfxsize=5truecm\epsfysize=6truecm\epsfbox{plant4.ps}
\end{center}
\end{document}


%montrer http://www.theory.csc.uvic.ca/~cos/
%L systems DOL, IFS