2011-05-12T12:30:00Z Sycomore Ce flux Atom informe des derniers articles en ligne sur Sycomore

For each collection of n discrete random variables, we can define a vector of 2^n-1 entropies, one for each singleton, pair, triple etc. We study the subset of the Euclidian space R^2^n-1 consisting of all such vectors, and few other related entropy spaces, from a geometric point of view. We (...)

2011-05-12T12:30:00Z 2011-05-10T16:22:52Z

Nous présenterons le phénomène de transition de phase dans les problèmes de satisfaction de contraintes (CSP). Le calcul de la valeur du seuil (dans 3-SAT notamment) résiste depuis une vingtaine d'années. En particulier, nous montrerons l'intérêt de la méthode du premier moment pour (...)

2011-05-05T12:31:00Z 2011-05-10T16:01:41Z

Les pavages et la récursivité sont intimement liés : en 1964, Berger prouvait l'indécidabilité de la pavabilité du plan, par la suite, Hanf et Myers prouvèrent qu'il existe des jeux de tuiles n'admettant aucun pavage récursif. Puis Simpson prouva en 2008 que les degrés (...)

2011-04-07T12:30:00Z 2011-04-05T09:57:55Z

Sand pile models are dynamical systems describing the evolution from N stacked grains to a stable configuration. It uses local rules to depict grain moves and iterate it until reaching a stable configuration from which no rule can be applied. The main interest of sand piles relies in their Self (...)

2011-03-24T13:30:00Z 2011-03-19T10:26:53Z

Nous commencerons par présenter un résultat de A. Shen montrant que quatre propriétés élémentaires de la complexité de Kolmogorov (la complexité pleine) suffisent à la caractériser. Après avoir présenté cette caractérisation, nous allons prouver qu'il est impossible de l'affaiblir (...)

2011-02-22T13:30:00Z 2011-03-20T12:07:44Z

Spatial computing aims at providing a scalable framework where computation is distributed on a uniform computing medium and communication happen locally between nearest neighbors. We study the particular framework of cellular automata, using a regular grid and synchronous update. As a first (...)

2011-02-10T13:25:00Z 2011-01-27T13:18:09Z

Un système dynamique auto-organisant peut être décrit de la manière suivante : avec des conditions initiales aléatoires, l'évolution du système laisse apparaître des structures régulières, qui sont toujours les mêmes. On s'intéresse ici à certains automates cellulaires 1D présentant (...)

2011-02-03T13:25:00Z 2011-01-28T17:18:22Z

In this talk we present three algorithmic problems for probabilistic automata on finite words : the Emptiness Problem, the Isolation Problem and the Value 1 Problem. The Emptiness Problem asks, given some probability 0\leq\lambda\leq 1, whether there exists a word accepted with probability (...)

2011-01-27T13:25:00Z 2011-01-25T09:47:15Z

Les réseaux d'automates booléens sont des systèmes dynamiques discrets largement utilisés dans la modélisation de phénomènes réels (régulations biologiques, en particulier, génétiques, circuits logiques, propagation d'épidémies...). Pour développer notre compréhension de leur (...)

2011-01-20T13:30:00Z 2011-01-17T09:06:28Z

à venir

2010-11-25T13:10:00Z 2010-12-04T10:38:37Z