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 (I2M).
Le programme du séminaire est organisé en deux temps:
-
les premières séances (jusqu’en novembre) sont assurées par des chercheurs des équipes impliquées dans le master;
-
les séances suivantes (à partir de début décembre) sont consacrées à des présentations d’articles travaillés par les étudiants.
Tous les exposés sont donnés en anglais.
Pour les exposés assurés par les étudiants :
-
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 par un étudiant 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.
Elle est faite en anglais.
Séances
- jeudi 31 octobre, 14h
- Exposé d’Arnaud Labourel (LIS)
- jeudi 7 novembre, 14h
- Exposé de Lionel Nguyen Van Thé (I2M): Is your brain open? Meeting with Paul Erdös
- jeudi 19 décembre, 14h
- Ariel Chenet:
Cellular Automata and Powers of p/q
de J. Kari et J. Kopra.
- Edoardo Rivetti:
Proof nets and boolean circuits
de K. Terui.
- jeudi 16 janvier, 14h
- Léo Kammerlocher:
Transformation Between Regular Expressions and omega-Automata
de C. Löding et A. Tollkötter.
- Guillaume Maurras:
Logics for context-free languages
de Clemens Lautemann, Thomas Schwentick et Denis Thérien.
- jeudi 23 janvier, 14h
- Luigi Bernardi:
Universal coating for programmable matter
de Z. Derakhshandeh, R. Gmyr, A. W. Richa, C. Scheideler, et T. Strothmann.
- Caroline Gaze-Maillot:
Views in a Graph: To Which Depth Must Equality Be Checked?
de J. M. Hendrickx.
- jeudi 30 janvier, 14h
- Enzo Laborde:
Paperfolding morphisms, planefilling curves, and fractal tiles
de M. Dekking.
- Charly Finette:
Metric spaces, generalized logic and closed categories
de F. W. Lawvere.
- Francesca Bacco:
A categorical theory of patches
de S. Mimram et C. Di Giusto.
Articles sélectionnés
- Francesca Bacco
-
A categorical theory of patches
de S. Mimram et C. Di Giusto.
-
Proposé par Lionel Vaux (I2M).
- Luigi Bernardi
-
Universal coating for programmable matter
de Z. Derakhshandeh, R. Gmyr, A. W. Richa, C. Scheideler, et T. Strothmann.
-
Proposé par Shantanu Das (LIS).
- Ariel Chenet
-
Cellular Automata and Powers of p/q
de J. Kari et J. Kopra.
-
Proposé par Pierre Guillon (I2M).
- Charly Finette
-
Metric spaces, generalized logic and closed categories
de F. W. Lawvere.
-
Proposé par Dimitri Ara (I2M).
- Caroline Gaze-Maillot
-
Views in a Graph: To Which Depth Must Equality Be Checked?
de J. M. Hendrickx.
-
Proposé par Jérémie Chalopin (LIS).
- Léo Kammerlocher
-
Transformation Between Regular Expressions and omega-Automata
de C. Löding et A. Tollkötter.
-
Proposé par Pierre-Alain Reynier (LIS).
- Enzo Laborde
-
Paperfolding morphisms, planefilling curves, and fractal tiles
de M. Dekking.
-
Proposé par Pierre Arnoux (I2M).
- Guillaume Maurras
-
Logics for context-free languages
de Clemens Lautemann, Thomas Schwentick et Denis Thérien.
-
Proposé par Séverine Fratani (LIS).
- Edoardo Rivetti
-
Proof nets and boolean circuits
de K. Terui.
-
Proposé par Emmanuel Beffara (I2M).
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.
D’autres propositions sont susceptibles d’être ajoutées à cette liste d’ici peu.
-
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.
-
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.
-
Proposé par Pierre-Alain Reynier (LIS), qui écrit:
Un algorithme majeur d’apprentissage de langages réguliers reposant sur la notion de résiduels.
Articles proposés (et non traités) l’année dernière
Ces articles ont été proposés l’année dernière, et les personnes qui les avaient
proposées n’ont pas explicitement renouvelé ces propositions cette année :
ça n’empêche pas de s’y intéresser, mais il est possible que ces personnes
ne soient vraiment pas disponibles pour discuter.
-
On the translation of languages from left to right
de D. Knuth.
-
Proposé par Alexey Muranov (I2M).
-
Groups defined by Automata
de L. Bartholdi, et P. V. Silva.
-
Proposé par Pierre Guillon (I2M), qui écrit:
survol sur les groupes automatiques, puis sur les groupes d'automates.
-
Decidability of the HD0L ultimate periodicity problem
de F. Durand.
-
Proposé par Pierre Guillon (I2M).
-
Episturmian words: a survey
de A. Glen et J. Justin.
-
Proposé par Pierre Guillon (I2M), qui écrit:
survol sur une généralisation des mots sturmiens à un alphabet infini.
-
New Directions in Cryptography
de W. Diffie et M. Hellman.
-
Proposé par David Kohel (I2M), qui écrit:
Seulement 11 pages, moins de mathématiques, mais un classique historique.
-
Statistical equilibrium in deterministic cellular automata
de S. Taati.
-
Proposé par Pablo Arrighi (LIS).
-
Thermodynamically Favorable Computation via Tile Self-assembly
de Cameron Chalk, Jacob Hendricks, Matthew J. Patitz, Michael Sharp.
-
Proposé par Pablo Arrighi (LIS).
-
On Non-Computable Functions
de T. Rado.
-
Proposé par Kevin Perrot (LIS), qui écrit:
Pour ouvrir la discussion/présentation je conseille la lecture de ce billet de blog par Scott Aaronson..
-
An algorithm for restricted least squares regression
de Richard L. Dykstra.
-
Proposé par Pascal Prea (LIS).
-
Transformation Between Regular Expressions and omega-Automata
de Christof Löding, Andreas Tollkötter.
-
Proposé par Pierre-Alain Reynier et Nicolas Baudru (LIS).
-
A Biological Solution to a Fundamental Distributed Computing Problem
de Yehuda Afek, Noga Alon, Omer Barad, Eran Hornstein, Naama Barkai et Ziv Bar-Joseph.
-
Proposé par Emmanuel Godard (LIS).