« VISI201 CMI : visite de laboratoire » : différence entre les versions

De Wiki du LAMA (UMR 5127)
Aller à la navigation Aller à la recherche
Aucun résumé des modifications
Aucun résumé des modifications
Ligne 2 : Ligne 2 :
[[VISI201 Analyse syntaxique (Tristan Porteries, 2018)]]
[[VISI201 Analyse syntaxique (Tristan Porteries, 2018)]]


* Cours du semestre 2 du parcours CMI Informatique (licence INFO).
Un algorithme d'analyse syntaxique est un algorithme permettant de reconnaître l'existence d'un mot selon un langage, en cas général il est appliqué pour les langages informatiques et valide ou non un code source pour la syntaxe d'un langage informatique dans tous les compilateurs et interpréteurs. Mais la plupart des analyseurs syntaxiques ne se contentent pas seulement de valider l'entrée, ils extraient aussi la construction de cette entrée sous la forme d'un arbre abstrait de syntaxe détenant le sens de la chaîne d'entrée.


* Responsable pour 2017--2018: Jacques-Olivier Lachaud
== Les grammaires ==
* Responsable pour 2016--2017: Jacques-Olivier Lachaud


= Contenu (2017-2018) =
=== Les symboles de grammaire ===


Une partie de ce module consiste à assister à des séminaires dédiés aux étudiants CMI Informatique et Mathématique (1 fois par mois, les jeudi après-midi). [[http://www.lama.univ-savoie.fr/index.php?use=seminaires&&lang=fr&equipe=cmi&annee=1&lang=fr Planning des séminaires CMI]]
Toutes les grammaires sont composées de symboles regroupés sous deux catégories, les terminaux et le non-terminaux.


Ces séminaires "grand public" portent sur des sujets variées en informatique et mathématiques.
Les terminaux sont les symboles les plus petits ne pouvant être subdivisé, ils forment la chaîne d'entrée.


Les étudiants choisissent ensuite d'approfondir un sujet, dans la liste proposée ci-dessous, ou un sujet motivé de leur choix (en accord avec le responsable du module). Ce travail personnel tuteuré donne lieu à la rédaction d'une synthèse sur le sujet sous forme d'une page wiki/web, ainsi que d'un mini-exposé.
Les non-terminaux sont des symboles pouvant être subdivisé, il servent à regrouper d'autre symboles. Il sont toujours associés à des productions décrivant les subdivisions possible.


= Sujets proposés (2017-2018) =


* Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"
Par exemple une grammaire pourrait définir le non-terminal <math>float</math> qui englobe toutes les expressions de littéraux de flottants, ce non-terminal se subdiviserait selon <math>float \rightarrow nombre\ .\ nombre</math>, ainsi toutes les chaînes d'entrées composées d'un nombre puis un point et un nombre pouront être englobées par le non-terminal <math>float</math>.
* Initiation à la démonstration sur ordinateur et certification de logiciel
* Fouille de données textuelles à partir des "Exercices de style" de R. Queneau
* Transformées en distance, diagramme de Voronoi et applications en geometry processing
* Pavages de Penrose


<ul>
<li>4.2</li>
<li><math>nombre\ .\ nombre</math></li>
<li><math>float</math></li>
</ul>


== [[Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"]] ==
=== Les productions de grammaires ===


* Tuteur: Jacques-Olivier Lachaud
Les productions décrivent les subdivisions de non-terminaux, dans le cas d'une grammaire non-contextuelle toutes les productions sont de la forme :
* Résumé: La segmentation d'image vise à identifier les régions d'intérêt dans une image. Typiquement, une région d'intérêt est une zone de l'image plutôt homogène (les pixels ont des valeurs proches) et le contour entre deux régions d'intérêt est tracé là où les valeurs subissent de fortes variations. La méthode de segmentation proposée ici suit ce principe en enchaînant deux calculs: (1) un premier traitement calcule une image "gradient" et fabrique une image dont les valeurs élevées correspondent à des zones de fortes variations, (2) le deuxième algorithme voit cette image comme un relief 3D et identifie ses bassins hydrographiques. Cette identification des lignes de partage des eaux permet de découper l'image en ses zones d'intérêt.
* Objectifs:
*# comprendre ce qu'est une image niveaux de gris ou couleur, ce qu'est le gradient d'une image et ce qu'on appelle segmentation d'image.
*# décrire un algorithme de calcul du gradient d'une image, e.g. le filtre de Sobel, voire les convolutions par dérivées de Gaussienne.
*# décrire le principe de ligne de partage des eaux ("watershed" en anglais), ses différentes définitions équivalentes, et les différents types d'algorithmes pour la calculer.
*# Coder un programme de segmentation d'image, qui prend une image (niveaux de gris) en entrée, calcule son gradient, et extrait les bassins de sa ligne de partage des eaux.
* Liens pour démarrer
** [[https://en.wikipedia.org/wiki/Watershed_(image_processing) Watershed Wikipedia]]
** Luc Vincent and Pierre Soille. Watersheds in digital spaces: an efficient algorithm based on immersion simulations. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, Num. 6 (1991), pages 583–598 [[https://pdfs.semanticscholar.org/a381/9dda9a5f00dbb8cd3413ca7422e37a0d5794.pdf PDF]]


== [[Initiation à la démonstration sur ordinateur et certification de logiciel]] ==
<math>A \rightarrow \gamma </math>


* Tuteur: Tom Hirschowitz
<ul>
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
<li><math>A</math> : un non-terminal.</li>
* Objectifs:
<li><math>\gamma</math> : une composition de terminaux et non-terminaux.</li>
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
</ul>
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]


== [[Fouille de données textuelles à partir des "Exercices de style" de R. Queneau]] ==
Un non-terminal peut être dérivé par une des ses productions associées, il est alors réécrit par la partie droite d'une production. Cette opération mène à une proto-phrase, cette proto-phrase est une phrase si elle est constituée seulement de terminaux.
De même il est possible de réduire une proto-phrase en un non-terminal par une des productions ayant en partie droite la proto-phrase.


* Tuteur: Laurent Vuillon
=== La hiérachie de Chomsky ===
* Résumé: L'idée de ce projet est de se familiariser avec les techniques de fouille de données textuelles à partir des "Exercices de style" de R. Queneau (https://fr.wikipedia.org/wiki/Exercices_de_style). On cherchera à comprendre la structure du vocabulaire du corpus de textes, à utiliser les techniques de TF/IDF pour extraire les mots significatifs du corpus puis à tester les techniques de LDA (Allocation de Dirichlet latente) pour extraire automatiquement les thématiques du corpus afin de construire des regroupements par thème. On pourra également proposer des visualisations des résultats afin de rendre accessible visuellement l'analyse de données produite sur le corpus de documents.
* Objectifs: Introduction à la fouille de données au travers d'un cas pratique
* Pour aller plus loin
** http://blogperso.univ-rennes1.fr/stephane.tuffery/
** http://www.editionstechnip.com/en/catalogue-detail/1005/data-mining-et-statistique-decisionnelle.html
* Liens pour démarrer
** https://fr.wikipedia.org/wiki/Exploration_de_donn%C3%A9es
** https://fr.wikipedia.org/wiki/TF-IDF
** "Recherche d'information : applications, modèles et algorithmes; Data mining, décisionnel et big data" de Amini et Gaussier aux éditions Eyrolles.


La hiérachie de Chomsky définit quatre classes de grammaires, chacune pouvant décrire toutes les règles des grammaires de hiérarchie inférieur, les grammaires générales couvrent toutes les grammaires possibles.


== [[Transformées en distance, diagramme de Voronoi et applications en geometry processing]] ==
[[Fichier:Chomsky.png|300px]]


* Tuteur: Jacques-Olivier Lachaud
Le niveau le plus faible est attribué aux grammaires régulières.
* Résumé: Les nuages de points constituent une source de données géométriques importantes (cf LIDAR scanner, 3D scanner) et qui permet de construire des modèles géométriques 3D d'objets réels. La difficulté est de transformer ces nuages de points en des surfaces (souvent des surfaces triangulées, c'est-à-dire des triangles collés entre eux). Un outil essentiel dans ce processus est la transformée en distance, le diagramme de Voronoi (et son dual la triangulation de Delaunay). A partir de ces outils, des algorithmes existent pour reconstruire les surfaces, estimer la géométrie du nuage de point (sa normale par exemple), etc.
* Objectifs:
*# Comprendre ce qu'est une distance, une transformée en distance, et un diagramme de Voronoi. Comprendre ce qu'est la stabilité d'une fonction.
*# Identifier les propriétés des diagrammes de Voronoi, de leur dual la triangulation de Delaunay, et comprendre leurs variantes comme les diagrammes de puissance
*# Identifier le lien avec l'axe médian et les squelettes
*# Décrire les principaux algorithmes de calcul des transformées en distance et du diagramme de Voronoi, pour des nuages de point quelconques ou pour des nuages de points à coordonnées entières.
*# Présenter un algorithme de reconstruction de surface utilisant le diagramme de Voronoi
*# Coder un algorithme de calcul du diagramme de Voronoi et, si le temps le permet, un algorithme de reconstruction de surface.


* Liens pour démarrer
<ul>
** [[https://en.wikipedia.org/wiki/Voronoi_diagram Diagramme de Voronoi Wikipedia]]
<li>Les grammaires régulières sont d'une forme linéaire gauche ou droite, chaque non-terminal peut être associé à une composition de terminaux et un non-terminal en préfixe ou suffixe seulement.
** [[https://en.wikipedia.org/wiki/Distance_transform Transformée en distance Wikipedia]]
<math>N \rightarrow A\gamma</math> <math>N \rightarrow \gamma A</math>
** [[https://en.wikipedia.org/wiki/Topological_skeleton Squelette Wikipedia]]
</li>
** [[http://dgtal.org/doc/nightly/moduleVolumetric.html Transformées discrètes en distance DGtal]]
<li>Les grammaires algébrique (ou non-contextuelles) offrent une plus grande liberté en autorisant d'associer à un non-terminal n'importe quelle combinaison de terminaux et non-terminaux.
<math>N \rightarrow \gamma</math>
</li>
<li>Les grammaires contextuelles sont semblables aux grammaires algébrique mise à part l'ajout d'un contexte autour des productions en partie gauche et partie droite.
<math>\alpha N\beta \rightarrow \alpha \gamma \beta</math>
</li>
<li>Les grammaires régulières rendent possible l'association de n'importe quelle composition de non-terminaux et terminaux vers une autre composition.
<math>\gamma \rightarrow \phi</math>
</li>
</ul>


== [[Pavages de Penrose]] ==
=== Les grammaire non-contextuelles ===
* Tuteur : Pierre Hyvernat
* Résumé : le "cerf-volant" et la "fléchette" de Penrose sont deux tuiles qui permettent de recouvrir le plan, mais uniquement de manière non-périodique. Autrement dit, les pavages correspondants ne sont pas obtenus en répétant un même motif de manière régulière. A cause de ceci, il n'est pas évident de générer un tel pavage.


[[Fichier:P2.png]]
Les grammaires non-contextuelles sont définits de la forme <math>G = (V, A, S, P)</math>.


* Objectifs
<ul>
*# comprendre les notion de pavage périodique, non périodique et apériodique,
<li><math>V</math> : l'ensemble des non-terminaux de la grammaires.</li>
*# comprendre la méthode "inflation / déflation" pour générer des pavages de Penrose des différents types,
<li><math>A</math> : l'ensemble des terminaux.</li>
*# comprendre le lien entre les 2 (ou 3) types de pavage de Penrose
<li><math>S</math> : le non-terminal axiome.</li>
*# écrire un programme permettant de générer de tels pavages : avec la méthode "inflation / déflation" et avec la méthode "grille de de Bruijn"
<li><math>P</math> : l'ensemble des productions associant un non-terminal à une composition de non-terminaux et terminaux : <math> N \rightarrow \alpha </math>.</li>
*# utiliser ces méthodes pour générer d'autres types de pavages apériodique.
</ul>


* Liens pour démarrer
Dans un contexte plus technique il suffit de préciser l'axiome et les productions car ces dernières listent tout les non-terminaux et terminaux existant.
** [[https://fr.wikipedia.org/wiki/Pavage_de_Penrose pavage de Penrose (wikipedia]]
L'axiome joue un rôle important dans la validation d'un mot par une grammaire, si des dérivations successives partant de l'axiome mènent à une phrase correspondant au mot d'entrée alors l'entrée est validé. De même si la phrase correspondante au mot d'entrée et réduite jusqu'à obtenir l'axiome.
** [[https://www.maa.org/sites/default/files/pdf/pubs/focus/Gardner_PenroseTilings1-1977.pdf Penrose Tiling (Marting Gardner, en anglais)]]


Plus formellement, soit <math>\omega</math> le mot d'entrée : <math>S \xrightarrow{*} \omega</math>.


== [[Algorithmes d'analyse syntaxique]] ==
== Les analyseurs lexicaux ==


* Tuteur : Pierre Hyvernat
L'analyse lexicale couvre toutes les règles de la grammaire régulière, elle est utilisée pour faciliter le travail de l'analyseur syntaxique par la reconnaissance de certain groupe de lexème (les noms de variables, les nombres entiers, les nombres flottants) en unité lexicale. Ces unités lexicales seront utilisées comme terminaux par l'analyseur syntaxique et formeront donc la chaine d'entrée.


* Résumé : le code source d'un programme, d'un fichier de configuration d'un serveur de base de données ou le code d'une page web sont des données ''textuelles'' et ''structurées''. Il est possible de définir exactement quelles données sont correctes, et quelle est leur signification. (Cela est beaucoup plus difficile pour des textes en langue naturelle par exemple.) En ce sens, il est possible de lire, d'interpréter ces données à l'aide d'un programme. On parle ''d'analyseur syntaxique'' ou de ''parseur''. Il existe de nombreux outils pour faire ça automatiquement, mais il est parfois important (et toujours intéressant) de comprendre les mécanismes correspondant. C'est ce que ce stage propose de faire.
La plupart des règles d'une grammaire régulière sont décrites avec des expressions rationnelles se basant sur trois opérations fondamentales : la concaténation, l'union et l'étoile de Kleene. Chacune de ces opérations produit un ensemble de mot pouvant être reconnu par le motif.


* Objectifs :
<ul>
*# étudier la formalisation du problème à travers la notion de ''langage'' et les premiers étages de la hiérachie de Chomsky (langages réguliers et grammaires hors contexte).
<li>La concaténation permet de créer un singleton avec la concaténation de deux mots, autrement dit reconnaître que la concaténation de deux mots. <math>ab \rightarrow \{ab\}</math></li>
*# comprendre le lien entre les langages et les automates (automates finis / automates à pile)
<li>L'union crée un ensemble constituée des deux mots, elle reconnaît l'un de deux mots seulement. <math>a|b \rightarrow \{a, b\}</math> </li>
*# implémenter un parseur "from scratch" et le tester sur des petits exemples simples, "à la main", soit en calculant "à la volée" la sémantique d'un langage, soit en produisant des "arbres de syntaxe abstraits", qui pourront être analysés par la suite,
<li>L'étoile de Kleene permet de créer un ensemble contenant toutes les combinaisons d'un ensemble ainsi que le vide. <math>(a|b)^* \rightarrow \{\epsilon, a, b, ab, ba, aab, ...\}</math> </li>
*# comprendre les restrictions souvent imposées sur les grammaires afin d'améliorer l'efficacité du parseur (''LL*(k)'', ''LR'', etc.)
</ul>
*# à partir de là, de nombreuses pistes sont ouvertes :
*#* essayer d'écrire un petit outils qui puisse lire une grammaire, et générer un parseur pour cette grammaire,
*#* comparer l'approche "automate" avec l'approche "combinateurs" et "parseur récursifs"
*#* améliorer l'efficacité des parseurs produits
*#* ajouter des fonctionnalités,
*#* ...


* Liens pour démarrer :
L'analyseur lexicale sépare en premier la chaine selon les blancs et d'autres séparateurs supplémentaires tels que les signes de ponctuations et les opérateurs, ensuite chaque portion de la chaine d'entrée est analysée selon un ensemble de règles rationnelles pour déterminer son unité lexicale.
** [[https://en.wikipedia.org/wiki/Parsing page wikipedia "parsing"]]
** [[https://en.wikipedia.org/wiki/Recursive_descent_parser page wikipedia "recursive descent parser"]]
** Le livre référence sur le parsing est probablement "Compilers: Principles, Techniques, and Tools" de Aho, Sethi et Ullman (le "dragon book")
** [[https://web.stanford.edu/class/archive/cs/cs143/cs143.1128/ exemples de notes cours de compilation]]


= Sujets réalisés (2016-2017) =
Par exemple la chaine d'entrée "float i = 4.2 + 5;" sera découpée en {"float", "i", "=", "4.2", "+", "5", ";"}, ensuite selon les règles suivantes (utilisant le format de regex POSIX) :


* [[Algorithme de rendu de scène 3D par Z-buffer]]
<ul>
* [[Traitement d'image]]
<li> type <math> \rightarrow </math> (int|float|bool) </li>
* [[Nim et la théorie des jeux impartiaux]]
<li> id <math> \rightarrow </math> ([A-z]([A-z]|[0-9])*)[^(int|float|bool)] </li>
* [[Calculabilité et modèles de calcul]]
<li> op_assign <math> \rightarrow </math> = </li>
* [[Génération et résolution de labyrinthes]]
<li> float <math> \rightarrow </math> [0-9]*\.[0-9]*f? </li>
<li> int <math> \rightarrow </math> [0-9]* </li>
<li> end <math> \rightarrow </math> ; </li>
<li> op <math> \rightarrow </math> \+|\-|/|\* </li>
</ul>


On obtiendra donc un ensemble des unités lexicales reconnues : {type, id, op_assign, float, op, int, end}.


= Sujets proposés (2016-2017) =
=== Les automates finis ===


== [[Algorithme de rendu de scène 3D par Z-buffer]] ==
Un analyseur lexicale peut être construit avec un automate finis car d'après le théorème de Kleene toutes les grammaires régulière sont reconnu par un automate finis.


* Tuteur: Jacques-Olivier Lachaud
Théorème de Kleene : l’ensemble des langages rationnels sur un alphabet A est exactement l’ensemble des langages sur A reconnaissables par automate fini.
* Résumé: Le Z-buffer est un algorithme classique de rendu de scène 3D. C'est celui (avec quelques variantes) qui est implémenté dans nos cartes graphiques 3D et qui permet de visualiser des scènes extrêmement complexes en temps réel (typiquement 24 image/s).
* Objectifs:
*# décrire le principe de la projection 3D vers 2D
*# décrire la rastérisation des triangles sur une image en pixel
*# expliquer le principe du Z-buffer qui permet de gérer le fait que certains objets sont cachés par d'autres
*# expliquer comment les couleurs sont calculées par pixel
*# indiquer les qualités et limitations de l'algorithme
* Pour aller plus loin
*# mettre du code démo (WebGL) avec quelques explications sur le pipeline graphique OpenGL
*# expliquer comment on peut utiliser cet algorithme pour calculer des ombres (shadow map)
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Z-buffer Wikipedia]]
** [[https://www.scratchapixel.com/lessons/3d-basic-rendering/rasterization-practical-implementation/overview-rasterization-algorithm Scratch a pixel]]


== [[Traitement d'image]] ==
L'automate suivant reconnaît le motif <math>a^*b^*</math>


* Tuteur: Jacques-Olivier Lachaud
[[Fichier:Automate-ab.png|400px]]
* Résumé: Le traitement d'image rassemble tous les algorithmes utilisés pour transformer les images, les améliorer, éliminer certaines perturbations, augmenter ou diminuer le contraste, changer les couleurs vers d'autres couleurs, éliminer le flou ou les yeux rouges, faire du cartooning pour un rendu moins photo-réaliste, etc.
* Objectifs:
*# identifier les grandes familles de traitement: restauration, égalisation, élimination du flou de déplacement, segmentation, etc
*# identifier les grandes familles de techniques: filtrage spatial, filtrage fréquentiel, optimisation, etc
*# comprendre les points communs et différences entre le traitement des images noir et blanc et le traitement des images couleurs.
*# choisir un ou deux algorithmes de traitement et les expliquer en détails
* Pour aller plus loin
*# Coder un algorithme de traitement d'image simple (e.g, un filtrage médian, ou un algo qui transporte les couleurs d'une photo vers une autre photo)


* Liens pour démarrer
Malheureusement la limite des analyseurs lexicaux et très vite atteint notamment avec le motifs de la forme <math>a^nb^n</math>. Dans ce cas il faut trouver un moyen de compter le nombre de a consommé pour essayer de consommer le même nombre de b, or les automates finis ne dispose pas de mémoire supplémentaire où placer ce compteur. Ce type de motif est fortement utilisé dans les languages de programmations pour vérifier le bon nombre de parenthèses, accolades etc…
** [[https://fr.wikipedia.org/wiki/Traitement_d%27images Wikipedia]]
** [[http://www.ipol.im/ Image Processing on line]] (permet de tester en ligne des algorithmes sur vos images)


== Les analyseurs syntaxiques ==


== [[Nim et la théorie des jeux impartiaux]] ==
L'analyse syntaxique suit l'analyse lexical en se basant sur les unités lexicales définit par ce dernier nommé lexèmes. Ces unités lexicales sont utilisées en tant que terminaux par l'analyseur syntaxique dans une liste de lexèmes.


* Tuteur: Pierre Hyvernat
Les algorithmes d'analyseur syntaxiques se basent tous sur le même type d'automates : les automates finis à pile. Les deux majeurs techniques connus sont l'analyse descendante et l'analyse ascendante. La première consiste à dériver l'axiome de la grammaire jusqu'à obtenir le mot d'entrée, la seconde technique consiste à réduire le mot d'entrée jusqu'à obtenir l'axiome.
Ces deux techniques sont considéré comme opposé par leur façon de traiter les proto-phrases, l'analyseur descendant va toujours dériver et l'analyseur ascendant toujours réduire. Malgré cette symétrie, ces deux types d'analyseur n'utilisent pas les mêmes ensembles de règles.


* Étudiant : Luca Chapelle
=== Les automates finis à pile ===


* Le jeu de Nim (aussi appelé jeu des allumettes) est l'un des premiers jeux ayant été analysé mathématiquement (par Charles Bouton en 1901). Les stratégies gagnantes peuvent être calculées en utilisant le développement en base 2 des nombres, et l'opération d'"addition de Nim" (XOR). La théorie de ce type de jeux (jeux "impartiaux") est assez simple, mais de nombreuses instances de jeux sont encore non résolues.
Les automates finis à pile forment une extension des automates finis par l'adjonction d'une mémoire organisée en pile.
* Objectifs:
*# comprendre la théorie du jeu de Nim (et la programmer)
*# comprendre le théorème de Sprague Grundy qui montre que tout jeu impartial est équivalent à un jeu de nim
*# regarder quelques autres exemples de tels jeux : jeu de Nim déguisés, ou jeux véritablement différents
*# programmer une version naịve de recherche de stratégie basée sur le théorème de Sprague-Grundy pour quelques jeux


* Liens pour commencer
Ils permettent de couvrir les limitations des analyseurs lexicaux en reconnaissant les motifs de la forme <math>a^nb^n</math>.
** [https://fr.wikipedia.org/wiki/Jeux_de_Nim jeu de Nim]
** [https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Sprague-Grundy théorème de Sprague Grundy]
** [https://fr.wikipedia.org/wiki/Jeu_de_Grundy jeu de Grundy]


== La suite de Conway et la classification périodique des "éléments" ==
[[Fichier:Automate-pile-ab.jpg|400px]]


* Tuteur : Pierre Hyvernat
Ce type d'automate est utilisé pour les analyseurs syntaxique tant descendant que ascendant.
* La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
** "1" : un "1" -> 11
** "11" : deux "1" -> 21
** "21" : un "2", un "1" -> 1211
** "1211" : un "1", un "2", deux "1" -> 111221
** etc.
Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".
* Objectifs :
*# comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
*# programmer la suite de Conway pour retrouver la classification des "atomes"
*# écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
*# écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway


* Liens pour commencer
=== Les analyseurs descendants ===
** [[https://fr.wikipedia.org/wiki/Suite_de_Conway suite de Conway]]
** [[https://fr.wikipedia.org/wiki/Suite_de_Robinson suite de Robinson]]


== Initiation à la démonstration sur ordinateur et certification de logiciel ==
Le principe de l'analyse descendante est assez simple à mettre en œuvre. L'analyseur initialise une proto-phrase contenant l'axiome de la grammaire, à chaque étape l'analyseur va lire le symbole à gauche de la proto-phrase. Si celui ci est un terminal alors on le compare avec le début de la chaîne d'entrée, si il correspond on consomme le début de la chaine d'entrée ainsi que le terminal au début de la proto-phrase, au contraire on signale une erreur. Si le début de la proto-phrase est un non-terminal alors on le remplace par la partie droite de l'une de ses productions.


* Tuteur: Tom Hirschowitz
Le pseudo code correspondant est le suivant :
* Résumé: [[https://coq.inria.fr Coq]] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
* Objectifs:
*# prendre en main le logiciel [[https://coq.inria.fr Coq]] de démonstration sur ordinateur,
*# programmer certaines démonstrations basiques en Coq,
*# suivre le début du cours [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]],
* Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
* Liens pour démarrer
** [[https://www.cis.upenn.edu/~bcpierce/sf Software Foundations]]
** [[https://coq.inria.fr Coq]]


== [[Calculabilité et modèles de calcul]] ==
<pre>
initialiser une pile contenant S
Tant que la pile et la chaine d'entrée sont non-vide
soit C le premier lexème de la chaine d'entrée
soit T le sommet de la pile
Si T est non-terminal
choisir une production P de T
dépiler le sommet de la pile
empiler la partie droite de P
Sinon si T équivaut C
dépiler le sommet de la pile
consommer le lexème C
Sinon
erreur
</pre>


* Tuteur: Rodolphe Lepigre
Si nous utilisons la grammaire contenant les deux productions <math>S \rightarrow aSb</math> et <math>S \rightarrow \epsilon </math> (<math>\epsilon</math> pour ne rien consommer ou ajouter), <math>S</math> est l'axiome de la grammaire implicitement.
* Résumé: Une fonction f sur l'ensemble des entiers naturels est dite calculable s'il existe une procedure effective (ou un algorithme) qui permet, étant donné un entier n, de calculer f(n) en temps fini. Il existe divers modèles de calcul qui permettent de représenter toutes les fonctions calculables : machines de Turing, λ-calcul, automates cellulaires, ...
La trace de l'algorithme descendant du mot d'entrée "aabb" est alors :
* Objectifs:
*# comprendre la notion de fonction calculable,
*# comparer l'ensemble des fonctions à l'ensemble des fonctions calculables,
*# regarder et comparer quelque modèles de calcul,
*# programmer un modèle de calcul et comprendre les limitations pratiques.


* Liens pour commencer:
{| class="wikitable"
** https://fr.wikipedia.org/wiki/Calculabilité
|-
** https://fr.wikipedia.org/wiki/Machine_de_Turing
! Pile
** https://fr.wikipedia.org/wiki/Lambda-calcul
! Entrée
** https://fr.wikipedia.org/wiki/Jeu_de_la_vie
! Opération
|-
| S
| aabb
|
|-
| aSb
| aabb
| dériver par <math>S \rightarrow aSb</math>
|-
| Sb
| abb
| consommer a
|-
| aSbb
| abb
| dériver par <math>S \rightarrow aSb</math>
|-
| Sbb
| bb
| consommer a
|-
| bb
| bb
| dériver par <math>S \rightarrow \epsilon</math>
|-
| b
| b
| consommer b
|-
|
|
| consommer b et valider le mot
|-
|}


== [[Génération et résolution de labyrinthes]] ==
Malgré la simplicité de cette technique, deux problèmes majeurs sont présents et mènent tous deux à utiliser un ensemble restreint de règles de grammaire par rapport aux grammaires algébriques.


* Tuteur: <strike>Jacques-Olivier Lachaud</strike> Xavier Provençal
Le premier problème concerne la récursivité gauche. Si l'algorithme ne sait pas exactement comment choisir les productions à appliquer et que la grammaire possède des productions de la forme <math>N \rightarrow N\alpha</math> ou autrement dit des productions associant le même non-terminal à gauche et au début de le partie droite de la production, alors la dérivation du sommet d'une proto-phrase contenant <math>N</math> mènera toujours à avoir le même non-terminal au sommet et l'algorithme ne pourra jamais arrêter de dériver.
* Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
* Objectifs:
*# Comprendre comment représenter avec une structure de données un labyrinthe
*# Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
*# Comprendre l'algorithme d'arbre couvrant minimum
*# Comprendre le principe du parcours en profondeur et de la récursivité
* Pour aller plus loin
*# coder la génération d'un labyrinthe et sa visualisation
* Liens pour démarrer
** [[https://fr.wikipedia.org/wiki/Mod%C3%A9lisation_math%C3%A9matique_d%27un_labyrinthe Wikipedia]]
** [[https://en.wikipedia.org/wiki/Maze_generation_algorithm Version anglaise plus complète]]


== Pavages par polyomino ==
<ul>
<li> <math> N </math> </li>
<li> <math> N\alpha </math> </li>
<li> <math> N\alpha\alpha </math> </li>
<li> <math> N\alpha\alpha\alpha </math> </li>
<li> <math> N\alpha\alpha\alpha\alpha </math> </li>
<li> … </li>
</ul>


* Tuteur: Xavier Provençal
Pour contrer ce problème il existe une méthode permettant de transformer la récursivité gauche en une récursivité droite d'un non-terminal secondaire :
* Résumé : On s'intéresse aux pavages du plan par des tuiles formées de petits carrés collés les uns aux autres, appelé "polyominos". Étant donné une tuile, peut-on paver le plan ? Si oui, avec quelles opérations (translation et/ou rotations et/ou réflexions) Une fois un pavage réalisé, on observe ses propriétés. Quelles symétries ? Le pavage est-il identique du point de vue de chacune des tuiles ? Si ce n'est pas le cas, en combien de classes peut-on diviser ces tuiles ?

On s'intéressera aussi à des propriétés connexes. Au lieu de paver tout le plan, on peut essayer de paver une région finie donnée. Plus localement, peut-on encercler complètement une tuile avec des copies d'elle-même, sans former de trous ? Si oui, peut-on faire de même avec la proto-tuile formée par la tuile de départ et toutes ses copies ? Si oui, combien de fois peut-on répéter l'opération ?
Soit <math>N \rightarrow N\alpha</math> <math>N \rightarrow \beta</math>
* Objectifs :

*# Comprendre les différentes classes de pavages (isohédral, k-isohédral, anisohédral).
<ul>
*# Pour chacun des sept types de pavages "isohédraux", comprendre le lien entre les symétries du pavages et la caractérisation des tuiles qui le réalisent.
<li> <math>N \rightarrow \beta N'</math> </li>
*# Pour un pavage k-isohédral, identifier les "classes d'équivalences" et le "domaine fondamental".
<li> <math>N' \rightarrow \alpha N'</math> </li>
* Pour aller plus loin :
<li> <math>N' \rightarrow \epsilon </math> </li>
*# Coder la génération de tuiles capables de paver le plan en fonction pour une classe de pavages donnée.
</ul>
*# Étudier et implémenter certains algorithmes pour le pavages d'un domaine fini.

* Liens pour démarrer
En effet, les règles initiales mènent intuitivement aux motifs de la forme <math>\beta \alpha \alpha \alpha ...\alpha</math>. Remplacer la récursivité gauche consisterait en réécrire les règles donnant les mêmes motifs, soit <math>\beta</math> en préfixe suivi d'une règle linéaire droite pour les <math>\alpha</math>.
** [[https://fr.wikipedia.org/wiki/Polyomino Polyomino]]

** [[https://en.wikipedia.org/wiki/Polyomino Polyomino (en)]]
Le second problème des analyseurs descendant et le déterminisme lors du choix des productions à dériver. L'algorithme doit dériver un non-terminal selon la production qui à le plus de chance de réussir l'analyse. Dans l'exemple de la trace de l'analyse du mot "aabb", il fallait lors de la troisième dérivation dériver selon <math>S \rightarrow \epsilon</math> seulement.
** [[https://fr.wikipedia.org/wiki/Pavage_par_des_polygones_r%C3%A9guliers Pavages]]
Dans le cas contraire non-déterministe, l'algorithme pourrait autoriser de revenir en arrière dans l'analyse lors d'erreur et d'appliquer les productions restantes jusqu'à ne plus avoir de production et donc signaler une véritable erreur.

==== Les analyseurs à symbole de prévision ====

Un analyseur à symbole de prévision, nommé LL(k) ou k est le nombre de symboles, lors d'une dérivation va lire k symboles au début de la chaine d'entrée pour déterminer la production à dériver contenant ces k symboles en préfixe. La plupart des analyseurs se contentent de 1 symbole de prévision.

En amont de l'analyse un algorithme est utilisé pour générer une table de la forme <math>PRODUCTION(N, c) \rightarrow P</math>.
<ul>
<li> <math>N</math> : Le non-terminal courant (au sommet de la proto-phrase). </li>
<li> <math>c</math> : Le lexème courant (au sommet de la chaine d'entrée) utilisé comme préfixe. </li>
<li> <math>P</math> : la production ayant pour préfixe <math>c</math> </li>
</ul>

Dans le cas de productions sans <math>\epsilon</math>, l'algorithme va pour chaque non-terminal lire toutes les productions associées. Pour chacune des productions déterminer les préfixes possibles, en parfois dérivant jusqu'à obtenir un terminal à gauche, puis associer cette production avec ses préfixes dans la table.

Dans l'exemple d'une grammaire reconnaissant les déclarations de variables avec initialisation optionnelle par les règles suivantes :

<ul>
<li> <math>decl \rightarrow type\,id\,decl'</math> </li>
<li> <math>decl' \rightarrow =\, expr\,;</math> </li>
<li> <math>decl' \rightarrow ; </math> </li>
</ul>

Cette grammaire reconnait les mots "int i = 0;" et "int i;" de la façon suivante :

<ul>
<li> Dérivation de l'axiome : <math>type\,id\,decl'</math></li>
<li> Reconnaissance de <math>type</math> et <math>id</math> par respectivement "int" et "i"</li>
<li> Dérivation de <math>decl'</math> par l'une de ses productions</li>
<li> Suite de l'analyse avec l'une des deux productions de <math>decl'</math> </li>
</ul>

Ici est mis en évidence le branchement lors de la dérivation de <math>decl'</math>, la table des productions par symbole de prévision est :

{| class="wikitable"
|-
! Non-terminal
! Préfixe
! Production
|-
| <math>decl</math>
| <math>type</math>
| <math>decl \rightarrow type\,id\,decl'</math>
|-
| <math>decl'</math>
| =
| <math>decl' \rightarrow =\,expr\,;</math>
|-
| <math>decl'</math>
| ;
| <math>decl' \rightarrow ;</math>
|-
|}

Lors de la dérivation de <math>decl'</math>, l'analyseur va interroger la table de production pour le lexème en sommet d'entrée, dans le cas des deux mots "int i = 0;" et "int i;" ce symbole sera respectivement "=" ou ";". Ces deux symboles donnent dans la table deux productions valide pour continuer l'analyse.

Dans le cas où le préfixe n'est pas associer à une production, l'analyseur peut signaler une erreur car cela signifie que n'importe quelle dérivation mènera à une erreur lors de la reconnaissance du premier symbole terminal.

En ce qui concerne les grammaires possédant des productions en <math>\epsilon</math>, ces productions sont valide pour n'importe quelle préfixe mais sont soumise à une condition supplémentaire sur les symboles rencontrés après l'usage des non-terminaux de ces productions.

Soit une production <math>N \rightarrow \epsilon</math>, nous regardons toutes les productions utilisant le non-terminal <math>N</math> de la forme <math>L \rightarrow N\gamma</math> et associant dans la table la production <math>N \rightarrow \epsilon</math> avec tous les préfixes de <math>\gamma</math>.

Dans le même exemple de grammaire reconnaissant les déclarations de variables, les règles peuvent s'écrire :

<ul>
<li> <math>decl \rightarrow type\,id\,decl'\,;</math> </li>
<li> <math>decl' \rightarrow =\,expr</math> </li>
<li> <math>decl' \rightarrow \epsilon </math> </li>
</ul>

Le non-terminal associé à la production <math>decl' \rightarrow \epsilon </math> et utilisé seulement dans <math>decl \rightarrow type\,id\,decl'\,;</math> et le symbole suivant <math>delc'</math> est ";". <math>decl' \rightarrow \epsilon </math> et donc associé à ";" dans la table comme pour la grammaire précédente sans productions utilisant <math>\epsilon</math>.

{| class="wikitable"
|-
! Non-terminal
! Préfixe
! Production
|-
| <math>decl</math>
| <math>type</math>
| <math>decl \rightarrow type\,id\,decl'\,;</math>
|-
| <math>decl'</math>
| =
| <math>decl' \rightarrow =\,expr</math>
|-
| <math>decl'</math>
| ;
| <math>decl' \rightarrow \epsilon</math>
|-
|}

=== Les analyseurs ascendants ===

Le principe de l'analyse ascendante est de réduire successivement une phrase correspondant à la chaine d'entrée jusqu'à obtenir l'axiome de la grammaire. Ce type d'analyseur nécessite la création en amont d'une table d'analyse difficilement concevable manuellement.

Cette table d'analyse se base sur deux opérations, réduire et décaler. Décaler consiste à déplacer un terminal en sommet de la chaine d'entrée dans la pile d'analyse, réduire consiste à remplacer le sommet de la pile d'analyse correspondant à la partie droite d'une production par le non-terminal associé à cette production.

Pour la grammaire suivante et le mot d'entrée "aabb" :

<ul>
<li><math> S \rightarrow aSb </math></li>
<li><math> S \rightarrow ab </math></li>
</ul>

La trace de l'analyse ascendante est :

{| class="wikitable"
|-
! Pile
! Entrée
! Opération
|-
|
| aabb
|
|-
| a
| abb
| décaler
|-
| aa
| bb
| décaler
|-
| aab
| b
| décaler
|-
| aS
| b
| réduire par <math> S \rightarrow ab </math>
|-
| aSb
|
| décaler
|-
| S
|
| réduire par <math> S \rightarrow aSb </math> et valider
|-
|}

Malheureusement il ne suffit pas de reconnaître la partie droite d'une production sur le sommet de la pile pour réduire par celle ci.
Le contre-exemple est le suivant :
Soit une grammaire linéaire droite de la forme <math>A \rightarrow aA</math>, <math>A \rightarrow a</math> et le mot "aa".
En premier "a" est décalé, puis réduit par la production <math>A \rightarrow a</math>, puis le second "a" est décalé pour obtenir sur la pile d'analyse "Aa". Aucune production n'a le motif "Aa" en partie droite pourtant le mot "aa" est bien valide intuitivement. Pour réussir cette analyse il aurait fallu décaler les deux "a" pour obtenir "aa", réduire le dernier en "aA" selon <math>A \rightarrow a</math> et enfin réduire en "A" selon <math>A \rightarrow aA</math>.

Les réductions valide sont nommées manche, ils dépendent de l'état de la pile.

==== Les tables d'analyse ====

La table d'analyse représente les différents états de l'automate à pile formant l'analyseur, ces états sont calculés en se basant sur la notion d'item de production.

Un item de production représente l'état actuel de validation d'une production, ou autrement dit, le nombre de symboles validés lors de l'analyse.

Pour une production de la forme <math>N \rightarrow \alpha \gamma \beta</math> il existe 4 items, en cas générale il existe n + 1 items pour une production de n symboles en partie droite. Ces items sont notés :

<ul>
<li><math>N \rightarrow \bullet \alpha \gamma \beta</math></li>
<li><math>N \rightarrow \alpha \bullet \gamma \beta</math></li>
<li><math>N \rightarrow \alpha \gamma \bullet \beta</math></li>
<li><math>N \rightarrow \alpha \gamma \beta \bullet</math></li>
</ul>

Par exemple l'item <math>N \rightarrow \alpha \bullet \gamma \beta</math> signifie que l'analyse à reconnu <math>\alpha</math> et espère reconnaître <math>\gamma \beta</math>. Le dernier item <math>N \rightarrow \alpha \gamma \beta \bullet</math> signifie que tous les symboles de la productions ont été reconnu et donc la production peut servir de réduction.

Tout d'abord pour pouvoir d'écrire des items de l'axiome de la grammaire, nous devons définir une grammaire augmenté similaire à la grammaire initiale mais avec l'adjonction d'un non-terminal <math>S'</math> et de la production <math>S' \rightarrow S</math>. Ainsi l'état initiale de l'analyse est décrit par <math>S' \rightarrow \bullet S</math>, aucun symbole n'est reconnu.

Deux fonctions vont être utilisées sur ces items, en particulier sur des ensembles d'items. La fonction <math>Fermeture(X)</math> et <math>Transition(X, c)</math>.

<math>Fermeture(X)</math> prend en argument un ensemble d'item.
Soit un item <math>N \rightarrow \gamma \bullet \alpha</math> de <math>X</math>, si <math>\alpha</math> est un terminal alors ajouter cet item dans le résultat, sinon si <math>\alpha</math> est un non-terminal alors concaténer au résultat <math>Fermeture(Y)</math> où <math>Y</math> et l'ensemble de toutes les items des productions de <math>\alpha</math> avec le point en première position : <math>\{\alpha \rightarrow \bullet \beta, \alpha \rightarrow \bullet \delta, ...\}</math>

<math>Transition(X, c)</math> prend en argument un ensemble d'item et un terminal, Soit <math>N \rightarrow \alpha \bullet c \beta</math> de <math>X</math>, concaténer au résultat <math>Fermeture(\{N \rightarrow \alpha c \bullet \beta\})</math>.

Ces deux fonctions vont permettre de déterminer les états de l'automates, chaque état et un ensemble d'items faisant partie de la collection canonique de l'analyseur. <math>Fermeture(S' \rightarrow \bullet S)</math> est l'état initiale <math>I_0</math> puis <math>Transition(X, c)</math> détermine tous les états atteignables par un décalage de c, et enfin un état où aucune transition n'est possible mais contenant un item de la forme <math>N \rightarrow \gamma \bullet</math> produira une réduction par <math>N</math>.

<ul>
<li><math> S \rightarrow aSb </math></li>
<li><math> S \rightarrow ab </math></li>
</ul>

La grammaire ci-dessus produits les états suivant :

<ul>
<li><math>Fermeture(\{S' \rightarrow \bullet S\}) = \{
S' \rightarrow \bullet S,
S \rightarrow \bullet aSb,
S \rightarrow \bullet ab
\} = I_0</math></li>
<li><math>Transition(I_0, S) = \{
S' \rightarrow S \bullet
\} = I_1</math></li>
<li><math>Transition(I_0, a) = \{
S \rightarrow a \bullet Sb,
S \rightarrow a \bullet b,
S \rightarrow \bullet aSb,
S \rightarrow \bullet ab
\} = I_2</math></li>
<li><math>Transition(I_2, S) = \{
S \rightarrow aS \bullet b
\} = I_3</math></li>
<li><math>Transition(I_2, a) = I_2</math></li>
<li><math>Transition(I_2, b) = \{
S \rightarrow ab \bullet
\} = I_4</math></li>
<li><math>Transition(I_3, b) = \{
S \rightarrow aSb \bullet
\} = I_5</math></li>
</ul>

L'automate résultant est le suivant :

[[Fichier:Automate-lr.png|400px]]

=== Les arbres abstraits de syntaxe ===

Les arbres abstraits de syntaxe contiennent le minimum de sens de la chaine d'entrée, soit dans la plupart des languages de programmation les opérateurs, les opérandes et les structures de donnée.

Dans l'exemple d'un bout de code HTML <nowiki>"<h1>Titre</h1>"</nowiki> nous voudrions obtenir un arbre nous indiquant seulement la présence de la balise <nowiki>"<h1>"</nowiki> contenant le mot "Titre" :

[[Fichier:AST-h1.png|200px]]

Pour obtenir cette arbre il faut transformer l'arbre de dérivation en sortie de l'analyseur syntaxique avec des attributs de productions.

==== Les arbres de dérivation ====

Les arbres de dérivation notent toutes les dérivations ou réductions de productions au cours de l'analyse. Lors de la dérivation d'une production <math>N \rightarrow \alpha \beta</math> nous produirons un sous arbre avec en racine le non-terminal <math>N</math> et en nœuds enfants les symboles <math>\alpha</math> et <math>\beta</math> :

[[Fichier:AST.png|200px]]

Malheureusement la majorité des grammaires utilisées par les analyseurs descendant produisent des arbres de dérivation éloigné des arbres abstraits de syntaxe, comme la grammaire suivante :

<ul>
<li><math> E \rightarrow id\ E'</math></li>
<li><math> E' \rightarrow op\ id\ E'</math></li>
<li><math> E' \rightarrow \epsilon </math></li>
</ul>

Cette grammaire optimisée pour l'analyse descendante par la suppression de l'ambiguité et l'utilisation de préfixes unique, produit pour le mot d'entrée "5 + 2 - 3" l'arbre de dérivation :

[[Fichier:AST-expr.png|400px]]

==== Les grammaires attribuées ====

Les transformations entre arbre de dérivation et arbre abstrait de syntaxe sont décrites par des règles attribués à chacune des productions. Ses règles permettent de lire ou écrire des attributs de symbole.
Pour éviter toute ambiguité entre les symboles dans les productions, les symboles de même nom sont renommés en <math>N_i</math>, <math> E' \rightarrow op\ id\ E'</math> devient <math> E_1' \rightarrow op\ id\ E_2'</math>.

Les règles se regroupent en deux catégories, les règles synthétisées et les règles héritées.

Les règles synthétisées modifient le non-terminal à gauche d'une production en fonction des attributs des symboles à droite de la production.
En gardant le même exemple de grammaire, la production <math>E' \rightarrow \epsilon </math> doit produire un noeud vide, elle est associée à <math>E'.noeud = noeud()</math>. De même la production <math> E_1' \rightarrow op\ id\ E_2'</math> définit le noeud <math>E_1'</math> avec l'operateur : <math>E'_1.noeud = noeud(op.val)</math>.

Les règles héritées modifient des symboles à droite de la production en fonction des autres symboles à droite, les nœuds voisins, ou le non-terminal à gauche de la production.
Ainsi la production <math> E_1' \rightarrow op\ id\ E_2'</math> doit basculer la valeur <math>id</math> dans le nœeud <math>E_2'</math>, elle est donc associée à la règle <math>E'_2.noeud.ajouter(noeud(id.val))</math>.

La totalité des règles est :

<ul>
<li> <math> E \rightarrow id\ E' \Longrightarrow E.noeud = E'.noeud </math> </li>
<li> <math> E'_1 \rightarrow op\ id\ E'_2 \Longrightarrow E'_1.noeud = noeud(op.val) E'_1.noeud.ajouter(E'_2.noeud)</math> </li>
<li> <math> E' \rightarrow \epsilon \Longrightarrow E'.noeud = noeud() </math> </li>
<li> <math> E \rightarrow id\ E' \Longrightarrow E'.noeud.ajouter(noeud(id.val)) </math> </li>
<li> <math> E'_1 \rightarrow op\ id\ E'_2 \Longrightarrow E'_2.noeud.ajouter(noeud(id.val)) </math> </li>
</ul>

Dans notre cas les attributs <math>N.noeud</math> contiennent les nœuds de l'arbre abstrait de syntaxe et donc <math>E.noeud</math> est l'arbre abstrait de syntaxe entier. Un problème se pose toujours lors de l'ordre d'application des règles. En effet la règle <math>E \rightarrow id\ E' \Longrightarrow E'.noeud.ajouter(noeud(id.val))</math> nécessite que <math>E'</math> contienne déjà un attribut <math>noeud</math> valide.
Pour résoudre ce problème, il est possible de préfixer l'ordre d'exécution des règles manuellement lors de leur conception ou déterminer par une analyse l'ordre d'exécution par la construction d'un arbre de dépendance entre les règles. Dans ce cas, les règles n'ayant aucune dépendance sont exécuté puis les autres.

== Le programme exemple ==

Pour mettre en application les algorithmes d'analyse syntaxique, un programme à été écrit avec le support de l'analyse descendante et ascendante simple.
Ce programme est disponible dans le dépôt : https://github.com/panzergame/analyseur_cmi

Un fois compilé, l'exécutable build/analyzer prend quatre arguments :

<ul>
<li>input_file : Fichier texte à analyser.</li>
<li>bnf_file : Fichier de description des productions.</li>
<li>regex_file : Fichier de description des règles lexicales et des séparateurs.</li>
<li>method : La méthode d'analyse, naive pour LL récursif, stack pour LL avec pile et slr pour SLR.</li>
<li>Résultat : un historique de l'analyse en console et un arbre de dérivation au format .dot : derivation_tree.dot.</li>
</ul>

Les fichiers de description de règles bnf_file et regex_file utilise le format Backus Naur Form, encadrant chaque non-terminal par "<>" et associant des productions à des non-terminaux grâce à "::=", ainsi <math>N \rightarrow ab</math> s'écrit :
<pre>
<N> ::= a b
</pre>

Pour analyser les expressions simple de la forme "a + b", il faut tout d'abord définir les règles de l'analyseur lexical ainsi que les séparateurs additionnels :

<pre>
<separator> ::= +-/*

<integer> ::= [0-9]*
<float> ::= [0-9]*\.[0-9]*f?
<identifier> ::= [A-z]([A-z]|[0-9])*
<operator> ::= \+|\-|/|\*

</pre>

Ici quatre unités lexicales sont définit pour reconnaitre les entiers (integer), les flottants (float), les noms (identifier) et les opérateurs (operator). De plus les opérateurs sont aussi utilisés pour séparer la chaîne d'entrée.

Ensuite pour un analyseur ascendant les règles seront au format BNF :

<pre>
<value> ::= identifier | float | integer
<expr> ::= <value> operator <expr> | <value>
<root> ::= <expr>
</pre>

Ici nous validons les mots composés de valeurs entremêler d'opérateurs, où les valeurs peuvent être des noms, entiers ou flottants. Le nom-terminal <pre><root></pre> et le nom prédéfinit pour l'axiome de la grammaire.

Pour le fichier input_file contenant "5 + 4.2 - 80", l'exécution de la commande avec le méthode slr produit en console un récapitulatif des règles présentes puis un historique de l'analyse et un affichage de l'arbre de dérivation qui se retrouve aussi dans derivation_tree.dot :

[[Fichier:Analyseur-resultat.png|400px]]

Version du 28 mai 2018 à 07:44

VISI201 Analyse syntaxique (Tristan Porteries, 2018)

  • Cours du semestre 2 du parcours CMI Informatique (licence INFO).
  • Responsable pour 2017--2018: Jacques-Olivier Lachaud
  • Responsable pour 2016--2017: Jacques-Olivier Lachaud

Contenu (2017-2018)

Une partie de ce module consiste à assister à des séminaires dédiés aux étudiants CMI Informatique et Mathématique (1 fois par mois, les jeudi après-midi). [Planning des séminaires CMI]

Ces séminaires "grand public" portent sur des sujets variées en informatique et mathématiques.

Les étudiants choisissent ensuite d'approfondir un sujet, dans la liste proposée ci-dessous, ou un sujet motivé de leur choix (en accord avec le responsable du module). Ce travail personnel tuteuré donne lieu à la rédaction d'une synthèse sur le sujet sous forme d'une page wiki/web, ainsi que d'un mini-exposé.

Sujets proposés (2017-2018)

  • Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"
  • Initiation à la démonstration sur ordinateur et certification de logiciel
  • Fouille de données textuelles à partir des "Exercices de style" de R. Queneau
  • Transformées en distance, diagramme de Voronoi et applications en geometry processing
  • Pavages de Penrose


Segmentation d'image par détection de contours et algorithme "ligne de partage des eaux"

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: La segmentation d'image vise à identifier les régions d'intérêt dans une image. Typiquement, une région d'intérêt est une zone de l'image plutôt homogène (les pixels ont des valeurs proches) et le contour entre deux régions d'intérêt est tracé là où les valeurs subissent de fortes variations. La méthode de segmentation proposée ici suit ce principe en enchaînant deux calculs: (1) un premier traitement calcule une image "gradient" et fabrique une image dont les valeurs élevées correspondent à des zones de fortes variations, (2) le deuxième algorithme voit cette image comme un relief 3D et identifie ses bassins hydrographiques. Cette identification des lignes de partage des eaux permet de découper l'image en ses zones d'intérêt.
  • Objectifs:
    1. comprendre ce qu'est une image niveaux de gris ou couleur, ce qu'est le gradient d'une image et ce qu'on appelle segmentation d'image.
    2. décrire un algorithme de calcul du gradient d'une image, e.g. le filtre de Sobel, voire les convolutions par dérivées de Gaussienne.
    3. décrire le principe de ligne de partage des eaux ("watershed" en anglais), ses différentes définitions équivalentes, et les différents types d'algorithmes pour la calculer.
    4. Coder un programme de segmentation d'image, qui prend une image (niveaux de gris) en entrée, calcule son gradient, et extrait les bassins de sa ligne de partage des eaux.
  • Liens pour démarrer
    • [Watershed Wikipedia]
    • Luc Vincent and Pierre Soille. Watersheds in digital spaces: an efficient algorithm based on immersion simulations. In IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 13, Num. 6 (1991), pages 583–598 [PDF]

Initiation à la démonstration sur ordinateur et certification de logiciel

  • Tuteur: Tom Hirschowitz
  • Résumé: [Coq] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
  • Objectifs:
    1. prendre en main le logiciel [Coq] de démonstration sur ordinateur,
    2. programmer certaines démonstrations basiques en Coq,
    3. suivre le début du cours [Software Foundations],
  • Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
  • Liens pour démarrer

Fouille de données textuelles à partir des "Exercices de style" de R. Queneau


Transformées en distance, diagramme de Voronoi et applications en geometry processing

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: Les nuages de points constituent une source de données géométriques importantes (cf LIDAR scanner, 3D scanner) et qui permet de construire des modèles géométriques 3D d'objets réels. La difficulté est de transformer ces nuages de points en des surfaces (souvent des surfaces triangulées, c'est-à-dire des triangles collés entre eux). Un outil essentiel dans ce processus est la transformée en distance, le diagramme de Voronoi (et son dual la triangulation de Delaunay). A partir de ces outils, des algorithmes existent pour reconstruire les surfaces, estimer la géométrie du nuage de point (sa normale par exemple), etc.
  • Objectifs:
    1. Comprendre ce qu'est une distance, une transformée en distance, et un diagramme de Voronoi. Comprendre ce qu'est la stabilité d'une fonction.
    2. Identifier les propriétés des diagrammes de Voronoi, de leur dual la triangulation de Delaunay, et comprendre leurs variantes comme les diagrammes de puissance
    3. Identifier le lien avec l'axe médian et les squelettes
    4. Décrire les principaux algorithmes de calcul des transformées en distance et du diagramme de Voronoi, pour des nuages de point quelconques ou pour des nuages de points à coordonnées entières.
    5. Présenter un algorithme de reconstruction de surface utilisant le diagramme de Voronoi
    6. Coder un algorithme de calcul du diagramme de Voronoi et, si le temps le permet, un algorithme de reconstruction de surface.

Pavages de Penrose

  • Tuteur : Pierre Hyvernat
  • Résumé : le "cerf-volant" et la "fléchette" de Penrose sont deux tuiles qui permettent de recouvrir le plan, mais uniquement de manière non-périodique. Autrement dit, les pavages correspondants ne sont pas obtenus en répétant un même motif de manière régulière. A cause de ceci, il n'est pas évident de générer un tel pavage.

P2.png

  • Objectifs
    1. comprendre les notion de pavage périodique, non périodique et apériodique,
    2. comprendre la méthode "inflation / déflation" pour générer des pavages de Penrose des différents types,
    3. comprendre le lien entre les 2 (ou 3) types de pavage de Penrose
    4. écrire un programme permettant de générer de tels pavages : avec la méthode "inflation / déflation" et avec la méthode "grille de de Bruijn"
    5. utiliser ces méthodes pour générer d'autres types de pavages apériodique.


Algorithmes d'analyse syntaxique

  • Tuteur : Pierre Hyvernat
  • Résumé : le code source d'un programme, d'un fichier de configuration d'un serveur de base de données ou le code d'une page web sont des données textuelles et structurées. Il est possible de définir exactement quelles données sont correctes, et quelle est leur signification. (Cela est beaucoup plus difficile pour des textes en langue naturelle par exemple.) En ce sens, il est possible de lire, d'interpréter ces données à l'aide d'un programme. On parle d'analyseur syntaxique ou de parseur. Il existe de nombreux outils pour faire ça automatiquement, mais il est parfois important (et toujours intéressant) de comprendre les mécanismes correspondant. C'est ce que ce stage propose de faire.
  • Objectifs :
    1. étudier la formalisation du problème à travers la notion de langage et les premiers étages de la hiérachie de Chomsky (langages réguliers et grammaires hors contexte).
    2. comprendre le lien entre les langages et les automates (automates finis / automates à pile)
    3. implémenter un parseur "from scratch" et le tester sur des petits exemples simples, "à la main", soit en calculant "à la volée" la sémantique d'un langage, soit en produisant des "arbres de syntaxe abstraits", qui pourront être analysés par la suite,
    4. comprendre les restrictions souvent imposées sur les grammaires afin d'améliorer l'efficacité du parseur (LL*(k), LR, etc.)
    5. à partir de là, de nombreuses pistes sont ouvertes :
      • essayer d'écrire un petit outils qui puisse lire une grammaire, et générer un parseur pour cette grammaire,
      • comparer l'approche "automate" avec l'approche "combinateurs" et "parseur récursifs"
      • améliorer l'efficacité des parseurs produits
      • ajouter des fonctionnalités,
      • ...

Sujets réalisés (2016-2017)


Sujets proposés (2016-2017)

Algorithme de rendu de scène 3D par Z-buffer

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: Le Z-buffer est un algorithme classique de rendu de scène 3D. C'est celui (avec quelques variantes) qui est implémenté dans nos cartes graphiques 3D et qui permet de visualiser des scènes extrêmement complexes en temps réel (typiquement 24 image/s).
  • Objectifs:
    1. décrire le principe de la projection 3D vers 2D
    2. décrire la rastérisation des triangles sur une image en pixel
    3. expliquer le principe du Z-buffer qui permet de gérer le fait que certains objets sont cachés par d'autres
    4. expliquer comment les couleurs sont calculées par pixel
    5. indiquer les qualités et limitations de l'algorithme
  • Pour aller plus loin
    1. mettre du code démo (WebGL) avec quelques explications sur le pipeline graphique OpenGL
    2. expliquer comment on peut utiliser cet algorithme pour calculer des ombres (shadow map)
  • Liens pour démarrer

Traitement d'image

  • Tuteur: Jacques-Olivier Lachaud
  • Résumé: Le traitement d'image rassemble tous les algorithmes utilisés pour transformer les images, les améliorer, éliminer certaines perturbations, augmenter ou diminuer le contraste, changer les couleurs vers d'autres couleurs, éliminer le flou ou les yeux rouges, faire du cartooning pour un rendu moins photo-réaliste, etc.
  • Objectifs:
    1. identifier les grandes familles de traitement: restauration, égalisation, élimination du flou de déplacement, segmentation, etc
    2. identifier les grandes familles de techniques: filtrage spatial, filtrage fréquentiel, optimisation, etc
    3. comprendre les points communs et différences entre le traitement des images noir et blanc et le traitement des images couleurs.
    4. choisir un ou deux algorithmes de traitement et les expliquer en détails
  • Pour aller plus loin
    1. Coder un algorithme de traitement d'image simple (e.g, un filtrage médian, ou un algo qui transporte les couleurs d'une photo vers une autre photo)


Nim et la théorie des jeux impartiaux

  • Tuteur: Pierre Hyvernat
  • Étudiant : Luca Chapelle
  • Le jeu de Nim (aussi appelé jeu des allumettes) est l'un des premiers jeux ayant été analysé mathématiquement (par Charles Bouton en 1901). Les stratégies gagnantes peuvent être calculées en utilisant le développement en base 2 des nombres, et l'opération d'"addition de Nim" (XOR). La théorie de ce type de jeux (jeux "impartiaux") est assez simple, mais de nombreuses instances de jeux sont encore non résolues.
  • Objectifs:
    1. comprendre la théorie du jeu de Nim (et la programmer)
    2. comprendre le théorème de Sprague Grundy qui montre que tout jeu impartial est équivalent à un jeu de nim
    3. regarder quelques autres exemples de tels jeux : jeu de Nim déguisés, ou jeux véritablement différents
    4. programmer une version naịve de recherche de stratégie basée sur le théorème de Sprague-Grundy pour quelques jeux

La suite de Conway et la classification périodique des "éléments"

  • Tuteur : Pierre Hyvernat
  • La suite de Conway est la suite suivante : 1 ; 11 ; 21 ; 1211 ; 111221 ; ... Chaque terme est obtenu en "lisant" le terme précédent.
    • "1" : un "1" -> 11
    • "11" : deux "1" -> 21
    • "21" : un "2", un "1" -> 1211
    • "1211" : un "1", un "2", deux "1" -> 111221
    • etc.

Cette suite possède des propriétés étonantes données par le théorème "chimique", le théorème "arithmétique" et le théorème "cosmologique".

  • Objectifs :
    1. comprendre les énoncés de ces théorèmes, et l'idée de la preuve du premier.
    2. programmer la suite de Conway pour retrouver la classification des "atomes"
    3. écrire un programme pour calculer expérimentalement une approximation de la constante "lambda" ainsi que des fréquences respectives des différents atomes.
    4. écrire un programme pour calculer la suite de Robinson, une variante plus simple de la suite de Conway

Initiation à la démonstration sur ordinateur et certification de logiciel

  • Tuteur: Tom Hirschowitz
  • Résumé: [Coq] est un logiciel de mathématiques sur ordinateur, grâce auquel des programmes élaborés ont pu être certifiés ces dernières années.
  • Objectifs:
    1. prendre en main le logiciel [Coq] de démonstration sur ordinateur,
    2. programmer certaines démonstrations basiques en Coq,
    3. suivre le début du cours [Software Foundations],
  • Pour aller plus loin : Software Foundations est un cours assez long et très bien fait, il y aura suffisamment à faire. Eventuellement, selon l'intérêt de l'étudiant, étude des fondements mathématiques de Coq.
  • Liens pour démarrer

Calculabilité et modèles de calcul

  • Tuteur: Rodolphe Lepigre
  • Résumé: Une fonction f sur l'ensemble des entiers naturels est dite calculable s'il existe une procedure effective (ou un algorithme) qui permet, étant donné un entier n, de calculer f(n) en temps fini. Il existe divers modèles de calcul qui permettent de représenter toutes les fonctions calculables : machines de Turing, λ-calcul, automates cellulaires, ...
  • Objectifs:
    1. comprendre la notion de fonction calculable,
    2. comparer l'ensemble des fonctions à l'ensemble des fonctions calculables,
    3. regarder et comparer quelque modèles de calcul,
    4. programmer un modèle de calcul et comprendre les limitations pratiques.

Génération et résolution de labyrinthes

  • Tuteur: Jacques-Olivier Lachaud Xavier Provençal
  • Résumé: On veut générer des labyrinthes aussi grands et complexes que possible, avec des murs dans une grille carré voire d'autres domaines. Comment faire pour qu'il y ait toujours un chemin de l'entrée à la sortie ? Comment faire pour qu'il n'y ait qu'un chemin ? Ensuite, comment trouver la sortie quand on est perdu dans le labyrinthe.
  • Objectifs:
    1. Comprendre comment représenter avec une structure de données un labyrinthe
    2. Voir le lien avec la théorie des graphes et voir que le problème se résout de la même façon pour des grilles carrées, hexagonales ou autres.
    3. Comprendre l'algorithme d'arbre couvrant minimum
    4. Comprendre le principe du parcours en profondeur et de la récursivité
  • Pour aller plus loin
    1. coder la génération d'un labyrinthe et sa visualisation
  • Liens pour démarrer

Pavages par polyomino

  • Tuteur: Xavier Provençal
  • Résumé : On s'intéresse aux pavages du plan par des tuiles formées de petits carrés collés les uns aux autres, appelé "polyominos". Étant donné une tuile, peut-on paver le plan ? Si oui, avec quelles opérations (translation et/ou rotations et/ou réflexions) Une fois un pavage réalisé, on observe ses propriétés. Quelles symétries ? Le pavage est-il identique du point de vue de chacune des tuiles ? Si ce n'est pas le cas, en combien de classes peut-on diviser ces tuiles ?

On s'intéressera aussi à des propriétés connexes. Au lieu de paver tout le plan, on peut essayer de paver une région finie donnée. Plus localement, peut-on encercler complètement une tuile avec des copies d'elle-même, sans former de trous ? Si oui, peut-on faire de même avec la proto-tuile formée par la tuile de départ et toutes ses copies ? Si oui, combien de fois peut-on répéter l'opération ?

  • Objectifs :
    1. Comprendre les différentes classes de pavages (isohédral, k-isohédral, anisohédral).
    2. Pour chacun des sept types de pavages "isohédraux", comprendre le lien entre les symétries du pavages et la caractérisation des tuiles qui le réalisent.
    3. Pour un pavage k-isohédral, identifier les "classes d'équivalences" et le "domaine fondamental".
  • Pour aller plus loin :
    1. Coder la génération de tuiles capables de paver le plan en fonction pour une classe de pavages donnée.
    2. Étudier et implémenter certains algorithmes pour le pavages d'un domaine fini.
  • Liens pour démarrer
Récupérée de « http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=VISI201_CMI_:_visite_de_laboratoire&oldid=10367 »