Actualités du LIPN

Le séminaire OCAD recevra le 6 avril Damien Regnault (ATER au LIF-CMI, Marseille).

Cet exposé commence par la présentation rapide de la règle Minorité stochastique et de ses particularités. Ensuite, je présenterai une application de cette règle pour modéliser la formation de quasi-cristaux.

Considérons un graphe où chaque sommet reçoit la couleur noire ou blanche. Une arête contient une erreur si elle relie deux sommets de la même couleur. Minorité est une dynamique stochastique minimisant rapidement l’énergie. Sous cette dynamique, un sommet, chosi aléatoirement et uniformément parmi l’ensemble des sommets, peut changer d’état si au moins la moitié des arêtes qui lui sont adjacentes sont erronées.. Cette dynamique est sensible à la topologie du graphe et son analyse fine s’est révélée compliquée.

En physique, dans les années 70, il était conjecturé que toutes les structures ordonnées soient périodiques. En 1984, un contre-matériaux fût découvert et reçu le nom de quasi-cristal. Dès 1974, Penrose avait présenté un structure théorique ordonnée et apériodique. Le but de notre projet est de présenter un modèle pour expliquer la formation d’une telle structure. Pour cela, nous considérons le modèle des pavages par coupe et projection (qui contient le pavage de Penrose). En définissant une notion d’erreur et d’énergie sur ces pavages, la règle Minorité procédant par flips permet de converger rapidement expérimentalement vers une structure ordonnée qui selon la famille de pavages par coupe et projection considérée est soit périodique, soit apériodique. Je présenterai nos résultats expérimentaux ainsi que notre analyse de cette dynamique pour les pavages 2 vers 1 (mots sur deux lettres).

Pour son premier séminaire de l’année ce 12 janvier, l’équipe OCAD accueille Antoine Genitrini (ATER, PRISM, Université de Versailles Saint-Quentin-en-Yvelines).

Écrivez une formule booléenne de manière aléatoire, construite avec des ensembles fixés de connecteurs et de littéraux. Quelle est la fonction booléenne « typique » qu’elle représente ? Quelle est la probabilité que la formule calcule la fonction Vrai ? Un littéral ? Ou une autre fonction donnée ? D’autres questions de nature un peu différente peuvent se poser : quelle est la complexité de la fonction booléenne représentée par cette formule aléatoire (i.e. la taille de la plus petite formule la représentant) ? Quelle est la complexité moyenne d’une fonction booléenne définie sur k variables ?

Ces questions mettent en avant le problème suivant : comment définir une distribution de probabilité sur les fonctions booléennes ? Les premiers articles se posant ce genre de questions ont mis en avant deux modèles de formules booléennes aléatoires, basées sur les connecteurs binaires Et/Ou, et qui engendrent une distribution (non uniforme) sur les fonctions booléennes. Ces articles n’ont répondu que très partiellement aux premières questions que j’ai évoquées. On adapte aisément ces distributions au cas de formules construites à l’aide de l’unique connecteur Implication, un des connecteurs de base d’un point de vue logique. Ce modèle de base suscite de l’intérêt car certaines formules représentant des tautologies (formule calculant toujours Vrai) en logique classique ne sont pas des tautologies en logique intuitionniste.

Dans un premier temps, j’exposerai les résultats concernant l’ensemble des fonctions booléennes construites sur l’Implication, puis j’aborderai en détail les tautologies. Dans un troisième temps, j’enrichirai le modèle de formules en utilisant plusieurs connecteurs logiques aléatoires. Enfin, je conclurai l’exposé en abordant différentes perspectives relatives à ces problèmes et sur lesquelles je travaille actuellement.

Le séminaire OCAD accueille Mathilde Bouvel (LIAFA, université Paris VII).

Dans cet exposé, on étudie les classes de permutations, qui sont des ensembles de permutations fermés par le bas pour la relation d’ordre de motif. Je présenterai d’une part des résultats de nature algorithmique sur la recherche de motif dans les permutations, et d’autre part des résultats plutôt combinatoires sur la structure des classes de permutations. Un point commun à ces résultats est qu’ils ont été obtenus en utilisant les arbres de décomposition des permutations. Je présenterai ces objets, et illustrerai par des exemples comment ils peuvent être utilisés en combinatoire comme en algorithmique.

Le séminaire OCAD accueille Julien David (doctorant, LIPN, université Paris 13).

Dans un premier temps, on présentera une méthode de génération aléatoire d’automates déterministes accessibles complets et un outil, REGAL, utilisant cette méthode. Les générateurs implantés dans REGAL permettent d’engendrer des automates de plusieurs milliers d’états et ce faisant, d’établir des conjectures crédibles sur les propriétés en moyenne des automates, ainsi que sur les algorithmes qui s’y appliquent.

Dans une deuxième partie, on présentera un résultat théorique sur la complexité moyenne de l’algorithme de Moore: si la complexité dans le pire cas de l’algorithme est connu pour être en , on montrera que pour un alphabet fini arbitraire et la distribution uniforme sur l’ensemble des automates déterministes accessibles complets n états, la complexité moyenne est .

Vlady Ravelomanana soutient son HDR le 27 novembre 2008 à 14h intitulée « Graphes aléatoires, optimisation, algorithmique distribuée : approches analytiques ».

Le jury est composé de

• Nadia Creignou (LIF -- Marseille),
• Luc Devroye (McGill),
• Gérard Duchamp (LIPN-P13),
• Philippe Flajolet (INRIA),
• Christian Lavault (LIPN-P13),
• Rémi Monasson (LPT -- ENS),
• Hsien-Kuei Hwang (Academia Sinica, Taipei),
• Brigitte Vallée (GREYC - Caen).

Nous présentons un ensemble de résultats portant sur trois axes distincts, tous obtenus en utilisant des approches analytiques. Dans ces travaux, nous faisons intervenir des méthodes de combinatoire analytique et d’algorithmique. Ces outils sont utilisés pour répondre aux problèmes suivants :

1. l’étude des composantes géantes des graphes et hypergraphes aléatoires,
2. la transition de phase de 2–XORSAT, l’analyse en moyenne d’un algorithme exact d’optimisation, et
3. l’élection et l’initialisation dans des réseaux radio.