LOGO et les L-systèmes
Le mot "L-système" est une abréviation
de "Lindenmayer system". Aristid Lindenmayer (1925-1989),
biologiste hongrois, a été le premier à
remarquer que certains processus de croissance naturels pouvaient être modélisés
par un simple ensemble de règles. C'est ainsi que lors de la croissance d'un
être vivant, les cellules de l'organisme, en se reproduisant, se divisent tour
à tour en deux, plus petites. Parfois, la cellule d'origine ne disparaît pas
tout de suite lors de la génération suivante. De cette observation,
Lindenmayer en a tiré plusieurs axiomes possibles et indépendants:
- On appellera C, la cellule "mère",
et c une cellule "fille".
- La flèche -> veut dire "... est
remplacée par ..."
-
- axiome 1: C-> c c C (les deux cellules
"filles" sont à gauche de la cellule "mère")
- axiome 2: C-> C c c (les deux cellules
"filles" sont à droite de la cellule "mère")
- axiome 3: C-> c C c (les deux cellules
"filles" encadrent la cellule "mère")
Lorsque la cellule "mère" disparaît
lors de la génération suivante, il n'y a qu'un seul axiome possible:
axiome 4: C -> c c
En prenant l'axiome 3 pour passer d'une
génération à la suivante, on aura:
- Génération initiale: C
- Génération 1: c C c
- Génération 2: c C c c C c c C c (les deux
cellules "fille" se sont divisées chacune de leur côté)
- Génération 3: c C c C c C c c C c C c C c c C
c C c C c
- Génération 4:
-
c C c C c C c C c C c C c C c c C c C c C c C c C c C c C c c C c C c C c C
c C c C c C c
- .......................
-
Comme on le constate, cet axiome engendre un
organisme qui peut devenir gigantesque. Dans
la nature, la cellule "mère" disparaît la plupart du temps lors des
premières générations qui suivent sa réplication, ce qui ramène l'organisme
en construction à une taille raisonnable (axiome 4).
Les observations de Lindenmayer en sont restées
là jusqu'en 1968, date qui a vu l'essor des mini-ordinateurs, ce qui a permis leur
adaptation au domaine de la géométrie et du graphisme
par le truchement de l'informatique. Il fallait simplement remplacer la cellule
"mère" et les deux cellules "fille" (3 configurations
possibles) pour définir une longueur de déplacement du crayon et un angle pour
passer d'une génération à la suivante. Ce passage d'une génération à
l'autre peut se faire soit en tournant à gauche (-), soit en tournant à droite
(+). La place des signes est purement arbitraire et ils peuvent être interchangés.
Si on définit la longueur de déplacement par L
(1 unité) et l'angle alpha par un nombre (exprimé en degré ou en radians, selon
le cas), on aura par exemple:
un carré par la gauche:
un carré par la droite:
-
L=1
L=1
-
alpha=90°
alpha=90°
- axiome: L -> L -
L
axiome: L -> L + L
-
- Pour le carré par la gauche, on aura
successivement:
-
- Génération initiale: L
- Génération 1: L - L
- Génération 2: L - L - L - L
- Génération 3: L - L - L - L - L - L - L
- L
-
-
Un L-système est donc une grammaire formelle : un ensemble de règles et de
symboles.
- Il est composé de quatre éléments :
-
1. Les variables : des symboles pouvant être remplacés.
2. Les constantes : des symboles ne pouvant pas être remplacés (angle,
module de déplacement).
3. Un axiome de reproduction, appliquées aux variables de manière récursive.
4. Une configuration initiale, ou encore objet de départ. En LOGO, la
tortue se trouve
- en (0,0).
Les conditions sont à présent réunies pour
traduire ces axiomes en langage LOGO.
Si AVANCE, TOURNEDROITE et TOURNEGAUCHE sont des
primitives évidentes à appliquer, il faut, avant de faire déplacer la tortue,
construire la liste des mouvements qui résulte de la transformation de l'axiome
de reproduction pendant le passage inter-générationnel. A la troisième
génération, le carré par la gauche aura pour liste des mouvements :
[ L - L - L - L - L - L - L - L ]
- Il faut donc prévoir l'utilisation des
primitives PREMIER, SAUFPREMIER,
- PHRASE, CARDINAL
On définira tout d'abord:
1) Les procédures de déplacement:
- pour L
- av :longueur
- fin
-
- pour moins
- tg :alpha
- fin
-
- pour plus
- td :alpha
- fin
-
- 2) Une procédure pour faire passer la liste
des mouvements d'une génération à la
- suivante:
-
- POUR transforme_liste :liste1 :liste2
:signe :niveau
-
- /*
- liste1: configuration actuelle.
- liste2: axiome de
reproduction.
- signe:
représente ici L.
- niveau:
nombre de configurations souhaitées.
- */
-
- TESTE :niveau = 0
- SIVRAI RENDS :liste1
- SIFAUX [
-
DONNE "l1 :liste1 DONNE "résu []
-
DONNE "c1 CARD :liste1 DONNE "c2 CARD :liste2
-
REPETE :c1 [
-
DONNE "s PREM :l1
-
TESTE :s = :signe
-
SIVRAI [
-
DONNE "l2 :liste2
-
DONNE "résu PH :résu [/]
-
/* On divise par 2 les déplacements dans la prochaine configuration. */
-
REPETE :c2 [ DONNE "résu PH :résu PREM :l2 DONNE "l2 SP :l2 ]
-
DONNE "résu PH :résu [x]
- /* On multiplie par 2 les
déplacements pour revenir à la configuration actuelle. */
-
]
-
SIFAUX DONNE "résu PH :résu PREM :l1
-
DONNE "l1 SP :l1
-
]
-
RENDS transforme_liste :résu :liste2 :signe :niveau -1
-
]
- FIN
-
- 3) Les variables:
-
- DONNE "alpha 90 /* PI/2 radians.
*/
- DONNE "longueur 7 /*module de
déplacement. */
4) La configuration initiale et l'axiome de
reproduction:
-
- DONNE "config [ L - L ] donne
"axiome [ L - L ]
-
- 5) On fixe la transformation de la
liste des mouvements après la deuxième génération:
-
-
- DONNE "config
transforme_liste :config :axiome "L 2 /* 2 générations. */
-
- 6) On peut à présent faire
évoluer la tortue:
-
- répète card :config [
-
donne "consigne PREM :config
-
donne "config SP :config
-
si :consigne = "L L
-
si :consigne = "- moins
-
si :consigne = "+ plus
-
si :consigne = "/ DONNE "longueur ENTIER (:longueur / 2 )
-
si :consigne = "x DONNE "longueur :longueur * 2
-
]
-
- Certains calculs itératifs peuvent être très
longs, car la configuration des mouvements s'allonge à chaque
génération. L'exemple illustré ici n'est esthétiquement pas très
probant (la tortue trace un carré autant de fois que de générations
(=2)), mais la plupart des ordinateurs construiront cette liste assez
rapidement. C'est son principal avantage.
- pour L
- av :longueur
- fin
-
- pour moins
- tg :alpha
- fin
-
- pour plus
- td :alpha
- fin
-
- POUR transforme_liste :liste1
:liste2 :signe :niveau
- TESTE :niveau = 0
-
SIVRAI RENDS :liste1
-
SIFAUX [
-
DONNE "l1 :liste1 DONNE "résu []
-
DONNE "c1 CARD :liste1 DONNE "c2 CARD :liste2
-
REPETE :c1 [
-
DONNE "s PREM :l1
-
TESTE :s = :signe
-
SIVRAI [
-
DONNE "l2 :liste2
-
DONNE "résu PH :résu [/]
-
REPETE :c2 [
-
DONNE "résu PH :résu PREM :l2 DONNE "l2 SP :l2
-
]
-
DONNE "résu PH :résu [x]
-
]
-
SIFAUX DONNE "résu PH :résu PREM :l1
-
DONNE "l1 SP :l1
-
]
-
RENDS transforme_liste :résu :liste2 :signe :niveau -1
-
]
- FIN
-
- EFF ACCELERE DEROULE
- DONNE "alpha 90 /* PI/2 */
- DONNE "longueur 7
-
- DONNE "config [ L - L ] donne
"axiome [ L - L ]
- DONNE "config transforme_liste
:config :axiome "L 2 /* 2 générations */
-
- répète card :config [
-
donne "consigne PREM :config
-
donne "config SP :config
-
si :consigne = "L L
-
si :consigne = "- moins
-
si :consigne = "+ plus
-
si :consigne = "/ DONNE "longueur ENTIER (:longueur / 2 )
-
si :consigne = "x DONNE "longueur :longueur * 2
-
]
-
- Pour télécharger cet exemple, cliquer ici
.

- Remarque: en remplaçant la
ligne de l'axiome:
-
- DONNE "config [ L - L ] donne
"axiome [ L - L ]
-
- par:
-
- DONNE "config [ L - L ] donne
"axiome [ L - L + ]
-
- on obtient une courbe C
nettement moins monotone à observer.

Haut de page
>>
Retourner à la page
d'accueil >>
Rückkehr >>
-
-