Évènements

La compilation de connaissances est un domaine de l’informatique qui étudie les différentes classes de représentations pour les fonctions, et les algorithmes permettant de passer d’une classe à l’autre. Dans cette présentation, on s’intéresse à l’approche de compilation dite bottom-up (ascendante) pour les fonctions Booléennes données comme des formules CNF. Cette approche permet de construire … Continue reading Séminaire Algorithmique : « Bornes Inférieures et Séparations pour la Compilation de Connaissances Bottom-Up », Alexis de Colnet (CRIL, Univ. Lens)

Utilisés notamment en écologie marine, les réseaux trophiques sont une représentation sous forme de graphes dirigés et pondérés des interactions proies/prédateurs d’un écosystème. Les nœuds du graphe représentent alors les espèces et les arêtes leurs interactions sous forme d’échanges de matière organique appelés flux. Dans le but d’estimer la valeur de ces flux, une classe … Continue reading Séminaire Algorithmique : « Samplelim: un package R pour l’échantillonnage de solutions à un problème linéaire inverse »,Théo Grente (LMNO, Caen)

A graph G is Hamiltonian if it exists a cycle in G containing all vertices of G exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G − S is at most |S| / t. We extended a theorem of Hoàng by proving the … Continue reading Séminaire Algorithmique : « Tough graphs and Hamiltonian degree conditions », Cléophée Robin (GREYC, Caen)

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)