Séminaire Algo : Edwin Hamel (Univ. libre Bruxelles, Belgique) « Two-player boundedness counter games »
Sciences 3- S3 351We consider two-player zero-sum games with winning objectives beyond regular languages, expressed as a parity condition in conjunction with a Boolean combination of boundedness conditions on a finite set of counters which can be incremented, reset to 0, but not tested. A boundedness condition requires that a given counter is bounded along the play. Such … Continue reading Séminaire Algo : Edwin Hamel (Univ. libre Bruxelles, Belgique) « Two-player boundedness counter games »
Séminaire Algorithmique : Gabriel Le Bouder (LIP6, Sorbonne Univ.) « Memory-Optimization for Self-Stabilizing Distributed Algorithms »
Sciences 3- S3 351Self-stabilization is a suitable paradigm for distributed systems, particularly prone to transient faults. Errors such as memory or messages corruption, break of a communication link, can put the system in an inconsistent state. A protocol is self-stabilizing if, whatever the initial state of the system, it guarantees that it will return a normal behavior in … Continue reading Séminaire Algorithmique : Gabriel Le Bouder (LIP6, Sorbonne Univ.) « Memory-Optimization for Self-Stabilizing Distributed Algorithms »
Séminaire Algorithmique : Julien Clément (GREYC, Caen) « Combinatorics of reduced ordered binary decision diagrams. Application to random uniform sampling »
Sciences 3- S3 351Any Boolean function corresponds to a complete full binary decision tree. This tree can in turn be represented in a maximally compact form as a directed acyclic graph where common subtrees are factored and shared, keeping only one copy of each unique subtree. This yields the celebrated and widely used structure called reduced ordered binary … Continue reading Séminaire Algorithmique : Julien Clément (GREYC, Caen) « Combinatorics of reduced ordered binary decision diagrams. Application to random uniform sampling »
Séminaire Algorithmique : Victor Lutfalla (GREYC, Caen)
Salle à déterminerUn pavage est un recouvrement du plan par des tuiles qui ne se chevauchent pas. On appelle sous-shift un ensemble de pavages qui est invariant par translation et fermé (pour la topologie habituelle sur les pavages). Ici on s’intéresse au cas où il y a un nombre fini de tuiles à translation près, les tuiles … Continue reading Séminaire Algorithmique : Victor Lutfalla (GREYC, Caen)
Séminaire Algorithmique : Mostafa Gholami (GREYC, Caen) « Multicolor bipartite Ramsey numbers for paths, cycles, and stripes »
Sciences 3- S3 351Frank Ramsey introduced the theory that bears his name in 1930. The main subject of the theory are complete graphs whose subgraphs can have some regular properties. Most commonly, we look for monochromatic complete subgraphs, i.e., complete subgraphs in which all of the edges have the same color. Ramsey numbers have attracted the attention of … Continue reading Séminaire Algorithmique : Mostafa Gholami (GREYC, Caen) « Multicolor bipartite Ramsey numbers for paths, cycles, and stripes »
Séminaire Algorithmique : Pierre Béaur (LISN, Université Paris-Saclay) « Walking On a Line: détection de marches S-adiques dans les ω-automates »
Sciences 3- S3 351En dynamique symbolique s'intersectent études des langages, des mots infinis et des structures dynamiques associées. Deux méthodes classiques de construction de ces objets coexistent. D'abord, la méthode de Thue construit un mot infini à l'aide d'une substitution (un morphisme de mots) : on itère la substitution sur une lettre initiale, et on considère le mot … Continue reading Séminaire Algorithmique : Pierre Béaur (LISN, Université Paris-Saclay) « Walking On a Line: détection de marches S-adiques dans les ω-automates »
Séminaire Algorithmique : “Robustness of the RAM model” or “how to perform a division in constant time”, Etienne Granjean (GREYC, Caen)
Sciences 3- S3 351Accurately measuring the complexity of algorithms and establishing the intrinsic computational complexity of problems are among the most important tasks/goals in computer science. For this, everyone agrees that the right model of computation (for sequential algorithms) is the random access machine (RAM). Contrary to this general agreement, paradoxically, there is no consensus on how to … Continue reading Séminaire Algorithmique : “Robustness of the RAM model” or “how to perform a division in constant time”, Etienne Granjean (GREYC, Caen)
Séminaire Algorithmique : « Bornes Inférieures et Séparations pour la Compilation de Connaissances Bottom-Up », Alexis de Colnet (CRIL, Univ. Lens)
Sciences 3- S3 351La 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)
Séminaire Algorithmique : « Samplelim: un package R pour l’échantillonnage de solutions à un problème linéaire inverse »,Théo Grente (LMNO, Caen)
Sciences 3- S3 351Utilisé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)
Séminaire Algorithmique : « Tough graphs and Hamiltonian degree conditions », Cléophée Robin (GREYC, Caen)
Sciences 3- S3 351A 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)
Séminaire Algorithmique : « Percolation Bootstrap (ou d’amorçage) sur les pavages de Penrose », Victor Lutfalla (I2M, Univ. Marseille)
Sciences 3- S3 351Les 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)
Séminaire Algorithmique : « Measuring robustness of dynamical systems. Relating time and space to length and precision », Manon Blanc (LIX, Ecole Polytechnique)
Sciences 3- S3 351Reasoning 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)