Ce site est en cours de construction.
Pour plus d'informations vous pouvez consulter les sites de nos anciens laboratoires :
Site du LIF - Site du LSIS


LIS UMR CNRS 7020

LIS UMR 7020

Le LIS Laboratoire d’Informatique et Systèmes est une nouvelle structure issue de la fusion de deux UMR : le Laboratoire d’Informatique Fondamentale de Marseille (LIF) UMR 7279 et le Laboratoire des Sciences de l’Information et des Systèmes (LSIS) UMR 7296. C’est une Unité Mixte de Recherche (UMR) sous tutelles du Centre National de la Recherche Scientifique (CNRS) rattachée à l’Institut des sciences de l'information et de leurs interactions (INS2I), de l’Université d’Aix-Marseille (AMU) et de l’Université de Toulon (UTLN).

Prochains évènements

Retour à l'agenda
21 September 2018

Séminaire CaNa : nombre de points fixes des réseaux Booléen : complexité algorithmique, Florian Bridoux

Résumé: 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 entierk, 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.

Tutelles