Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

19 novembre 2018

TBA

Valentina Castiglioni (LIX - Ecole Polytechnique)

TBA

12 novembre 2018

TBA

Antoine Amarilli (Télécom ParisTech)

TBA

8 octobre 2018

Modèle géométriques de programmes concurrents conservatifs

Emmanuel Haucourt (LIX - Ecole Polytechnique)

Un programme concurrent est constitué de plusieurs processus
séquentiels qui s'exécutent simultanément et partagent des ressources.
Pour un processus séquentiel standard, le graphe de flot de contrôle
(GFC) est une sur-approximation classique (et omniprésente dans les
compilateurs et analyseurs statiques) de l'ensemble des traces
d'exécutions du programme. La propriété cruciale du graphe de flot de
contrôle est sa finitude. Définir l'équivalent de cette structure pour
les programmes concurrents n'a rien d'évident. La solution que l'on
propose est basée sur la notion d'espace partiellement ordonné. À chaque
GFC on associe sa réalisation géométrique dirigée, qui consiste à
remplacer chaque flèche du GFC par une copie du segment unité [0,1]
joignant la source de la flèche à son but. Un programme parallèle
constitué des processus séquentiels P_1,...,P_n sera alors représenté
par un sous-espace du produit cartésien E = G_1 x ... x G_n où G_i est
la réalisation du GFC's du i-ème processus. En effet, sous l'hypothèse
que le programme considéré est conservatif, on peut définir une fonction
de potentiel qui associe à chaque point de E la quantité de ressources
nécessaire au fonctionnement du programme en ce point. Si cette quantité
dépasse la quantité de ressources disponible, alors le point est
«interdit». L'ensemble des points interdits forme une sous partie de E
dont le complémentaire M est le modèle géométrique du programme. 
On a les résultats suivants:
1) les chemins (continus) dirigés sur M forment une sur-approximation de
l'ensemble des traces d'exécutions du programme
2) chaque chemin f possède un voisinage V dont tous les éléments g (qui
sont eux-mêmes des chemins dirigés sur M) son équivalent à f au sens où
l'état de la mémoire
de la machine abstraite à la fin de l'exécution de g ne dépend pas de g
3) l'ensemble des traces d'exécution forment un ouvert de l'espace des
chemins dirigés sur M
4) les modèles géométriques appartiennent à une classe d'objets qui
satisfait une propriété de décomposition unique vis-à-vis du produit
cartésien. À partir de la décomposition du modèle géométrique d'un
programme, on peut regrouper ses processus de manière à obtenir des
sous-programmes indépendants.

Les constructions et résultats annoncés ci-dessus seront illustrés de
nombreux exemples. :-)

1 octobre 2018

Une perspective personnelle sur le problème de satisfaction de contraintes et ses variantes.

Florent Madelaine (LACL UPEC)

La conjecture de la dichotomie énoncée en 1993 par Feder et Vardi stipule que tout problème de contraintes est soit dans P, soit NP-complet.
Un phénomène qu’il faut contraster avec le théorème de Ladner qui implique que ceci n’est pas vrai en général (provisio P différent de NP).
Cette conjecture est un théorème depuis 2017 : il y a deux preuves proposées indépendemment par Bulatov et Zhuk.
Entre ces deux dates, cette question a permis de réunir des personnes issues de profils variés (combinatoire, bases de données, logique, algèbre, …).

On n’en voudra pas au lecteur de se poser la question suivante : ce domaine est-il moribond?
Cet exposé sera l’occasion de tenter d’y répondre par la négative après avoir fait un présentation personnelle de ce domaine.

24 septembre 2018

Nombre de points fixes des réseaux booléen: Complexité algorithmique

Florian Bridoux (LIS - Marseille)

Dans cette présentation nous allons nous intéresser aux
réseaux booléens (RB).
Un RB de taille n peut être vu comme une fonction f: {0,1}^n -> {0,1}^n ou
bien comme un produit de n fonctions f_1, f_2, …, f_n de {0,1}^n à
{0,1}.
Un problème classique est le calcul du nombre de points fixes,
c’est-à-dire le nombre de configurations x dans {0,1}^n tel que
f(x) = x.
Un objet souvent utilisé (et qui justifie la terminologie de «
réseaux ») quand on s’intéresse aux réseaux booléens est le
graphe d’interaction.
Il s’agit d’un graphe à n sommets numérotés de 1 à n tel qu’il y a
un arc entre le sommet i et j ssi la valeur de f_j(x) dépendant de la
i-eme composante de x pour un certain x (= le sommet i “a une
influence” sur j).
Chaque RB a son graphe d’interaction mais un même graphe
d’interaction peut correspondre à de nombreux RBs.
Nous allons noter F(G) l’ensemble des RBs correspondant à un certain
graphe d’interaction G.
Et nous allons nous intéresser à la question: “Étant donné G et un
entier k, existe-t-il f dans F(G) qui a au moins/au plus k points
fixes?”
Nous allons voir que selon la nature de k et l’exacte question posée,
le problème peut appartenir à différentes classe de complexité allant de P à NEXPTIME.