Posts classified under: Séminaire Algo

The sum of digits function in base 2, also called the Hamming weight, is the number of non-zero binary digits of an integer. This function is a central object for all my present research and appears in many scientific fields, such as number theory, combinatorics on words, and coding theory. In this talk, I will … Continue reading Séminaire Algo : Pierre Popoli (LORIA, Univ. de Lorraine) « Sum of digits, pseudorandomness and measures of complexity »

Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. They are an omnipresent data structure in computer science and the problem of counting the DAGs of given number of vertices has been solved in the 70’s by Robinson. In this talk, I will introduce a new … Continue reading Séminaire Algorithmique : Martin Pépin (LIPN, Univ. Paris Nord) « Directed Ordered Acyclic Graphs, asymptotic analysis and efficient random sampling »

Silvère Gangloff (Univ. AGH, Cracovie, Pologne) « Classes de transitivité pour les sous-décalages de type fini multi-dimensionnels » Ce travail est en commun avec B. Hellouin et P. Oprocha. Les sous-décalages de type fini multidimensionnels ont été étudiés dans les dernières décennies à travers le spectre de propriétés topologiques telles que la transitivité ou le … Continue reading Séminaire Algorithmique: ANNULÉ EN RAISON DU MOUVEMENT DE GRÈVE

Self-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 »

Any 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 »

Un 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)

Frank 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 »

En 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 »

Accurately 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)