Page personnelle de Aloys Paupe

Informations personnelles

Je suis actuellement étudiant en troisième année au département d'informatique de l'ENS Rennes et en stage à l'Institut de Mathématiques de Toulouse jusqu'en décembre 2026. Vous pouvez trouver mon cv ici.

Recherche

Langages d'ordre supérieur

Travail de recherche issu d'un stage de 8 semaines au sein de l'équipe LogicA de l'INRIA Rennes sous la supervision de Sophie Pinchinat.
Un alphabet indexé est un alphabet pour lequel chaque symbole possède une arité. Les mots générés par un tel alphabet sont donc des arbres et on peut donc avoir des grammaires avec des règles de production sur un alphabet indexé et dont le langage associé est un langage d'arbres. En particulier, on s'intéresse aux grammaires qui produisent des arbres représentant des expressions régulières, et on définit le langage du second ordre d'une telle grammaire comme étant l'union des langages des expressions régulières qu'elle produit. On se pose alors la question de connaître l'expressivité des langages d'ordre supérieur.

Logique MSO et automates du second ordre

Travail de recherche issu d'un projet de recherche au sein de l'équipe LogicA de l'INRIA Rennes sous la supervision de Sophie Pinchinat.
Pour un alphabet fini et une dimension d fixés, on définit un bloc comme étant un ensemble de transitions (au sens d'un automate) entre d états de départ et d états d'arrivée. L'ensemble des blocs étant fini, on peut le voir comme un alphabet et donc étudier les automates définis sur cet alphabet; de tels automates sont dits du second ordre. La question que nous nous sommes posés est la suivante : une formule MSO est-elle décidable si son ensemble de variables est quantifié sur un langage généré par un automate de Büchi du second ordre?

Coloriage fortement majoritaire de graphes

Travail de recherche issu d'un stage de 11 semaines au sein du Delft Institute of Applied Mathematics (Pays-Bas) sous la supervision de Carla Groenland.
On dit qu'un coloriage d'un graphe est fortement majoritaire si chaque sommet est tel qu'aucune couleur n'est associée à strictement plus que la moitié de ses voisins. On s'interroge alors sur le nombre de couleurs nécessaires pour obtenir un tel coloriage de certaines classes de graphes (graphes planaires, graphes de petits degrés, graphes de degrés divisible par 3 etc.). Nous avons également étudié une variante correspondant à un coloriage des arêtes au lieu des sommets.

Projets

Génération de parcours de course à pied
Dans le cadre de mon TIPE de 3/2, j'ai participé à la conception d'un programme qui génère des parcours de course à pied en fonction de paramètres indiqués par l'utilisateur. Il reposait sur un algorithme d'optimisation d'une fonction de coût décrivant la qualité du parcours (quantité d'arbres, de bancs, proximité à une surface d'eau etc.) selon des paramètres entrés par l'utilisateur. L'optimisation se faisait par un algorithme de type Branch-And-Bound, et les données nécessaires étaient récupérées d'OpenStreetMap par un script Python, avant d'être converties pour traitement en Ocaml.
Polyominos
Dans le cadre de mon TIPE de 5/2, j'ai étudié la pavabilité des polyominos. J'ai commencé par la caractérisation de Beauquier et Nivat des polyominos qui pavent le plan (en implémentant l'algorithme de Gambini et Vuillon qui les reconnaît). Puisque dire si un ensemble de polyominos pave le plan est indécidable, j'ai implémenté l'algorithme des liens dansants de Donald Knuth pour déterminer si un ensemble de polyominos peut paver une surface finie.
Musique

En plus de mes cours à l'ENS Rennes je joue du piano et compose des morceaux.

Go [En cours]

Je joue au jeu de Go et suis en train de développer un programme permettant d'y jouer et de réviser des josekis. Il est codé en Ocaml, avec un affichage et une intéraction avec l'utilisateur par la librairie graphics.

Pretty printing [En cours]
Je code souvent en Ocaml et j'ai régulièrement des problèmes pour afficher des structures d'arbre lorsque j'en utilise. J'ai donc décidé de coder des fonctions de pretty printing d'arbres réutilisables. Pour l'instant, elles ne sont applicables que sur des arbres binaires.
Parseur d'arbres [En cours]

Ce projet correspond plus au moins au projet complémentaire du précédent. De même qu'il n'est pas agréable de visualiser les arbres sous leur syntaxe Ocaml, il n'est pas forcément agréable non plus d'en écrire. J'ai donc décidé de faire un parseur en ligne qui permet de dessiner plutôt facilement des arbres simples et de générer leur syntaxe Ocaml. Pour l'instant, le parseur ne permet que de dessiner des arbres binaires. L'outil est disponible ici.

Contact

Vous pouvez me contacter via mon adresse e-mail: aloys.paupe[at]ens-rennes.fr.