Nous organisons des séminaires réguliers depuis 1995. D'abord dans le cadre des séminaires PACOM puis à partir de 2003, dans le cadre de l'équipe RECIF et à partir de 2008, dans le cadre de l'équipe MC3. Les séminaires sont l'occasion pour l'équipe MC3 de se retrouver de manière informelle, autour d'un thème introduit par l'orateur du jour. Ils sont ouverts à tous.

Pour être informés des séminaires à venir, consultez régulièrement cette page ou écrivez à julien [dot] provillard [at] i3s.unice.fr pour vous inscrire ou vous désinscrire de la liste de diffusion.

Signalons au passage les séminaires de l'équipe CeP et du pôle MDSC dont fait partie notre équipe ainsi que le Colloquium Jacques Morgenstern.

Programme des exposés

223. salle de réunion (I3S)

     Sous-calculabilités

     Fabien Givors I3S, Sophia Antipolis

     La calculabilité est l'étude des fonctions récursives, c'est à dire des algorithmes, des programmes que l'on peut écrire. L'objectif abordé par cet exposé est la mise en regard la puissance de calcul de ces fonctions avec la puissance de théories mathématiques associées. Ces considérations nous amènent à définir les sous-calculabilités, une axiomatique pour les fragments de calculabilité. Nous montrons ensuite que cette définition s'applique également à des fonctions plus puissantes que les fonctions récursives.
222. Mercredi 09 juillet 2014 à 10h30
     salle de conférence (I3S)

     Computational Complexity on decision problems for majority automata networks

     Eric Goles Universidad Adolfo Ibáñez, Santiago du Chili

     Consider a majority networks (i.e each node changes its state following the majority of its neighbors) We present some complexity results related to the prediction problem PRED (i.e. to determine efficiently if a given node in the network will change its state) for the parallel update of the network. In particular we prove that generalized majority is P-Complete in a two dimensional grid with von Neumann neighborhood.
221. Mardi 17 juin 2014 à 14h30
     salle de conférence (I3S)

     The simultaneous number-in-hand communication model for networks: private coins, public coins and determinism

     Pedro Montealegre Université d'Orléans

     We study the multiparty communication model where players are the nodes of a network and each of these players knows his/her own identifier together with the identifiers of his/her neighbors. The players simultaneously send a unique message to a referee who must decide a graph property. The goal of this article is to separate, from the point of view of message size complexity, three different settings: deterministic protocols, randomized protocols with private coins and randomized protocols with public coins. For this purpose we introduce the boolean function Twins. This boolean function returns 1 if and only if there are two nodes with the same neighborhood.
222. Jeudi 22 mai 2014 à 09h30
     Espaces Antipolis, Sophia

     Journée du pôle

     Programme
220. Vendredi 18 avril 2014 à 14h00
     salle de conférence (I3S)

     Automates cellulaires : ensembles μ-limites et calculabilité

     Martin Delacourt CMM, Universidad de Chile
219. Mercredi 16 avril 2014 à 16h00
     salle de conférence (I3S)

     Cryptographic Properties and Applications of Bipermutive Cellular Automata

     Luca Mariot Università di Milano-Bicocca

     Bipermutive Cellular Automata (BCA) are defined by local rules which have a simple combinatorial characterization. It has been shown that BCA satisfy several definitions of chaotic systems (Devaney-chaos, Mixing-chaos and Expansive-chaos), and are thus of interest for cryptographic applications, in particular for pseudorandom number generation. In this talk, we consider BCA local rules with respect to their cryptographic properties, showing how their nonlinearity, resiliency and algebraic degree can be determined by studying the corresponding generating functions. We then report some results on the heuristic optimization of the cryptographic properties of BCA using various soft computing techniques. Finally, we show how the surjectivity of BCA can be employed to design a perfect and ideal secret sharing scheme, pointing out some possible future developments to improve its access structure.
220. du Mardi 08 avril au Jeudi 10 avril 2014
     LORIA, Nancy

     FRAC et Journées SDA2

     Programme
218. Jeudi 20 février 2014 à 16h30
     salle de réunion (I3S)

     Programmation par contraintes et Systèmes dynamiques discrets

     Pierre-Alain Scribot I3S, Sophia Antipolis

     Les réseaux d'automates booléens, lorsqu'ils sont mis à jour de manière synchrone, peuvent être vus comme des systèmes dynamiques discrets dont l'espace des états est fini (2^n états possibles pour un réseau de n automates). Le comportement asymptotique de ces réseaux consiste alors en un ensemble d'attracteurs, mais les calculer dans le cas général est coûteux. Une approche bien connue pour obtenir les points fixes (i.e. les attracteurs de taille 1) consiste à résoudre un problème SAT équivalent. Afin de calculer les autres attracteurs, je présenterai un algorithme dû à E. Dubrova et M. Teslenko, également basé sur l'utilisation de SAT-solver (bounded model checking).
217. Vendredi 31 janvier 2014 à 14h30
     salle de conférence (I3S)

     Normalité et automates

     Olivier Carton LIAFA, Paris 7

     We strengthen the theorem that establishes that deterministic finite transducers can not compress normal infinite words. We prove that, indeed, non-deterministic finite transducers, even augmented with a fixed number of counters, can not compress normal infinite words. However, there are push-down non-deterministic transducers that can compress normal infinite words. We also obtain new results on the preservation of normality with automata selectors. Complementing Agafonov's theorem for prefix selectors, we show that suffix selectors also preserve normality. However, there are simple two-sided selectors that do not preserve normality. Joint work with V. Becher and P. Heiber (University of Buenos Aires)
216. Jeudi 16 janvier 2014 à 10h00
     salle de réunion, 5ème étage au Petit Valrose

     Diffusion of innovations in random clustered networks with overlapping communities

     Emilie Coupechoux I3S, Sophia Antipolis

     We consider a threshold epidemic model on a clustered random graph with overlapping communities. In other words, our epidemic model is such that an individual becomes infected as soon as the proportion of her infected neighbors exceeds the threshold q of the epidemic. In our random graph model, each individual can belong to several communities. The distributions for the community sizes and the number of communities an individual belongs to are arbitrary. We consider the case where the epidemic starts from a single individual, and we prove a phase transition (when the parameter q of the model varies) for the appearance of a cascade, i.e. when the epidemic can be propagated to an infinite part of the population. More precisely, we show that our epidemic is entirely described by a multi-type (and alternating) branching process, and then we apply Sevastyanov's theorem about the phase transition of multi-type Galton-Watson branching processes.
217. du Jeudi 24 octobre au Vendredi 25 octobre 2013
     LIFO, Orléans

     12e rencontre FRAC

     Programme
215. Jeudi 17 octobre 2013 à 14h30
     salle de conférence (I3S)

     Classification of Reaction Systems

     Luca Manzoni I3S, Sophia Antipolis

     Reaction systems are a model of computation recently introduced by Ehrenfeucht and Rozenberg that is inspired by biochemical reactions involving reactants, inhibitors and products from a finite set of entities (chemical species). We define a notion of multi-step simulation among reaction systems and derive a classification with respect to the amount of resources (reactants and inhibitors) involved in each reaction. We prove that one reactant and one inhibitor per reaction suffice in order to simulate arbitrary systems. Finally, we show that the equivalence relation of mutual simulation induces exactly five linearly ordered classes of reaction systems characterising subclasses of the functions over finite Boolean lattices, like the additive, isotone, and antitone functions.
214. Jeudi 10 octobre 2013 à 14h00
     salle de réunion (I3S)

     Un modèle pour les graphes bipartis aléatoires avec redondance

     Emilie Coupechoux I3S, Sophia Antipolis

     Actuellement, les modèles de graphes aléatoires ne capturent pas toutes les propriétés connues des réseaux réels. En particulier, ils ne permettent pas à deux cliques d'avoir plusieurs noeuds en commun bien que ce soit une propriété observée dans les réseaux réels. Dans les réseaux sociaux par exemple, deux amis ont souvent plus d'un centre d'intérêt commun. Le modèle présenté ici vise à capturer ce genre de propriété. Plus précisément, nous présentons un modèle de graphe triparti aléatoire dont le projeté biparti possède des distributions de degrés et de redondances proches de ceux d'un graphe biparti donné.
213. Jeudi 26 septembre 2013 à 11h00
     salle de conférence (I3S)

     The firing squad problem: yesterday, today and tomorrow

     Jacques Mazoyer ENS Lyon
212. Jeudi 26 septembre 2013 à 11h45
     salle de conférence (I3S)

     Some families of generalized firing squad algorithms

     Hiroshi Umeo Université d'Osaka
210. Jeudi 13 juin 2013 à 10h30
     salle de conférence (I3S)

     Causal graph dynamics: Physical and algorithmic approach

     Simon Martiel I3S, Sophia Antipolis

     Causal graph dynamics is a model of computation which generalizes cellular automata to arbitrary graphs. In this model, the vertices of the graph are considered as computation nodes and the dynamics only depends upon the neighbor's states. These local dynamics are run in parallel and synchronously within discrete time steps and provide a global dynamics on the graph. The originality of this model is that the graph's topology can also be changed during the computation, in the sense of graph rewriting. In this talk we present two different approaches of this model.In a first time, we will show how the model can be restricted in order to constructively characterize physical transformations of two dimensional surfaces. We use the formalism of simplicial complexes to define discrete surfaces and we define a correspondance between graphs and oriented complexes to see any graph transformation as a surface transformation. We then add a constraint to ensure the causality of the transformation regarding to the geometrical distances on the surface. In a second time, we present a result of intrinsic universality of the model. Intrinsic universality is the ability of an instance of a model to simulate every other instance of the model while preserving the structure of the computation at every step of the simulation. We will present a universal machine together with a universal local rule that are able to construct and intrinsically simulate every instance of causal graph dynamics with some fixed parameters.
209. Jeudi 25 avril 2013 à 15h00
     salle de conférence (I3S)

     Epidémies dans des graphes aléatoires avec clustering

     Emilie Coupechoux LIP6, Paris

     Nous considérons un modèle d'épidémie à seuil issu de la théorie des jeux (Morris, 2000), et qui permet de modéliser notamment la propagation d'une nouvelle technologie dans un réseau. Le réseau social sur lequel se propage l'épidémie est modélisé par un graphe aléatoire avec clustering (la propriété de clustering traduit le fait que deux individus d'un réseau social ayant un ami commun ont tendance à être également amis entre eux). Nous nous intéressons au cas où l'épidémie part initialement d'un seul individu choisi au hasard dans la population. Lorsque l'épidémie se propage à une grande partie de la population (le nombre d'individus infectés est supposé croître au cours du temps), on dit qu'une cascade se produit. Nous prouvons une transition de phase pour le phénomène de cascade (lorsque le paramètre de l'épidémie varie). A l'aide d'évaluations numériques, nous en déduisons l'impact du clustering sur la propagation de l'épidémie.

     Travail effectué sous la direction de Marc Lelarge.

208. Jeudi 04 avril 2013 à 14h00
     salle de réunion (I3S)

     Introduction à la calculabilité 2 - La structure des degrés Turing

     Grégory Lafitte LIRMM, Montpellier

     Nous poursuivrons l'introduction à la calculabilité proposée par Christophe Papazian en donnant un aperçu de la structure induite par la réduction Turing sur la famille des ensembles d'entiers, en particulier ceux qui sont récursivement énumérables.
207. Jeudi 28 mars 2013 à 11h15
     salle de conférence (I3S)

     Ensembles limite d'automates cellulaires

     Alexis Ballier CMM, Universidad de Chile

     Les automates cellulaires (AC) servent souvent de modèles desystèmes dynamiques discrets ou comme modèles de calcul et constituentun système complexe: Une définition locale simple mais un comportementglobal difficile à prédire.Nous nous intéresserons ainsi à leur comportement à long terme: Lesétats du système atteignables arbitrairement tard lors de leurévolution, c'est à dire l'ensemble limite de l'automate cellulaire.Si un AC atteint son ensemble limite au bout d'un temps fini il est dit"stable", dans le cas contraire il est dit "instable".Nous montrerons brièvement comment, en collaboration avec PierreGuillon et Jarkko Kari, nous avons obtenu le premier exemple d'ensemblelimite atteignable à la fois par un AC stable et un (autre) AC instable.Ce résultat a donné lieu à une conjecture sur une possiblecaractérisation des ensembles limite d'ACs stables. Par la suitenous montrerons que les ensembles limite ayant la propriété conjecturéenécessaire correspondent aux ensembles limite d'un certain typed'automates cellulaires stables. Le problème de savoir si tous lesensembles limite d'AC stables peuvent être atteints par ces ACs stablesparticuliers reste cependant ouvert.
206. Mercredi 20 mars 2013 à 14h30
     salle de conférence (I3S)

     Introduction to Data Clustering

     Francesco Masulli Universita di Genova

     A combination of various technological, scientific and economic factors is leading our society to invest ever more in collecting and analyzing data at scales of quantity and detail unimaginable until recently, in fields ranging from economics to biology, astronomy, physics, and Internet. Following David L. Donoho, this century may be called, to good account, the "Century of Data". One of the most important families of techniques for data mining is the clustering. Clustering allows us to perform unsupervised data analysis in situations where the labeling of data is very expensive or impossible, or when the available labeling of data is ambiguous, or when we need to improve our understanding of the nature of data, or even when we want to reduce the number of data (better, the amount of information) to be transmitted
     or stored. The course presents an introduction to the current clustering techniques for unsupervised data analysis.

     Program:

     - Introduction to Clustering

     - Hierarchical Clustering

     - Central Clustering

     - Mixtures of densities

     - K-Means

     - Vector Quantization

     - Self Organizing Maps

     - Fuzzy sets

     - Fuzzy Clustering

     - Kernel Clustering

     - Clustering Ensemble

     - Evolutionary algorithms and clustering

     - Biclustering

     - Comparison of partitions.

205. Jeudi 07 mars 2013 à 10h30
     salle de conférence (I3S)

     Degrés Turing des SFTs

     Pascal Vanier Einstein institute, Hebrew University of Jerusalem

     Si l'on s'intéresse aux Sous-shifts de Type Fini (SFTs) d'un point de vue calculatoire, ceux-ci sont des classes $\Pi^0_1$, un objet bien connu de la théorie de la calculabilité : il s'agit des ensembles de suites sur lesquels une machine de Turing donnée ne s'arrête pas. Nous nous intéressons en particulier à savoir à quel point les classes $\Pi^0_1$ et les SFTs sont similaires. Un premier pas dans ce sens a été effectué par Simpson qui a prouvé que les degrés Medvedev des deux objets étaient les mêmes. Dans cet exposé, nous nous intéressons à une notion plus fine, qui est l'ensemble des degrés Turing. Dans un premier temps nous allons montrer que pour toute classe $\Pi^0_1$ il existe un SFT lui étant quasi-isomorphe récursivement. Ceci a pour conséquence que l'on peut construire des SFTs ayant le même ensemble de degrés Turing que n'importe quelle classe $\Pi^0_1$ au degré 0 près. Puis nous montrons que lorsque l'ensemble de degrés Turing d'un SFT ne contient pas 0, il contient nécessairement un cône de degrés Turing, ce qui montre que certains ensembles de degrés Turing de classes $\Pi^0_1$ ne sont pas réalisables à l'aide de SFTs.
204. Mardi 05 mars 2013 à 15h00
     salle de réunion (I3S)

     Automates cellulaires et applications à la morphogenèse

     Alexandra Fronville Université de Brest

     Exposé informel.
203. Jeudi 21 février 2013 à 14h30
     salle de réunion (I3S)

     Introduction à la calculabilité 1

     Christophe Papazian I3S, Sophia Antipolis

     Dans ce premier GdT nous allons présenter les bases de la calculabilité ainsi que les liens entre calculabilité et logique. Nous tenterons d'aborder cette problématique à la fois d'un point de vue épistémologique et d'un point de vue algorithmique.Ce groupe de travail est destiné tant aux néophytes curieux qu'aux chercheurs intéressés par ce domaine.
202. Jeudi 21 février 2013 à 11h00
     salle de conférence (I3S)

     Generalized Cayley Graphs and Cellular Automata over them

     Pablo Arrighi IMAG, Grenoble

     Cellular Automata can be characterized as the translation-invariant continuous functions, where continuity is with respect to a certain distance over the set of configurations. This distance, and its properties, easily extend from grids to Cayley graphs. As a consequence, Cellular Automata also extend from grids to Cayley graphs. Cayley graphs have a number of useful features: the ability to graphically represent finitely generated group elements and their equality; to name all vertices relative to a point; the fact that they have a well-defined notion of translation, and that they can be endowed with such a compact metric. But they are very regular. We propose a notion of graph associated to a language, which conserves or generalizes these features. These associated graphs can be arbitrary, although of a bounded degree. We extend Cellular Automata to these Generalized Cayley graphs, so that they define a local dynamics over time-varying graphs.
201. Jeudi 14 février 2013 à 10h30
     salle de conférence (I3S)

     The Hardy paradox and the nonlocality of symmetric states

     Zizhu Wang Telecom ParisTech

     Nonlocality is one of the most striking and controversial features of quantum mechanics. The first nonlocality test, devised by John Bell in the 60s, involves the violation of an inequality of expectation values obtained from measuring physical observables. Although this remains the most common nonlocality test today, other tests do exist. Lucien Hardy proposed an "almost probability-free" test of nonlocality in the form of a logical paradox in addition to an inequality. This Hardy paradox is shown by Hardy to hold for almost all bipartite entangled states. We show that the extended version of the paradox holds for almost all permutation symmetric states. The nonlocality of all permutation symmetric states can be established via the violation of a single inequality. Joint work with Damian Markham. Reference:

      http://link.aps.org/doi/10.1103/PhysRevLett.108.210407 (eprint: http://arxiv.org/abs/1112.3695).

200. salle de réunion (I3S)

     Accession optimale au coeur dans les jeux coopératifs

     Eric Rémila LIP, Université de Lyon

     (travail en commun avec S. Béal et P. Solal) Je rappellerai le cadre des jeux coopératifs : un jeu coopératif consiste en une valeur, attribuée chaque coalition de joueurs. On se pose ensuite la question de la rétribution des joueurs. Une proposition de rétribution satisfaisant des critère minimaux de rationalité est appelée une imputation. Le coeur d'un jeu est une notion classique, c'est l'ensemble des imputations ou aucune coalition n'est frustrée (une coalition est frustrée si elle reçoit moins que ce que sa valeur). Quand une coalition est frustrée elle peut imposer une nouvelle allocation où elle n'est pas frustrée. Un tel changement d'allocation est appelé un bloc. La question de l'accessibilité du coeur est la suivante : à partir de n'importe quel imputation, peut-on atteindre le coeur par une succession de blocs ? Autrement dit, plus informellement, peut-on arriver à une situation stable ? Une réponse positive a été donnée par Sengupta (dans le cas où le coeur est non vide, bien sûr). Mais la preuve donnée ne donne aucune information sur la longueur de la suite de bloc nécessaires pour arriver au coeur. Différents papiers ont précédemment donné des bornes supérieures assez énormes. Récemment, nous sommes arrivés à une borne en n^2, (n désigne le nombre de joueurs). Nous venons d'améliorer le résultat précédent en arrivant à la borne n-1. De plus cette borne est optimale. La preuve est étonnamment simple est repose sur une réduction classique des jeux.
199. Jeudi 10 mai 2012 à 14h30
     salle de réunion (I3S)

     Automated Validation of Internet Security Protocols using AVISPA

     Sheikh Ziauddin I3S, Sophia Antipolis

     Manual analysis of internet security protocols is time consuming and error prone therefore an automated tool for doing security analysis has a great appeal. In this talk, I will present a tool for automated analysis of internet security protocols named AVISPA. I will talk about the features of AVISPA and its architecture with an emphasis on High Level Protocol Specification Language (HLPSL) which is the language used to write protocol specifications for AVISPA. The application of the tool will be illustrated using a sample protocol which will also contain protocol simulation, automated attack simulation, building interactive attacks and analysis of attack traces.
198. Jeudi 26 avril 2012 à 14h30
     salle de conférence (I3S)

     On non-standard string matching: problems and algorithms

     Zsuzsanna Lipták Università di Verona, Italie

     In recent years, many new string problems have been introduced which are motivated by applications from molecular biology, but which are also of independent interest. In this talk, I will discuss two of these: weighted string matching and jumbled string matching. The classical exact string matching problem is: Given a string s over a (finite) alphabet and a query string t, find all occurrences of t as substring of s. In weighted string matching, every character of the alphabet is assigned a (real or integer) weight (or mass), and the query is a (real or integer) number, the query mass: We want to find all occurrences of substrings whose total mass equals the query. In jumbled string matching, we have a standard alphabet but the query is a "jumbled string": the vector specifying the multiplicities of each character, also called Parikh vector. For example, with w(a)=2, w(b)=3 and w(c)=5, the string s=abacab has three occurrences of mass 7, and three occurrences of the Parikh vector (2,1,1). Both of these problems can be viewed as special cases of approximate string matching. I will talk about different approaches and algorithms for several variants of these problems. I will also sketch the connections to a certain class of binary strings, the prefix normal strings. A binary string s is prefix normal if, for every k \leq |s|, no substring of length k has more a's than the prefix of length k. For example, aababaaab is not prefix normal because the substring aaa has more a's than the prefix aab. Using the prefix normal forms of a string, it is possible to answer quickly jumbled pattern matching queries.
197. Jeudi 19 avril 2012 à 15h00
     salle de réunion (I3S)

     Transducteurs bidirectionnels

     Olivier Carton LIAFA, Paris 7

     Dans cet exposé, on considère des transducteurs bidirectionnels à bande de sortie bidirectionnelle. À chaque cellule de la bande d'entrée correspond une cellule de la bande de sortie. À chaque transition, le transducteur lit une cellule de la bande d'entrée et soit laisse inchangé la cellule correspondant de la bande de sortie ou écrit un mot qui remplace le contenu précédent. Nous montrons que chaque relation réalisée par un tel transducteur est rationnelle. Elle peut être réalisée par un transducteur de gauche à droite. Nous montrons également que toute fonction rationnelle peut être réalisée par un transducteur bidirectionnel déterministe.
196. Jeudi 05 avril 2012 à 14h30
     salle de conférence (I3S)

     Cellular automata between sofic tree shifts

     Francesca Fiorenzi LRI, Orsay

     In this talk we illustrate some results about cellular automata on a finitely generated free monoid $\Sigma^*$, that is, on a regular rooted tree. This includes the characterization of sofic tree shifts in terms of unrestricted Rabin automata and the decidability of the surjectivity problem for cellular automata between sofic tree shifts. (This is a joint work with Tullio Ceccherini-Silberstein, Michel Coornaert and Zoran Sunic.)
195. Jeudi 16 février 2012 à 15h30
     salle de conférence (I3S)

     Planar Configurations Induced by Exact Polyominoes

     Daniela Battaglino Università di Siena, Italie

     An unknown planar discrete set of points A can be inspected by means of a probe P of generic shape that moves around it, and reveals, for each position, the number of its elements as a magnifying glass. All the data collected during this process can be naturally arranged in an integer matrix that we call the scan of the starting set A w.r.t. the probe P. When the probe is a rectangle, a set A whose scan is homogeneous shows a strong periodical behavior, and can be decomposed into smaller homogeneous subsets. Here we extend this result, which has been conjectured true for all the exact polyominoes, to the class of diamonds, and we furnish experimental evidence of the decomposition theorem for exact polyominoes of small dimension, using the mathematical software Sage.
194. Jeudi 16 février 2012 à 14h30
     salle de conférence (I3S)

     String inference from integer arrays

     Arnaud Lefebvre LITIS, Rouen

     In different research area such as string matching or indexing problems, many algorithms generate integer arrays reflecting combinatorial properties of strings. Our problem is that given an integer array and a combinatorial property, are we able to infer the corresponding string(s). We will see some solutions and discuss possible applications and open problems.
193. Jeudi 09 février 2012 à 14h30
     salle de conférence (I3S)

     Particle dynamics in cellular automata: known results and open questions

     Enrico Formenti I3S, Sophia Antipolis

     tba
192. Jeudi 19 janvier 2012 à 14h30
     salle de conférence (I3S)

     Modélisation spatiale et déplacements pédestres

     Fabrice Decoupigny Université de Nice - Sophia Antipolis

     A partir de différentes observations effectuées aux cours d’études de fréquentations, nous avons pu mettre au point un modèle de simulation des déplacements de visiteurs sur un espace naturel régional (modèle FRED). La modélisation des déplacements pédestres consiste à créer un automate cellulaire pour simuler les cheminements pédestres sur un graphe sous contrainte de pénibilité liée aux conditions géomorphologiques. On définit un espace praticable formé de nœuds accessibles ou pas, en fonction de la pente et des caractéristiques géomorphologiques. Ensuite nous calculons par un automate cellulaire tous les chemins pouvant exister entre les parkings et les curiosités naturelles en fonction d'une double contrainte, la distance et la pénibilité de la pente. Deux hypothèses de cheminement sont programmées soit au plus court soit au plus facile. Exemple de simulation de cheminements pédestres sur la Vallée des Merveilles du parc national du Mercantour.
191. salle de conférence (I3S)

     Soutenance de thèse : Des codes pour engendrer les langages de mots infinis

     Tran Vinh Duc I3S, Sophia Antipolis

     Le sujet de cette thèse est l'étude des langages de mots infinis, en particulier les puissances infinies de langages de mots finis (puissance w). Plus précisément, nous nous intéressons à la question ouverte suivante: étant donné un langage L, existe-t-il un w-code C tel que C^w = L^w ? Cette question est l'analogue de celle pour la concaténation finie: un sous-monoïde d'un monoïde libre est-il engendré par un code ou non ? Dans un premier temps, nous étudions l'ensemble des relateurs d'un langage L, c'est-à-dire les couples de factorisations différentes d'un même mot de L^* + L^w ; nous établissons une condition nécessaire pour que L^w ait un code ou un w-code générateur. Ensuite, nous définissons une nouvelle classe de langages : les langages à un relateur. Leurs ensemble de relateurs est le plus simple possible sans qu'ils soient des codes. Pour cette classe intéressante de langages, on caractérise les langages L tels qu'il existe un w-code ou un code C tels que L^w = C^w. On montre que C ne peut pas être un langage fini. Enfin, une caractérisation des codes concernant les mots infinis nous amène à définir les langages réduits; nous considérons les propriétés de ces langages en tant que générateurs de langages de mots infinis.
190. Vendredi 16 décembre 2011 à 10h00
     salle de conférence (I3S)

     Complexité abélienne

     Gwénaël Richomme LIRMM, Montpellier

     La complexité abélienne d'un mot infini w est la fonction qui associe à chaque entier n le nombre de vecteurs de Parikh des facteurs de w. Nous présentons une synthèse de résultats sur ce sujet, notamment ceux obtenus avec J. Cassaigne, K. Saari et L.Q. Zamboni : propriétés de base, complexités de quelques mots célèbres, liens avec les puissances abéliennes, ...
189. Jeudi 08 décembre 2011 à 14h30
     salle de conférence (I3S)

     Classification des règles de rayon 2 d'automates cellulaires élémentaires vis à vis de la résilience

     Bruno Martin I3S, Sophia Antipolis

     Nous étudions les règles d'automates cellulaires élémentaires vis à vis de la résilience en nous appuyant sur des travaux sur les fonctions booléennes. Cela nous permet de trouver des règles d'automates cellulaires élémentaires qui satisfont les critères de 1-résilience jusqu'au rayon deux. Nous nous intéresserons également aux transformations qui préservent la résilience et nous discuterons de deux expérimentations. La première sur la préservation de propriétés aléatoires et la seconde sur la génération de suites aléatoires. Ces qualités sont mesurées au moyen de tests statistiques.
188. Jeudi 27 octobre 2011 à 14h30
     salle de conférence (I3S)

     Complexity of Non-Uniform Cellular Automata

     Julien Provillard I3S, Sophia Antipolis

     Nu-CA are cellular automata which can have different local rules at each site of their lattice. Indeed, the spatial distribution of local rules completely characterizes Nu-CA. In this talk, we will interest to sets of distributions inducing Nu-CA which share some properties. When we use a finite number of local rules to define distributions, these sets are associated with languages of bi-infinite words. The complexity classes of these languages are investigated for several classical properties, namely number conserving, surjectivity, injectivity, equicontinuity and sensitivity to initial conditions.
187. Jeudi 20 octobre 2011 à 11h00
     Colloquium Jacques Morgenstern (INRIA)

     Réseaux d'automates : trente ans de recherche

     Eric Goles Universidad Adolfo Ibáñez, Santiago du Chili
186. Jeudi 13 octobre 2011 à 15h30
     salle de conférence (I3S)

     Minimal uncompletable words

     Sandrine Julia I3S, Sophia Antipolis

     Given a rational set X, we investigate the set of uncompletable words in X*. These words cannot appear as factor of any word in X*. Some of them are minimal uncompletable as soon as all their proper factors are factors of some words in X*. We study the deep structure of the set of minimal uncompletable words and then focus on the finite case. We find a quadratic upper bound for the length of the shortest minimal uncompletable words in terms of the length of the longest words in X.
185. Jeudi 29 septembre 2011 à 13h00
     salle de conférence (I3S)

     Yet Another Talk on Sub-Computabilities

     Grégory Lafitte LIF, Marseille

     I will talk about new links to old work on sub-recursivity, which have shed new light on the relevance of sub-computabilities.
184. Mercredi 28 septembre 2011 à 13h30
     salle 4/2 Bat. TP Physique (Valrose)

     Stochastic modelling of biological systems: membrane systems in Systems Biology

     Giancarlo Mauri Università di Milano-Bicocca

     The talk will survey the main definitions and properties of membrane systems, or P-systems, introduced by G. Paun as a bioinspired model of computation. Furthermore, an extension of P-systems with stochastic features, and their application to modelling some biological systems, in the frame of systems biology will be presented. It will be explained why and how stochastic modelling, Genetic Algorithms and Communicating Classes integrate each other and well fit in the investigation of biological systems.
183. salle de conférence (I3S)

     Statistics of entry times in a cellular automaton with annihilating particles

     Petr Kůrka Charles University, Prague

     The dynamics of some Cellular Automaton can be understood as the dynamic of signal or particles which move in a neutral background and interact on encounters. We derive the asymptotic distribution of appearance of particles at a given site in a CA with annihilating particles.
184. Jeudi 23 juin 2011 à 09h15
     Espaces Antipolis, Sophia

     Journée du pôle MDSC

     Programme
182. Jeudi 16 juin 2011 à 10h30
     salle de conférence (I3S)

     Systèmes à membranes: modèle de calcul et outil de modélisation biologique

     Serghei Verlan LACL, Paris

     Les systèmes à membranes (P systems) sont un modèle de calcul inspiré par la structure et le fonctionnement de la cellule vivante. Ils présentent un moyen convenable pour décrire l'expression formelle des différents processus cellulaires et la réécriture parallèle des multiensembles. L'exposé se concentrera sur les 3 points suivants: 1) la présentation générale le modèle, les liens avec des modèles similaires comme la réécriture des multiensembles et les réseaux de Petri, 2) la présentation (rapide) des classes principales des systèmes à membranes, 3) l'utilisation du formalisme des systèmes à membranes pour la formalisation (discrète) des processus biologiques.
181. Jeudi 19 mai 2011 à 10h30
     salle de conférence (I3S)

     Descriptional Complexity and Regular Languages

     Giovanni Pighizzini Università di Milano-Bicocca

     Descriptional complexity investigates formal systems as, for instance, automata and grammars, with the aim of comparing their relative succinctness. Several variants of finite automata (e.g., one-way/two-way, deterministic/nondeterministic) have been proposed in the literature. All of them characterize the class of regular languages. However, their descriptional powers are different: the descriptions of a same regular language by two different models can have different sizes. In this talk we present some descriptional complexity results related to regular languages. In particular, we discuss the problem posed by Sakoda and Sipser in 1978 concerning the optimal simulation of two-way nondeterministic finite automata by two-way deterministic finite automata, which is still open, and the use of context-free grammars for the description of regular languages. Some aspects related to unary languages, i.e., languages defined over a one letter alphabet, will be also presented.
180. Jeudi 12 mai 2011 à 13h30
     salle de conférence (I3S)

     Kadanoff sandpile model: in pursuit of a wave pattern

     Kevin Perrot ENS Lyon

     Sandpile 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 Organized Criticality (SOC), the property that a small perturbation - adding some sand grains - on a stable configuration has uncontrolled consequences on the system, involving an arbitrary number of grain fall. We will concentrate on Kadanoff sandpile model and try to convey today's ideas on how to handle its sharp SOC behavior. The main objective is to prove the experimentally checked emergence of a wave pattern issued from complexity.
179. Jeudi 12 mai 2011 à 15h00
     salle de conférence (I3S)

     Computational Aspects of Asynchronous CA

     Jérôme Chandesris

     In this talk we consider some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are universal, i.e., allowing a (specific family of) ACA to simulate any TM on any input. We also consider the computational cost of such simulations.
178. Jeudi 21 avril 2011 à 14h00
     salle de conférence (I3S)

     Points, Distances and Cellular Automata: Geometric and Spatial Algorithmics

     Luidnel Maignan INRIA, Paris - Rocquencourt

     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 step towards generic computation, we propose to develop primitives allowing to structure the medium around a set of particles. We consider three problems of geometrical nature: moving the particles on the grid in order to uniformize the density, constructing their convex hull, constructing a connected proximity graph establishing connection between nearest particles. The last two problems are considered for multidimensional grid while uniformization is solved specifically for the one dimensional grid. The work approach is to consider the metric space underlying the cellular automata topology and construct generic mathematical object based solely on this metric. As a result, the algorithms derived from the properties of those objects, generalize over arbitrary regular grid. We implemented the usual ones, including hexagonal, 4 neighbors, and 8 neighbors square grid. All the solutions are based on the same basic component: the distance field, which associates to each site of the space its distance to the nearest particle. While the distance values are not bounded, it is shown that the difference between the values of neighboring sites is bounded, enabling encoding of the gradient into a finite state field. Our algorithms are expressed in terms of movements according to such gradient, and also detecting patterns in the gradient, and can thus be encoded in finite state automata, using only a dozen of state.
177. Jeudi 21 avril 2011 à 15h30
     salle de conférence (I3S)

     Particules dans les automates cellulaires

     Benjamin Hellouin De Menibus ENS Lyon

     A la fois modèle de calcul et système dynamique discret, les automates cellulaires sont surtout un modèle de système complexe : la grande simplicité de sa définition contraste avec la complexité des comportements observés. Pour les automates en 1 dimension, les simulations suggèrent une classification en trois catégories : les automates qui convergent vers une configuration fixe ou au comportement très simple; les automates chaotiques, qui ne présentent aucune forme d'auto-organisation apparente; enfin, une troisième catégorie qui présente un mode d'auto-organisation non trivial. Les comportements des automates de cette troisième catégorie présentent des similitudes : régions constituées de motifs réguliers persistant dans le temps, frontières se comportant comme des particules (propagation, interaction, etc.). Dans cette présentation, je m'efforcerai de donner un sens à toutes ces notions, et de montrer comment on peut les utiliser pour prouver des résultats sur le comportement de tels automates en régime stationnaire.
176. Jeudi 14 avril 2011 à 14h00
     salle de conférence (I3S)

     New LFSRs and FCSRs representations for stream ciphers hardware and software design

     Marine Minier INSA Lyon

     In this talk, we will sum up our recent research results concerning the introduction of a new representation for FCSRs based upon a known LFSRs representation. This matrix based representation allows to construct FCSRs with a more compact hardware representation and a quicker diffusion while preserving the usual and proven good properties (good periods, l-sequences, good statistical behaviors, etc.). Moreover, this new approach circumvents the weaknesses of the Fibonacci and Galois representations. We also show how to extend the LFSRs representation to a particular LFSR case called the windmill case. LFSRs are well-known primitives used in cryptography especially for stream cipher design. However they have some drawbacks when looking at their resistance against algebraic attacks because of their linearity. In the contrary, FCSRs are inherently resistant to algebraic attacks due to the non-linearity of the update function. Using the new representation, we propose two new stream ciphers based on the so-called ring FCSR representation. The first proposal called F-FCSR is dedicated to hardware applications whereas the second proposal called X-FCSR is designed for software purposes but is also efficient in hardware.
175. Jeudi 24 mars 2011 à 14h00
     salle de conférence (I3S)

     Algorithmes d'Euclide multidimensionnels et géométrie discrète

     Valérie Berthé LIAFA, Paris 7

     Les plans arithmétiques discrets sont obtenus en sélectionnant des points à coordonées entières situés à une certaine distance (épaisseur) d'un plan euclidien donné. L'algorithme des fractions continues permet une description complète des propriétés combinatoires, arithmétiques et dynamiques des droites discrètes. La situation est moins claire en dimension supérieure du fait de l'absence d'algorithme de fractions continues multidimensionnel canonique. Le but de cet exposé est néanmoins de montrer comment des algorithmes d'Euclide multidimensionnels classiques permettent de décrire de nombreuses propriétés des plans discrets, ainsi que d'établir des algorithmes d'engendrement ou de reconnaissance, même dans le cas d'une épaisseur quelconque. La stratégie sous-jacente consiste à traduire des développements en fractions continues multidimensionnels en termes symboliques, à travers la notion de substitution.
174. Jeudi 17 mars 2011 à 14h00
     salle de conférence (I3S)

     Dynamique des machines à une tête

     Pierre Guillon IML, Marseille

     A toute machine de Turing on peut associer plusieurs types de systèmes dynamiques symboliques, notamment le sous-shift contenant la suite des états pris par la tête et des caractères qu'elle lit, et topologiques, notamment, les modèles à tête mobile et à ruban mobile. Nous allons voir quelques liens entre la restriction des mouvements qu'on autorise pour la tête de lecture, la complexité du langage du sous-shift et les points d'équicontinuité dans les deux derniers systèmes.
173. Jeudi 03 mars 2011
     DISCO, Università di Milano-Bicocca, Italie

     Meeting on "Topology and Computer Science"

      

     Topology was born as an independent discipline more than one century ago. Today it represents one of the main branches of mathematical research. The aim of this day-long workshop is to present the influence and the use of topologies inside some fields of computer science.
172. Jeudi 24 février 2011 à 14h00
     salle de conférence (I3S)

     On continuous Cellular Automata

     Julien Cervelle LACL, Paris

     This talk is about a result which allows to turn a cellular automata into a partial differential equation system. We first present this result and illustrate it with some examples. Then we give an analysis about the relation between the two ways of modeling a phenomenon based on local interactions as well as intermediate models such as sand automata or stochastic cellular automata.
171. Jeudi 17 février 2011 à 14h00
     salle de conférence (I3S)

     Construction of μ-limit Sets

     Laurent Boyer LAMA, Chambéry

     The µ-limit set of a cellular automaton is a subshift whose forbidden patterns are exactly those, whose probabilities tend to zero as time tends to infinity. For a given subshift in a large class of subshifts, we propose the construction of a cellular automaton which realizes this subshift as µ-limit set where µ is the uniform Bernoulli measure.
170. Jeudi 03 février 2011 à 14h00
     salle de conférence (I3S)

     Algorithmes pour la recherche de périodes Abéliennes dans les mots

     Gabriele Fici

     La notion de période Abélienne a récemment été introduite pour capturer les aspects de répétition avec permutation des lettres dans les mots. Nous montrons qu'un mot fini peut avoir un nombre de périodes Abéliennes distinctes qui est quadratique en sa longueur. Nous discutons ensuite des algorithmes off-line et on-line pour la recherche des périodes Abéliennes dans un mot fini.
171. Vendredi 28 janvier 2011 à 14h00
     Marseille

     Rencontre PEPS "Chaos" - Approche épistémologique à la notion de chaos

      
172. du Mercredi 15 décembre au Vendredi 17 décembre 2010
     Turku (Finlande)

     JAC 2010 - Second international symposium on Cellular Automata

      
169. Jeudi 25 novembre 2010 à 14h00
     salle de conférence (I3S)

     Sub-computabilities

     Grégory Lafitte LIF, Marseille

     tba
168. Jeudi 18 novembre 2010 à 14h00
     salle de conférence (I3S)

     Polyominoes determined by permutations

     Simone Rinaldi Università degli Studi di Siena

     Let P be a polyomino without holes having n rows and columns, n>=1. We say that P is a permutomino if, for each abscissa (ordinate) between 1 and n, there is exactly one vertical (horizontal) side in the boundary of P with that coordinate, and n is called the size of the permutomino. We study enumeration of column-convex polyominoes according to their size by determining a direct recursive construction for the convex permutominoes of a given size, such that every column-convex permutomino of size n+1 is uniquely obtained from a column-convex permutomino of size n. Using the technique of generating trees our construction can be easily translated into a functional equation. Moreover, we obtain enumerative results concerning some subclasses of convex permutominoes, both in an analytic and in a bijective way.
167. Jeudi 04 novembre 2010 à 14h00
     salle de réunion (I3S)

     Rough sets and three valued connectives

     Davide Ciucci Università di Milano-Bicocca

     Rough sets were defined almost 30 years ago by Z. Pawlak as an instrument to deal with uncertainty due to incompleteness of the available information. Since the begging attempts to relate them to three valued logics and algebraic semantics have been carried out. After showing the relationship among three-valued sets and rough sets, we introduce a systematic study of truth-functional connectives which are definable on these two collections. We discuss tsignificance of truth-functionality on rough sets showing that, while the mathematical underpinnings are sound, the application of these logics for reasoning about data-tables containing incomplete descriptions is not straightforward. Finally, we give an overview of the rough-sets algebraic structures.
166. Jeudi 14 octobre 2010 à 14h00
     salle de conférence (I3S)

     Implémentation de l'Universalité sur Automates Cellulaires

     Jean-Baptiste Yunès LIAFA, Paris 7

     Nous montrerons comment l'universalité intrinsèque est obtenue en s'affranchissant du diagramme espace-temps d'un automate cellulaire. Cette abstraction consiste à ne considérer que les causalités nécessaire au calcul. Les causalités sont projetées sur une grille (espace-temps d'un automate cellulaire ayant la propriété de conserver les dépendances). Ces grilles sont flexibles et nous permettent d'envisager pouvoir considérer la compilation de programmes vers une architecture massivement parallèle.
165. Jeudi 07 octobre 2010 à 12h30
     salle de réunion (I3S)

     On deterministic asynchronous automata

     Enrico Formenti

     Asynchronous Cellular Automata (ACA) are receiving more and more attention as formal models for physical and biological phenomena. Historically they were introduced as a formal model for concurrent systems. In the first part of this talk we will briefly review these historical models for ACA and make the transition to fully deterministic ACA. Afterwards we will review some basic results about deterministic ACA and their relations to classical cellular automata.
166. Mardi 21 septembre 2010 à 14h00
     Ascoli Piceno (Italy)

     Workshop ACA - First international workshop on Asynchronous Cellular Automata

      
164. Jeudi 16 septembre 2010 à 14h00
     salle de conférence (I3S)

     Adding a referee to an interconnection network: what can(not) be computed in one round?

     Ivan Rapaport DIM, Universidad de Chile

     In this talk we will analyze which properties of a distributed network can be computed from a few amount of local information provided by its nodes. Each of these n nodes -which only knows its own ID and the IDs of its neighbors- is allowed to send a message of O(log n) bits to some central entity, called the referee. Is it possible for the referee to decide some basic structural properties of the network topology G? We show that simple questions like "does G contain a triangle (resp., a square)?" cannot be solved in general. On the other hand, the referee can decode the messages in order to have full knowledge of G when G belongs to many graph classes such as planar graphs, bounded treewidth graphs and, more generally, bounded degeneracy graphs. We leave open questions related to the connectivity and the diameter (of arbitrary graphs).
163. Jeudi 29 juillet 2010 à 10h00
     salle de conférence (I3S)

     Communication complexity of monotone elementary cellular automata

     Eric Goles, Andrés Moreira Universidad de Chile

     We will present results on the one-shot communication complexity of the prediction problem for all number-conserving and monotone elementary cellular automata (all in all, about 1/4 of the ECA). We will also show how the communication complexity of arbitrary one-dimensional CA can be transfered to NCCA. lang=en
162. Mardi 22 juin 2010 à 10h00
     salle de réunion, 5ème étage au Petit Valrose

     Pavages et calculs

     Michael Weiss

     Les pavages de Wang sont un des modèles les plus simple de pavages et possèdent la particularité de pouvoir simuler du calcul Turing facilement; ils peuvent être vu comme un modèle de calcul. Il est donc naturel d'essayer de comprendre les propriétés de ce modèle. Le point central de l'exposé consistera à prouver un équivalent du théorème du point fixe pour les pavages. Nous montrerons ensuite les différentes applications de ce résultat théorique.
161. Jeudi 10 juin 2010 à 10h00
     salle I, Bâtiment Dieudonné, LJAD

     Pavages et automates

     Jarkko Kari Université de Turku
160. Mardi 04 mai 2010 à 11h00
     salle de réunion (I3S)

     Periodicity in tilings

     Pascal Vanier LIF, Marseille

     Tilings and tiling systems are an abstract concept that arise both as a computational model and as a dynamical system. We characterize here the sets of periods that a tiling system can produce. We prove that up to a slight recoding, they correspond exactly to languages in the complexity classes NSPACE(n) and NE.
159. Vendredi 30 avril 2010 à 14h00
     salle de réunion (I3S)

     Automates Cellulaires 2D : constructions et dynamique

     Alberto Dennunzio Università di Milano-Bicocca

     Les automates cellulaires (AC) sont des systèmes dynamiques à temps et espace discret. Ils sont l'un des modèles formels les plus utilisés pour étudier des systèmes complexes. Bien que les applications concernent principalement les AC en dimension 2 ou supérieure, les études formelles ont été menées surtout en dimension 1. Dans cet exposé je présente des résultats sur la dynamique des AC en dimension 2. Ces résultats sont obtenus par deux constructions qui permettent de considerer un AC en dimension 2 comme un AC en dimension 1.
158. Jeudi 22 avril 2010 à 13h45
     salle de conférence (I3S)

     Périodicité et pavages

     Emmanuel Jeandel LIF, Marseille

     Le premier problème fondamental de l'étude des pavages est appelé le Domino Problem: décider, étant donné un jeu de tuiles, si un pavage existe. Ce problème a été démontré indécidable par Berger en 1964. Afin de mieux comprendre ce problème, de nombreuses améliorations de ce résultat ont été produites au cours du temps. Nous nous intéresserons ici à un problème proche: décider si un jeu de tuiles produit un pavage périodique. De façon assez surprenante, toutes les preuves connues de ce résultat partent de démonstrations du domino problem, en raffinant les constructions qu'elles contiennet. Nous donnerons une nouvelle démonstration très simple de ce résultat qui montre que ce détour est inutile et que la seule clé est l'existence d'un pavage apériodique du plan.
157. Jeudi 01 avril 2010 à 11h00
     salle de conférence (I3S)

     Caractérisation des langages rationnels binaires géométriques

     Jérôme Chandesris

     La validation des applications temps-réel a introduit une nouvelle caractéristique de langage. Cette caractéristique est basé sur le lien entre deux types de modèles : les langages rationnels, et la géométrie discrète. Ce type de langage est nommé langage géométrique. Le but de mon étude au cours de mon stage a été de programmer une méthode afin de décider si un langage rationnel est géométrique et d'en étudié la distribution. La recherche de cette méthode a permis de développer un algorithme polynomial sur les langages binaires. Nous présenterons dans cet exposé cet algorithme, ainsi que les différentes optimisations. Une analyse de la proportion de ces langages à partir d'un échantillonnage conclura la présentation.
156. Jeudi 18 mars 2010 à 10h30
     salle de conférence (I3S)

     Families and omega-ambiguity removal

     Sandrine Julia

     We consider the following open problem: let L be a rational language, how to decide whether its w-power is generated by an w-code ? We investigate languages whose ambiguity and/or w-ambiguity are minimal. To do this, we introduce a notion of family over relations fulfilled by words. If L is finite, the number of families is finite. Each of them produces its proper set of incompatible prefixes. In case of a unique family, this leads to two twin languages that are candidates to be w-codes and w-generators if some exists.
155. Mardi 02 mars 2010 à 10h30
     salle de conférence (I3S)

     Quelques problèmes autour de la combinatoire des mots, des langages formels et des automates finis.

     Gabriele Fici

     Nous présenterons rapidement cinq sujets de recherche liés aux mots : 1) Les mots interdits minimaux et leurs applications. 2) Les systèmes splicing circulaires finis. 3) Les facteurs permutés. 4) Les mots différentiables. 5) Les liens entre la combinatoire des mots et les structures d'indexation. Nous allons en suite développer de plus près la théorie des mots différentiables et des mots lisses, et nous présenterons la construction d'un automate déterministe minimal qui reconnaît les facteurs des mots lisses. Cette construction est basée sur les mots interdits minimaux. On en derivera une borne supérieure polynomiale sur la longueur minimale d'une répetition d'un mot lisse. lang=fr
154. Mardi 02 mars 2010 à 11h30
     salle de conférence (I3S)

     Minorité stochastique sur les graphes

     Damien Regnault LIF, Marseille
153. Mardi 02 mars 2010 à 11h00
     salle de conférence (I3S)

     Pavages et sous-shift indénombrables

     Alexis Ballier LIF, Marseille
152. Jeudi 28 janvier 2010 à 10h30
     salle de conférence (I3S)

     Caractérisation des sous-shifts indénombrables

     Alexis Ballier LIF, Marseille

     Dans cet exposé nous nous intéresserons aux ensembles indénombrables de pavages. Les ensembles de pavages sont des cas particuliers d'une notion plus générale: les sous-shifts. Nous savons qu'un sous-shift est indénombrable si et seulement s'il a la cardinalité du continu; ceci découle du fait qu'un sous-shift indénombrable a un sous-ensemble parfait (ce qui constitue déjà une caractérisation). Ensuite nous essaierons de trouver les causes de l'indénombrabilité, en particulier quel type de configurations l'entrainent. Enfin, nous parviendrons à caractériser les sous-shifts indénombrables soit par l'existence de certains types de pavages soit par la façon dont on peut trouver les motifs dans les pavages. lang=fr
151. Jeudi 14 janvier 2010 à 14h00
     salle de conférence (I3S)

     A Residue Approach to the Finite Field Arithmetics (REPORTE)

     Jean-Claude Bajard LIP6, Paris

     Finite fields arithmetic is one of the challenges in current computer arithmetic. It occurs, in particular, in cryptography where the needs increase with the evolution of the technologies and also of the attacks.Through our research, we have proposed different systems based on residues representations. Different kinds of finite fields are concerned with. For each of them, some specificities of the representations are exploited to ensure the efficiency, as well as for the performances, than for the robustness to side channel attacks. In this paper, we deal with three similar approaches: the first one is dedicated to prime field using residue number systems, a seconde one concerns extension finite fields of characteristic two, the last one discusses of medium characteristic finite fields. The main interest of these systems is their inherent modularity, well suited for circuit implementations. lang=en
152. du Mardi 01 décembre au Vendredi 04 décembre 2009
     Petit chateau de Valrose

     Journées FRAC-SDA2-NAFIT

      
150. Jeudi 19 novembre 2009 à 14h00
     salle de conférence (I3S)

     Countable ordinals galore.

     Grégory Lafitte LIF, Marseille
149. Jeudi 29 octobre 2009 à 10h30
     salle de conférence (I3S)

     Stochastic analysis of a simple gene regulation network

     Siamak Taati

     I will talk about our recent work with Enrico, Gilles Bernot, and Jean-Paul Comet. We consider a simple network consisting only of two interacting genes: gene s and gene t. Gene s generates proteins of type S, which in turn activate gene t to generate proteins of type T. We build a simple stochastic model and analyze the dynamic of the concentration of proteins S and T with time. lang=en
148. Jeudi 08 octobre 2009 à 10h30
     salle de conférence (I3S)

     Minorité stochastique sur les graphes

     Damien Regnault LIF, Marseille

     Nous considérons un graphe où les cellules sont caractérisées par un état qui est soit noir, soit blanc. À chaque pas de temps, une cellule, choisie aléatoirement, se met à jour et passe dans l'état minoritaire dans son voisinage. L'évolution globale de ce processus ne semble pas dépendre de la topologie du graphe: dans un premier temps des régions, pavées par des motifs dépendant de la topologie du graphe, se forment rapidement. Puis dans un deuxième temps, les frontières entre ces régions évoluent jusqu'à devenir relativement stables. Nous étudions ce processus sous différentes topologies: arbres, anneaux, grilles, cliques. Ceci nous permet de montrer que même si ce processus se comporte à priori globalement de la même manière sur n'importe quel graphe, modifier la topologie influence la façon dont les régions sont pavées (rayures, damiers), la structure et les mouvements des frontières entre les régions, l'ensemble limite, le temps de relaxation (le temps nécessaire pour que le processus atteigne une configuration de l'ensemble limite). Ainsi, Minorité entraîne des comportements riches et variés qui se révèlent difficile à analyser. Comprendre cette règle simple est néanmoins nécessaire avant de considérer des règles plus compliquées.
147. Jeudi 01 octobre 2009 à 10h00
     salle de conférence (I3S)

     Soutenance de stages

     Etudiants M1 IFI
146. Jeudi 24 septembre 2009 à 10h30
     salle de conférence (I3S)

     On non-trivial relations and w-codes generators

     Tran Vinh Duc
145. Dimanche 09 août 2009 à 10h30
     salle de conférence (I3S)

     Natural Computing and Bioinformatics

     Franco Masulli Univ. di Genova, Italie, Temple Univ., Philadelphie, US

     Natural Computing studies the computing going on in Nature as well as the computing inspired by Nature. Over the past few years many Natural Computing strategies, ranging from Neural Networks, Evolutionary Computation, Fuzzy Sets, Support Vector Machines to Ant Colony Optimization, Particle Swarm Optimization, etc., have been successfully applied to the solution of complex problems including those proposed by Bioinformatics and Systems Biology. In this seminar I'll present some recent results obtained in the application of Natural Computing to the problems of class discovering, biomarker selection and genotyping using the DNA microarray technology. The proposed approaches exploit many Natural Computing methodologies, comprising clustering, classification, variable selection, image analysis, and ensembles of learning machines.
146. Lundi 29 juin 2009 à 09h15
     Espaces Antipolis, Sophia

     Première Journée du Pôle MDSC

      

     9h15 - 9h45	Accueil (café)
     9h45 - 10h00	Un mot sur le pôle, Michel Rueher
     10h00 - 10h30	Exposé CEP, Michel Rueher, "Recherche du bugs sous contraintes"
     10h30 -11h00	Exposé invité, Willem Jan van Hoeve,
     11h00 - 11h30	Pause café
     11h30 - 12h30	Présentation MC3, Bruno Martin, "L'aléatoire & l'informatique"
     12h30 - 14h00	Déjeuner
     14h00 - 15h00	Présentation BioInfo, Adrien Richard, "Circuits positifs et négatifs dans les modèles discrets de réseaux de gènes"
     15h00 - 15h30	Exposé invité, Eric Goles
     15h30 - 16h00	Pause café
     16h00 - 17h00	Présentation RL, Lionel Nicolas "Correction de lexiques linguistiques: une des applications du projet Victoria"
     17h00 - 18h30	Cocktail

144. Jeudi 18 juin 2009 à 10h30
     salle de conférence (I3S)

     What conservation laws may tell us about the dynamics of a cellular automaton? (part II)

     Siamak Taati

     I will talk about some restrictions that the existence of conservation laws imposes on the dynamical properties of a cellular automaton (CA). A trivial example is that a CA with a non-trivial conservation law cannot be nilpotent. A less trivial result is that a positively expansive CA cannot have any non-trivial conservation laws. Another result states that a surjective CA has a dense set of temporally periodic configurations, provided it conserves a real-valued energy with a unique ground configuration.
143. Jeudi 04 juin 2009 à 10h30
     salle de réunion (I3S)

     What conservation laws may tell us about the dynamics of a cellular automaton? (part I)

     Siamak Taati

     I will talk about some restrictions that the existence of conservation laws imposes on the dynamical properties of a cellular automaton (CA). A trivial example is that a CA with a non-trivial conservation law cannot be nilpotent. A less trivial result is that a positively expansive CA cannot have any non-trivial conservation laws. Another result states that a surjective CA has a dense set of temporally periodic configurations, provided it conserves a real-valued energy with a unique ground configuration.
142. Lundi 27 avril 2009 à 14h30
     salle de conférence (I3S)

     Virologie informatique

     Matthieu Kaczmarek LORIA

     Cet exposé aborde trois thèmes : la formalisation de la virologie informatique, l'élaboration de protections contre l'auto-reproduction et le problème de la détection des programmes malicieux. La formalisation s'appuie sur les fondements de l'informatique théorique et sur les travaux fondateurs de la discipline. Il résulte un cadre souple où le théorème de récursion prend le rôle d'un compilateur de virus informatiques. Ce théorème trouve alors la place qui lui manquait encore dans la théorie de la programmation. Sur ce formalisme, nous étudions deux pistes de protection. La première cible les capacités de calcul afin d'identifier un modèle raisonnable où l'auto-reproduction serait impossible. La seconde étudie les flux d'information en employant la complexité de Kolmogorov comme un outil reliant la sémantique et la syntaxe concrète des langages de programmation. Le thème de la détection comporte deux parties. La première traite de la difficulté de la détection des virus informatiques. La seconde aborde des aspects plus pratiques en décrivant un nouveau détecteur de programmes malicieux. Ce prototype utilise une détection morphologique, l'idée est de reconnaître la forme des programmes malicieux en utilisant des outils de l'analyse statique et dynamique.
141. Vendredi 17 avril 2009 à 10h30
     LJAD, Valrose

     Courbes elliptiques sur un anneau et applications cryptographiques (thèse)

     Marie Virat
140. Jeudi 16 avril 2009 à 14h30
     salle de conférence (I3S)

     Nouvelle classe de fonctions courbes en représentation polynomiale

     Sihem Mesnager LAGA, Paris 8 et 13

     Une fonction Booléenne est dite courbe si sa non-linéarité est maximale. Cela correspond à être à distance maximale pour la distance de Hamming de l'ensemble des fonctions booléennes affines, ou encore le code de Reed-Muller d'ordre 1. Les fonctions courbes n'existent qu'en dimension paire. Elles ont été largement étudiées en raison de leurs propriétés algébriques et combinatoires intéressantes ainsi qu'en en raison de leurs multiples applications et jouent un rôle important en cryptographie ainsi qu'en théorie des codes. / Classifier les fonctions courbes semblant sans espoir à ce jour, il a été proposé dans la littérature de nombreuses constructions de fonctions courbes définies sur le corps de Galois à 2^n éléments (n pair). Les constructions proposées sont principalement des fonctions courbes monomiales (c'est a dire dont l'expression est une la trace sur le corps fini à 2^n éléments d'une fonction puissance) . On ne connait que tres peu d'exemples de fonctions courbes non monomiales. / Dans cet exposé, je rappellerai d'abord l'importance des fonctions courbes en cryptographie symétrique et je présenterai l'état de l'art du domaine. Ensuite, je donnerai des résultats nouveaux à savoir une nouvelle famille infinie de fonctions courbes non monomiale (de degré algébrique optimal) définies sur le corps fini a 2^n éléments dont l'expression est la somme d'une trace sur le corps fini à 2^n éléments d'une fonction puissance d'exposant de Dillon (à savoir 2^{n/2}-1) et d'une fonction trace sur le corps fini à 4 éléments d'une fonction puissance dont l'exposant est (2^n-1)/3. Plus précisément, j'expliquerai que l'étude du caractère "courbe" d'une fonction de telle famille dépend de la parité de n/2 et je donnerai une caractérisation explicite pour le caractère "courbe" en termes de sommes de Kloosterman en s'appuyant sur les resulats récents de Charpin, Helleseth et Zinoviev sur les sommes de Kloosterman et les sommes cubiques.
139. Jeudi 09 avril 2009 à 14h30
     salle de conférence (I3S)

     Combinatoire des mots et conjecture de Fraenkel

     Laurent Vuillon LAMA, Chambéry

     Ce séminaire donnera les liens entre un problème de recouvrement des entiers et la combinatoire des mots afin d'étudier la conjecture de Fraenkel. Cette conjecture a été formulée dans le cadre de la théorie des nombres il y a maintenant plus de 30 ans. Elle prétend que pour k > 2 entier fixé, il y a une unique façon de recouvrir les entiers par $k$ suites de Beatty avec des fréquences deux à deux distinctes. Ce problème peut être exprimé en termes de combinatoire des mots de la façon suivante : pour un alphabet à k lettres, il existe une unique suite équilibrée avec des fréquences de lettres deux à deux distinctes qui est exactement la suite de Fraenkel notée $(F r_k )^omega$ où F r_k = F r_(k−1) k F r_(k−1), avec F r_3 = 1213121. Cette conjecture est prouvée pour k = 3, 4, 5, 6 d'après les travaux de Altman, Gaujal, Hordijk et Tijdeman ainsi que dans d'autres cas particuliers. Dans ce séminaire, nous présenterons donc une synthèse sur ce sujet et la résolution de la conjecture dans un cas particulier.
138. Jeudi 26 mars 2009 à 14h30
     salle de conférence (I3S)

     Recent Advances in the Design of Optimum-Time Synchronization Algorithms for Two-Dimensional Cellular Automata - A Survey -

     Hiroshi Umeo Univ. of Osaka Electro-Communication, Japan
137. Vendredi 13 mars 2009 à 10h30
     salle de conférence (I3S)

     Combinatoire des mots et structures de données

     Gabriele Fici DIA, Università di Salerno

     Il existe beaucoup de structures de données pour représenter un texte. Dans la recherche de motifs on utilise largement l'automate des suffixes, c.à.d. l'automate déterministe minimal qui accepte les suffixes d'un mot. On se pose le problème de relier la structure de l'automate des suffixes d'un mot aux propriétés combinatoires du mot. Par exemple on sait que la classe des mots binaires dont l'automate des suffixes est de complexité minimale coïncide avec la classe des préfixes des mots sturmiens standards. Dans cet exposé on s'occupera des propriétés combinatoires des mots qui peuvent être lues sur le graphe de l'automate des suffixes, et, symétriquement, on verra comment ce graphe est déterminé par certains paramètres combinatoires du mot.
138. du Mercredi 04 mars au Vendredi 06 mars 2009
     IGM, Marne-la-Vallée

     6e rencontre FRAC

      
136. Jeudi 19 février 2009 à 15h30
     salle de conférence (I3S)

     Pavages, universalité et calculs

     Michael Weiss FISLAB, Università di Milano-Bicocca

     La notion de pavage du plan est présente dans de nombreuses disciplines, dont les mathématiques, la physique, la chimie ou encore l'informatique. Le modèle utilisé ici est basé sur des carrés de taille unitaire dont les bords sont colorés. Deux tuiles peuvent s'assembler si leur côté commun ont la même couleur. Malgré sa simplicité, ce modèle peut simuler n'importe quelles autres notions de pavage du plan et depuis Berger en 64, nous savons que ce modèle peut aussi simuler du calcul Turing. Notre approche des pavages se fait donc d'un point de vue calculabilité en essayant d'établir des outils forts de calculabilité propres aux pavages et ainsi comprendre mieux le calcul qui se développe dans les structures naturelles géométriques. Nous nous intéresserons entre autres à deux notions de bases : dans un premier temps nous définirons les outils nous permettant d'obtenir des notions d'universalités propres aux pavages, et dans un deuxième temps, nous établirons un équivalent au théorème classique du point fixe de Kleene pour les pavages, et nous montrerons ses applications.
135. Jeudi 12 février 2009 à 15h00
     salle de conférence (I3S)

     Mots infinis et ensembles d'entiers reconnus par automates dénombrables

     Marion Le Gonidec Toulon

     Dans cet exposé, nous introduisons une classe de mots infinis engendrés par des automates dénombrables. Nous présentons des résultats structurels et des résultats de complexité pour cette famille. L'étude de ces mots nous a également amené à nous intéresser à la structure des ensembles d'entiers engendrés par automates finis ou dénombrables. Nous introduirons 2 familles distinctes de tels ensembles d'entiers. Les résultats obtenus sur ces familles mettront en lumière des phénomènes spécifiques au cas fini ou qui s'étendent (plus ou moins bien) au cas dénombrable.
134. Jeudi 18 décembre 2008 à 14h30

     Automates cellulaires à états continus

     Alexis Ballier LIF, Marseille

     Cet exposé présentera les travaux de P. Flocchini et H. Betel sur les automates cellulaires à états dans l'intervalle 0--1, quelquefois en tentant de les généraliser sans grand succès. La méthode utilisée pour obtenir des AC à états continus à partir d'AC à états booléens est de transformer la règle locale en fonction sur (0--1)^n et à valeurs dans 0--1. La transformation utilisée préserve de nombreuses propriétés de conservation de l'automate cellulaire de départ, notamment le fait d'être "Number conserving". Dans un second temps, nous présenterons un résultat général de convergence pour des AC à états continus particuliers : ceux effectuant une "moyenne" entre leur cellule et une cellule voisine. Enfin, nous montrerons comment étudier à partir de ces AC bien particuliers des AC à états continus plus généraux.
133. Jeudi 11 décembre 2008 à 14h00
     salle de conférence (I3S)

     Attaque algébrique et application au schéma de chiffrement à flot E_0

     Pierre-Louis Cayrel Paris 8

     Cette présentation donne un aperçu des systèmes de chiffrement à flot basés sur des LFSR (LFSR, LFSR filtré, LFSR avec mémoire) et décrit une amélioration des algorithmes permettant de déterminer l'existence ou non d'annulateurs de fonctions booléennes. Je termine par une application dans le cas du registre à décalage avec mémoire utilisé dans le système Bluetooth (E_0). Les résultats de nos travaux sont les suivants. Tout d'abord, nous donnons quelques améliorations pour le calcul des ensembles X_Z et un algorithme effectif simple pour le calcul de leurs annulateurs. Ensuite, nous utilisons ces améliorations pour exclure l'existence d'équations de degré 3 pour E_0 en considérant entre 5 et 9 tops d'horloge, ce qui est pour l'instant le meilleur résultat de non existence d'équation de bas degré pour E_0. Nous avons aussi trouvé 4 annulateurs de degré 4 ce qui nous permet de réduire la quantité de bits de clair nécessaire de 2^23 à 2^21 (travail réalisé avec Frederik Armknecht, Philippe Gaborit et Olivier Ruatta (BFCA 2007)).
134. du Lundi 01 décembre au Mercredi 03 décembre 2008
     véranda du Gd Château de Valrose, Nice

     5e rencontre FRAC : Systèmes complexes et modèles de calcul

      
132. Jeudi 27 novembre 2008 à 10h00
     salle de conférence (I3S)

     Cryptanalyse linéaire

     Abdou Wahidi Bello

     La cryptanalyse linéaire est une attaque à "texte clair connu" inventée par Mitsuru Matsui, chercheur chez Mitsubishi. Elle date de 1993 et fut développée à l’origine pour casser l’algorithme de chiffrement symétrique DES (Data Encryption Standard). Nous présentons cette approche de cryptanalyse dont l’idée consiste à trouver des relations linéaires de dépendance de probabilités exceptionnelles entre les bits d’entrée et de sortie des S-boîtes d’un réseau de Substitution-Permutation d’un système cryptographique à bloc tel le DES. Plus précisément, pour un message w = x(1)x(2) · · · x(n) en entrée d’une S-boîte et w' = S(w) = y(1)y(2) · · · y(n) le message à la sortie de la S-boîte, on cherche des relations du type x(i1)+ x(i2) + · · · + x(is) = y(j1) + y(j2) + · · · + y(jt) mod 2 qui sont vérifiées avec une forte ou faible probabilité.
131. Jeudi 30 octobre 2008 à 10h30
     salle de conférence (I3S)

     Complexité de communication des automates cellulaires

     Pierre-Etienne Meunier

     La complexité de communication est une mesure de complexité dûe à Yao, dans les années 70. Je présenterai les résultats de nos travaux sur la complexité de communication des automates cellulaires, et en particulier des automates cellulaires élémentaires. Les récents travaux de D. Woods et T. Neary sur la règle 110 justifient entre autres l'intérêt de ce type de questions. L'idée originale est dûe à Ivan Rapaport, et est exposée de manière détaillée dans l'article http://www.dim.uchile.cl/~rapaport/cc.pdf.
130. Jeudi 23 octobre 2008 à 10h30
     salle de conférence (I3S)

     Calculabilité des pavages

     Michael Weiss FISLAB, Università di Milano-Bicocca

     Au début des années 60, Wang a introduit un modèle de pavage du plan à l'aide de tuiles orientées de taille unitaire aux bords colorés pour résoudre des problèmes de logique. Ce modèle a été montré Turing-équivalent par Berger qui montra qu'un jeu de tuiles pouvait simuler une machine de Turing. Nous nous intéressons à la calculabilité de ce modèle en introduisant des outils sur les pavages permettant d'obtenir des résultats plus généraux sur les jeux de tuiles. A l'aide de notions de simulation, nous obtenons une première approche de l'universalité puis, nous montrons quelques uns des théorèmes fondamentaux de la calculabilité (Kleene, Rice...), dans le cadre des pavages, toujours relativement à certaines notions de simulation. Ces résultats nous permettront d'obtenir, dans un premier temps, de nouvelles preuves sur des théorèmes classiques des pavages et, dans un deuxième temps, de construire un cadre de construction de jeux de tuiles apériodiques.
129. Jeudi 09 octobre 2008 à 10h30
     salle de conférence (I3S)

     Reconnaissance de plan et fractions continues

     Thomas Fernique LIF, Marseille

     Une manière de stocker de manière économe un gros objet géométrique discret (images 3D acquises expérimentalement etc.) est de le vectoriser. Une façon de procéder est de le décomposer en plans discrets (approximations de plans euclidiens). Pour cela, un problème crucial est celui de la reconnaissance de plan : déterminer si un ensemble discret est ou non inclus dans un plan discret. Nous présentons une approche originale, qui généralise une approche similaire pour le cas de la reconnaissance de droites. Plus précisément, on montre comment calculer un développement en fraction continues multi-dimensionnel du vecteur normal d'un plan discret simplement en lisant les configurations locales de ce plan. Ce procédé peut alors être étendu à des ensembles discrets plus généraux, bien qu'ils n'aient pas forcément de vecteur normal. Les développements de plans possèdent cependant des propriétés qui permettent finalement de les reconnaître.
128. Jeudi 02 octobre 2008 à 09h45
     salle de conférence (I3S)

     Sur les points fixes du modèle de piles de sable symétrique en parallèle

     Phan Thi Ha Duong Paris 7 et Hanoï, Vietnam

     Le modèle de piles de sables (SPM) et ses extensions ont été beaucoup étudiés par plusieurs approches. Dans le modèle linéaire original introduit par Bak, Tang et Weisenfeld en 1987, la règle de mouvements constitue des transitions de gauche à droite et en séquentiel. L'étude de ce modèle en parallèle a été effectuée dans le cadre de l'étude des automates cellulaires (par Durand-Lose, etc). Récemment, le modèle SPM symétrique (SSPM) a été introduit (par Formenti et al. et Phan) en considérant les mouvements à deux directions : à droite et à gauche. Ce modèle présente la nature des mouvements de piles de sable et possède une structure beaucoup plus complexe que celui de SPM. Surtout, il est différent de SPM qui converge à un seul point fixe, ce nouvel modèle diverge à plusieurs points fixes. L'objectif de notre travail (en collaboration avec Formenti, Pham et Tran) est de considérer la complexité du modèle SPM symétrique en parallèle (PSSPM) à travers ses points fixes. Par des résultats expérimentaux, on a constaté que l'espace de PSSPM est beaucoup moins complexe que celui de SSPM, mais PSSPM possède un nombre important de points fixes. Le résultat principal de cet exposé est de montrer que PSSPM ont toutes les formes de points fixes de SSPM. Nous donnons une preuve formelle et un algorithme efficace pour illustrer les chemins les plus courts pour atteindre ces points fixes.
127. Jeudi 11 septembre 2008 à 10h30
     salle de conférence (I3S)

     Ambiguity of infinite words

     Sandrine Julia

     The ambiguous words in L^+ prevent the language L from being a code. Respectively, the ambiguous infinite words in L^w prevent a language L from being an w-code. This paper is an extensive study of these two sets in order to clarify their structures and also their links. In addition, we propose a restricted notion of ambiguity, the strong ambiguity coupled to its infinitary version. The aim is to refine the descriptions previously obtained. Indeed, finding appropriate representatives constitutes a challenge to go deeper inside open decidability problems like deciding whether a rational w-language is generated by a code or an w-code.
126. Jeudi 28 août 2008 à 10h30
     salle de réunion (I3S)

     On 'hand-made' three-dimensional cellular automata simulators and their

     Katsunobu Imai Hiroshima, Japan

     There are many simulation programs of various kinds of cellular automata (CA). In the two-dimensional case, there are some "killer applications" such as Golly. Such a multi-purpose simulator enables constructing rules and configurations without programming any new simulation tool. In the three-dimensional case, there are many simulation tools and even Mathematica also serves one as an example. But it is difficult to study three-dimensional cellular automata employing existing simulation tools. Because the configurations of three-dimensional CAs apt to be large and designing a user interface of intuitive and comprehensive manipulation of them is quite difficult. So quite a few developed tools are intend to simulate just a specific type of three-dimensional CA. We will show our several trials and illustrate why it is difficult to make a multi-purpose three-dimensional CA simulator.
125. Vendredi 08 août 2008 à 10h30
     salle de réunion (I3S)

     k-Bent functions and quadratic cryptanalysis of block ciphers

     Natalia N. Tokareva Sobolev Institute of Mathematics, Novosibirsk
124. Jeudi 17 juillet 2008 à 09h30
     salle de conférence (I3S)

     Entropie, Complexité et Information - Journée thématique I3S

     Programme
123. Mercredi 16 juillet 2008 à 10h30
     salle de réunion (I3S)

     Decidable properties of 2D cellular automata

     Alberto Dennunzio Università di Milano-Bicocca

     In this paper we study some decidable properties of two-dimensional cellular automata (2D CA). The notion of closingness is generalized to the 2D case and it is linked to permutivity and openness. The major contributions of this work are two deep constructions which have been fundamental in order to prove our new results and we strongly believe it will be a valuable tool for proving other new ones in the near future.
122. Mercredi 09 juillet 2008 à 14h30
     salle de réunion (I3S)

     Moebius number systems with sofic subshifts

     Petr Kůrka Charles University, Prague

     A real Moebius iterative system is an action of a free semigroup of finite words acting via Moebius transformations on the extended real line. Its convergence space consists of all infinite words, such that the images of the Cauchy measure by the prefixes of the word converge to a point measure. A Moebius number system consists of a Möbius iterative system and a sofic subshift included in the convergence space, such that any point measure can be obtained as the limit of some word of the subshift. We give some sufficient conditions on sofic subshifts to form Möbius number systems. We apply our results to several systems based on continued fractions.
121. Jeudi 03 juillet 2008 à 10h30
     salle de conférence (I3S)

     Automates cellulaires perturbés

     Julien Provillard ENS Lyon

     Dans cet exposé nous allons présenter de nouvelles classes intermédiaires entre les automates cellulaires et les fonctions continues dans l'espace de Cantor. Certaines de ces classes peuvent être interprétées comme des automates cellulaires perturbés (nouveaux objets obtenus par des modifications locales de la règle de transition de l'automate). Nous nous attachons à l'étude des propriétés dynamiques des automates cellulaires perturbés et à faire le lien avec les automates cellulaires classiques.
120. Jeudi 26 juin 2008 à 10h30
     salle de réunion (I3S)

     On the influence of symmetries to two-dimensional number-conserving cellular automata rules

     Katsunobu Imai Hiroshima, Japan

     A number-conserving cellular automaton (NCCA) is a cellular automaton such that all states of cells are represented by integers and the total number of the state of each cell of its configuration is conserved throughout its computing process. It can be thought as a kind of modelization of the physical conservation law of mass or energy. In this talk, we show the influence of symmetric conditions in the case of von Neumann neighborhood NCCA and show a design method of NCCA rules employing our result. We also discuss about the case of Moore neighborhood NCCAs.
119. Jeudi 29 mai 2008 à 14h30
     salle de réunion (I3S)

     Construction générale de fonctions pour débiaiser un générateur vraiment aléatoire

     Patrick Lacharme GRIM, Toulon

     Le biais est un problème statistique courant dans les générateurs aléatoires physiques. Dans cet exposé, on propose des constructions générales de fonctions choisies pour réduire fortement ce biais. Ces constructions ont des tailles d'entrée et des taux de compressions variables et sont efficaces à implanter. Mots clés : générateur vraiment aléatoire, biais, fonctions booléennes, codes correcteurs d'erreurs, transformée de Walsh, fonctions résilientes, entropie minimale.
118. Jeudi 22 mai 2008 à 14h30
     salle de réunion (I3S)

     Enumération d'une famille de tuiles rectilignes verticalement convexes

     Christiane Bercoff LIF, Marseille

     Le problème de l'énumération des polyominos est encore hors de notre portée. Le problème du dénombrement des tuiles rectilignes qui généralisent les polyominos l'est tout autant. Par contre, il existe plusieurs résultats concernant des sous-classes de polyominos définies par contraintes. Une de ces conditions concerne la convexité. Ici nous étendons la convexité partielle à une famille de tuiles rectilignes particulières, appelées e-serpents, e étant un entier strictement positif. Un e-serpent est une tuile rectiligne verticalement convexe composée de c colonnes de e cellules adjacentes (cellules ayant une arête en commun). Ainsi un e-serpent est contenu dans un rectangle dit circonscrit. On note l_b (resp. r_b) le sommet le plus bas du contour d'un e-serpent qui appartient au côté gauche (resp. droit) du rectangle circonscrit. On montre qu'un e-serpent est un pseudo-carré et si e est strictement supérieur à 1, il est à la fois un pseudo-carré et un pseudo-hexagone (au sens de Beauquier et Nivat). En d'autres termes, un e-serpent est une tuile pavant le plan par translation. Une ligne polygonale tracée sur le réseau à mailles carrées (ici dans le sens trigonométrique) est codée sur l'alphabet des déplacements d'une unité sur le réseau. La propriété principale du contour d'un e-serpent est qu'il est entièrement défini par sa ligne polygonale inférieure l_b r_b et que cette ligne se code, de manière univoque, par un mot de longueur c défini sur les entiers, où chaque lettre représente l'ordonnée inférieure de chacune de ses colonnes. Ceci nous permet de construire récursivement, pour e fixé, l'ensemble des codages de longueur c des e-serpents (ayant c colonnes). en appliquant des règles d'extension locales aux codages de longueur c-1 : ceci est une méthode de type ECO (introduite par Barcucci et ses co-auteurs). Ensuite, on définit une prototuile comme étant le représentant de la classe des quatre isométries d'un e-serpent, à savoir : l'identité, les symétries horizontale et verticale et la rotation d'angle pi. On montre alors que les classes d'isométries de l'ensemble des prototuiles de e-serpents ayant c colonnes sont décrites d'une part, par les codages palindromiques et d'autre part, par les codages dont la ligne polygonale associée est invariante par la rotation d'angle pi. Ce qui conduit au résultat combinatoire de cet exposé.
117. Vendredi 18 avril 2008 à 10h00
     salle de conférence (I3S)

     Propriétés et interactions sur des réseaux booléens

     Eric Goles Chili

     Étant donné un réseau booléen fini, on choisit un mode d'actualisation du réseau : synchrone, séquentiel, par bloces, etc. Il est clair que les points fixes sont invariants vis-à-vis du mode d'itération, mais ce n'est pas pareil pour les cycles. On va présenter des résultats qui permettent de mieux comprendre l'apparition (ou la disparition) des cycles, et aussi la notion de "filtre" qui permet, étant donné un réseau initial qui a au moins un point fixe, d'obtenir un réseau avec les mêmes points fixes mais sans aucun cycle. Ce type de résultat est intéressant pour la modélisation des réseaux d'interaction génétique.
116. Vendredi 28 mars 2008 à 14h30
     salle de réunion (I3S)

     Suites aléatoires, pseudo-aléatoires et quasi-aléatoires

     Bruno Martin I3S, Sophia Antipolis

     Dans cet exposé, nous présenterons une caractérisation combinatoire des suites aléatoires et nous dirons pourquoi celles-ci ne peuvent pas être engendrées par un procédé effectif. Nous donnerons ensuite quelques caractérisations des suites pseudo-aléatoires et quasi-aléatoires, utilisables respectivement pour des applications cryptographiques et des méthodes de Monte-Carlo.
115. Jeudi 21 février 2008 à 14h30
     salle de réunion (I3S)

     Lois de conservation dans les automates cellulaires (AC)

     Enrico Formenti I3S, Sophia Antipolis

     Après un petit panorama des résultats connus, je présenterai une nouvelle formalisation des lois de conservation permettant d'exprimer la notion de "Lois de conservation la plus générale" pour un AC. L'exposé terminera avec la preuve d'indécidabilité du problème d'établir si un AC donné possède ou non une loi de conservation non-triviale.
114. Lundi 04 février 2008 à 14h30
     salle de réunion (I3S)

     Les piles de sable de A à Z

     Benoît Masson LIF, Marseille
113. Jeudi 13 décembre 2007 à 14h00
     salle de réunion (I3S)

     Problème de "Timing Closure" pour les systèmes-sur-puce

     Robert de Simone INRIA, Sophia-Antipolis Méditerranée

     Le prétexte initial de ce travail vient de la conception actuelle des Systèmes-sur-Puce, à base de composants synchrones (dits "IP"). Les temps de propagation des signaux globaux (entre composants) dans le système introduisent des latences entières, qui ne permettent plus une approche synchrone globale (problème dit de "Timing Closure"). Dans un premier temps, nous montrons comment ce problème se formalise par des Graphes d'Evènements Marqués (Marked Event Graphs) à l'aide d'une expansion des latences ainsi que des places bornées de capacité 2 utilisées comme station-relais pour segmenter les connexions globales. Ensuite nous rappelons des résultats classiques (et d'application plus large que ce contexte spécifique de System-on-Chip), qui établissent l'existence d'ordonnancements statiques réguliers (dits "ultimement k-périodiques dans la littérature). Ces résultats sont essentiellement dûs à Carlier-Chrétienne (1988) et Baccelli-Cohen-Olsder-Quadrat (1992). Une syntaxe explicite a été introduite récemment (Pouzet-Cohen 2006) pour représenter explicitement de tels ordonnancements sous la forme de mots binaires infinis. Notre problème est désormais de reconstruire une version optimisée du réseau d'interconnexion, en simplifiant les ressources et la signalisation de contrôle de flux induite par la "bornitude" des stations-relais. L'objectif est d'agir sur la forme des séquences d'initialisation, afin d'obtenir des "mots d'ordonnancement" les plus étals possibles (smoothness), c'est-à-dire dans lesquels la distribution des 0 et des 1 soit la mieux répartie. Ces hypothèses doivent mener à une minimisation des ressouurces exploitées et à un résultat de clôture sur l'espace des ordonnancements. Si le temps le permet on décrira enfin une extension au modèle (différente des réseaux de Petri généraux, plutôt influencée par le non déterminisme interne et confluent des réseaux de Kahn), afin d'introduire des noeuds de routage alternatif dans les descriptions de systèmes. Les conditions d'aiguillage sont elles-mêmes des mots binaires ultimement périodiques, et le problème devient celui de savoir combiner routages et ordonancements k-périodiques. Nous possédons une axiomatique complète pour les (réseaux acycliques de) noeuds Select/Merge permettant d'y définir des formes normales d'expressions.
112. Jeudi 25 octobre 2007 à 15h00
     salle de réunion (I3S)

     Automates des suffixes et mots interdits minimaux

     Gabriele Fici DIA, Università di Salerno

     L'automate des suffixes (appelé aussi DAWG) d'un mot fini w est l'automate déterministe minimal qui reconnaît le langage des facteurs de w. Un mot fini v est dit interdit minimal pour w s'il n'est pas facteur de w et lorsque tous les facteurs de v sont en revanche facteurs de w. L'ensemble des mots interdits minimaux de w permet de reconstruire toute l'information sur les facteurs du mot w, ainsi que son automate des suffixes. Quelques applications des mots interdits minimaux seront aussi présentées.
111. Jeudi 11 octobre 2007 à 15h30
     salle de réunion (I3S)

     Nilpotence des automates de sable

     Benoît Masson LIF, Marseille

     Dans cet exposé nous étudierons la nilpotence des automates de sable. Après avoir vu que la définition classique n’avait pas de sens, nous définirons une nouvelle notion plus souple : un automate est nilpotent s’il rapproche chaque configuration bornée d’une configuration constante. Puis nous montrerons que cette propriété est indécidable, en simulant un automate cellulaire éparpillant (spreading en VO) croisé avec un automate de sable nilpotent.
110. Jeudi 20 septembre 2007 à 13h45
     salle de réunion (I3S)

     Approximation de grammaires algébriques pour l'analyse syntaxique et la vérification

     Sylvain Schmitz I3S, Sophia Antipolis

     La thèse s'intéresse au problème de l'analyse syntaxique pour les langages de programmation. Si ce sujet a déjà été traité à maintes reprises, et bien que des outils performants pour la génération d'analyseurs syntaxiques existent et soient largement employés, l'implémentation de la partie frontale d'un compilateur reste encore extrèmement complexe.Ainsi, si le texte d'un programme informatique se doit de n'avoir qu'une seule interprétation possible, l'analyse des langages de programmation, fondée sur une grammaire algébrique, est, pour sa part, le plus souvent non déterministe, voire ambiguë. Confrontés aux insuffisances des analyseurs déterministes traditionnels, les développeurs de parties frontales se sont tournés massivement vers des techniques d'analyse générale, à même d'explorer des choix nondéterministes, mais aussi au prix de la garantie d'avoir bien traité toutes les ambiguïtés grammaticales. Une difficulté majeure dans l'implémentation d'un compilateur réside alors dans l'identification (non décidable en général) et le traitement de ces ambiguïtés. Les techniques décrites dans la thèse s'articulent autour d'approximations des grammaires à deux fins. L'une est la génération d'analyseurs syntaxiques non canoniques, qui sont moins sensibles aux difficultés grammaticales, en particulier parce qu'ils peuvent exploiter un langage algébrique non fini en guise de contexte droit pour résoudre un choix non déterministe. Ces analyseurs rétablissent la garantie de non ambiguïté de la grammaire, et en sus assurent un traitement en temps linéaire du texte à analyser. L'autre est la détection d'ambiguïté en tant que telle, avec l'assurance qu'une grammaire acceptée est bien non ambiguë quel que soit le degré d'approximation employé.
109. Vendredi 07 septembre 2007 à 14h30
     salle de réunion (I3S)

     Throughput of context-free languages

     Wojciech Fraczak Canada

     Let 'A' be a finite alphabet with a weight function r: A -> N, where 'N' is the set of positive integers. The weight function extends onto non-empty words in the natural way, e.g., r(aba) = r(a)+r(b)+r(a)... The "mean weight" of a non-empty word "w" is defined as r(w)/w , where w is the length of the word. given a non-empty language L over A, we define "throughput" of L as the infimum of the mean weight of all non-empty words of L. In our talk, we will describe a polynomial time algorithm computing the throughput of context-free languages. The algorithm is applicable in the context of system-performance analysis, particularly in the context of network packet processing. The essential criterion for the evaluation of a system is the measure of its worst case speed of processing data, i.e., its "throughput". More precisely, this criterion is the lower bound (the infimum) of the greatest ratio of the length of processed input packet to its processing time, taken over all possible input packets. In some cases, a simple system allows a representation by a regular language (a finite automaton) with each alphabet symbol representing a constant time "task" consuming a constant amount of packet data. In such a case the standard algorithms for minimum mean cycle calculation are used. In practice, however, especially when more complex systems are analyzed and a better accuracy is required, context-free grammars have to be used to adequately describe the behavior of the systems. As a consequence, the practical worst case throughput computation of a system is equivalent to the context-free grammar throughput computation.
110. du Lundi 02 juillet au Mercredi 04 juillet 2007
     IGM, Marne-la-Vallée

     Workshop on Symbolic Dynamics and Coding (WSDC 2007)

      
111. du Jeudi 28 juin au Vendredi 29 juin 2007
     Campus Valrose (Nice)

     FRAC d'été 2007

      
108. Jeudi 31 mai 2007 à 14h30
     salle de réunion (I3S)

     Stable Sand Pile Model

     Tran Huong

     In this talk we present the stability of Sand Pile Model by simulating mathematically it as a discrete dynamical system where the evolution rule consists of the adding one grain on a random column and an avalanche to reach a stable configuration. We prove that the infinite set of all stable configurations have a lattice structure which is a sub-lattice of Young lattice. Moreover the formulas for the real times to reach stable configurations are given. At the end, we construct a generating tree of this model and show its strongly recursive structure.
107. Jeudi 24 mai 2007 à 14h30
     salle de réunion (I3S)

     Attracteurs sous-shifts des automates cellulaires

     Petr Kůrka

     On donne la caractérisation des attracteurs des automates cellulaires qui sont sous-shifts. On décrit une méthode de construction des attracteurs sous-shifts en utilisant le concept de sous-shifts des signaux.
106. Jeudi 15 février 2007 à 14h30
     salle 309 (EPU)

     Incomplétude de Gödel en informatique

     Grégory Lafitte

     Nous parlerons de calculabilités généralisées permettant de définir de nouvelles complexités à la Kolmogorov-Chaitin et de préciser les liens entre incomplétude et calcul.
105. Jeudi 18 janvier 2007 à 14h30
     salle 309 (EPU)

     Dynamique directionnelle : une propagation spatio-temporelle de l'information

     Mathieu Sablik

     Un automate cellulaire peut être défini comme une fonction continue F sur AZ qui commute avec le décalage σ. Généralement, lorsqu'on étudie un automate cellulaire, on considère seulement la N-action engendrée par l'automate cellulaire F sans se préoccuper du décalage σ. Cependant, le diagramme espace-temps de l'automate cellulaire (AZ; F) n'est pas si différent de celui de (AZ; F ο σm) pour m ∈ Z. Comme F et σ commutent, on peut s'intéresser à la N × Z-action (F; σ) afin de mettre en évidence la structure spatio-temporelle que l'on observe dans les diagrammes espace-temps. L'étude de l'action (F; σ) dans sa totalité n'est pas pertinente car σ a une dynamique trop forte, on est donc amené à étudier la dynamique dans des directions données. S'inspirant des travaux de M. Boyle et D. Lind sur les directions d'expansivité pour une Zd-action quelconque, nous définissons les différentes notions de sensibilité aux conditions initales suivant une direction. Je me suis alors intéressé à caractériser l'ensemble des directions d'équicontinuité (respectivement contenant des points d'équicontinuité, d'expansivité et de μ-presque équicontinuité). Cela fait apparaître une géométrie discrète dans les diagrammes espace-temps. On montre que si l'automate cellulaire a une direction d'expansivité alors il y a un cône ouvert de directions pour lesquelles l'automate cellulaire est expansif. Cela montre qu'il y a alors un fort transfert d'information puisque chacune de ces directions contient l'information contenue dans la configuration initiale. À l'opposé, si l'automate cellulaire a une direction contenant des points d'équicontinuité, alors l'information se propage uniquement suivant cette direction ; et si il y a une autre direction d'équicontinuité, toute propagation d'information est annihilée, l'automate cellulaire évolue vers une configuration uniforme. De plus les bornes de ces ensembles de directions, qui vérifient une certaine propriété dynamique, révèlent des propriétés algorithmiques profondes des automates cellulaires. Par example, dans le cas des directions équicontinues, on peut construire des exemples afin de réaliser toutes les directions rationnelles, cependant il est impossible de construire un exemple avec une direction irrationnelle. Il reste encore de nombreuses questions ouvertes autour de ces ensembles.
104. Mercredi 13 décembre 2006 à 11h00
     salle 310 (EPU)

     Soutenance de thèse : Des piles de sable aux automates de sable

     Benoît Masson

     Dans cette thèse nous étudions différents systèmes dynamiques discrets permettant de simuler la formation des piles de sable. Le comportement des modèles de base SPM ou IPM(k) est bien connu dans des conditions initiales spécifiques. Nous étendons ces résultats à des conditions initiales plus générales, et nous introduisons le modèle SSPM qui ajoute de la symétrie à ces modèles et améliore leur réalisme. Dans un second temps, nous étudions un autre système dynamique, les automates de sable. Ils sont définis de manière analogue aux automates cellulaires, avec la contrainte supplémentaire qu'une configuration n'admet pas de « trous ». Ces automates peuvent simuler tous les modèles de piles de sable définis localement, et à l'aide d'un cadre mathématique solide, ils permettent d'obtenir des résultats plus généraux. Nous nous intéressons à la dynamique des automates de sable, plus précisément aux propriétés de réversibilité d'un automate, et nous étudions la décidabilité de propriétés caractérisant les piles de sable classiques : conservation des grains et périodicité ultime.
103. Jeudi 30 novembre 2006 à 14h00
     salle 309 (EPU)

     Générateurs pseudo-aléatoires sur les anneaux de Galois

     Pierre Liardet & Dimitri Zinoviev

     We provide a new construction of nonlinear pseudorandom numbers generators. We use the inversive congruential method over Galois rings. This generalizes both the work of Niederreiter et al. over finite fields and Eichenauer-hermann et al over integers modulo a power of two. The main proof technique to bound the discrepancy from above is the local Weil bound on hybrid character sums over Galois rings.
102. Jeudi 23 novembre 2006 à 14h30
     salle 307 (EPU)

     Un voyage dans le monde des automates cellulaires : ascenseur et glissements

     Alberto Dennunzio

     L'ingrédient principal d'un automate cellulaire est une règle finie f: Ad+1 → A. La même règle engendre plusieurs automates cellulaires sur les espaces AZ et AN. On étudie les relations entre les propriétés dynamiques de ces différents automates cellulaires, qui partagent la même règle.
101. Jeudi 16 novembre 2006 à 14h45
     salle 307 (EPU)

     Algorithme des paires équilibrées pour les langages substitutifs

     Julien Bernat

     Sous des hypothèses algébriques, certains systèmes dynamiques symboliques associés à des substitutions peuvent admettre une représentation géométrique. Dans ce cas, on peut établir des liens entre des propriétés de nature combinatoire, géométrique ou ergodique, et formuler de nombreuses questions encore non résolues. Dans cet exposé, nous nous intéressons à l'étude de propriétés combinatoires. Après avoir rappelé les notions utiles à l'étude de systèmes substitutifs, nous montrerons comment l'étude des paires équilibrées irréductibles permet d'obtenir des informations sur l'algorithme des paires équilibrées. Nous nous intéresserons plus particulièrement aux cas des langages sturmiens, d'Arnoux-Rauzy, puis nous nous intéresserons à une représentation géométrique discrète permettant d'étudier une classe de langages substitutifs.
100. Jeudi 02 novembre 2006 à 14h30
     salle 311 (EPU)

     Pavage du plan par translation

     Xavier Provençal
99. Jeudi 28 septembre 2006 à 14h30
    salle 303 (EPU)

    ω-puissance d'un code ? ω-puissance d'un langage réduit ?

    Sandrine Julia

    Dans le cadre de la théorie des langages et des automates, nous nous intéressons aux langages rationnels de mots de longueur infinie i.e. ceux reconnus par les automates de Büchi. Un tel langage peut être engendré à partir d'un langage rationnel classique (i.e. de mots finis) en appliquant à ses mots l'opération de concaténation infinie, appelée puissance ω. Quid des langages qui, par concaténation infinie, redonnent un langage infinitaire donné ? Nombre de problèmes de décision se posent sur cet ensemble de langages appelé ensemble des générateurs. Les codes sont les plus connus des langages car ils garantissent le décodage unique des mots. Existe-t-il un code parmi les générateurs ? Le problème est ouvert. Nous n'avons montré que très récemment qu'il n'en existe pas forcément. La recherche des codes nous a amenés à définir une nouvelle classe de langages, les langages réduits. Les codes en font partie et l'idée est de réduire des générateurs choisis pour éventuellement trouver un code. Pour l'instant, si cette méthode ne nous fournit pas un code, il semble qu'il n'y en ait pas.
98. Jeudi 07 septembre 2006 à 14h30
    salle 302 (EPU)

    Traces sofiques

    Pierre Guillon

    Un automate cellulaire A trace un sous-shift (uni-directionnel) S quand S est l'ensemble de toutes les colonnes apparaissant dans les différentes évolutions de A. En termes de dynamique symbolique, on dit que S est un facteur de A. Dans cet exposé on donnera une condition suffisante pour qu'un sous-shift uni-directionnel soit tracé par un automate cellulaire.
97. Vendredi 30 juin 2006 à 10h00
    salle 310 (ESSI)

    Construction de boîtes elliptiques de substitution

    Franck Leprévost

    Les cryptosystèmes par blocs, tels l'AES ou FOX, utilisent de manière essentielle des fonctions de substitutions sur 8 bits. Ces fonctions doivent présenter une bonne résistance à la cryptanalyse linéaire et différentielle. Plus récemment, une nouvelle classe d'attaques, dite XSL, utilisent des relations algébriques de petit degré (essentiellement quadratiques) reliant les entrées et les sorties de fonctions de substitution. Dans cet exposé, nous présentons succinctement des mesures de résistance des fonctions de substitution à la cryptanalyse linéaire, différentielle et algébrique. Puis nous rappelons les valeurs de ces mesures pour les fonctions de substitution utilisées dans l'AES, et dans FOX. En utilisant des courbes elliptiques définies sur des corps finis, nous obtenons de nouvelles fonctions de substitution, ayant une résistance à la cryptanalyse linéaire et différentielle moins bonne que dans le cas de l'AES, mais meilleure que dans celui de FOX. Nous montrons aussi que ces boîtes de substitution, que nous appelons elliptiques, ne présentent pas du tout le flan à des attaques du type XSL, à la différence de l'AES et de FOX. Des exemples simples, et des résultats numériques seront présentés.
96. Jeudi 27 avril 2006 à 15h45
    salle 307 (ESSI)

    Cryptanalyse linéaire des algorithmes de chiffrement par bloc

    Michaël Quisquater

    Les algorithmes de chiffrement par bloc sont abondamment utilisés dans les communications modernes et assurent la confidentalité des données. Un algorithme de chiffrement par bloc est une permutation dépendant d'un paramètre appelé clé secrète. Différentes méthodes ont été proposées pour mettre en défaut la sécurite de ces algorithmes. Parmi les méthodes statistiques, on retrouve notamment la cryptanalyse linéaire et différentielle. Ces méthodes se basent sur la recherche d'expressions simples appelées caractéristiques. Ces expressions sont probabilistes et donnent de l'information sur la clé secrète à partir de paires clair/chiffré. L'évaluation de l'efficacité de ces méthodes permet de mettre en évidence les propriétés algébriques auxquelles les composantes de l'algorithme de chiffrement doivent satisfaire afin de rendre l'algorithme le plus résistant possible aux attaques connues. Nous commencerons l'exposé par une brève introduction à la cryptographie. Nous décrirons ensuite les réseaux de Feistel, une des classes importantes d'algorithmes de chiffrement par bloc dont le précédent standard américain DES fait partie. Nous poursuivrons l'exposé en esquissant les principes de la cryptanalyse linéaire. En outre, nous présenterons une généralisation de cette méthode développée par Biryukov, De Cannière et moi-même et publiée à la conférence Crypto 2004. Nous terminerons par un bref rappel de théorie de Fourier et nous décrirons les critères de conception induits par la cryptanalyse linéaire.
95. Jeudi 27 avril 2006 à 14h30
    salle 307 (ESSI)

    Ensembles de Kerdock

    Philippe Langevin
94. Jeudi 16 mars 2006 à 15h30
    salle 307 (ESSI)

    Un algorithme optimal pour détecter les pseudo-carrés

    Xavier Provençal

    Nous considérons le problème de déterminer si un polyomino, codé par un mot représentant son bord, pave le plan par translations. Beauquier et Nivat ont montré que les pièces qui permettent de tel pavages correspondent soit à un pseudo-carré, soit à un pseudo-hexagone. Nous verrons un algorithme permettant de déterminer si un polyomino correspond à un pseudo-carré en temps linéaire.
93. Jeudi 02 mars 2006 à 15h30
    salle 311 (ESSI)

    Tic Tac Toe on a finite plane

    Steven Dougherty

    Everyone knows how to play tic-tac-toe. On an n × n board, if a player places n of her marks either horizontally, vertically, or diagonally before her opponent can do the same, then she wins the game. What if we keep the rules of the game the same but increase the number of ways to win? Full article from Maureen T. Carroll's website
92. Jeudi 26 janvier 2006 à 14h30
    salle 310 (ESSI)

    Contribution à l'algorithmique des automates pondérés à une, deux ou plusieurs bandes

    Franck Guingne

    Je vais presenter les différents travaux effectués pendant ma thèse. Ces travaux se situent dans le cadre de la théorie des automates. Je parlerai de la notion de couverture d'automates ainsi que de son extension aux transducteurs. Les automates multi-bandes pondérés sont une généralisation des automates et transducteurs. Je définirai des opérations de jointure et d'auto-intersection et proposerai les algorithmes correspondants. J'exposerai les compilateurs d'états finis de XEROX, WFSC et XFST, à travers leurs spécificités ainsi qu'une étude de la complexité au pire des cas de l'impression de tous les chemins d'un automate acyclique. Je finirai par une description de mon sujet de recherche actuel.
91. Jeudi 10 novembre 2005 à 14h00
    ESSI

    Introduction aux mots lisses (II)

    Jean-Marc Fédou

    Suite du précédent exposé.
90. Jeudi 03 novembre 2005 à 14h00
    ESSI

    Introduction aux mots lisses (I)

    Srecko Brlek

    Généralités sur les mots Codages par blocs : Δ : N* -> N* Restriction de Δ à l'alphabet Σ = {1, 2} Points fixes de Δ = {1, K, 1·K} K n'est pas ultimement périodique : ne représente donc pas un nombre rationnel est-il "normal", possède-t-il les caractéristiques statistiques d'aléatoirité : - tout facteur apparaît-il infiniment souvent ? Notion de récurrence faible - à délai borné : récurrence faible - densité des 1 et des 2 Complexité : P(n) le nombre de facteurs, pas de formule exacte Définition de l'opérateur D et des facteurs C∞ Conjectures sur K : K est récurrent F(K) est fermé par permutation, c'est-à-dire l'opération qui permute les lettres de l'alphabet Note : b => a Les facteurs C∞ coïncident avec les F(K) Caractérisation des facteurs palindromes de K (article Brlek & Ladouceur) Description de la classe infinie des mots lisses : K n'est pas tout seul Résultats combinatoires : répétitions, palindromes, mots minimaux Conjectures de la première partie : revisitées
89. Lundi 17 octobre 2005 à 11h00
    salle 311 (ESSI)

    Présentation de l'ACI Chronos (2003-2006)

    Alexis Bonnecaze

    L'ACI Chronos s'attache à étudier le problème suivant : comment horodater d'une manière sûre (prouvable) des documents électroniques ? Je présenterai les méthodes d'horodatage existantes ainsi que celles que nous avons proposées dans le cadre de l'ACI.
88. Jeudi 22 septembre 2005 à 14h30
    salle 307 (ESSI)

    Les automates cellulaires dans l'espace des mesures

    Petr Kůrka

    Chaque AC peut être regardé comme un système dynamique dans l'espace des mesures Boréliennes. Nous montrons qu'un tel système a un seul attracteur et nous donnons quelques propriétés sur leur structure.
87. Mardi 24 mai 2005 à 11h00
    salle 307 (ESSI)

    Graphes d'automates

    Christophe Papazian

    Un tour rapide de ce qu'on sait faire et de ce qu'on aimerait savoir faire sur les graphes d'automates et autres modèles semblables, pour le calcul distribué : Reconnaissance, Election, Calcul...
86. Vendredi 25 mars 2005 à 14h30
    salle 307 (ESSI)

    Règles de successions et ECO Systèmes (2)

    Jean-Marc Fédou & Christine Garcia

    Etant donnée une application "successeurs" de l'ensemble des entiers dans l'ensemble de ses parties, on considère l'ensemble des mots sur l'alphabet N qui commencent par 1 et tels que chaque lettre du mot est un "successeur" de la précédente. On s'intéresse alors aux nombres de mots de longueur donnée et à la série génératrice.

     

    Par exemple, si les successeurs de k sont {1,2,3,...,k-1,k,k+1}, les premiers mots engendrés seront {1,11,12,111,112,121,122,123,...}.

    Dans ce premier exposé, nous introduirons la problématique et les bases sur les règles de succession. La prochaine fois, nous montrerons que certaines règles de succession induisent des séries génératrices algébriques et aborderons également le cas de règles "signées".

85. Vendredi 11 mars 2005 à 14h30
    salle 307 (ESSI)

    Règles de successions et ECO Systèmes (1)

    Jean-Marc Fédou & Christine Garcia

    Etant donnée une application "successeurs" de l'ensemble des entiers dans l'ensemble de ses parties, on considère l'ensemble des mots sur l'alphabet N qui commencent par 1 et tels que chaque lettre du mot est un "successeur" de la précédente. On s'intéresse alors aux nombres de mots de longueur donnée et à la série génératrice.

     

    Par exemple, si les successeurs de k sont {1,2,3,...,k-1,k,k+1}, les premiers mots engendrés seront {1,11,12,111,112,121,122,123,...}.

    Dans ce premier exposé, nous introduirons la problématique et les bases sur les règles de succession. La prochaine fois, nous montrerons que certaines règles de succession induisent des séries génératrices algébrique et aborderons également le cas de règles "signées". lang=fr slides1=05-03-11_fedou-garcia.ppt fra slides2=05-03-11_fedou-garcia.pdf fra

84. Vendredi 25 février 2005 à 14h30
    salle 307 (ESSI)

    NB-complétude du démineur

    Johny Bond

    Preuve de Richard Kaye, tirée de Some Minesweeper Configurations.

     

    Si vous êtes sur le réseau ESSI ou Unice, les transparents (à peu de choses près) sont ceux du cours 7 d'Algorithmique et complexité. lang=fr

83. Vendredi 21 janvier 2005 à 14h30
    salle 307 (ESSI)

    Chiffrement El Gamal sur une courbe de Weierstrass

    Marie Virat

    Dans cet exposé nous proposons un chiffre aussi sûr que la version elliptique d'El Gamal.

     

    Pour cela, nous considérons l'anneau artinien F_q[ε] avec ε² = 0, et nous étudions les courbes elliptiques données par une équation de Weierstrass Y² = X³+aX+b avec a et b dans F_q[ε]. L'ensemble des éléments d'une telle cubique est muni d'une structure de groupe.

    La sûreté de notre système repose, elle aussi, sur la difficulté de calculer un logarithme discret. Ainsi, dans le groupe que nous considérons, nous montrons que le calcul d'un logarithme discret est aussi difficile que dans le cas des courbes elliptiques.

    Un avantage de notre chiffre est de permettre de coder plus facilement un bloc de clair en un élément du groupe que dans la version elliptique d'El Gamal. lang=fr

82. Vendredi 05 novembre 2004 à 14h30
    salle 307 (ESSI)

    Sur l'existence d'automates cellulaires transitifs dans l'espace de Besicovitch

    Enrico Formenti

    Dans cet exposé nous montrons un autre succès de la méthode d'incompressibilité : la non existence d'automates cellulaires transitifs dans l'espace de Besicovitch. Cette méthode permet de trouver une preuve simple et élégante d'un résultat dont la preuve combinatoire directe semble être très compliquée. lang=fr
81. Vendredi 22 octobre 2004 à 14h30
    salle 316 (ESSI)

    Méthode d'incompressibilité et plus longue sous-séquence commune

    Enrico Formenti

    Dans cet exposé nous reconstruisons la preuve classique de Vitanyi et al. Ensuite nous proposons des améliorations. lang=fr
80. Jeudi 30 septembre 2004 à 14h00
    salle 301 (ESSI)

    Convolutional codes over rings

    Virgilio P. Sison

    Convolutional codes over rings behave quite differently than convolutional codes over fields, but they are the ones best suited for phase modulation. This behavior depends strongly on the structure of the underlying ring. Some basic concepts about ring convolutional codes, in particular over Z_p^r, and their structural properties such as basicity, systematicity, non-catastrophicity and minimality, will be presented.

     

    Moreover, we will describe ways of constructing ring convolutional codes from linear block codes. Firstly, from an (n,k) linear block code over the Galois ring GR(4,m) with minimum Hamming distance d, a rate-k/n convolutional code over the ring Z₄ with memory at most m-1 and squared Euclidean free distance at least 2d is constructed. Secondly, from a Z_2^r-linear block code we construct a binary partial unit memory trellis code with designed free distance. lang=en slides1=04-09-30_sison.pdf eng

79. Jeudi 23 septembre 2004 à 11h00
    salle 301 (ESSI)

    Réversibilité des automates de sable

    Benoît Masson

    L'étude de la dynamique des automates de sable commence par la recherche des comportements décidables et de ceux qui ne le sont pas. En particulier on verra ce qu'il est possible de dire à propos de la réversibilité d'un automate donné. Nous verrons donc les relations qui existent entre plusieurs propriétés, pouvant nous aider dans des preuves de décidabilité. lang=fr slides1=04-09-23_masson.pdf fra
78. Jeudi 16 septembre 2004 à 14h00
    salle 301 (ESSI)

    Périodicité dans les automates cellulaires

    Enrico Formenti
77. Jeudi 29 avril 2004 à 14h00
    salle 301 (ESSI)

    Reconnaissance de graphes par automates

    Christophe Papazian
76. Jeudi 15 avril 2004 à 14h00
    salle 301 (ESSI)

    Chaos déterministes (5e exposé)

    Enrico Formenti

    Après un survol sur quelques définitions et résultats sur les systèmes dynamiques discrets, nous abordons l'épineux problème de trouver une définition acceptable de chaos déterministe qui concilie la vision mathématique et la vision intuitive du phénomène. Il s'agit probablement d'une quête sans espoir. Nous donnerons un aperçu d'une possible solution qui semble pouvoir (bien que de manière encore incomplète) conjuguer les deux visions
75. Jeudi 01 avril 2004 à 15h00
    salle 301 (ESSI)

    Pile de sable (SPM)

    Benoît Masson
74. Jeudi 25 mars 2004 à 14h00
    salle 301 (ESSI)

    Chaos déterministes (4e exposé)

    Enrico Formenti

    Après un survol sur quelques définitions et résultats sur les systèmes dynamiques discrets, nous abordons l'épineux problème de trouver une définition acceptable de chaos déterministe qui concilie la vision mathématique et la vision intuitive du phénomène. Il s'agit probablement d'une quête sans espoir. Nous donnerons un aperçu d'une possible solution qui semble pouvoir (bien que de manière encore incomplète) conjuguer les deux visions.
73. Jeudi 19 février 2004 à 14h00
    salle 301 (ESSI)

    Chaos déterministes (3e exposé)

    Enrico Formenti

    Après un survol sur quelques définitions et résultats sur les systèmes dynamiques discrets, nous abordons l'épineux problème de trouver une définition acceptable de chaos déterministe qui concilie la vision mathématique et la vision intuitive du phénomène. Il s'agit probablement d'une quête sans espoir. Nous donnerons un aperçu d'une possible solution qui semble pouvoir (bien que de manière encore incomplète) conjuguer les deux visions.
72. Jeudi 15 janvier 2004 à 14h00
    salle 301 (ESSI)

    Chaos déterministes (2e exposé)

    Enrico Formenti

    Après un survol sur quelques définitions et résultats sur les systèmes dynamiques discrets, nous abordons l'épineux problème de trouver une définition acceptable de chaos déterministe qui concilie la vision mathématique et la vision intuitive du phénomène. Il s'agit probablement d'une quête sans espoir. Nous donnerons un aperçu d'une possible solution qui semble pouvoir (bien que de manière encore incomplète) conjuguer les deux visions.
71. Jeudi 11 décembre 2003 à 11h00
    salle 301 (ESSI)

    Codes quasi-cycliques : constructions algébriques et représentations par treillis

    Anne Desideri-Bracco

    Au sein des codes correcteurs d'erreurs et de la Théorie de l'Information, les codes quasi-cycliques sont de plus en plus étudiés. Ce sont des codes de longueur finie qui généralisent les codes cycliques mais qui approchent également les codes de longueur infinie que sont les codes convolutifs. Les codes quasi-cycliques possédent de plus d'excellents paramètres, c'est-à-dire qu'ils ont une grande capacité de correction. Deux approches algébriques différentes existent pour ces codes : l'approche constructive proposée par Ling San et Patrick Solé dans "On the Algebraic Structure of Quasi-Cyclic Codes I : Finite Fields" et l'approche cyclique présentée par Kristine Lally dans "Quasi-Cyclic Codes of Index ell over F_q Viewed as F_q-Submodules of F_q^ell/x^m-1". Les treillis sont des graphes qui permettent de représenter les codes correcteurs d'erreurs, dans le but de les décoder avec l'algorithme de Viterbi. Il existe deux types de treillis : les treillis conventionnels et les treillis cycliques. Nous associons à chacun de ces types de treillis une construction graphique de codes quasi-cycliques qui rejoint l'une des deux approches algébriques présentées précédemment. Pour les treillis conventionnels, la construction graphique est une généralisation de la construction proposée par G.D. Forney dans "Coset Codes - Part II : Binary Lattices and Related Codes". Elle rejoint l'approche de S. Ling et P. Solé sous certaines conditions. Les treillis cycliques sont associés à la reprsentation cyclique de K. Lally. Ces treillis permettent de représenter les codes avec moins de sommets que les treillis conventionnels. Enfin, la décomposition algébrique de S. Ling et P. Sol nous a permis de construire de nouveaux codes, et en particulier des codes auto-duaux de longueur 70.
70. Jeudi 04 décembre 2003 à 15h30
    salle 301 (ESSI)

    Chaos déterministes (3e exposé)

    Enrico Formenti

    Après un survol sur quelques définitions et résultats sur les systèmes dynamiques discrets, nous abordons l'épineux problème de trouver une définition acceptable de chaos déterministe qui concilie la vision mathématique et la vision intuitive du phénomène. Il s'agit probablement d'une quête sans espoir. Nous donnerons un aperçu d'une possible solution qui semble pouvoir (bien que de manière encore incomplète) conjuguer les deux visions.
69. Jeudi 12 octobre 2000 à 14h00
    salle 309 (ESSI)

    Quelques mots sur le calcul par machine de Turing réversible

    Jérôme Durand-Lose I3S, Sophia Antipolis

    Au cours de cet exposé très informel, je compte présenter les idées et les techniques pour la simulation de machine de Turing quelconque par des machines de Turing réversibles.
68. Jeudi 06 juillet 2000 à 10h00
    salle 3.. (ESSI)

    Une nouvelle famille de codes lineaires à bons paramètres

    San Ling

    A linear code of length n over a finite field GF(q) is none other than a vector subspace of GF(q)^n. If the dimension of this code is k and the minimal distance separating two words in this code is d, a well known fact in coding theory is the Singleton bound: k+d \leq n-1. Hence, for given n and k, the d is bounded by n-k-1. (Other bounds exist and show that d may not always attain the value n-k-1.) Codes which have d=n-k-1 are called MDS (maximum distance separable) codes. A well known family of MDS codes are the Reed-Solomon (RS) codes and the punctured RS codes derived from them. Unfortunately such codes have lengths at most q. Taking cue from the construction of punctured RS codes, we construct a class of codes over GF(q) whose lengths are approximately q^2. This construction really comes from the structure of algebraic curves over finite fields. However, in this talk, we shall restrict ourselves to a special case of this construction which can be fully described in terms of just polynomials. In many instances, for given n and k, this construction yields codes whose minimal distance d is better (i.e., larger) than all other known codes of the same n and k. An interactive table of the codes of the best parameters over GF(q), where q \leq 9, may be found at the website of Brouwer: http://www.win.tue.nl/~aeb/voorlincod.html
67. Vendredi 30 juin 2000 à 10h00
    salle 3.. (ESSI)

    An Order on Cellular Automata

    Ivan Rapaport DIM, Universidad de Chile

    In his well-known Computational Complexity book, Christos Papadimitriou says that "some of the least understood areas in science seem to involve the concurrent interaction of large number of agents". Cellular automata (CAs) are large number of agents interacting locally. And in fact they are not yet completely understood. Understanding is classifying. The dynamical system approach for classifying CAs is the most developed one but many question remain open: we don't known whether some classes are empty, simple CAs appear to be chaotic, etc. We propose a new classification approach by considering the CAs as algebraic objects. A partial order is introduced and a global minimum is found. We conjecture that the "distance" of any CA from the global minimum is a measure of complexity and we give some evidence supporting this idea.
66. Jeudi 22 juin 2000 à 14h00
    salle 309 (ESSI)

    Systèmes de semi-Thue et graphes context-free

    Hugues Calbrix LaPCS, Université Lyon 1

    L'étude de la logique monadique du second ordre, débutée avec les résutats de Büchi (62) qui a montré sa décidabilité pour $\omega$, puis Rabin (69) qui a montré sa décidabilité pour l'arbre binaire infini, s'est poursuivie sur les graphes context-free, définis par Müller et Schupp (86). Dans notre exposé, nous rappelons que cette logique est indécidable dans le cas de la grille $\omega \times \omega$, résultat du à Robinson, qui infirme une conjecture de Wang. Nous rappelons la définition des graphes context-free et qu'ils sont les graphes de transition des automates à pile. Nous rappelons la définition de Caucal des systèmes de récriture préfixes et des graphes qui y sont associés, qui sont également les graphes context-free. Nous définissons la notion de graphe de système de semi-Thue, basée sur la récriture des mots irréductibles concaténée avec une lettre. Nous définissons les familles des systèmes de semi-Thue à réductions bornées et fortement bornées. Nous montrons que ces deux classes de systèmes engendrent les mêmes graphes, qui sont les graphes context-free complets (de degré sortant uniforme). Nous montrons qu'on peut décider si un système est à réductions fortement bornées, mais pas à réductions bornées. Nous terminons par l'étude des systèmes de semi-Thue monadiques.
65. Jeudi 22 juin 2000 à 10h30
    salle 309 (ESSI)

    fin de l'exposé Autostabilisation II : élection d'un chef

    Jérôme Durand-Lose I3S, Sophia Antipolis
64. Jeudi 15 juin 2000 à 14h00
    salle 309 (ESSI)

    Autostabilisation II : élection d'un chef

    Jérôme Durand-Lose I3S, Sophia Antipolis

    Dans les réseaux, les pannes locales et passagères peuvent désorganiser un réseau à tel point qu'il faut une intervention extérieure et parfoit arrêter les calculs en cours et réinitialiser tout le réseau. L'autostabilisation cherche à pourvoir le système de facultés de corrections autonomes. Beaucoup de protocoles autostabilisants existent déjà. Au cours de cet exposé, nous présenterons deux algorithmes pour l'élection d'un leader. Ces algorithmes assurent qu'au bout d'un temps fini, il y aura un et un seul leader dans le réseau. L'algorithme de Dolev, Israeli, et Moran (Token management schemes and random walks yields self-stabilizing mutual exclusion. {\em Principles of Distributed Computing (PODC}~'90), pages 119--130, 1990.) est basé sur des forêts dont les arbres vont fusionner pour qu'il ne reste finalement qu'un arbre dont la racine sera le chef. L'algorithme de Beauquier, Durand-Lose, Gradinariu et Johnen (soumis) lui se base sur des déplacements de jetons qui vont servir aux prétendants à savoir s'ils sont seuls dans le réseau. S'ils ne sont pas seul, ils se déplacent un peu. Quand deux prétendants se rencontrent, ils fusionnent. Ces deux algorithmes ont tous deux des composantes probabilistes; mais les techniques employés pour résoudre le même problème sont très différentes.
63. Jeudi 27 avril 2000 à 15h30
    salle 309 (ESSI)

    Algorithmique de la réduction des réseaux : Phénomènes de seuil dans les réseaux aléatoires et analyse des algorithmes

    Ali Akhavi GREYC, Caen

    Un réseau euclidien est l'ensemble des combinaisons linéaires entières d'une famille libre de vecteurs de l'esapce euclidien $R^p$. Cette famille est appelée une base du réseau et le problème de la réduction consiste à trouver parmi toutes les bases qui générent le même réseau une base ayant de bonnes propriétés vis à vis de la structure euclidienne: les vecteurs de la base sont "assez courts" et la base est "assez orthogonale". Ce problème est d'un intérêt majeur en particulier par ses nombreuses applications en optimisation entière, en cryptographie ou encore en théorie algorithmique des nombres. Dans cet exposé, je présenterai deux nouveaux algorithmes de réduction: appelées réduction de Gram et réduction de Schmidt, ils sont obtenus en relaxant les conditions exigées par l'algorithme classique de réduction LLL. L'analyse dans le pire des cas de ces différents algorithmes ne permet pas de différencier leur comportement. Cependant, je donnerai l'idée qui apporte des éléments de réponse à la question ouverte du nombre d'iterations des algorithmes, pour le choix optimal du paramètre d'approximation (par exemple la valeur $1$ pour LLL classique): à dimension fixée, le nombre d'itérations reste linéaire en la taille de la base. Je me placerai alors dans un modèle aléatoire simple et naturel, où les vecteurs d'entrée sont choisis uniformément et indépendamment dans la boule unité. L'étude de la géométrie des réseaux aléatoires mettra en évidence des phénonènes de seuils et permettra de montrer que les nouveaux algorithmes introduits sont en moyenne plus efficaces que l'algorithme classique: Les bases de sortie sont de qualité similaire et obtenues bien plus rapidement en moyenne.
62. Jeudi 27 avril 2000 à 14h00
    salle 309 (ESSI)

    Essayons de calculer plus vite (dans un corps)

    Natacha Portier ENS Lyon

    Quand on est petit, on aime bien les devinettes. Un des jeux favoris des cours de récré consiste à faire deviner un entier avec des questions comme « est-ce 17 ? ». En grandissant, on découvre qu'on peut aller plus vite en posant des questions comme « Est-ce plus grand que 13 ? ». Que se passe-t-il si on autorise plutôt les questions du style « Est-ce une racine de x^2-30x+221 ? » ? Et si on prend en compte la taille de la question ? Continuons à prendre de l'âge et découvrons la dérivée, les puissances et les racines. Il faut maintenant deviner une puissance ou une racine d'un élément. La dérivée est un outil qui nous permet de poser des questions plus compliquées. Mais permet-elle vraiment de résoudre plus vite la devinette ?
61. Jeudi 13 avril 2000 à 14h00
    salle 309 (ESSI)

    Echange Total en Temps Linéaire

    Guillaume Fertin LaBRI, Bordeaux

    On peut modéliser un réseau par un graphe, où les sommets représentent les entités du réseau (utilisateur, processeur...), et où les arêtes représentent les liens de communication. Dans ces réseaux, plusieurs types de communications peuvent intervenir : point-à-point, diffusion, multicast, échange total... Nous nous proposons ici d'étudier l'échange total, i.e. chaque sommet du réseau transmet son information à tous les autres. Le modèle choisi est de type ``temps linéaire'', c'est-à-dire que le temps de communication est proportionnel à la longueur des messages échangés (on notera que, contrairement au modèle dit ``temps constant'', les communications ne sont pas nécessairement synchrones). Nous nous intéresserons ici au temps de communication optimal pour réaliser l'échange total en temps linéaire dans un réseau à n sommets, en supposant que celui-ci soit entièrement connecté. Ce temps de communication est de la forme : f(n) x Beta + g(n) x Tau, où Beta et Tau sont deux paramètres dépendant du réseau. Notamment, si f(n) et g(n) ne peuvent atteindre leur minimum théorique en même temps, il peut être intéressant d'étudier les compromis possibles entre f(n) et g(n) (les valeurs de Beta et Tau déterminant alors le temps total de communication). Dans cet exposé, je ferai un survol des résultats connus dans ce domaine, principalement obtenus par Pierre Fraigniaud, Joseph Peters et moi-même. On verra notamment que : * dans le cas où n est pair, il est possible de réaliser l'échange total en minimisant à la fois f(n) et g(n). De plus, le temps optimal est réalisable par un algorithme de communication synchrone (Fraigniaud, Peters). * dans le cas où n est impair, il est impossible de faire atteindre à f(n) et à g(n) leur minimum théorique en même temps. Il convient alors d'étudier les compromis possibles entre f(n) et g(n). Je montrerai divers résultats dans ce sens, principalement dans le cas synchrone.
60. Jeudi 06 avril 2000 à 14h00
    salle 309 (ESSI)

    Approximating Algebraic Functions by means of Rational Ones

    Renzo Pinzani Florence, Italie

    Cet exposé fait suite à l'exposé du 30 mars. Nous utilisons la méthode ECO pour dénombrer des sous classes d'objets combinatoires. Plus précisément, si une règle R décrit la construction d'une classe d'objets, une sous-classe d'objets peut être décrite par des opérateurs issus de R. Les séries génératrices des sous-classes fournissent alors des approximations rationnelles de la série génératrices des objets décrits par R.
59. Jeudi 30 mars 2000 à 14h00
    salle 309 (ESSI)

    Méthode ECO et Grammaires d'objets

    Renzo Pinzani et Jean-Marc Fédou Florence, Italie et I3S, Sophia Antipolis

    Il s'agit d'un exposé introductif pour lequel aucun prérequis n'est nécessaire. Nous présenton deux manières d'aborder la description d'objets combinatoires. Une méthode par description récursive (grammaires d'objets) et une méthode par opérateurs (méthode ECO). Ces deux approches permettent toutes deux de déduire les équations satisfaites par les séries génératrices des objets engendrés. Elles permettent également de déduire des algorithmes de génération aléatoire. Enfin, elles définissent des classes d'objets en bijection. Le programme de recherche que nous proposons est d'affiner les contours, intersections et différences de ces deux approches.
58. Jeudi 02 décembre 1999 à 14h00
    salle 309 (ESSI)

    Isomorphismes du graphe de de Bruijn, appliqués à l'architecture OTIS

    David Coudert I3S, Sophia Antipolis

    Dans cet exposé, nous allons tout d'abord présenter l'architecture Optical Transpose Interconnection System (OTIS) qui permet de réaliser un grand nombre d'interconnexions en espace libre. Nous donnerons quelques propriétés sur les réseaux de communications optique réalisables avec cette architecture. Nous montrerons en particulier, quelle permet de réaliser des réseaux basés sur des graphes complet et des graphes de Bruijn, de Kautz et de Imase et Itoh. Ensuite, nous approfondirons l'implantation du de Bruijn avec OTIS. En effet, le graphe de de Bruijn de degré d et de diamètre D, B(d,D), est généralement défini comme l'ensemble des mots de longueur D sur un alphabet à d lettres, ou les adjacences sont obtenues par décalage. Dans cet exposé, nous montrons plusieurs autre façon de définir ce graphe. Une méthode consiste à opérer une permutation de l'alphabet et une autre opère une permutation des indices des lettres des mots. Ensuite, nous utilisons ces résultats pour optimiser l'implantation de réseaux de communications optique en espace libre, basé sur le de Bruijn et OTIS.
57. Jeudi 04 novembre 1999 à 14h00
    salle 309 (ESSI)

    Minimisation du trafic dans la distribution d'information

    Frédéric Havey

    Dans cet exposé, nous présenterons un problème le probléme suivant: Considérons un graphe $G=(V,E)$ qui correspond à un réseau dont un des sommets $s$ est une source d'informations. Chaque arête $e$ possède une longueur $l_e$. Chaque sommet $v$ de $R\subseteq V$ adresse un nombre $r(v)$ (possiblement nul) de requêtes d'information par unité de temps. Les informations contenues dans $s$ peuvent être dupliquées sur le sous-graphe savant $S=(V_S,E_S)$. A chaque fois qu'une information stockée dans $G$ est modifiée, un message de mise à jour est envoyée à travers les arêtes $E_S$ vers les sommets de $V_S$. Le trafic de mise à jour par unité de temps est $\mu \sum_{e\in E_S} l_e$ avec $\mu$ le nombre de requêtes modifiées par unité de temps. Chaque requête d'information en un sommet $v\in R$ envoie un message de requête de $v$ vers un sommet $w$ de $S$ qui renvoie une réponse vers $v$. On suppose que les deux messages suivent le même chemin $P$ dans le réseau. Le trafic engendré par les requêtes de $v$ est alors $r(v)d(v,S)$ o\`u $d(v,S)= \sum_{e\in P} l_e$ est la distance du sommet $v$ au sous-graphe savant $S$. Le trafic total du au requêtes est donc $\sum_{v\in R} r(v)d(v,S)$. Le but du problème est de minimiser le trafic total $\ds \mu \sum_{e\in E_S} l_e + \sum_{v\in R} r(v)d(v,S)$.
56. Jeudi 14 octobre 1999 à 14h00
    salle 309 (ESSI)

    Communications a diametre fixe dans les chemins et cycles ATM

    Sebastien Choplin I3S, Sophia Antipolis

    Dans le cadre des reseaux de telecommunications ATM (Mode de Transfert Asynchrone), nous nous interessons au probleme suivant : concevoir une topologie virtuelle (graphe H) sur une topologie physique (graphe G).A chaque arc de H (appeles en ATM chemins virtuel (VP) est associe un chemin dans le reseau physique. Deux parametres sont importants : la charge d'un lien physique (nombre de VP qui partagent le meme lien physique) et le nombre de sauts (nombre de VP utilises pour etablir une connection). Nous considerons ici le cas de l'echange totals pour deux topologies physiques : le chemin et le cycle. Nous donnons des encadrements serres de la charge en fonction du nombre de saut maximal (diametre de H).
55. Jeudi 30 septembre 1999 à 14h00
    salle 309 (ESSI)

    WDM Routing in All-Optical Ring Networks

    Luisa Gargano Università di Salerno
54. Lundi 20 septembre 1999 à 14h00
    salle 309 (ESSI)

    Packing of graphs

    Pavol Hell Simon Fraser University, Canada
53. Vendredi 25 juin 1999 à 10h00
    salle 309 (ESSI)

    Quantum computing

    Jozef Gruska Université de Brno

    In quantum computing we witness a merge of two of the most important areas of science and technology of 20th century: quantum physics and computing. This mearge is bringing new aims, challenges and potentials for informatics and also new approaches to explore quantum world. In the talk the very basic aims, history, principles, concepts, models methods and results, as well as problems of quantum computing and quantum information processing will be presented with emphais more on computational aspects than on the underlying physics.
52. Jeudi 17 juin 1999 à 14h00
    Amphi EST, ESSI

    Outils pour des mathématiques intéractives et distribuées

    Laurent Dirat I3S et Société OVE, basée au CICA

    Cette thèse réalisée au sein de la société OVE, basée au CICA, s'incrit dans le cadre du projet européen (ESPRIT) OpenMath, dont le but est la définition d'un standard indépendant de toute plateforme, pour la représentation d'objets mathématiques, donnant ainsi à plusieurs applications un moyen efficace pour communiquer. L'objectif de cette thèse est le développement d'outils permettant la présentation d'un contenu mathématique dans des pages WEB, de manière interactive et distribuée. Cela se matérialise actuellement sous la forme de JOME, un composant logiciel (Java Bean), conçu à la base comme une interface interactive pour la saisie, l'édition, la manipulation et l'échange d'expressions mathématiques. En particulier, des bases de données mathématiques et des outils de calcul formel. OpenMath fournissant le standard nécessaire à un tel échange. Mais les mathématiques ne sont pas que de simples formules, ce qui donne de larges perspectives pour JOME, notamment en ce qui concerne le domaine de l'enseignement à distance, de la gestion de grosses formules...
51. Jeudi 27 mai 1999 à 14h00
    salle 309 (ESSI)

    Réseaux de neurones artificiels pour l'optimisation combinatoire

    Michel Winter LIRA-Lab, Dist - Universita di Genova, Italie

    Certains types de réseaux de neurones artificiels, inspirés de la biologie et de la physique statistique (modèle de Hopfield, machine de Boltzmann, réseaux à approximation en champs moyen,...) peuvent être employés pour résoudre des problèmes complexes de recherche opérationnelle. Après avoir rapidement présentés ces modèles neuronaux, je montrerai comment ils peuvent être utilisés dans le contexte de l'optimisation combinatoire, en m'appuyant sur un problème particulier : l'affectation multi-dimensionnelle. Plusieurs résultats théoriques ont permis qualifier la configuration du réseau à la convergence, assurant ainsi que la solution délivrée vérifie les contraintes du problème. Je présenterai également quelques résultats de simulations illustrant l'intérêt de ces approches pour des problèmes réels.
50. Jeudi 22 avril 1999 à 14h00
    salle 309 (ESSI)

    Cartes pointées, équations fonctionnelles et fractions continues

    Jean-François Béraud Université de Marne la Vallée, Institut Gaspard Monge

    L'énumeration des cartes pointées est un domaine étudié initialement par W. T. Tutte dans les années soixantes, avec les cartes planaires. Divers résultats nouveaux ont depuis été obtenus pour les cartes pointées sur des surfaces plus générales (tore à 1, 2, 3 trous, plan projectif ...). Je présenterais l'énumération des cartes pointées sur la bouteille de Klein, dans le but de mieux comprendre la résolution de ce probl`eme dans le cas général. Je présenterais ensuite une autre approche de l'énumération des cartes pointées, cette fois considérées indépendamment du genre de leur surface associée. Cette étude conduit à des équations de Riccati dont les solutions séxpriment sous la forme de fractions continues, qui permettent d'obtenir une équation de Dyck généralisée
49. Mardi 23 février 1999 à 14h00
    salle 208 (ESSI)

    Algorithmes paralleles de traitement de graphes : une approche basee sur l'analyse experimentale

    Isabelle Guerin-Lassous LIAFA, Paris 7

    Nous nous interessons aux algorithmes paralleles de traitement de graphes et plus specifiquement aux implantations de tels algorithmes : est-il possible, dans l'etat actuel de nos connaissances, d'ecrire du code portable, efficace, predictif pour le traitement de graphes en parallele ? Dans cet expose, je vous presenterai les resultats que nous avons obtenus sur quelques algorithmes paralleles de traitement de graphes (tri, list ranking, composantes connexes,...), ainsi que les analyses qui decoulent de ces resultats et qui apportent les premiers elements de reponse a la question initiale. L'orateur sera chez SLOOP du mardi apres-midi au jeudi soir pour ceux qui voudraient la rencontrer pour des eventuelles discussions.
48. Jeudi 07 janvier 1999 à 14h00
    salle 309 (ESSI)

    Diagnostic des systemes multiprocesseurs, ou comment deduire la verite des mensonges

    Andrzej Pelc Universite du Quebec, Hull, Canada et INRIA, Sophia Antipolis

    La croissance de la taille des systemes multiprocesseurs augmente leur vulnerabilite aux pannes des composantes. C'est pourquoi les utilisateurs s'interessent de plus en plus a la question de fiabilite de ces systemes. Un des problemes majeurs dans ce domaine, connu sous le nom du probleme de diagnostic des pannes, est de repondre a la question quels processeurs sont en panne et quels sont fonctionnels. Nous etudions le diagnostic des pannes dans un modele de graphe du a Preparata, Metze et Chien. Les processeurs sont representes par les noeuds du graphe et les liens par lesquels on peut effectuer des tests sont representes par les aretes. Les processeurs effectuent des tests sur leurs voisins et le diagnostic est base sur l'ensemble des resultats des tests. On suppose que les testeurs fonctionnels donnent toujours des resultats corrects de tests, alors que les testeurs en panne sont entierement imprevisibles: ils peuvent retourner des resultats quelconques, independement de l'etat du processeur teste. Plusieures variantes de ce modele ont ete etudiees dans la litterature: le scenario pire cas vs. le scenario aleatoire, le diagnostic nonadaptatif vs. adaptatif et le choix de tests centralise vs. distribue. Deux criteres de performance d'un algorithme de diagnostic ont ete surtout etudies: le nombre de tests et le temps parallele (nombre de rondes de tests), en supposant que seulement les tests impliquant des paires disjointes des processeurs peuvent etre effectues au cours de la meme ronde. Dans cet expose nous presentons un choix de resultats classiques et nouveaux, en soulignant les aspects algorithmiques et les problemes d'optimisation de performance.
47. Jeudi 10 décembre 1998 à 14h00
    salle 309 (ESSI)

    Sudans Algorithm for Reed Solomon and Algebraic-Geometric Codes

    Ralf Koetter Coordinated Science Lab., University of Illinois

    Efficient decoding of Reed-Solomon code beyond half the minimum distance has puzzled the coding theory comunity ever since these codes were invented. In 1997 M.Sudan presented a polynomial time algorithm that accomplishes this task in a list decoding setting. His algorithm was adapted to algebraic geometric codes by Shokrollahi and Wasserman. Recently Gurusvami and Sudan improved on the first version of the decoding algorithm, which, for length n, dimension k Reed-Solomon codes, gave a polynomial time algorithm that produces a list of nearest codewords from a particular received word provided the weight of the error vector does not exceed n-(kn)^0.5. In this talk we describe the algorithm for Reed Solomon codes and point out the key steps in generalizing the result to algebraic geometric codes.
46. Jeudi 03 décembre 1998 à 14h00
    salle 309 (ESSI)

    Etude de la complexite bilineaire de la multiplication dans les corps finis par interpolation sur des courbes algebriques

    Stephane Ballet Institut de mathematiques de Luminy
45. Jeudi 15 octobre 1998 à 15h30
    salle 309 (ESSI)

    Autostabilisation

    Jérôme Durand-Lose I3S, Sophia Antipolis

    Dans un réseau, un protocole est dit autostabilisant s'il retrouve une cohérence glob ale en un temps fini après toute perturbation de son état. Formellement, un protocole est autostabilisant s'il vérifie les deux propriétés suiva ntes : - correction (la moindre des choses) d'un état cohérent, le système ne peut aller que d ans des états cohérents ; - convergence (le morceau de choix) de n'importe quel état, le système retrouve sa cohé rence en un temps fini. Nous nous proposons d'illustrer ce concept à l'aide d'exemples concernant l'exclusion mutuelle : - [Dijskra 74] article fondateur sur les anneaux semi-uniforme ; - [Israeli Jalfon 90] technique des jetons voyageurs ; - [Beauquier Delaët 94] sur les anneaux uniformes ; - [JDL] sur les réseaux uniformes.
44. Mercredi 03 juin 1998

    Clustering moléculaire pour le "drug design":de la recherche de voisins sur hyper-cube aux problèmes de partitionnement de graphes

    Frédéric Cazals Project PRISME, INRIA Sophia-Antipolis

    Étant donnée une base de donneés moléculaire M et une pathologie, une méthode utilisée par les concepteurs de médicaments consiste à (1)tester au hasard un échantillon de molécules de M (2)sélectionner les molécules les plus prometteuses de l'échantillon (3)tester de façon plus systématique les molécules ayant une structure similaire à ces dernières. Un préalable à cette exploration fonctionnelle est donc le partitionnement de M en classes de molécules similaires. Via le formalisme ad-hoc et en termes algorithmiques, la première étape consiste à chercher des paires de points "voisins" sur un hyper-cube $H_d={0,1}^d$ de grande dimension -par exemple d=1500 pour M contenant $n=10^4$ molécules. Les méthodes classiques d'algorithmique géométrique -diagrammes de Voronoï, box-trees, etc- souffrant de constantes exponentielles en la dimension, nous proposons une solution à ce problème fondée sur deux nouvelles structures de données probabilistes, les Skip Lists Directionnelles et les Skip Lists Directionnelles Récursives -DLS et RDSL. Nous montrerons que l'analyse probabiliste des RDSLs est reliée aux hyper-graphes et systèmes de Sperner, et donc difficile. Et nous présenterons également quelques résultats expérimentaux sur données réelles. La seconde étape consiste à trouver un partitionnement du graphe dont les sommets sont les molécules et les arêtes les paires de molécules similaires. Sa mise en oeuvre étant moins avancée que la première, nous évoquerons simplement quelques stratégies possibles basées sur les MST et les cliques.
43. Jeudi 14 mai 1998

    Suites construites à partir de la trace et de caractères multiplicatifs

    Carine Boursier Université de Toulon et du Var

    Les suites vérifiant de bonnes propriétés de corrélation sont très utiles dans de nombreuses applications (radar, transmissions de messages,..). Soit K un corps fini, L une extension finie de K et tr la trace de L dans K. On étudiera la fonction de corrélation de la suite t \rightarrow \chi(tr(\alpha^t)) où \alpha est une racine primitive de L, \chi un caractère multiplicatif de K, prolongé en zéro par 0\rightarrow 0 ou 0\rightarrow1. La période de cette suite dépend de [L:K] et de l'ordre de \chi. Le cas où \chi est quadratique sera plus particulièrement étudié.
42. Jeudi 30 avril 1998

    Séquences de STURM et application au contrôle d'admission dans les réseaux de communication

    Bruno Gaujal INRIA/UNSA

    Dans cet expose, nous presentons la notion de sequences de Sturm qui peuvent etre definies de facon informelle comme etant la solution au probleme suivant: Comment distribuer p jetons parmi k cases de facon aussi equilibree que possible. Nous allons donner plusieurs caracterisations de telles sequences et nous allons montrer certaines des proprietes curieuses qu'elles verifient. Dans la deuxieme partie de l'expose, nous montrons leur application pour le controle optimal d'admission dans certaines classes de reseaux. ( Abstract: In this talk, we give an overview on the notion of balanced sequences, which can be defined as the solution of the following simple problem: Given k slots, how can we distribute p tokens as evenly as possible among those slots? We will provide several characterizations of the balanced sequences and we will also show some curious properties of such sequences. In the second part of the talk, we will show their application to optimal admission control in some classes of communication networks.)
41. Jeudi 23 avril 1998

    Programmation semi-définie positive et Lift-and-project, applications à l'optimisation combinatoire

    Alexandre Laugier France Telecom

    On dit qu'une matrice A est semi-definie positive, et on note A\succeq 0, si x^{t}Ax\geq 0, \forall x\in R^{n}, les trois propositions suivantes sont alors equivalentes - A est une matrice semi-definie positive. - Toutes les valeurs propres de la matrice A sont positives ou nulles. - Il existe une matrice B reguliere d'ordre n telle que A=B^{t}B. Nous verrons qu'il existe une version semi-definie positive du lemme de Farkas et que la dualite en programmation lineaire peut etre etendue au cas semi-defini positif. On regardera comment on peut definir des relaxations semi-definies positives de problemes d'optimisation en nombres entiers et plus particulierement le parametre sandwich de L. Lov'asz pour le probleme du stable. La methode de Lift-and-project consiste a transformer un programme lineaire defini dans R^{n} en un probleme dans R^{n\times n} puis a le reprojeter dans R^{n} apres linearisation. L'etape de linearisation permet l'elimination de points fractionaires. Nous presenterons la construction recursive de L. Lov'asz et A. Schrijver en montrant les connexions qui existent avec la programmation semi-definie positive. Cette construction permet de generer l'enveloppe convexe de points a coordonnees entieres. Enfin nous presenterons une construction sequentielle de Lift-and-project due a E. Balas, S. Ceria et G. Cornuejols ainsi qu'une application a la conception d'algorithmes de type branch-and-cut.
40. Jeudi 02 avril 1998

    Sur un théorème de Delsarte et McEliece

    Philippe Langevin

    La divisibilité des poids des mots des codes cycliques et des codes abéliens a été étudiée par R. McEliece et P. Delsarte. Dans l'article weight congruences of p-ary cyclic codes R. McEliece donne la divisibilité des poids d'un code cyclique p-aire, et dans Weights of p-ary abelian codes, P. Delsarte donne celle des poids des codes abéliens. Les ingrédients utilisés dans leurs preuves sont : les congruences de Stickelberger, et la transformée de Mattson-Solomon. Ils adaptent leurs démonstrations au cas général des codes abéliens q-aire dans Zeros of Functions in Finite Abelian Group Algebras. Dans mon exposé, je rappelerai les notions fondamentales de codes cycliques et de codes abéliens. Je montrerai comment utiliser la représentation trace des codes abéliens , exposée dans mon article Weights of Abelian Codes, pour aboutir à leurs résultats.
39. Jeudi 19 mars 1998

    Virtual Path Layout in ATM networks

    Nausicaa Marlin

    Les communications dans un réseau ATM se font sur des chemins virtuels, déterminés à la configuration du réseau. Le problème est de placer correctement ces chemins virtuels en fonction de la capacité des liens physiques pour optimiser la durée des communications. On modélise le réseau virtuel formé par les chemins virtuels par un graphe. On cherche à minimiser le nombre de chemins virtuels empruntés par une cellule ATM pour aller d'un point quelconque du réseau à un autre. Modélisation du problème: G=(V,E) un graphe modélisant le réseau physique, V est l'ensemble des sommets, E est l'ensemble des arcs, H=(V,E') le graphe virtuel construit sur G. Un arc de H correspond à un chemin dans G. Si e est un arc de G, l(e) est la charge de e (nb d'arcs de H utilisant e). Pb1: Etant donnée D une borne sur le diamètre de H, on cherche à minimiser la charge maximale induite par H. Pb2 (dual): G est muni d'une contrainte de capacité sur ses arcs. c(e) est la capacité de l'arc~e. H est valide s'il induit une charge sur les arcs inférieure à leur capacité. l(e) \leq c(e). On cherche à minimiser le diamètre de H.
38. Jeudi 19 février 1998

    Minimizing Service and Operation Costs of Periodic Scheduling (The Broadcast Disks Problem)

    Amotz Bar-Noy Tel-Aviv University

    We study the problem of scheduling activities of several types under the constraint that at most a fixed number of activities can be scheduled in any single period. Any given activity type is associated with a service cost, and an operating cost that increases linearly with the number of periods since the last service of this type. The problem is to find an optimal schedule that minimizes the long-run average cost per period. Applications of such a model are the scheduling of maintenance service to machines, multi-item replenishment of stock, and minimizing the mean response time in {broadcast disks}. Broadcast disks gained a lot of attention recently, since they are used to model backbone communications in wireless systems, Teletext systems, and web caching in satellite systems. The first contribution of our work is the definition of a general model that combines into one several important previous models. We prove that an optimal cyclic schedule for the general problem exists and establish the NP-hardness of the problem. Next we show a lower bound on the cost achieved by an optimal solution. Using this bound we analyze several approximation algorithms. Next, we give a non-trivial 9/8-approximation for a variant of the problem that models the broadcast disks application. The algorithm uses some properties of ``Fibonacci sequences". Using this sequence we present a 1.57-approximation algorithm for the general problem. Finally, we describe a simple randomized algorithm and a simple deterministic greedy algorithm for the problem, and prove that both achieve approximation factor of 2. To the best of our knowledge this is the first worst case analysis of a widely used greedy heuristic for this problem. The talk will concentrate on the broadcast disks application. Joint work with: Randeep Bhatia, University of Maryland, Seffi Naor, Technion Israel, Baruch Schieber, IBM, New York. The full version of the paper could be found in: http://www.cs.umd.edu/~randeep/ http://www.eng.tau.ac.il/~amotz/publications.html
37. Jeudi 15 janvier 1998

    Différentes approches du partage de secret

    Guillaume Huysmans Université de Toulon et du Var
36. Jeudi 13 novembre 1997

    Les fonctions courbes

    Philippe Langevin
35. Jeudi 23 octobre 1997

    Binomial Coefficients, Jacobi Sums, Hypergeometric Function over Finite Fields and Group Representations

    Anna Helversen-Pasotto

    The analogy between binomial coefficients and Jacobi sums over finite fields will be illustrated in several ways. Gaussian sums appear as analogues of factorials, the Gaussian sum function defined on the group of multiplicative characters of a finite field appears as an analogue of the classical Gamma function. Analogues of multinomial coefficients will be studied in this context. Many beautiful classical identities for factorials, binomial coefficients, multinomial coefficients, gamma, beta or other special functions are shown to admit analogues. Some of these identities can be obtained as evaluations of the hypergeometric function as well in the classical as in the "finite" context. Many identities appear naturally studying the complex represen- tations of finite groups of Lie type. The group theoretical approach gives rise to new combinatorial questions.
34. Jeudi 16 octobre 1997

    Algorithmes parallèles pratiques (BSP et CGM) pour des problèmes discrets en graphes, géométrie et images

    Afonso Ferreira

    Le calcul parallele de problemes discrets traite, en bonne partie, de la solution d'un probleme sur des graphes, d'imagerie ou geometrique de taille n sur un ordinateur parallele avec p processeurs. La solution parallele est dite optimale si T_par = O(T_seq / p), ou T_par et T_seq sont, respectivement, le temps parallele et sequentiel requis pour resoudre le probleme. Le modele theorique utilise pour ce genre de problemes a ete jusqu'a tres recemment, celui ou n/p = O(1), aussi connu comme le modele de parallelisme "a grain fin". Toutefois, pour qu'un algorithme parallele soit important en pratique, il doit etre portable et extensible "scalable", i.e. il doit etre applicable sur plusieurs ordinateurs paralleles et efficace pour un large intervalle de valeurs de n/p. La conception de ce type d'algorithmes est l'un des grands objectifs de l'algorithmique parallele depuis toujours, principalement parce que les architectures de la plupart des ordinateurs existants (e.g. Paragon d'Intel et le T3D de Cray) sont composees de p processeurs "etat-de-l'art" (e.g. le Sparc), chacun avec une memoire locale importante, connectes par un reseau d'interconnexion (e.g. grille, hypercube, fat-tree). Ces machines sont d'habitude "a gros grain", i.e., la taille de chaque memoire locale est beaucoup plus grande que O(1). Les modeles "Bulk Synchronous Processes" (BSP) and "Coarse Grained Multicomputer" (CGM) sont donc composes de p processeurs avec O(n/p) memoire locale chacun, connectes par un reseau d'interconnexion quelconque ou par une memoire partagee. Le terme ``bulk'' fait reference au fait que le grain de calcul est important, et le terme ``coarse-grained'' fait reference au fait que (comme dans la pratique) la taille O(n/p) de chaque memoire locale est definie ``beaucoup plus large'' que O(1). Nous remarquons que s'il existe un algorithme optimal a grain fin avec T_par=O (T_seq / p ), alors - au moins d'un point de vue theorique -, le probleme de l'extensibilite ne se pose pas. En effet, une simulation standard (aussi appele simulation par ``processeurs virtuels'' dans plusieurs systemes d'exploitation de machines paralleles) donne un algorithme optimal pour tout n et p. Cependant, pour la plupart des reseaux d'interconnection utilises dans la pratique nombreux sont les problemes pour lequels il n'existe pas de telles solutions optimales a grain fin, ou encore des algorithmes optimaux a grain fin sont impossibles a cause des limitations dues a la largeur de bande ou au diametre (e.g. sur la grille). Les algorithmes developpes pour ces modeles ont pour but de proposer des resultats independants du reseau de communication des machines cibles pour que les algorithmes soient portables. Une des caracteristiques principales de cette approche est que toutes les communications entre les processeurs doivent etre restraintes a un nombre constant d'etapes de communications globales. La strategie de base est la suivante : on essaye de combiner des algorithmes sequentiels optimaux existants avec un routage global et un mecanisme de partitionnement efficaces. Chaque processeur resout alors en sequentiel un nombre constant de sous-problemes de taille O(n/p), et on utilise un tres petit nombre d'etapes de communication pour permuter les sous-problemes parmi les processeurs. A la fin, chaque processeur combine les solutions des sous-problemes pour determiner sa partie de la solution "globale", partie de taille O(n/p). Cette description est aussi breve que simplifiee. Les vrais algorithmes font plus que seulement permuter des donnees. En fait, la vraie difficulte se trouve dans le developpement des schemas de partitionnement coherents, puisque chaque processeur resout seulement un tres petit nombre de sous-problemes de taille O(n/p), mais doivent determiner leur contribution (de taille O(n/p)) a la resolution du probleme complet (sans pour autant avoir acces a toutes les n donnees). La partie la plus technique de la conception des algorithmes est celle de garantir qu'un tres petit nombre d' etapes de communication globales sont suffisantes. Dans cette expose nous allons d'abord motiver et decrire les modeles BSP et CGM. Ensuite, nous montrerons les principales techniques algorithmiques au travers le calcul de l'enveloppe convexe d'un nuage planaire de points, de la conception de l'algorithme jusqu'a son implantation sur CRAY T3D. Cet exemple nous permettra de montrer que ces modeles sont bien adaptes au portage sur ordinateurs paralleles, puisque les predictions sur le comportement des algorithmes - extensibilite, portabilite, performance -, sont corroborees par les resultats pratiques. Enfin, nous ferons un rapide tour d'horizon des resultats connus et des perspectives de recherche sur ces modeles aussi attrayants pour des developpements pratiques que theoriques.
33. Jeudi 09 octobre 1997

    Gamma-coupes sur les grilles rectangulaires multidimensionnelles

    Jérôme Galtier

    Le probleme de separation et de partitionnement de graphe est etudie ici sur une classe de graphes, les grilles rectangulaires multidimensionnelles. Cette classe de graphes est un exemple fondamental de graphes de l'analyse numerique, et possede en outre de nombreuses autres applications. Par des arguments combinatoires et analytiques, les valeurs des bornes precedemment connues sont ameliorees, plus particulierement dans le cas ou une grille de n noeuds doit etre partitionnee en deux ensembles A et B ayant respectivement k et p noeuds (k+p=n), et que k differe de p. A partir de cela, des bornes ameliorees sur le partitionnement en plus de deux ensembles peuvent etre deduites. Non seulement cela, mais la forme precise des coupes optimales des grilles est decrite, ce qui permet une meilleure comprehension de ce qu'est une coupe optimale pour les graphes irreguliers de l'analyse numerique.
32. Jeudi 02 octobre 1997

    Heuristiques pour les problèmes de communications personnalisées dans les réseaux point-à-point

    Sandrine Vial

    A communication pattern in an n-node point-to-point network is given by an n x n integer matrix whose entry (i,j) represents the amount of data that must be transfered from processor i to processor j. Routing optimally an arbitrary communication pattern yields NP-complete problems, even for particular cases of matrices, or particular cases of networks. I will present heuristics that approximate the optimal solution of this problem. The good behaviors of our heuristics are illustrated by an analytic study of specific cases, and by running a large number of experiments on the usual interconnection topologies for massively parallel computers.
31. Jeudi 25 septembre 1997

    Quantum Computing

    Jozef Gruska Mazaryk University, Brno

    Research in quantum computing seems to be of large importance both for computing and quantum mechanics and makes a merge in these two perhaps the most influential areas of science and technology of 20th century. This research seems to start quite new area in computing and it brings new problems, paradigms, views, concepts, methods and results in the search for understanding the most basic and puzzling phenomena of natural world. In a very simplified way a quantum computer can be seen as one having memory exponentially larger than its apparent physical size, that can manipulate exponential set of inputs and that computes in twilight zone of Hilbert space. In the talk basic ideas, interesting results, new methods and hard problems of quantum information processing are introduced, explained and discussed.
30. Jeudi 26 juin 1997

    On connectivity, superconnectivity and conditional diameter of graphs and digraphs

    Josep Fabrega Canudas Univ. Politecnica de Catalunya
29. Jeudi 24 avril 1997

    Decompositions of Cayley graphs

    Brian Alspach Simon Fraser University, Canada

    I shall present a survey about decompositions of Cayley graphs. In particular, I will discuss 1-factorizations, Hamilton decompositions, and self-comp[lementary graphs.
28. Jeudi 27 mars 1997

    Objets combinatoires comptés par les fonctions de Bessel

    Jean-Marc Fédou

    Nous decrivons differents objets combinatoires enumeres par les q-analogues de fonctions de Bessel: diagrammes de Ferrer gauches selon la largeur et l'aire, tresses simples selon le nombre de brins et de croisements, paires de permutations selon le nombre de descentes communes et d'inversions. Ces enumerations nous permettent d'introduire differentes techniques de comptage et de q-comptage: series generatrices, theorie des empilements (monoides partiellemment commutatifs, adjacence dans les mots). La premiere partie aborde les diagrammes de Ferrer gauches tandis que les tresses simples et les paires de permutations seront l'objet des deuxieme et troisieme parties.
27. Mercredi 05 mars 1997

    Permutations on Circuit-Switched Toroidal Meshes

    Joseph G. Peters Simon Fraser University, Canada et CNRS-IMAG

    The data movement patterns that occur in algorithms for distributed memory multiple processor systems can often be decomposed into structured phases, each phase involving one-to-one, one-to-all, or all-to-all data movement patterns. This seminar will consider permutations (one-to-one patterns) that commonly occur in numerical and image processing applications involving matrices: reflections, rotations, translations, and transpositions. The seminar will focus on a few of the more interesting algorithms for toroidal meshes that use synchronous circuit-switched routing with virtual channels. This research is joint work with Curtis Spencer (Newbridge Networks, Ottawa, Canada).
26. Jeudi 06 février 1997

    Analyse de granularité des graphes de tâches réguliers

    Jean-Paul Stromboni

    Le graphe des taches etendu est un formalisme interessant et repandu pour decrire les dependances des programmes. Arrange en niveaux de precedence, il revele le parallelisme potentiel d'une application et permet a un compilateur de decider de l'implantation sur une architecture parallele. La complexite du probleme d'implantation croit exponentiellement avec la taille du graphe (entre autres selon le grain de programmation), alors que meme massives, certaines applications (e.g. en Traitement du Signal) qu'on appellera regulieres sont programmees simplement a l'aide de sequences de boucles imbriquees. Pour partitionner efficacement le graphe des taches d'une application reguliere, le principe retenu ici consiste a detecter des la lecture du programme les repetitivites de la structure des dependances a partir des parametres des nids de boucles dans le domaine d'iteration. L'exploitation de ce resultat consistera a agglomerer ou a superposer les periodes detectees, en multipliant en consequence les granularites des taches et des echanges pour conserver la charge totale de calcul. Pratiquement, les premieres conclusions sont reportes dans un heuristique qui scrute les instructions du programme etudie afin de determiner l'ensemble des agglomerations de taches possibles dans un graphe engendre par une application restreintea une suite de nids de boucles operant sur des tableaux linearises.
25. Vendredi 22 novembre 1996

    Distributed computing on the global network computer

    Gul A. Agha University of Illinois at Urbana-Champaign

    Concurrent computing technologies are advancing rapidly. At one end of the spectrum, hardware technology is making multiprocessor workstations feasible. At the other, emerging information highways allow one to view the nodes connected to the internet as a global distributed computer. To effectively use the emerging technological infrastructure, parallelism and distribution must be understood in fundamental ways. In particular, the interrelated issues of naming, resource management, coordination, mobility, and availability are critical. I will discuss the current trends in programming paradigms, such as web browsers, agents, and reflective architectures. I will also discuss the state of the art in programming languages -- such as Java and Rosette -- which are in use in the real world. Finally, I will provide my assessment of the technological requirements for software to enable effective use of the emerging global network computer.
24. Vendredi 08 novembre 1996

    Head of corporate initiative in evolvable interoperable information systems

    Bhavani Thuraisingham MITRE Corp., Bedford, Massachusetts

    Object Technology for Designing and Implementing an Infrastructure and Data Manager for Command and Control Applications Between now and the early part of the next century, significant portions of today's real-time C3 systems will become either functionally inadequate or logistically unsupportable. MITRE's Evolvable Real-Time C3 project has developed an approach that would enable current real-time systems to evolve into the systems of the future. The candidate evolution approach is to leverage off near-term system upgrade and/or Pre Processing Product Improvement (P3I) activity to put a new architecture framework in place. The emphasis is on transitioning to open architectures which are modular and free from proprietary or unnecessarily complex software designs. The open framework can also accommodate new upgrades more easily. Availability of a suitable software architecture is key for this approach to succeed. The investment plan would continue incremental transition of current systems into more flexible systems. The extensible system architecture would ultimately replace the current hardware and software architecture. This presentation describes our approach to evolving legacy real-time command and control systems into systems of the future by taking advantage of the commercial off the shelf products as well as the state-of-the-art developments in real-time systems and distributed systems technologies. We have used AWACS (Air Borne Warning and Control System) as an example to test out the concepts and architectures developed. We have also utilized object technology in the design and implementation of the system. Evolvable Interoperable Information Systems Initiative at MITRE The old systems are too important to throw away and too costly to change, as well as being too expensive to maintain. As an attack on this collection of issues, we have identified five key technical areas for evolvable interoperable information systems. The five technical areas that form the evolvable interoperable information systems thrust (EIIS) are the following. System Architectures and Object Technology Data Management Software Reverse Engineering Real-time Systems Economics of Evolving Information Systems The presentation will describe the EIIS Initiative and describe the research directions we are taking in the five technology areas.
23. Lundi 28 octobre 1996

    Communication complexity of gossiping by packets

    Luisa Gargano, A. Rescigno, U. Vaccaro Università di Salerno

    This paper considers the problem of gossiping with packets of limited size in a network with cost function. We show that the problem of determining the minimum cost necessary to perform gossiping among a given set of participants with packets of limited size is NP-hard. We also give an approximate (with respect to the cost) gossiping algorithm. The ratio between the cost of an optimal algorithm and the approximate one is less than 1+2(k-1)/n, where n is the number of nodes participating to the gossiping process and k less or equal to n-1 is the upper bound on the number of individual blocks of information that a packet can carry. We also analyze the communication time and communication complexity, i.e., the product of the communication cost and time, of gossiping algorithms.
22. Jeudi 24 octobre 1996

    Combinatoire géométrique des descentes dans les groupes symétriques

    Frédéric Patras Lab. J.A.Dieudonné, Nice

    On montre comment decrire geometriquement les proprietes de l'algebre des descentes des groupes symetriques, en indiquant les differentes applications de ce type de calculs: algebres tensorielles/combinatoire des mots; algebres de Hopf; geometrie des simplexes et polytopes; formules de denombrement a la Ehrhart, etc.
21. Jeudi 24 octobre 1996

    Ordre de Bruhat faible et permutoèdres

    Clemens Berger Lab. J.A.Dieudonné, Nice

    L'ordre de Bruhat faible du groupe symetrique S_n permet de comprendre combinatoirement le polytope defini par l'enveloppe convexe d'une S_n-orbite generique dans R^n. Ce polytope convexe, appele permutoedre, intervient dans plusieurs theories mathematiques, actuellement a la mode; il permet notamment une nouvelle approche aux categories monoidales tressees expliquant leur lien avec les espaces de lacets doubles et les 3-categories faibles.
20. Mardi 01 octobre 1996

    Présentation de JAVA

    Franck Vamparys EPFL, Suisse

    La presentation se fera en deux parties: une partie sur le langage JAVA (une bonne heure): - historique - positionnement du langage (C++, smalltalk, ...) - influence sur la conception des programmes (type vs. class) - presentation du langage - la machine virtuelle - les classes de base - JAVA et WWW (applets, HotJava) une partie sur l'environnement JAVA (une heure): - architecture Java (JAVA Beans) - Java API (Enterprise, Server, Security, Commerce, Media, ...) - JDK 1.1 (Q4 1996) - outils de developpement (Java WorkShop 1.0, ...)
19. Vendredi 27 septembre 1996

    List homomorphisms and the lexicographic method

    Pavol Hell SFU, Vancouver

    List homomorphisms are related to homomorphisms in the same way list colourings are related to colourings. Just as with list colourings, we are finding that many questions about homomorphisms have nicer answers in the context of list homomorphisms. I will present some new results (joint with T. Feder and J. Huang) on list homomorphisms to mixed graphs (where each vertex may or may not have a loop). I will also explain how a new technique (the `lexicographic method') allows us to find new characterizations of certain circular arc graphs related to list homomorphisms. (Despite the English abstract and the English transparencies, I will give the talk in (a kind of) French.)
18. Jeudi 12 septembre 1996

    Indice de transmission des graphes et distorsion des codes couvrants

    Patrick Solé

    L'indice de transmission des graphes est un parametre qui mesure la congestion lorsque le graphe est utilise en reseau d'interconnexion. Il a ete relie aux parametres d'expansion du graphe par divers auteurs. En particulier lorsque le graphe en question est le graphe aux classes d'un code lineaire en utilisant les prorietes de symmetrie du code et en s'appuyant sur des resultats recents de Shahrokhi et Szekely sur les multiflots, on donne des bornes sur le diametre moyen du graphe en fonction de la distance minimale et de la dimension.
17. Jeudi 23 mai 1996

    Evaluation du signe d'un déterminant en arithmétique simple précision

    Mariette Yvinec

    Evaluation du signe d'un deteterminant en arithmetique simple precision. Mariette Yvinec. Les algorithmes geometriques sont par nature tres sensibles aux erreurs d'arrondi. L'evaluation du signe d'un determinant etant le test numerique de base de la plupart des algorithmes geometriques, l'evaluation exacte d'un tel signe est tres souvent le moyen le plus sur d'obtenir un algorithme robuste. L'expose presente deux methodes pour evaluer exactement le signe d'un determinant dont les entrees sont des entiers codees sur b bits. Dans les deux cas, l'algorithme se contente d'une arithmetique simple precision et evite de calculer completement le determinant sauf lorsque celui-ci est nul.
16. Jeudi 09 mai 1996

    Un PGRS pour calculer la majorité dans un graphe bicolore

    Chiara Biancheri

    Dans l'etude de la resolution des problemes utilisant le modele base sur la technique de reetiquetage de graphe avec priorites, nous nous sommes interesses au probleme de la majorite. Soit G un graphe dont les sommets ont les etiquettes A ou B, nous dirons que l'etiquette A a la majorite si le nombre de sommets marques A est strictement superieur au nombre de sommets marques B. Avec ce systeme, et ce quelque soit le graphe irreductible, tous les sommets connaissent le resultat du calcul : si un sommet etiquete A- ou a- (respectivement B- ou b-) alors A (respectivement B) est majoritaire alors que si un sommet est marque N- ou n- il n'y a pas de majorite.
15. du Lundi 29 avril au Mardi 30 avril 1996

    Journées PACOM

     
14. Jeudi 11 avril 1996

    Tas de sable en espace linéaire

    Jérôme Durand-Lose LaBRI, Bordeaux

    Le phenomene etudie est une chute grain a grain dans un systeme qui se stabilise. Des signaux sont mis en evidence. Leur etude facilite la descrption du systeme et donne sa forme asymptotique.
13. Mardi 02 avril 1996

    Opération zigzag et enveloppes z-libres

    Bruno Patrou LaBRI, Bordeaux

    L'operation zigzag est une operation sur les langages qui etend l'operation etoile de Kleene. A partir d'un ensembble de mots donne, elle permet de generer de nouveaux elements a l'aide d'une succession de pas avants et de pas arrieres. Autour de l'operation etoile ont ete definies dans les annees cinquantes les notions de code, liberte, stabilite, enveloppe libre. Nous proposons de retrouver ces notions dans le cadre de l'operation zigzag en insistant sur les aspects qui entrainent des demonstrations ou des resultats differents d'une operation a l'autre.
12. Jeudi 14 mars 1996

    Présentation du serveur Web

    Olivier Dalle

    Plan de l'expose: - presentation generale du Web - presentation des outils de consultation (Netscape) - introduction a la conception de pages Web : a. fonctionnement d'un serveur Web en general et de celui d'I3S en particulier b. survol du langage HTML - Reponse aux questions diverses
11. Mardi 27 février 1996

    Redistribution de données réparties cycliquement par blocs

    Bernard Tourancheau LIP, Ens Lyon

    L'implantation de programmes scientifiques sur les machines paralleles a memoire distribuee pose le probleme du choix de la distribution des donnees pour les matrices et les vecteurs sur les differents processeurs. Une distribution bloc-cyclique semble convenir pour la plupart des algorithmes (HPF, ScaLAPACK), mais un compromis est necessaire dans le choix de la taille des blocs (pour avoir a la fois des calculs et communications efficaces et une bonne repartition de charge). Le choix optimal est different pour chaque algorithme, et il est donc essentiel de pouvoir passer d'une distribution a l'autre tres rapidement. Nous presentons ici les algorithmes de redistribution que nous avons implantes dans la bibliotheque SCALAPACK. Une etude de complexite vient ensuite prouver l'efficacite des solutions choisies. Les performances obtenues sur Intel Paragon et Cray T3D corroborent nos resultats. Nous montrons le gain obtenu en utilisant une bonne distribution des donnees avec 3 noyaux de calcul numerique et nos fonctions de redistribution.
10. Jeudi 22 février 1996

    Pavages et Bin-Packing dans le plan

    Claire Kenyon LIP, Ens Lyon

    Le pavage d'une region rectilineaire du plan par des figures de formes donnees est un probleme NP-hard en general. Nous etudions deux problemes de ce type. D'une part, on peut mettre des restrictions sur les paves: dans le cas particulier ou les paves sont des rectangles tous identiques mais ou les rotations sont autorisees, une technique utilisant theorie des groupes et graphes de Cayley, generalisant des idees de Conway, Lagarias et Thurston, permet d'obtenir un algorithme polynomial. D'autre part, on peut mettre des restrictions sur la region a paver. Dans le cas ou cette region est une bande semi-infinie, et ou il y a n paves carres dont chacun doit etre utilise une et une seule fois, le but est de paver une portion de la bande de facon aussi compacte que possible: il s'agit la du "strip-packing", probleme d'optimisation classique. Nous presentons un algorithme polynomial base sur la programmation lineaire et donnant un pavage a (1+epsilon ) du pavage optimal. Le premier resultat est le fruit d'une collaboration avec Richard Kenyon, et le deuxieme d'une collaboration avec Eric Remila.
9. Vendredi 26 janvier 1996

   Codes cycliques auto-duaux sur Z4

   Patrick Solé
8. Vendredi 15 décembre 1995

   Résultats fondamentaux sur les graphes de de Bruijn

   J. de Casanis, Michel Syska

   Alors qu'un reseau en de bruijn decode des codes de viterbi sur la fusee de la mission galileo de la Nasa et va fondre a l'approche de jupiter, nous sommes heureux de celebrer les 50 ans de l'un de ses plus fervents serviteur. Les publications simultanees de Good et de Bruijn sont de 1946, mais il est vrai que en 1945 il y avait autre chose a faire, et c'est donc probablement en 1945, alors que JCB venait au monde que le graphe fut decouvert ...
7. Jeudi 07 décembre 1995

   Sur les omega-générateurs et les codes

   Sandrine Julia

   Un code C est un langage de mots finis tel que tout mot fini compose avec les mots du code ait une seule decomposition sur C. Par analogie, un omega-code W est un langage de mots finis tel que tout mot infini ecrit avec les mots de W ait une unique decomposition sur W. Les omega-codes forment une classe de codes, parmi de nombreuses autres. On considere un langage de mots infinis construits en mettant bout a bout des mots finis d'un code. Alors, on cherche a savoir si on peut l'obtenir ou pas a l'aide des mots d'un code issu d'une classe donnee.
6. Jeudi 30 novembre 1995

   Efficient Collective Communication in Optical Networks

   Jean-Claude Bermond, L. Gargano, S.Perennes, A.A. Rescigno, U. Vaccaro

   This paper studies the problems of broadcasting and gossiping in optical networks. In such networks the vast bandwidth available is utilized through wavelength division multiplexing: a single physical optical link can carry several logical signals, provided that they are transmitted on different wavelengths. In this paper we consider both single-hop and multihop optical networks. In single-hop networks the information, once transmitted as light, reaches its destination without being converted to electronic form in between, thus reaching high speed communication. In multi hop networks a packet may have to be routed through a few intermediate nodes before reaching its final destination. In both models, we give efficient broadcasting and gossiping algorithms, in terms of time and number of wavelengths. We consider both networks with arbitrary topologies and particular networks of practical interest. Several of our algorithms exhibit optimal performances.
5. Jeudi 16 novembre 1995

   Un algorithme de numérotation du dictionnaire pour la quantification vectorielle par les réseaux

   Pierre Loyer

   La quantification vectorielle consiste a remplacer des points de l'espace (par exemple des blocs de pixels) par des representants choisis dans un ensemble fini appele dictionnaire. En fait, on ne transmet pas les vecteurs du dictionnaire tels quels mais leur numero, d'ou la necessite de les numeroter. Le dictionnaire considere est ici un reseau arithmetique tronque. On tire avantage de cette structure pour mettre au point un algorithme realisant un bon compromis cout de stockage/complexite.
4. Jeudi 09 novembre 1995

   Diagrammes de Voronoi en normes polyédriques convexes

   Mariette Yvinec

   Lorsque la distance entre deux points est la distance Euclidienne, le diagramme de Voronoi de n sites ponctuels dans un espace de dimension d est la projection d'un polytope de dimension d+1 et la complexite de ce diagramme est bien connue. Il n'en est plus de meme lorsque la distance entre deux points est la distance L1, Linfini ou tout autre distance definie a partir d'un polytope. Apres un bref rappel sur la notion de diagramme de Voronoi, l'expose presentera quelques resultats recemment obtenus dans ce domaine.
3. Jeudi 02 novembre 1995

   Générateurs pseudo-aléatoires cryptographiquement sûrs

   Bruno Martin

   Nous definissons la classe de complexite du temps polynomial probabiliste a erreur bornee sur les machines de Turing appelee BPP. Nous utilisons ensuite cette classe pour definir la notion de difficulte d'inversion d'une fonction a sens unique sous l'hypothese que BPP \neq NP et nous donnerons une idee de la preuve du resultat de Goldreich qui lie l'existence de generateurs pseudo-aleatoires a celle de fonctions a sens unique.
2. Dimanche 19 novembre 1995

   Schémas d'association de codes quaternaires

   Alexis Bonnecaze

   Nous donnons une methode pour calculer les enumerateurs de poids complet des codes lineaires sur Z_4. Cette methode permet aussi de construire des codes sur Z_4 interessants. Nous etudions en particulier le code de Preparata dont les translates definissent un DRG (graphe distance-regulier).
1. Vendredi 06 octobre 1995

   Décomposition en cycles Hamiltoniens du graphe "Butterfly"

   Olivier Delmas, Jean-Claude Bermond, Eric Darrot et Stéphane Pérennes

   Nous prouvons que le graphe "Wrapped Butterfly" note WBF(d,n) de degre d et de dimension n, est decomposable en cycles Hamiltoniens. Ceci repond a une conjecture de D. Barth et A. raspaud qui ont resolu le cas d=2.