Évènements

Les pavages de Penrose sont des pavages non-périodiques du plan par losanges. Dans cet exposé, je vais présenter la percolation dynamique sur ces pavages, c’est-à-dire un processus de contamination sur ces pavages depuis une configuration initiale aléatoire. Étant donné un pavage de Penrose, on met sur chaque tuile un état 0 ou 1. On fait … Continue reading Séminaire Algorithmique : « Percolation Bootstrap (ou d’amorçage) sur les pavages de Penrose », Victor Lutfalla (I2M, Univ. Marseille)

Reasoning about dynamical systems evolving over the reals is well-known to lead to undecidability. However, various results in the literature have shown that decision procedures exist when restricting to robust systems, with a suitably-chosen notion of robustness. In particular, in verification, it has been established that if the state reachability is not sensitive to infinitesimal … Continue reading Séminaire Algorithmique : « Measuring robustness of dynamical systems. Relating time and space to length and precision », Manon Blanc (LIX, Ecole Polytechnique)

Le problème du pattern matching (trouver une ou toutes les occurrences d'un motif dans un texte) est un problème classique en informatique. L'algorithmique du texte propose de nombreuses solutions efficaces lorsque le motif et le texte sont des chaînes de caractères. Procéder à la recherche de motifs dans les séries temporelles se révèle plus délicat, … Continue reading Séminaire Algorithmique : « Approximate Cartesian tree matching », Bastien Auvray (LITIS, Univ. Rouen)

Automata (DFA) are state machines that accept or reject words. The set of words recognized by an automaton is its its language. Regular languages coincide with languages that can be recognized by automata. Here, we’re going to focus on a measure, namely state complexity. For rational languages, this is defined as the size of the … Continue reading Séminaire Algorithmique : « State complexity: Inverting a language reduces the complexity of the root operation », Alexandre Durand (LITIS, Univ. Rouen)

We consider the problem of learning a logical formula from a set of positive and negative examples. The logic we target is Linear Temporal Logic (LTL), a prominent formalism in program verification and analysis, software engineering, and robot motion planning. We’ll discuss on the one hand theoretical results, in particular NP-completeness, and on the other … Continue reading Séminaire Algorithmique : « Learning Linear Temporal Logic », Nathanaël Fijalkow (CNRS, LaBRI, Univ. Bordeaux)

Consider a graph drawn on a surface (for example, the plane minus a finite set of obstacle points), possibly with crossings. We provide a polynomial time algorithm to decide whether such a drawing can be untangled, namely, if one can slide the vertices and edges of the graph on the surface (avoiding the obstacles) to … Continue reading Séminaire Algorithmique : « Untangling Graphs on Surfaces », Loïc Dubois (LIGM, Univ. G.Eiffel)

Je présente l’application pratique du codage et de l’algorithmisation corécursive (extrapolatrice, paresseuse, qui engendre des flots “infinis”) dans le domaine du calcul scientifique : la manipulation des suites illimitées de dérivées “automatiques” du code numérique. Je discute l’usage du langage fonctionnel Haskell dans le traitement des structures comme les séries formelles ou les approximants de Padé. La … Continue reading Séminaire Algorithmique : « Corecursivity and higher-order computational differentiation, and some applications », Jerzy Karczmarczuk (GREYC, Caen)

Le Générateur Sac à dos, proposé en 1985 par Rueppel et Massey est un générateur pseudo aléatoire (PRNG) qui combine un premier PRNG faible, le LFSR, et un problème dur ,le problème de la somme de sous-ensemble, dérivé du problème de sac à dos. Ce générateur a été attaqué avec succès par Knellwolf et Meyer … Continue reading Séminaire Algorithmique : « Discussion autour du Générateur Sac à dos », Florette Martinez (ENS Ulm)