Séminaire tutoré

Cette page rassemble les informations et ressources relatives au séminaire tutoré du M2 IMD, organisé par Jérémie Chalopin (LIS) et Lionel Vaux Auclair (I2M).

Le programme du séminaire est organisé en deux temps:

les premières séances sont assurées par des chercheurs et chercheuses des équipes impliquées dans le master;
les séances suivantes sont consacrées à des présentations d’articles travaillés par les étudiantes et étudiants.

Tous les exposés sont donnés en anglais.

Pour les présentations d’articles :

Chaque étudiant choisit un article de recherche, en anglais, parmi les propositions ci-dessous.
L’exposé donné au séminaire consiste en la présentation de l’article choisi. Cette présentation doit être focalisée sur les aspects classiques (contexte, objectif, résultats obtenus, perspectives) et détailler un peu la partie technique de l'article.

Articles proposés

Pour chaque article, on indique la personne qui l’a proposé : cette personne acceptera probablement (mais pas nécessairement) de correspondre et discuter avec vous pour éclairer votre lecture si nécessaire.

Le gros des propositions devraient arriver d’ici début octobre.

Graph theory and probability de P. Erdös.: Proposé par Lionel Nguyen Van Thé (I2M), qui écrit:
Il s'agit de l'article d'Erdös qui a lancé la méthode probabiliste en théorie des graphes (et plus généralement, en combinatoire), donc d'intérêt historique certain.

Archives

Ici on trouve des exemples d’articles proposés les années précédentes. Il est très probable qu’une partie sera reprise cette année.

A categorical theory of patches de S. Mimram et C. Di Giusto.

Proposé par Lionel Vaux (I2M), qui écrit:

une approche catégorique de la conception d’un logiciel de gestion de versions, qui a inspiré une implémentation prometteuse à la fois en termes de fonctionnalités et de performances.

Universal coating for programmable matter de Z. Derakhshandeh, R. Gmyr, A. W. Richa, C. Scheideler, et T. Strothmann.

Proposé par Shantanu Das (LIS), qui écrit:

Un des premiers articles sur les algorithmes pour la matière programmable en utilisant le modèle d'Amoebot (nanorobots inspirés par des amibes). Cet article concerne le problème du coating (c.-à-d. couvrir un objet donné).

Cellular Automata and Powers of p/q de J. Kari et J. Kopra.

Proposé par Pierre Guillon (I2M), qui écrit:

AC et théorie des nombres,

un AC qui fait des multiplications et du coup des orbites parcourent tous les mots finis.

Metric spaces, generalized logic and closed categories de F. W. Lawvere.

Proposé par Dimitri Ara (I2M).

Views in a Graph: To Which Depth Must Equality Be Checked? de J. M. Hendrickx.

Proposé par Jérémie Chalopin (LIS), qui écrit:

La vue d'un sommet v dans un graphe G est un arbre (infini) dont les sommets correspondent aux chemins issus de v dans G. Si deux sommets ont la même vue, ils ont la même vue de hauteur k (on ne considère que les chemins de longueur au plus k). Dans cet article, l'auteur cherche pour quelles valeurs de k, la réciproque est vraie.

Transformation Between Regular Expressions and omega-Automata de C. Löding et A. Tollkötter.

Proposé par Pierre-Alain Reynier (LIS), qui écrit:

Un article qui étudie les transformations entre automates et expressions régulières dans le contexte des mots infinis.

Paperfolding morphisms, planefilling curves, and fractal tiles de M. Dekking.

Proposé par Pierre Arnoux (I2M).

Logics for context-free languages de Clemens Lautemann, Thomas Schwentick et Denis Thérien.

Proposé par Séverine Fratani (LIS).

Proof nets and boolean circuits de K. Terui.

Proposé par Emmanuel Beffara (I2M), qui écrit:

Une approche originale de la correspondance entre modèles de calcul et preuves formelles: les circuits booléens sont interprétés comme des démonstrations dans un système logique, on en déduit une correspondance entre la complexité des circuits et la complexité logique.

On time-symmetry in cellular automata de A. Gajardo, J. Kari, A. Moreira.

Proposé par Guillaume Theyssier et Pierre Guillon (I2M), qui écrivent:

quand la dynamique est proche de la dynamique inverse…;

facile sauf la fin, nouveau par rapport au cours mais connecté à des notions vues, permet de faire une belle présentation.

Periodicity and Immortality in Reversible Computing de J. Kari et N. Ollinger:

Proposé par Guillaume Theyssier et Pierre Guillon (I2M), qui écrivent:

indécidabilité de la périodicité des machines de Turing, puis des AC;

gros résultat, beau mélange de modèles de calcul et systèmes dynamiques.

On the Undecidability of the Tiling Problem de J. Kari:

Proposé par Guillaume Theyssier et Pierre Guillon (I2M), qui écrivent:

une preuve de l'indécidabilité du problème du pavage (y compris dans le plan hyperbolique) en passant par l'indécidabilité de la mortalité des fonctions affines par morceaux.

A polygon is determined by its angles de Y. Disser, M. Mihalák et P. Widmayer.

Proposé par Shantanu Das (LIS), qui écrit:

Un robot se promène sur le bord d'un polygone et il peut mesurer les angles à chaque sommet du polygone. Cette information est-elle suffisante pour reconstruire le polygone, par le robot? Un problème assez drôle et intéressant.

Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes de J. Czyzowicz, S. Dobrev, T. Fevens, H. González-Aguilar, E. Kranakis, J. Opatrny et J. Urrutia.

Proposé par Arnaud Labourel (LIS).

Simpler, faster and shorter labels for distances in graphs de S. Alstrup, C. Gavoille, E. B. Halvorsen et H. Petersen.

Proposé par Arnaud Labourel (LIS).

Finding the longest isometric cycle in a graph de D. Lokshtanov.

Proposé par Jérémie Chalopin (LIS), qui écrit:

Un algorithme polynomial pour trouver un plus long cycle isométrique (c'est à dire que les distances entre les sommets du cycle sont les mêmes dans le cycle et dans le graphe). Un résultat un peu surprenant parce que de nombreuses variantes de recherches de plus longs cycles dans un graphe sont NP-difficiles.

Disjunctive tautologies as synchronisation schemes de V. Danos et J.-L. Krivine.

Proposé par Emmanuel Beffara (I2M), qui écrit:

Une illustration exemplaire de la correspondance preuves-programmes quand elle quitte le domaine purement fonctionnel: les formules propositionnelles de la logique classique apparaissent comme des spécifications pour des structures de contrôle qui rappellent de la synchronisation entre processus.

The Structure of Multiplicatives de V. Danos et L. Regnier.

Proposé par Emmanuel Beffara (I2M), qui écrit:

Un article fondateur sur l'approche géométrique des démonstrations initiée par la logique linéaire, où la correction d'une démonstration est présentée comme une propriété combinatoire de certains graphes.

Solos in concert de C. Laneve et B. Victor.

Proposé par Emmanuel Beffara (I2M), qui écrit:

Une réflexion sur l'expressivité de différents langages abstraits pour représenter les processus parallèles et concurrents, avec un regard plus précisément sur les question d'ordonnancement et de synchronisation.

Two-variable logic on data words de M. Bojańczyk, C. David, A. Muscholl, T. Schwentick et L. Segoufin.

Proposé par Benjamin Monmège (LIS), qui écrit:

Ça parle de logique mais via le prisme des automates. Un peu long, mais on peut se concentrer sur les sections 1 à 6 (ou 7 maximum), le reste étant des extensions moins pertinentes.

Learning Regular Sets from Queries and Counter-Examples de D. Angluin.